http://codeforces.com/gym/101078
和ysy、方老师一起打的virtual
打的不是很好...下面按过题顺序放一下过的题的题（dai）解（ma）。
A
给两个1~n的排列，把它们割成尽量短的一些段，使得每一段sort之后一样。
随便写个hash了事（1min交是因为之前顺手写了这题）
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#ifdef LOCAL
#define TIMER cerr<<clock()<<"ms\n"
#else
#define TIMER
#endif
#define SZ 666666
int n,a[SZ],b[SZ];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=n;i++) scanf("%d",b+i);
int ca1=0,ca2=0,ca3=1,cb1=0,cb2=0,cb3=1;
int lst=0;
for(int i=1;i<=n;i++)
{
ca1+=a[i]; cb1+=b[i];
ca2^=a[i]; cb2^=b[i];
ca3*=a[i]+(233^n)+666; cb3*=b[i]+(233^n)+666;
if(ca1!=cb1||ca2!=cb2||ca3!=cb3);else
{
printf("%d-%d ",lst+1,i); lst=i;
ca1=0,ca2=0,ca3=1,cb1=0,cb2=0,cb3=1;
}
}
puts("");
}
}
D
有一排洞，从1开始左到右编号，对于每个m，如果m是偶数，那么m和m/2有一条绳子相连，如果m是奇数，m与3m+1有一条绳子相连。
现在在n和n+1这两个洞中间劈一刀，问会砍断多少条绳子。
推推公式...ysy写的
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int t,n;
inline int s(int l,int r)
{
if(!(l&1))
l++;
if(!(r&1))
r--;
return (r-l)/2+1;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",n-n/2+s((n-1)/3+1,n));
}
return 0;
}
L
有一个01串，现在要通过交换变成前面全是0，后面全是1。
交换i、j，i<=j需要sqrt(j-i)的代价，求最小代价。
注意到（目测出）sqrt(a+b+c)+sqrt(b)<sqrt(a+b)+sqrt(b+c)（因为sqrt增长越来越慢），那么我们只要倒着暴力枚举，能换就换。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#ifdef LOCAL
#define TIMER cerr<<clock()<<"ms\n"
#else
#define TIMER
#endif
#define SZ 666666
char s[SZ];
char ep[SZ];
int n;
int main()
{
scanf("%s",s);
n=strlen(s);
int zero=0;
for(int i=0;i<n;i++) zero+=s[i]=='0';
for(int i=0;i<n;i++) ep[i]=(i>=zero)+48;
double ans=0;
for(int i=0;i<n;i++)
{
if(s[i]==ep[i]) continue;
for(int j=n-1;j>=i+1;j--)
{
if(s[j]!=ep[i]) continue;
swap(s[i],s[j]);
ans+=sqrt(j-i);
break;
}
}
printf("%.11lf\n",ans);
}
C
有一个3*3*n的立方体，每一块可以和相邻块匹配，求全部匹配上的方案数。
十分难写的状压dp，ysy码的
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int t,n,f[5010][600],g[600][600],a[600][600],x[10][10],q=10007;
inline int dfs(int i,int j)
{
if(i>3)
return 1;
if(j>3)
return dfs(i+1,1);
if(!x[i][j])
return dfs(i,j+1);
int p=0;
if(x[i][j+1])
{
x[i][j]=0;
x[i][j+1]=0;
p+=dfs(i,j+1);
x[i][j]=1;
x[i][j+1]=1;
}
if(x[i+1][j])
{
x[i][j]=0;
x[i+1][j]=0;
p+=dfs(i,j+1);
x[i][j]=1;
x[i+1][j]=1;
}
return p;
}
inline void js(int n,int m)
{
int i,j;
for(i=0;i<9;i++)
if((n&(1<<i)) && (m&(1<<i)))
return;
else if((n&(1<<i)) || (m&(1<<i)))
x[i/3+1][i%3+1]=0;
else
x[i/3+1][i%3+1]=1;
g[n][m]=dfs(1,1);
a[n][++a[n][0]]=m;
}
int main()
{
int i,j,k;
n=5000;
for(i=0;i<512;i++)
for(j=0;j<512;j++)
js(i,j);
f[0][0]=1;
for(i=1;i<=n;i++)
for(j=0;j<512;j++)
for(k=1;k<=a[j][0];k++)
f[i][a[j][k]]=(f[i][a[j][k]]+f[i-1][j]*g[j][a[j][k]])%q;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",f[n][0]);
}
return 0;
}
F
交互库走迷宫，最后输出最短路径。
一波dfs即可，注意细节。
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#ifdef LOCAL
#define TIMER cerr<<clock()<<"ms\n"
#else
#define TIMER
#endif
#define SZ 666666
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int npp[233];
bool mp[233][233][5];
int ex=-1,ey=-1;
bool vis[233][233];
char tmp[2333],fm[]={"NSEW"};
#define P 101
bool& Vis(int a,int b)
{
return vis[a+P][b+P];
}
bool* Mp(int a,int b)
{
return mp[a+P][b+P];
}
#define FFF fflush(NULL);
void dfs(int x,int y)
{
Vis(x,y)=1;
scanf("%s",tmp);
for(int i=0;tmp[i];i++)
{
if(tmp[i]=='*')
{
ex=x; ey=y;
}
else Mp(x,y)[npp[tmp[i]]]=1;
}
for(int i=0;i<4;i++)
{
if(!Mp(x,y)[i]) continue;
if(Vis(x+dx[i],y+dy[i])) continue;
printf("%c\n",fm[i]); FFF
dfs(x+dx[i],y+dy[i]);
printf("%c\n",fm[i^1]); FFF
scanf("%s",tmp);
}
}
pii ps[SZ];
int dis[233][233];
int& Dis(int a,int b)
{
return dis[a+P][b+P];
}
void bfs()
{
memset(dis,127/3,sizeof(dis));
int inf=dis[0][0];
int h=0,t=0;
Dis(0,0)=0; ps[t++]=pii(0,0);
while(h^t)
{
pii x=ps[h++];
for(int k=0;k<4;k++)
{
if(!Mp(x.fi,x.se)[k]) continue;
if(Dis(x.fi+dx[k],x.se+dy[k])!=inf) continue;
Dis(x.fi+dx[k],x.se+dy[k])=Dis(x.fi,x.se)+1;
ps[t++]=pii(x.fi+dx[k],x.se+dy[k]);
}
}
}
int T;
int main()
{
npp['N']=0; npp['S']=1; npp['E']=2; npp['W']=3;
scanf("%d",&T);
while(T--)
{
ex=-2333, ey=-2333;
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
dfs(0,0);
if(ex==-2333)
{
puts("-1"); FFF
continue;
}
memset(vis,0,sizeof(vis));
bfs();
printf("%d\n",Dis(ex,ey)); FFF
}
}
I
叫你写一个编辑器，可以指针左移，指针右移，打一个字母。
写个链表，方老师写的。
# include <stdio.h>
# include <string.h>
using namespace std; int test;
char str[1300000]; int pre[1300000], nxt[1300000], s[1300000], cur=0, siz=0, sz=0; int main() {
scanf("%d", &test);
while(test--) {
for (int i=0; i<=1000000; ++i) pre[i]=nxt[i]=s[i]=0;
cur=0,siz=0,sz=0;
scanf("%s", str);
sz=strlen(str);
for (int i=0; i<sz; ++i) {
if(str[i] == '<') {
if(cur != 0) cur = pre[cur];
}
else if(str[i] == '>') {
if(nxt[cur] != 0) cur = nxt[cur];
} else if(str[i] == '-') {
if(cur) {
nxt[pre[cur]] = nxt[cur];
pre[nxt[cur]] = pre[cur];
cur = pre[cur];
}
} else {
++siz;
nxt[siz] = nxt[cur];
pre[siz] = cur;
nxt[cur] = siz;
int NEXT = nxt[siz];
pre[NEXT] = siz;
s[siz] = str[i];
cur=siz;
}
}
int pos = nxt[0];
while(pos != 0) {
printf("%c", (char)s[pos]);
pos=nxt[pos];
}
puts("");
}
}
E
w*h的矩形内有c个圆，给定圆心半径，圆两两不相交（可能相离、相切），求矩形内一个最大的圆使得与任何给定圆不交，输出半径，相对/绝对误差1e-6。
瞎退火，似乎调参挺蛋疼的，ysy写的。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<time.h>
using namespace std;
int t,a,b,n,x[51],y[51],r[51];
double sx,sy,sr,tx[1000],ty[1000],tr[1000],p;
int main()
{
srand(time(NULL));
int i,j,l;
double k,q;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&a,&b,&n);
for(i=1;i<=n;i++)
scanf("%d%d%d",&x[i],&y[i],&r[i]);
p=0;
for(i=1;i<=10;i++)
{
sx=double(((rand()<<15)+rand())%(10*a+1))/10;
sy=double(((rand()<<15)+rand())%(10*b+1))/10;
sr=min(min(sx,a-sx),min(sy,b-sy));
for(j=1;j<=n;j++)
sr=min(sr,sqrt((sx-x[j])*(sx-x[j])+(sy-y[j])*(sy-y[j]))-r[j]);
for(k=1e6;k>1e-9;k*=0.9)
{
for(l=1;l<=10;l++)
{
q=double(((rand()<<15)+rand())%6283)/1000;
tx[l]=sx+k*sin(q);
ty[l]=sy+k*cos(q);
tx[l]=min(max(tx[l],0.0),double(a));
ty[l]=min(max(ty[l],0.0),double(b));
tr[l]=min(min(tx[l],a-tx[l]),min(ty[l],b-ty[l]));
for(j=1;j<=n;j++)
tr[l]=min(tr[l],sqrt((tx[l]-x[j])*(tx[l]-x[j])+(ty[l]-y[j])*(ty[l]-y[j]))-r[j]);
}
for(l=1;l<=10;l++)
if(tr[l]>sr)
{
sx=tx[l];
sy=ty[l];
sr=tr[l];
}
}
p=max(p,sr);
}
printf("%.9lf\n",p);
}
return 0;
}
J
给出一个填字游戏，有横着的和竖着的，横着的互相不交，竖着的互相不交，现在填上去发现横竖有一些交叉的地方不一样，不能共存。于是让你求出最多的可以共存的。
把不能共存的连边，就是要求二分图最大独立集。n-最大匹配即可。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <limits>
#include <set>
#include <map>
using namespace std;
namespace gg
{
#define SZ 666666
int n,M=1;typedef long long ll;
int fst[SZ],nxt[SZ],vb[SZ],cap[SZ];
void _ad_dl(int a,int b,int c) {++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;cap[M]=c;}
void ad_dl(int a,int b,int c) {_ad_dl(a,b,c); _ad_dl(b,a,0);}
int S,T,q[SZ],d[SZ];
bool bfs()
{
for(int i=1;i<=n+1;i++) d[i]=-1;
d[S]=0; q[1]=S; int h=1,t=2;
while(h!=t)
{
int cur=q[h++];
for(int e=fst[cur];e;e=nxt[e])
{
int b=vb[e];
if(d[b]==-1&&cap[e]) d[b]=d[cur]+1, q[t++]=b;
}
}
return d[T]!=-1;
}
int dfs(int x,int f)
{
if(f<=0) return 0;
if(x==T) return f;
int ca=0;
for(int e=fst[x];e;e=nxt[e])
{
int b=vb[e];
if(d[b]!=d[x]+1) continue;
int w=dfs(b,min(cap[e],f-ca));
cap[e]-=w; cap[e^1]+=w; ca+=w;
if(ca==f) break;
}
if(!ca) d[x]=-1;
return ca;
}
#define inf 1000000000
int dinic()
{
int ans=0;
while(bfs()) ans+=dfs(S,inf);
return ans;
}
int Tat,h,v,x1[SZ],y1[SZ],x2[SZ],y2[SZ];
int s1l[SZ],s2l[SZ];
char s1[503][1003],s2[503][1003];
int main()
{
//freopen("test.txt","r",stdin);
scanf("%d",&Tat);
while(Tat--)
{
M=1;
scanf("%d%d",&h,&v);
for(int i=1;i<=h;i++)
{
scanf("%d%d ",x1+i,y1+i);
gets(s1[i]);
s1l[i]=strlen(s1[i]);
}
for(int i=1;i<=v;i++)
{
scanf("%d%d ",x2+i,y2+i);
gets(s2[i]);
s2l[i]=strlen(s2[i]);
}
n=h+v; S=++n; T=++n;
for(int i=1;i<=n;i++) fst[i]=0;
for(int i=1;i<=h;i++) ad_dl(S,i,1);
for(int i=1;i<=v;i++) ad_dl(i+h,T,1);
for(int i=1;i<=h;i++)
{
for(int j=1;j<=v;j++)
{
int xx=x2[j],yy=y1[i];
bool ok=1;
if(x1[i]<=xx&&xx<=x1[i]+s1l[i]-1)
{
if(y2[j]<=yy&&yy<=y2[j]+s2l[j]-1)
{
if(s1[i][xx-x1[i]]==s2[j][yy-y2[j]])
ok=1;
else ok=0;
}
}
//cout<<i<<","<<j<<" "<<ok<<"\n";
if(!ok) ad_dl(i,j+h,1);
}
}
printf("%d\n",h+v-dinic());
}
}
}
int main()
{
gg::main();
}
接下来就卡题了...打出gg