「CF543X」Codeforces Round #302 (Div. 1)
本场血崩
A. Writing Code
显然的n^3 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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 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,m,b,mod; int a[505]; int f[505][505],g[505][505]; int main() { n=read();m=read();b=read();mod=read(); for(int i=1;i<=n;i++)a[i]=read(); f[0][0]=1; for(int i=0;i<n;i++) { for(int j=0;j<=m;j++) for(int k=0;k<=b;k++) if(f[j][k]) { if(k+a[i+1]<=b)(f[j+1][k+a[i+1]]+=f[j][k])%=mod; (g[j][k]+=f[j][k])%=mod; } for(int j=0;j<=m;j++) for(int k=0;k<=b;k++) f[j][k]=g[j][k],g[j][k]=0; } int ans=0; for(int k=0;k<=b;k++) ans=(ans+f[m][k])%mod; printf("%d\n",ans); return 0; } |
B. Destroying Roads
n个结点,m条边的无向图(边权全为1),问最多能删掉多少条边使得s1到t1距离不超过l1,s2到t2距离不超过l2。
\(1\leq n\leq 500,1\leq m\leq n(n-1)/2\)
题解
其实就是问，至少需要多少条边，才能使得s1到t1距离不超过l1,s2到t2距离不超过l2。
如果这两条路径不相交，那么答案为dis(s1,t1)+dis(s2,t2)。
如果相交部分为(p1,p2)，答案为p1,p2的最短路，加上p1,p2到其它4个点的最短路。
预处理任意点对距离，枚举两条路径重叠部分。
|
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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 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,m,cnt; int last[3005],q[3005],dis[3005][3005]; int s1,t1,l1,s2,t2,l2; bool vis[3005]; struct edge{ int to,next; }e[6005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } void bfs(int x) { memset(vis,0,sizeof(vis)); int head=0,tail=1; q[0]=x;vis[x]=1; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(!vis[e[i].to]) { vis[e[i].to]=1; dis[x][e[i].to]=dis[x][now]+1; q[tail++]=e[i].to; } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++)bfs(i); s1=read();t1=read();l1=read(); s2=read();t2=read();l2=read(); if(dis[s1][t1]>l1||dis[s2][t2]>l2){puts("-1");return 0;} int ans=dis[s1][t1]+dis[s2][t2]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(dis[s1][i]+dis[i][j]+dis[j][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2) ans=min(ans,dis[s1][i]+dis[s2][i]+dis[i][j]+dis[j][t1]+dis[j][t2]); if(dis[s1][j]+dis[i][j]+dis[i][t1]<=l1&&dis[s2][i]+dis[i][j]+dis[j][t2]<=l2) ans=min(ans,dis[s1][j]+dis[s2][i]+dis[i][j]+dis[i][t1]+dis[j][t2]); } printf("%d\n",m-ans); return 0; } |
D. Road Improvement
两遍树形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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 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; vector<int>a[200005]; ll f[200005],g[200005],s1[200005],s2[200005]; void dp1(int x) { f[x]=1; for(int i=0;i<a[x].size();i++) { int t=a[x][i]; dp1(t); f[x]=f[x]*(f[t]+1)%mod; } } void dp2(int x) { s1[0]=1;s2[a[x].size()]=1; for(int i=0;i<a[x].size();i++) s1[i+1]=s1[i]*(f[a[x][i]]+1)%mod; if(a[x].size()) for(int i=a[x].size()-1;i>=0;i--) s2[i]=s2[i+1]*(f[a[x][i]]+1)%mod; for(int i=0;i<a[x].size();i++) { int t=a[x][i]; g[t]=g[x]*s1[i]%mod*s2[i+1]%mod; g[t]=(g[t]+1)%mod; } for(int i=0;i<a[x].size();i++) dp2(a[x][i]); } int main() { n=read(); for(int i=2;i<=n;i++) { int p=read(); a[p].push_back(i); } g[1]=1; dp1(1);dp2(1); for(int i=1;i<=n;i++) printf("%I64d ",f[i]*g[i]%mod); return 0; } |
计数器 9319276
OI 课件=>
OI 课件=>
请问D题的两个dp是什么意思啊…