Codeforces Round #263 (Div. 2)

吐槽：一辈子要在DIV 2混了。

A,B,C都是简单题，看AC人数就知道了。

A:如果我们定义数组为N*N的话就不用考虑边界了

 1 #include<iostream>
 2 #include <string>
 3 #include <vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<string>
 8 #include<algorithm>
 9 using namespace std;
10 #define inf 0x3f3f3f
11 #define N 12345
12 typedef long long ll;
13 int a[N];
14 char  s[123][123];
15 int main()
16 {
17   int n;
18   scanf("%d",&n);
19   for (int i=1;i<=n;i++)
20     scanf("%s",s[i]+1);
21 
22     int flag=1;
23   for (int i=1;i<=n;i++)
24   for (int j=1;j<=n;j++){
25         int ans=0;
26     if (s[i-1][j]=='o') ans++;
27     if (s[i][j-1]=='o') ans++;
28     if (s[i][j+1]=='o') ans++;
29     if (s[i+1][j]=='o') ans++;
30     if (ans&1) {flag=0;break;}
31   }
32 
33   if (flag) printf("YES");
34   else printf("NO");
35   return 0;
36 }

B:语文实在...。。

可以是贪心。。。

只要对26个字母排序

233

 1 #include<iostream>
 2 #include <string>
 3 #include <vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<string>
 8 #include<algorithm>
 9 using namespace std;
10 #define inf 0x3f3f3f
11 #define N 123456
12 typedef long long ll;
13 ll a[N];
14 string s;
15 int main()
16 {
17   int  n;
18   ll k;
19   cin>>n>>k;
20   cin>>s;
21   for (int i=0;i<s.size();i++)
22    a[s[i]-'A']++;
23     sort(a,a+26);
24     ll ans=0;
25     for (int i=26;i>=0;i--)
26     {
27         if (k>=a[i]) {ans+=a[i]*a[i];k-=a[i];
28         }
29         else {ans+=k*k;break;}
30     }
31    cout<<ans<<endl;
32    return 0;
33   }

这题也是贪心做法。。

因为我们要加的数的个数是一定的。。。

如果排序好，尽量加大的，就OK了。。所以每次我们把最小的踢出去。

就可以算出每个数要加多少。

 1 #include<iostream>
 2 #include <string>
 3 #include <vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<string>
 8 #include<algorithm>
 9 using namespace std;
10 #define inf 0x3f3f3f
11 #define N 323456
12 typedef long long ll;
13 ll a[N];
14 string s;
15 int main()
16 {
17   int  n;
18   cin>>n;
19   for (int i=1;i<=n;i++)cin>>a[i];
20   ll ans=0;
21   sort(a+1,a+n+1);
22   for (int i=1;i<n;i++)
23     ans+=a[i]*(i+1);
24     ans+=a[n]*n;
25   cout<<ans;
26   return 0;
27 }

D：练了不少树形DP了，但是这题完全没思路。真是渣一辈子DIV 2。

思路：定义DP[I][1]表示以I为根的数中有BLACK节点

DP[I][0]表示没有BLACK节点。。

转移方程

U是ROOT的子节点

初始：DP[ROOT][COLOR[ROOT]]=1;

DP[ROOT][1]=DP[ROOT][1]*DP[U][1]+DP[ROOT][0]*DP[U][1]+DP[ROOT][1]*DP[U][0];

DP[ROOT][0]=DP[ROOT][0]*DP[U][0]+DP[ROOT][0]*DP[U][1];

 1 #include<iostream>
 2 #include <string>
 3 #include <vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<algorithm>
 8 #define N 112345
 9 #define inf 1000000007
10 typedef long long ll;
11 using namespace std;
12 vector<int>G[N];
13 ll dp[N][2];
14 int col[N];
15 int n;
16 
17 
18 void dfs(int root,int pre)
19 {
20     dp[root][col[root]]=1;
21     for (int i=0;i<G[root].size();i++)
22     {
23         int x=G[root][i];
24         if (x==pre) continue;
25         dfs(x,root);
26         dp[root][1]=(dp[root][1]*dp[x][0]%inf+dp[root][1]*dp[x][1]+dp[root][0]*dp[x][1])%inf;
27         dp[root][0]=(dp[root][0]*dp[x][1]%inf+dp[root][0]*dp[x][0]%inf)%inf;
28         }
29 }
30 
31 int main()
32 {
33     scanf("%d",&n);
34     for (int i=1;i<n;i++)
35     {
36         int x;
37        scanf("%d",&x);
38         G[i].push_back(x);
39         G[x].push_back(i);
40      }
41      for (int i=0;i<n;i++)
42      scanf("%d",&col[i]);
43      dfs(0,-1);
44      printf("%d
",dp[0][1]);
45      return 0;
46 }

后记：

树形DP比较抽象。。。多做题才能提高