Codeforces Round #263 (Div. 2)

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

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

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

 #include<iostream>

 #include <string>

 #include <vector>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<string>

 #include<algorithm>

 using namespace std;

 #define inf 0x3f3f3f

 #define N 12345

 typedef long long ll;

 int a[N];

 char  s[][];

 int main()

 {

   int n;

   scanf("%d",&n);

   for (int i=;i<=n;i++)

     scanf("%s",s[i]+);

     int flag=;

   for (int i=;i<=n;i++)

   for (int j=;j<=n;j++){

         int ans=;

     if (s[i-][j]=='o') ans++;

     if (s[i][j-]=='o') ans++;

     if (s[i][j+]=='o') ans++;

     if (s[i+][j]=='o') ans++;

     if (ans&) {flag=;break;}

   }

   if (flag) printf("YES");

   else printf("NO");

   return ;

 }

B:语文实在...。。

可以是贪心。。。

只要对26个字母排序

233

 #include<iostream>

 #include <string>

 #include <vector>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<string>

 #include<algorithm>

 using namespace std;

 #define inf 0x3f3f3f

 #define N 123456

 typedef long long ll;

 ll a[N];

 string s;

 int main()

 {

   int  n;

   ll k;

   cin>>n>>k;

   cin>>s;

   for (int i=;i<s.size();i++)

    a[s[i]-'A']++;

     sort(a,a+);

     ll ans=;

     for (int i=;i>=;i--)

     {

         if (k>=a[i]) {ans+=a[i]*a[i];k-=a[i];

         }

         else {ans+=k*k;break;}

     }

    cout<<ans<<endl;

    return ;

   }

这题也是贪心做法。。

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

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

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

 #include<iostream>

 #include <string>

 #include <vector>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<string>

 #include<algorithm>

 using namespace std;

 #define inf 0x3f3f3f

 #define N 323456

 typedef long long ll;

 ll a[N];

 string s;

 int main()

 {

   int  n;

   cin>>n;

   for (int i=;i<=n;i++)cin>>a[i];

   ll ans=;

   sort(a+,a+n+);

   for (int i=;i<n;i++)

     ans+=a[i]*(i+);

     ans+=a[n]*n;

   cout<<ans;

   return ;

 }

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];

 #include<iostream>

 #include <string>

 #include <vector>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #define N 112345

 #define inf 1000000007

 typedef long long ll;

 using namespace std;

 vector<int>G[N];

 ll dp[N][];

 int col[N];

 int n;

 void dfs(int root,int pre)

 {

     dp[root][col[root]]=;

     for (int i=;i<G[root].size();i++)

     {

         int x=G[root][i];

         if (x==pre) continue;

         dfs(x,root);

         dp[root][]=(dp[root][]*dp[x][]%inf+dp[root][]*dp[x][]+dp[root][]*dp[x][])%inf;

         dp[root][]=(dp[root][]*dp[x][]%inf+dp[root][]*dp[x][]%inf)%inf;

         }

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=;i<n;i++)

     {

         int x;

        scanf("%d",&x);

         G[i].push_back(x);

         G[x].push_back(i);

      }

      for (int i=;i<n;i++)

      scanf("%d",&col[i]);

      dfs(,-);

      printf("%d\n",dp[][]);

      return ;

 }

后记：

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

秒客网

Codeforces Round #263 (Div. 2)

相关文章