「CF546X」Codeforces Round #304 (Div. 2)
A. Soldier and Bananas
模拟
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> 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,k,w; int main() { k=read();n=read();w=read(); for(int i=1;i<=w;i++) n-=i*k; if(n>=0)puts("0"); else printf("%d\n",-n); return 0; } |
B. Soldier and Badges
排序
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> 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,ans; int a[3005]; int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); sort(a+1,a+n+1); int t=0; for(int i=1;i<=n;i++) if(a[i]>t)t=a[i]; else ans+=t+1-a[i],t++; printf("%d\n",ans); return 0; } |
C.Soldier and Cards
暴力模拟个一百万次。。。
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> 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,k1,k2; queue<int>q1,q2; void solve() { int t1=q1.front(),t2=q2.front(); q1.pop(); q2.pop(); if(t1>t2)q1.push(t2),q1.push(t1); else q2.push(t1),q2.push(t2); } int main() { n=read(); k1=read();for(int i=1;i<=k1;i++){int x=read();q1.push(x);} k2=read();for(int i=1;i<=k2;i++){int x=read();q2.push(x);} bool flag=0; for(int i=1;i<=1000000;i++) { solve(); if(q1.empty()||q2.empty()) { printf("%d ",i); if(q1.empty())puts("2"); else puts("1"); flag=1; break; } } if(!flag)puts("-1"); return 0; } |
D.Soldier and Number Game
用筛法得出每个数质因子个数前缀和即可
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> 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,a,b,cnt; int pri[1000005],sum[5000005]; bool mark[5000005]; void pre() { for(int i=2;i<=5000000;i++) { if(!mark[i])pri[++cnt]=i,sum[i]=1; for(int j=1;j<=cnt&&pri[j]*i<=5000000;j++) { mark[pri[j]*i]=1; sum[pri[j]*i]=sum[i]+1; if(i%pri[j]==0)break; } } for(int i=2;i<=5000000;i++)sum[i]+=sum[i-1]; } int main() { pre(); n=read(); while(n--) { a=read();b=read(); printf("%d\n",sum[a]-sum[b]); } return 0; } |
E. Soldier and Traveling
我比较愚蠢写了网络流。。正解是什么我不知道
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<ll,int> 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,cnt=1,T,sum,sum2,ans; int h[205],last[205],q[205],a[105],b[105]; int f[105][105]; struct edge{ int to,next,v; }e[1000005]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=0;h[0]=0; while(head!=tail) { int x=q[head];head++; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==-1&&e[i].v) { h[e[i].to]=h[x]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } int main() { n=read();m=read();T=2*n+1; for(int i=1;i<=n;i++) { a[i]=read(); insert(0,i,a[i]); insert(i,i+n,inf); sum+=a[i]; } for(int i=1;i<=n;i++) { b[i]=read(); sum2+=b[i]; insert(i+n,T,b[i]); } for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,n+v,inf); insert(v,n+u,inf); } while(bfs())ans+=dfs(0,inf); if(ans==sum&&ans==sum2) { puts("YES"); for(int i=1;i<=n;i++) for(int j=last[i];j;j=e[j].next) if(e[j].to>n)f[i][e[j].to-n]=e[j^1].v; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%d ",f[i][j]); puts(""); } } else puts("NO"); return 0; } |
计数器 9774789
OI 课件=>
OI 课件=>
正解也是网络流啊？
我是说E
我不知道啊。。。看好像有些人代码很短
然而最短的也是网络流啊？
噢