第六场各种数论题，对此没什么想写的（知道结论就是20行的事，无多少意义）故从第七场开始写
1001Hyperspace
曼哈顿距离多次求解，用2^k来维护最大最小值既能得解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
const int maxn = 60005;
struct node
{
int d;
int id;
bool operator<(const pp a)const
{
return d<a.d;
}
};
bool vis[maxn];
int p[10];
int main()
{
int n,k;
while(~scanf("%d %d",&n,&k))
{
priority_queue<pp>pq[1<<k];
clr(vis,0);
int all=(1<<k)-1;
for(int i=1; i<=n; i++)
{
int op;
scanf("%d",&op);
if(op)
{
int del;
scanf("%d",&del);
vis[del]=1;
}
else
{
for(int j=0; j<k; j++)
scanf("%d",&p[j]);
for(int s=0; s<=all; s++)
{
pp t;
t.d=0;
t.id=i;
for(int j=0; j<k; j++)
if(s&(1<<j)) t.d+=p[j];
else t.d-=p[j];
pq[s].push(t);
}
}
int ans=0;
for(int s=0; s<=all; s++)
{
pp t1,t2;
int t=all-s;
while(!pq[s].empty())
{
t1=pq[s].top();
if(!vis[t1.id]) break;
pq[s].pop();
}
while(!pq[t].empty())
{
t2=pq[t].top();
if(!vis[t2.id]) break;
pq[t].pop();
}
if(!pq[s].empty()&&!pq[t].empty())
ans=max(ans,t1.d+t2.d);
}
printf("%d\n",ans);
}
}
}
1004Mutiples on a circle
比赛的时候因为感觉数据连在一起将远远超出long long而不敢下手，后来想了想开了取余表来记录，但是却因为位数问题伤透了心，结果写的好长好长，时间效率也不是太好。。
勉强算A了。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int MAXN = 50010;
int a[MAXN];
int end[MAXN];
int len[MAXN];
int b[2][220];
int getlen(int n)
{
int ret = 0;
while(n)
{
ret++;
n/=10;
}
return ret;
}
int Ten[10];
int main()
{
int n,k;
while(scanf("%d%d",&n,&k) == 2)
{
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
len[i] = getlen(a[i]);
}
Ten[0] = 1;
for(int i = 1;i < 5;i++)
Ten[i] = Ten[i-1]*10%k;
int now = 0;
memset(b,0,sizeof(b));
b[now][a[1]%k] = 1;
long long ans = 0;
ans += b[now][0];
for(int i = 2;i <= n;i++)
{
memset(b[now^1],0,sizeof(b[now^1]));
b[now^1][a[i]%k] = 1;
for(int j = 0;j < k;j++)
{
if(b[now][j] == 0)continue;
int ttt = j*Ten[len[i]]%k+a[i];
ttt%=k;
b[now^1][ttt] += b[now][j];
}
now^=1;
ans += b[now][0];
}
end[n] = a[n]%k;
int tmp = len[n];
int SSSS = Ten[len[n]];
for(int i = n-1;i>= 1;i--)
{
end[i] = a[i]*SSSS%k + end[i+1];
end[i]%=k;
tmp += len[i];
SSSS = SSSS*Ten[len[i]]%k;
}
tmp = len[1];
SSSS = Ten[len[1]];
int tt = a[1]%k;
for(int i = 1;i < n;i++)
{
b[now][end[i]]--;
for(int j = 0;j < k;j++)
{
int ppp = (j*SSSS%k+tt)%k;
if(ppp == 0)ans += b[now][j];
}
tt = tt*Ten[len[i+1]]+a[i+1];
tt%=k;
tmp+=len[i+1];
SSSS = SSSS*Ten[len[i+1]]%k;
}
printf("%I64d\n",ans);
}
return 0;
}
1006Backup Plan
暴搞的一道题，唯一的问题是当m > n时需要讨论第二数据的内容（因为按题意每个数据库只有前两个有用途）然后所有内容按逆序写就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define maxn 2005
#define INF 0xfffffff
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n>m)
{
for(int i=1; i<=m; i++)
{
cout<<i<<' '<<n;
if(i==1)
{
for(int j=i+1; j<n; j++)
cout<<' '<<j;
}
else
{
for(int j=i+1; j<n; j++)
{
cout<<' '<<j;
}
for(int j=1; j<i; j++)
{
cout<<' '<<j;
}
}
cout<<endl;
}
}
else if(n==m)
{
for(int i=1; i<=m; i++)
{
cout<<i;
if(i==1)
{
for(int j=i+1; j<=n; j++)
{
cout<<' '<<j;
}
}
else
{
for(int j=i+1; j<=n; j++)
{
cout<<' '<<j;
}
for(int j=1; j<i; j++)
{
cout<<' '<<j;
}
}
cout<<endl;
}
}
else
{
int num=1,tmp=n,flag=0;
for(int i=1; i<=m; i++)
{
int s=i%n?i%n:n;
cout<<s;
if(num<=n-1)
{
cout<<' '<<tmp;
flag=tmp;
num++;
if(num==n)
{
num=1;
tmp--;
if(tmp==0)
{
flag=1;
tmp=n;
}
}
}
for(int j=1; j<=n; j++)
{
if(j!=s&&j!=flag)
cout<<' '<<j;
}
cout<<endl;
}
}
}
return 0;
}
除去这三道，1003和1005也是能做的，可惜思路不够宽扩，硬生生的悲剧了。。