首页 > 代码库 > Codeforces Training S03E01泛做
Codeforces Training S03E01泛做
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_pairtypedef 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 666666int 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_pairtypedef 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 666666char 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_backtypedef 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 666666int 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 101bool& 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 666666int 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 1000000000int 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
Codeforces Training S03E01泛做
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。