首页 > 代码库 > Codeforces Round #263 (Div. 2)
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 0x3f3f3f11 #define N 1234512 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 0x3f3f3f11 #define N 12345612 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 0x3f3f3f11 #define N 32345612 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 100000000710 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\n",dp[0][1]);45 return 0;46 }
后记：
树形DP比较抽象。。。多做题才能提高
Codeforces Round #263 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。