「CF317X」Codeforces Round #188 (Div. 1)
A. Perfect Pair
每次把小的那个变成两个的和，注意考虑负数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll x,y,m,ans; int main() { x=read();y=read();m=read(); while(1) { if(x>=m||y>=m)break; if(x<=0&&y<=0){puts("-1");return 0;} if(x>y)swap(x,y); ll K=max(1LL,min(m-x,0-x)/y); x+=y*K; ans+=K; } cout<<ans<<endl; return 0; } |
B. Ants
蚂蚁的活动范围不太大，所以依然是暴力QAQ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,t; int mp[205][205]; void dfs(int x,int y) { int t=mp[x][y]/4;mp[x][y]%=4; if(t==0)return; mp[x+1][y]+=t;dfs(x+1,y); mp[x-1][y]+=t;dfs(x-1,y); mp[x][y+1]+=t;dfs(x,y+1); mp[x][y-1]+=t;dfs(x,y-1); } int main() { mp[70][70]=read();t=read(); dfs(70,70); for(int i=1;i<=t;i++) { int x=read(),y=read(); if(x<-70||y<-70||x>70||y>70)puts("0"); else printf("%d\n",mp[x+70][y+70]); } return 0; } |
C. Balance
每次从缺水的地方出发，找一条能送水过来的路径a->b，要保证a是路径上符合要求的第一个容器
运送量\(d=min(b_b-a_b,a_a-b_a)\)，找n次
若没有容量限制，每次从b到a扫，找当前水量超过d的往b方向运
由于有容量限制，把d拆成d/2和d-d/2分两次运
运送次数2nL
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,v,m,top; int a[305],b[305]; vector<int>e[305],q; struct edge{ int u,v,w; }ans[200005]; bool vis[305]; int findpath(int x) { if(!vis[x])vis[x]=1; else return 0; q.push_back(x); if(a[x]>b[x])return 1; for(int i=0;i<e[x].size();i++) if(findpath(e[x][i])) return 1; q.pop_back(); return 0; } int main() { n=read();v=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=n;i++) while(a[i]<b[i]) { memset(vis,0,sizeof(vis)); q.clear(); findpath(i); if(q.empty()){puts("NO");return 0;} int ed=q.back(),d=min(b[i]-a[i],a[ed]-b[ed]); bool t[305]={},flag=1; int d1=d/2,d2=d-d1; while(flag&&d1) { flag=0; for(int j=1;j<q.size();j++) if(!t[q[j]]&&a[q[j]]>=d1) { a[q[j]]-=d1,a[q[j-1]]+=d1; ans[++top]=(edge){q[j],q[j-1],d1}; t[q[j]]=1;flag=1; } } flag=1;memset(t,0,sizeof(t)); while(flag) { flag=0; for(int j=1;j<q.size();j++) if(!t[q[j]]&&a[q[j]]>=d2) { a[q[j]]-=d2,a[q[j-1]]+=d2; ans[++top]=(edge){q[j],q[j-1],d2}; t[q[j]]=1;flag=1; } } } for(int i=1;i<=n;i++) if(a[i]!=b[i]) { puts("NO");return 0; } printf("%d\n",top); for(int i=1;i<=top;i++) printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].w); return 0; } |
D. Game with Powers
状压+爆搜得出个数为1-30的sg值
然后把不同底数的sg值异或一下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,K,ans; bool mark[100005]; int sg[]={0,1,2,1,4,3,2,1,5,6,2,1,8,7,5,9,8,7,3,4,7,4,2,1,10,9,3,6,11,12}; //map<int,int>sg; /*int pre(int x) { if(sg[x])return sg[x]-1; bool mark[15];for(int i=0;i<13;i++)mark[i]=0; for(int i=1;(1<<(i-1))<=x;i++) if(x&(1<<(i-1))) { int t=x; for(int k=i;k<30;k+=i) if((1<<(k-1))&t)t^=(1<<(k-1)); mark[pre(t)]=1; } for(int i=0;i<13;i++) if(!mark[i]) { sg[x]=i+1; return i; } return 14; } */ int main() { //for(int i=0;i<30;i++)cout<<pre((1<<i)-1)<<' '; n=read();m=(int)sqrt(n);K=n; for(int i=2;i<=m;i++) if(!mark[i]) { ll k=i,t=0; while(k<=n) { K--;t++; if(k<=m)mark[k]=1; k*=i; } ans^=sg[t]; } if(K&1)ans^=1; if(ans)puts("Vasya"); else puts("Petya"); return 0; } |
E. Princess and Her Shadow
拉出小树林再找一棵边界上的树把影子卡住
说起来简单QAQ
第一步不断走到影子的最短路，后面的就分类讨论
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #define ll long long #define in(x,y) (0<=x&&x<=300&&0<=y&&y<=300) using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int sx,sy,tx,ty,n; int xx[]={1,0,0,-1},yy[]={0,1,-1,0}; char c[]={'R','U','D','L'}; struct data{ int x,y; }a[405],P[4],L,R,U,D,q[100005]; int dir[100005],from[100005]; vector<int>p; bool vis[305][305],mp[305][305]; bool bfs() { int head=0,tail=1; q[0]=(data){sx,sy};vis[sx][sy]=1; while(head!=tail) { int x=q[head].x,y=q[head].y; for(int k=0;k<4;k++) { int nx=x+xx[k],ny=y+yy[k]; if(in(nx,ny)&&!vis[nx][ny]) { q[tail]=(data){nx,ny};vis[nx][ny]=1; dir[tail]=k;from[tail]=head; if(nx==tx&&ny==ty) { p.clear(); for(;tail;tail=from[tail]) p.push_back(dir[tail]); reverse(p.begin(),p.end()); return 1; } tail++; } } head++; } return 0; } bool move(int k) { sx+=xx[k];sy+=yy[k]; tx+=xx[k];ty+=yy[k]; putchar(c[k]); if(in(tx,ty)&&mp[tx][ty]) { tx-=xx[k];ty-=yy[k]; return 0; } return 1; } void pre() { while((0<=sx&&sx<=300)||(0<=tx&&tx<=300))move(0); while((0<=sy&&sy<=300)||(0<=ty&&ty<=300))move(1); } void ud(int d) { pre(); while((d==2&&0<=ty)||(d==1&&ty<=300))move(d); while(tx!=P[d].x)move(tx<P[d].x?0:3); while(sy!=ty)move(3-d); } void lr(int d) { pre(); while((d==3&&0<=tx)||(d==0&&tx<=300))move(d); while(ty!=P[d].y)move(ty<P[d].y?1:2); while(sx!=tx)move(3-d); } void solve() { if(!n||!bfs()){puts("-1");return;} for(int i=0;i<p.size();i++) { if(move(p[i]))p.push_back(p[i]); if(sx==tx&&sy==ty)return; if(!in(sx,sy))break; } if(sy<ty)ud(2); if(sy>ty)ud(1); if(sx<tx)lr(3); if(sx>tx)lr(0); } int main() { sx=read();sy=read();tx=read();ty=read();n=read(); sx+=150;sy+=150;tx+=150;ty+=150; int x,y; L.x=D.y=inf;R.x=U.y=-inf; for(int i=1;i<=n;i++) { x=read()+150;y=read()+150; if(x<L.x)L=(data){x,y}; if(x>R.x)R=(data){x,y}; if(y<D.y)D=(data){x,y}; if(y>U.y)U=(data){x,y}; mp[x][y]=vis[x][y]=1; } P[0]=R;P[1]=U;P[2]=D;P[3]=L; solve(); return 0; } |
计数器 9851976
OI 课件=>
OI 课件=>
> <