CERC 2014 填坑计划(9 / 12)
又是一个深不见底的大坑
9/12
A.Parades
树形dp，dp[x]=∑dp[son]
可能还有从一个子树出发，到达另一个子树的路径
在每个结点记录在这棵树最优解的情况下去掉覆盖的路径树根能到达的点，这个每次暴力合并
每个结点用状压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 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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #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,m,T; int f[1005],g[2005]; vector<int>e[1005],d[1005],st; bool mp[1005][1005],t[15][15]; bool check(int x,int y) { for(int i=0;i<d[x].size();i++) for(int j=0;j<d[y].size();j++) if(mp[d[x][i]][d[y][j]])return 1; return 0; } void dfs(int x,int fa) { f[x]=0; for(int i=0;i<e[x].size();i++) if(e[x][i]!=fa) dfs(e[x][i],x); d[x].push_back(x); st.clear(); for(int i=0;i<e[x].size();i++) if(e[x][i]!=fa) { f[x]+=f[e[x][i]]; if(check(x,e[x][i]))f[x]++; else st.push_back(e[x][i]); } memset(t,0,sizeof(t)); for(int i=0;i<st.size();i++) for(int j=i+1;j<st.size();j++) t[i][j]=check(st[i],st[j]); int ed=(1<<st.size())-1,now=0,ans=0; for(int i=0;i<=ed;i++) { g[i]=0; for(int x=0;x<st.size();x++) if(i&(1<<x)) for(int y=x+1;y<st.size();y++) if(i&(1<<y)) if(t[x][y]) g[i]=max(g[i],g[i-(1<<x)-(1<<y)]+1); if(g[i]>ans)now=0,ans=g[i]; if(g[i]==ans)now|=(ed-i); } f[x]+=ans; for(int i=0;i<st.size();i++) if((1<<i)&now) { int t=st[i]; for(int j=0;j<d[t].size();j++) d[x].push_back(d[t][j]); } } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++) { d[i].clear();e[i].clear(); for(int j=1;j<=n;j++)mp[i][j]=0; } for(int i=1;i<n;i++) { int u=read(),v=read(); e[u].push_back(v); e[v].push_back(u); } m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); mp[u][v]=mp[v][u]=1; } dfs(1,0); printf("%d\n",f[1]); } return 0; } |
C.Sum
我傻逼了。。。
枚举答案后二分（其实可以直接算）
不合法的情况似乎是2的幂
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define eps 1e-9 #define sqr(x) x*x #define pi acos(-1) #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 T,n,L,R; bool check(int x) { int l=1,r=n/x; while(l<=r) { ll mid=(l+r)>>1; ll sum=(2*mid+x-1)*x/2; if(sum==n) { L=mid,R=mid+x-1; return 1; } if(sum<n)l=mid+1; else r=mid-1; } return 0; } int main() { T=read(); while(T--) { L=-1;n=read(); int m=n;while(m%2==0)m/=2; if(m==1) { puts("IMPOSSIBLE"); continue; } if(n&1) L=n/2,R=L+1; else for(int i=2;i*i/2<=n;i++) if(check(i))break; if(L!=-1) { printf("%d = ",n); for(int i=L;i<=R;i++) if(i==L)printf("%d",i); else printf(" + %d",i); puts(""); } else { puts("IMPOSSIBLE"); } } return 0; } |
D.Wheels
模拟
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define eps 1e-10 #define ll long long using namespace std; int gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } 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 T,n; int x[1005],y[1005],r[1005],c[1005],vx[1005],vy[1005]; double sqr(double x) { return x*x; } double dis(int a,int b) { return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b])); } bool check(int a,int b) { return fabs(r[a]+r[b]-dis(a,b))<=eps; } void dfs(ll x,int fa) { if(c[x]!=-1)return; if(x!=1) { vx[x]=vx[fa]*r[fa]; vy[x]=vy[fa]*r[x]; } c[x]=c[fa]^1; int &a=vx[x],&b=vy[x]; int t=gcd(a,b); a/=t;b/=t; for(int i=1;i<=n;i++) if(check(x,i)) { dfs(i,x); } } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),r[i]=read(); memset(c,-1,sizeof(c)); vx[1]=vy[1]=1;c[0]=1; dfs(1,0); for(int i=1;i<=n;i++) if(c[i]==-1)puts("not moving"); else { if(vy[i]==1)printf("%d ",vx[i]); else printf("%d/%d ",vx[i],vy[i]); if(c[i])puts("counterclockwise"); else puts("clockwise"); } } return 0; } |
E.Can’t stop playing
维护一个递增+递减序列
dp(i,j)表示前i个，递减序列和为j的方案是否存在
|
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 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 #define N 8193 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[15]; int T,n,a[1005],s[1005]; int f[1005][N],g[1005][N],dir[1005][N]; void update(int x,int p,int y,int d) { f[x][y]=1; g[x][y]=p; dir[x][y]=d; } int low(int x) { return x&(-x); } int high(int x) { for(int i=N-1;i;i>>=1) if(i&x)return i; return 0; } int main() { bin[0]=1;for(int i=1;i<15;i++)bin[i]=bin[i-1]<<1; T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]; update(1,0,a[1],1); for(int i=1;i<n;i++) for(int j=0;j<N;j++) if(f[i][j]) { int r=s[i]-j+high(j); if(a[i+1]<=low(r)) { int t=r+a[i+1]; if(low(t)==t) update(i+1,j,s[i+1],1); else update(i+1,j,j,1); } else if(s[i]==j) update(i+1,j,s[i+1],1); if(low(j)>=a[i+1]) update(i+1,j,j+a[i+1],0); } if(!f[n][s[n]]||low(s[n])!=s[n])puts("no"); else { vector<int>ans; for(int i=s[n],x=n;x;i=g[x][i],x--) ans.push_back(dir[x][i]); while(!ans.empty()) { int t=ans.back(); ans.pop_back(); putchar(t?'r':'l'); } puts(""); } for(int i=1;i<=n;i++) for(int j=0;j<=s[n];j++) f[i][j]=0; } return 0; } |
F.Vocabulary
dp(i,j)表示前i个字符，状态为j的方案
状态0,1,2,3
0 未分出字典序
1 A=B<C
2 A<B=C
3 A<B<C
暴力预处理出转移
|
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 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 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 T,n; char a[3][1000005];int l[3]; int f[28][28][28][4][4]; ll g[1000005][4]; void pre() { for(int x=0;x<=27;x++) for(int y=0;y<=27;y++) for(int z=0;z<=27;z++) { int xs=x,xt=x,ys=y,yt=y,zs=z,zt=z; if(x==27)xs=1,xt=26; if(y==27)ys=1,yt=26; if(z==27)zs=1,zt=26; for(int xn=xs;xn<=xt;xn++) for(int yn=ys;yn<=yt;yn++) for(int zn=zs;zn<=zt;zn++) for(int k=0;k<=3;k++) { int t=k; if(k==0) { if(zn>yn)t+=1; if(yn>xn)t+=2; if(zn<yn||yn<xn)t=-1; } if(k==1) { if(yn>xn)t+=2; if(yn<xn)t=-1; } if(k==2) { if(zn>yn)t+=1; if(zn<yn)t=-1; } if(t!=-1)f[x][y][z][k][t]++; } } } void dp() { g[0][0]=1; for(int i=1;i<=n;i++) { int x=a[0][i]-'a'+1,y=a[1][i]-'a'+1,z=a[2][i]-'a'+1; if(a[0][i]=='?')x=27; if(a[1][i]=='?')y=27; if(a[2][i]=='?')z=27; for(int j=0;j<=3;j++) if(g[i-1][j]) for(int k=0;k<=3;k++) g[i][k]=(g[i][k]+g[i-1][j]*f[x][y][z][j][k]%mod)%mod; } printf("%I64d\n",g[n][3]); } int main() { pre(); T=read(); while(T--) { n=0; for(int i=0;i<3;i++) { scanf("%s",a[i]+1); l[i]=strlen(a[i]+1); n=max(n,l[i]); } for(int i=1;i<=n;i++) for(int j=0;j<=4;j++) g[i][j]=0; for(int i=0;i<3;i++) for(int j=l[i]+1;j<=n;j++) a[i][j]='a'-1; dp(); } return 0; } |
H.Good morning!
把方案全搜出来二分
|
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<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define eps 1e-9 #define sqr(x) x*x #define pi acos(-1) #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,top; int a[4][3]={1,2,3,4,5,6,7,8,9,-1,0,-1}; set<int> q; void dfs(int x,int y,int tot) { if(x>=4||y>=3||a[x][y]==-1)return; if(tot>1000)return; q.insert(tot); dfs(x+1,y,tot); dfs(x,y+1,tot); if(tot+a[x][y]!=0)dfs(x,y,tot*10+a[x][y]); } int main() { dfs(0,0,0); T=read(); while(T--) { n=read(); int t1=*q.lower_bound(n)-n,t2=n-(*--q.lower_bound(n)); if(t1<t2)printf("%d\n",*q.lower_bound(n)); else printf("%d\n",*--q.lower_bound(n)); } return 0; } |
I.Bricks
贪心
|
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 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define mod 1000000007 #define inf 1000000000 #define eps 1e-10 #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 T,n,ans; ll a[100005],b[100005]; ll num[2],now[2]; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } int main() { T=read(); while(T--) { ans=num[0]=num[1]=0; n=read(); char ch[2]; for(int i=1;i<=n;i++) { a[i]=read(); scanf("%s",ch+1); if(ch[1]=='B')b[i]=1; else b[i]=0; num[b[i]]+=a[i]; } if(!num[0]||!num[1]) { printf("%I64d\n",num[0]+num[1]); continue; } ll t=gcd(num[0],num[1]),tmp; num[0]/=t;num[1]/=t; for(int i=1;i<=n;) { tmp=now[b[i]^1]*num[b[i]]/num[b[i]^1]; if(now[b[i]^1]*num[b[i]]%num[b[i]^1])tmp=0; if(now[b[i]]>=tmp||now[b[i]]+a[i]<tmp) { now[b[i]]+=a[i]; i++; } else { int t=min(a[i],tmp-now[b[i]]); a[i]-=t;now[b[i]]+=t; if(now[b[i]]==tmp) { now[0]=now[1]=0; ans++; } } } printf("%d\n",ans); } return 0; } |
K.The Imp
http://blog.csdn.net/u012647218/article/details/42191461
|
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 |
#include<map> #include<cmath> #include<ctime> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define mod 1000000009 #define inf 1000000000 #define eps 1e-8 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 T,n,K; int f[1500005][10]; struct data{ int v,c; }a[1500005]; bool operator<(data a,data b) { return a.v>b.v; } void dp() { for(int i=1;i<=n;i++) f[i][0]=max(f[i-1][0],a[i].v-a[i].c); for(int i=1;i<=n;i++) for(int j=1;j<=K;j++) f[i][j]=max(f[i-1][j],min(a[i].v-a[i].c,f[i-1][j-1]-a[i].c)); } int main() { T=read(); while(T--) { n=read();K=read(); for(int i=1;i<=n;i++) a[i].v=read(),a[i].c=read(); sort(a+1,a+n+1); dp(); printf("%d\n",f[n][K]); } return 0; } |
L.Outer space invaders
http://blog.csdn.net/u012647218/article/details/42148639
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 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 T,n,tot; int f[605][605]; vector<int>disc; struct data{ int st,ed,d; }a[305]; void dp() { for(int k=0;k<=tot;k++) for(int i=0;i+k<=tot;i++) { int j=i+k,mx=0; for(int t=1;t<=n;t++) if(i<a[t].st&&j>a[t].ed&&a[t].d>=a[mx].d)mx=t; if(!mx)f[i][j]=0; else { f[i][j]=inf; for(int t=a[mx].st;t<=a[mx].ed;t++) f[i][j]=min(f[i][j],f[i][t]+f[t][j]+a[mx].d); } } } int main() { T=read(); while(T--) { n=read(); disc.clear(); for(int i=1;i<=n;i++) { a[i].st=read(),a[i].ed=read(),a[i].d=read(); disc.push_back(a[i].st); disc.push_back(a[i].ed); } sort(disc.begin(),disc.end()); disc.erase(unique(disc.begin(),disc.end()),disc.end()); for(int i=1;i<=n;i++) { a[i].st=lower_bound(disc.begin(),disc.end(),a[i].st)-disc.begin()+1; a[i].ed=lower_bound(disc.begin(),disc.end(),a[i].ed)-disc.begin()+1; } tot=disc.size()+1; dp(); printf("%d\n",f[0][tot]); } return 0; } |
Subscribe
计数器 9813842
OI 课件=>
OI 课件=>