Codeforces Round #302 (Div. 1) 训练

链接：

http://codeforces.com/contest/543

过程：

惨淡的只做出了A和C

题解：

A

题解：

简单的一道题

我们用$dp[i][j]$表示当前考虑到前num个人（这个另外枚举），当前写了$i$行代码，当前的bug数量为$j$的方案数

然后转移就是$dp[i][j]=sum {dp[i-1][j-a[num]]}$

Code：

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<map>
 7 #include<set>
 8 #include<cmath>
 9 #include<iostream>
10 #include<queue>
11 #include<string>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef long double ld;
16 typedef unsigned long long ull;
17 typedef pair<long long,long long> pll;
18 #define fi first
19 #define se second
20 #define pb push_back
21 #define mp make_pair
22 #define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
23 #define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
24 
25 ll read(){
26     ll x=0,f=1;char c=getchar();
27     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
28     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
29     return x*f;
30 }
31 
32 const int MAXN = 510;
33 
34 int mod;
35 int a[MAXN];
36 int dp[MAXN][MAXN];
37 
38 int add(int a, int b)
39 {
40     return (a + b) % mod;
41 }
42 
43 int main()
44 {
45     int n, m, b;
46     cin >> n >> m >> b >> mod;
47     for (int i = 0; i < n; i++)
48         cin >> a[i];
49     dp[0][0] = 1;
50     for (int i = 0; i < n; i++)
51         for (int j = 1; j <= m; j++)
52             for (int k = a[i]; k <= b; k++)
53                 dp[j][k] = add(dp[j][k], dp[j - 1][k - a[i]]);
54     int ans = 0;
55     for (int i = 0; i <= b; i++)x
56         ans = add(ans, dp[m][i]);
57     cout << ans << endl;
58 }

View Code

Review：

比较容易的一道题

B

题解：

首先可以通过BFS得到dis[i][j]数组，也就是任意两点的最短路

然后分两种情况

1. 只剩下s1到t1，s2到t2的最短路代价：m-dis[s1][t1]-dis[s2][t2]

2. 剩下的两条路径有交，组成一个‘H’形状

代价：枚举i，j表示那个交集的两端

然后剩下的边数的可能情况就是dis[s1][i]+dis[s2][i]+dis[i][j]+dis[j][t1]+dis[j][t2] 或者 dis[s1][i]+dis[t2][i]+dis[i][j]+dis[j][t1]+dis[j][s2]

取一个最小值再用m减去就好了

注意判断这样的i，j不满足l1，l2的要求的情况

Code：

  1 #include<stdio.h>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<map>
  7 #include<set>
  8 #include<cmath>
  9 #include<iostream>
 10 #include<queue>
 11 #include<string>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,int> pii;
 15 typedef long double ld;
 16 typedef unsigned long long ull;
 17 typedef pair<long long,long long> pll;
 18 #define fi first
 19 #define se second
 20 #define pb push_back
 21 #define mp make_pair
 22 #define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
 23 #define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
 24 
 25 ll read(){
 26     ll x=0,f=1;char c=getchar();
 27     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
 28     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
 29     return x*f;
 30 }
 31 
 32 const int maxn=3030;
 33 int n,m;
 34 vector<int> gr[maxn];
 35 int dis[maxn][maxn];
 36 bool vis[maxn];
 37 
 38 void bfs(int u){
 39     queue<int> q;
 40     while(!q.empty()) q.pop();
 41     memset(vis,0,sizeof(vis));
 42     vis[u]=1;q.push(u);
 43     while(!q.empty()){
 44         int v=q.front();
 45         q.pop();
 46         for(int i=0;i<gr[v].size();i++){
 47             int nw=gr[v][i];
 48             if(vis[nw]) continue;
 49             vis[nw]=1;
 50             dis[u][nw]=dis[u][v]+1;
 51             q.push(nw);
 52         }
 53     }
 54 }
 55 
 56 int main(){
 57     n=read(),m=read();
 58     rep(i,1,m){
 59         int a=read(),b=read();
 60         gr[a].pb(b),gr[b].pb(a);
 61     }
 62     int s1,t1,l1,s2,t2,l2;
 63     s1=read(),t1=read(),l1=read();
 64     s2=read(),t2=read(),l2=read();
 65     
 66     rep(i,1,n){
 67         bfs(i);
 68     }
 69     
 70     if(dis[s1][t1]>l1 || dis[s2][t2]>l2){
 71         puts("-1");
 72         return 0;
 73     }
 74     int ans1=m-dis[s1][t1]-dis[s2][t2];
 75     int ans2=0;
 76     for(int i=1;i<=n;i++){
 77         for(int j=1;j<=n;j++){
 78             if(i==j) continue;
 79             int nw=dis[s1][i]+dis[s2][i]+dis[i][j]+dis[j][t1]+dis[j][t2];
 80             if(dis[s1][i]+dis[i][j]+dis[j][t1]>l1 || dis[s2][i]+dis[i][j]+dis[j][t2]>l2) nw=1e9;
 81             int nw2=dis[s1][i]+dis[t2][i]+dis[i][j]+dis[j][t1]+dis[j][s2];
 82             if(dis[s1][i]+dis[i][j]+dis[j][t1]>l1 || dis[t2][i]+dis[i][j]+dis[j][s2]>l2) nw2=1e9;
 83             ans2=max(ans2,max(m-nw,m-nw2));
 84         }
 85     }
 86     printf("%d
",max(ans1,ans2));
 87     return 0;
 88 }
 89 
 90 /*
 91 9 9
 92 1 2
 93 2 3
 94 2 4
 95 4 5
 96 5 7
 97 5 6
 98 3 8
 99 8 9
100 9 6
101 1 7 4
102 3 6 3
103 */

View Code

Review：

我竟然连能够求出dis数组都没看出来

傻傻的以为要floyd或者n遍dijkstra

没注意到边权为1。。。

所以边权为1----BFS

C

题解：

很显然要用状压dp

（毕竟20的数据范围摆在那里）

那么令$dp[mask]$表示将mask对应的字符串变成easy to remember的最小代价

复杂度最多只能为$O(2^n imes n)$ 所以还可以枚举一层

那么怎么做呢

考虑转移：

首先我们不能做到O（1）转移

所以不能枚举每一个属于mask的字符串

那么我们必须做到对于任意一个属于mask的字符串通过我们的转移都能够得到答案

所以必须得有两种转移

我们令选取的字符串为$s_i$，剩下的状态为$nwmask$

1. 把$s_i$改动一位，并压进去

因为最多20个字符串而有26个字母，所以可以保证改任意一位都可行

那肯定选择最少的代价的那一位去修改

2. 改动其他的字符串的某一位，使得他们和$s_i$的这一位都不同

这个代价是可以预处理的

Code：

 1 #include <bits/stdc++.h>
 2 
 3 #define forn(i, n) for(int i = 0; i < int(n); i++)
 4 
 5 using namespace std;
 6 
 7 const int N = 20;
 8 const int leng = 300;
 9 string s[N];
10 int cost[N][leng], c[N][leng], sv[N][leng], a[N][leng];
11 int d[1 << N];
12 
13 int main() {
14   int n, m;
15   cin >> n >> m;
16   forn(i, n) cin >> s[i];
17   forn(i, n) forn(j, m) cin >> a[i][j];
18   
19   forn(i, n) {
20     forn(j, m) {
21       int curv = 0;
22       forn(k, n) {
23         if (s[i][j] == s[k][j]) {
24           sv[i][j] |= (1 << k);
25           c[i][j] += a[k][j];
26           curv = max(curv, a[k][j]);
27         }
28       }
29       c[i][j] -= curv;
30     }
31   }
32   forn(i, 1 << n) d[i] = 1000000000;
33   d[0] = 0;
34   forn(mask, 1 << n) {
35     if (mask == 0) continue;
36     int lowbit = -1;
37     forn(i, n) {
38       if ((mask >> i) & 1) {
39         lowbit = i;
40         break;
41       }
42     }
43     forn(i, m) {
44       d[mask] = min(d[mask], d[mask & (mask ^ sv[lowbit][i])] + c[lowbit][i]);
45       d[mask] = min(d[mask], d[mask ^ (1 << lowbit)] + a[lowbit][i]);
46     }
47   }
48   printf("%d
", d[(1 << n) - 1]);
49   return 0;
50 }

View Code

Review：

我觉得挺难的，但是怎么那么多人随手切啊

D

题解：

首先如果只要算1为根的答案是个很简单的树形dp

用$dp[i]$表示以i为根的子树的答案

$dp[i]=prod {(dp[son]+1)}$

然后我们考虑怎么算每个点的答案

我们通过父亲的答案求儿子的答案

怎么做呢？

首先我们看从父亲到儿子有哪些变化

我们用ans[i]记录i结点对应的上方给i的贡献然后再乘上dp[i]（i的下方对i的贡献）就是i为根的答案

我们怎么计算ans数组呢

发现从父亲到儿子的变化就在于多了几个儿子对应的兄弟

$ans[son]=ans[father] imes prod {(dp[brother]+1)}$

所以我们记录L，R表示当前结点的儿子们的前缀(dp+1)的积，后缀(dp+1)的积

然后$ans[son]=ans[father]*L[son]*R[son]*ans[father]+1$就可以了

+1指的是把儿子的父亲当作儿子的儿子的时候计算答案的时候要把dp+1相乘

Code：

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<map>
 7 #include<set>
 8 #include<cmath>
 9 #include<iostream>
10 #include<queue>
11 #include<string>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef long double ld;
16 typedef unsigned long long ull;
17 typedef pair<long long,long long> pll;
18 #define fi first
19 #define se second
20 #define pb push_back
21 #define mp make_pair
22 #define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
23 #define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
24 
25 ll read(){
26     ll x=0,f=1;char c=getchar();
27     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
28     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
29     return x*f;
30 }
31 
32 const int mod=1000000007;
33 int n;
34 vector<int> adj[200200];
35 ll dp[200200],L[200200],R[200200];
36 ll ans[200200];
37 
38 void dfs(int x){
39     dp[x]=1;
40     for(int i=0;i<adj[x].size();i++){
41         int v=adj[x][i];
42         dfs(v);
43         dp[x]=dp[x]*(dp[v]+1)%mod;
44     }
45 }
46 
47 void dfs2(int x){
48     int num=adj[x].size();
49     if(num==0) return;
50     L[0]=1,R[num-1]=ans[x];
51     for(int i=0;i<adj[x].size();i++){
52         int v=adj[x][i];
53         L[i+1]=L[i]*(dp[v]+1)%mod;
54     }
55     for(int i=num-1;i>=0;i--){
56         int v=adj[x][i];
57         R[i-1]=R[i]*(dp[v]+1)%mod;
58     }
59     for(int i=0;i<num;i++){
60         int v=adj[x][i];
61         ans[v]=(L[i]*R[i]+1)%mod;
62     }
63     for(int i=0;i<num;i++){
64         int v=adj[x][i];
65         dfs2(v);
66     }
67 }
68 
69 int main(){
70     n=read();
71     rep(i,2,n){
72         int x=read();
73         adj[x].pb(i);
74     }
75     dfs(1);
76     ans[1]=1;
77     dfs2(1);
78     rep(i,1,n)
79         printf("%lld ",dp[i]*ans[i]%mod);
80     puts("");
81     return 0;
82 }
83 
84 /*
85 5
86 1 2 3 4
87 */

View Code

Review：

第一个dp很好想

但是怎么求ans不知道怎么想的

可能需要灵机一动？