「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Exam
yy个奇怪的构造T T
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int 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; int main() { n=read(); if(n==2) { puts("1");puts("1"); } else if(n==3) { puts("2"); puts("1 3"); } else { printf("%d\n",n); if(n&1)printf("%d ",n/2+1); for(int i=1;i<=n/2;i++) if(n&1)printf("%d %d ",i,n-i+1); else printf("%d %d ",n/2+i,i); return 0; } } |
「cf534B」Covered Path
d很小，最大速度就很小，dp即可
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int 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 a,b,t,d; int f[105][1050]; int main() { a=read();b=read(); t=read();d=read(); memset(f,-1,sizeof(f)); f[0][a]=0; for(int i=0;i<t-1;i++) for(int j=0;j<=1000;j++) if(f[i][j]!=-1) for(int k=0;k<=d;k++) { f[i+1][j+k]=max(f[i+1][j+k],f[i][j]+j); if(j>=k)f[i+1][j-k]=max(f[i+1][j-k],f[i][j]+j); } printf("%d\n",f[t-1][b]+b); return 0; } |
「cf534C」Polycarpus’ Dice
对于每个骰子，得出其它骰子的和sum
则它的最小值为A-sum，最大值为A-n+1
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #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; ll d[200005],A,sum; int main() { n=read();A=read(); for(int i=1;i<=n;i++)d[i]=read(); for(int i=1;i<=n;i++)sum+=d[i]; for(int i=1;i<=n;i++) { ll mn=A-(sum-d[i]),mx=A-n+1; int t1=mn-1,t2=d[i]-mx; if(t1<0)t1=0;if(t2<0)t2=0; printf("%d ",t1+t2); } return 0; } |
「cf534D」Handshakes
尽量大的能处理则处理
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #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,now,top; int a[200005],ans[200005]; vector<int> c[200005]; int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)c[a[i]].push_back(i); while(top<n) { while(!c[now].size()) { now-=3; if(now<0){puts("Impossible");return 0;} } ans[++top]=c[now].back(); c[now].pop_back(); now++; } puts("Possible"); for(int i=1;i<=top;i++)printf("%d ",ans[i]); return 0; } |
「cf534E」Berland Local Positioning System
非常恶心T T
特判。。。
一段路径走的次数是俩端点出现次数最小值
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #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 ans; int n,m,tot; int a[200005],b[400005]; ll c[200005]; bool check(int l,int r) { for(int i=l+1;i<=r;i++) if(a[i]-a[i-1]!=a[l+1]-a[l])return 0; return 1; } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); m=read(); for(int i=1;i<=m;i++) { int x=read(); c[x]++; if(x==1||x==n)c[x]++; } ll mn=inf,mx=0; for(int i=1;i<=n;i++) mn=min(mn,c[i]),mx=max(mx,c[i]); if(mn==mx) if(check(1,n))printf("%lld\n",(a[n]-a[1])*mn-(a[2]-a[1])); else puts("-1"); else { for(int i=2;i<=n;i++) ans+=(a[i]-a[i-1])*min(c[i],c[i-1]); printf("%lld\n",ans); } return 0; } |
「cf534F」Simplified Nonogram
状压搞了半天。。。
f(i,j,k)表示前i列，末列为j，各行线段数状压为11^5。。。
输出方案还是dfs转移好。。。
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #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 bin[30],bin2[10],v[35][35]; int n,m,ed,top; int a[25],b[25]; vector<int> q[25]; bool f[25][32][161051]; char ans[10][25]; struct data{ int a,b; }; void p(int sta) { for(int i=1;i<=n;i++) if(sta&bin[i-1])ans[i][top]='*'; else ans[i][top]='.'; top--; } void dfs(int x,int tot,int sta,bool last) { if(x==n+1) { q[tot].push_back(sta); return; } dfs(x+1,tot+(!last),sta+bin[x-1],1); dfs(x+1,tot,sta,0); } bool dfs2(int i,int t1,int k) { f[i][t1][k]=1; if(i==m) { if(k==ed) { p(t1);return 1; } return 0; } for(int y=0;y<q[b[i+1]].size();y++) { int t2=q[b[i+1]][y]; int nk=k+v[t1][t2]; if(nk<=ed) if(!f[i+1][t2][nk]) if(dfs2(i+1,t2,nk)){p(t1);return 1;} } return 0; } int main() { bin[0]=1;for(int i=1;i<30;i++)bin[i]=bin[i-1]<<1; bin2[0]=1;for(int i=1;i<10;i++)bin2[i]=bin2[i-1]*11; n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=m;i++)b[i]=read(); for(int i=1;i<=n;i++)ed+=a[i]*bin2[i-1]; dfs(1,0,0,0); for(int t1=0;t1<=bin[n]-1;t1++) for(int t2=0;t2<=bin[n]-1;t2++) for(int l=1;l<=n;l++) if((t2&bin[l-1])&&(t1&bin[l-1])==0)v[t1][t2]+=bin2[l-1]; top=m; dfs2(0,0,0); for(int i=1;i<=n;i++)printf("%s\n",ans[i]+1); return 0; } |
Subscribe