首页 > 代码库 > Codeforces Round #263 (Div. 1) 题解
Codeforces Round #263 (Div. 1) 题解
A：Appleman and Toastman
题意：两个人玩游戏 初始第一个人给第二个人一个数组 第二个人把数组中每个数相加的和加到他的总得分里面，然后把这个数组还给第一个人，第一个人进行操作：若数组中只剩下一个数，就把这个数组扔了，否则把这个数组拆成两个数组扔回给第二个人，求第二个人的最大得分。
题解：游戏结束即为数组中N个数全被拆成了单独的一个数，而且我们可以知道若一个数在第一个人操作第K次时候变成只有一个数的数组，那么这个数在第二个人那算了K+1次，于是不难想到贪心算法，即让越大的数算的次数越多，于是从小到大排序后，第I个数在第I次变成单独的数组，于是第I个数被算了I+1次，注意最后一次是把第N-1和N个数都变成了单独的，于是最后两个数都是被算了N次，问题得到解决。
1 #include <cstdio> 2 3 #include <cmath> 4 5 #include <iostream> 6 7 #include <cstring> 8 9 #include <algorithm>10 11 12 13 using namespace std;14 15 long long a[500000],ans,x;16 17 int n;18 19 int main()20 21 {22 23 scanf("%d",&n);24 25 if (n==1)26 27 {28 29 scanf("%I64d",&x);30 31 printf("%I64d",x);32 33 return 0;34 35 }36 37 for (int i=1;i<=n;++i) scanf("%I64d",&a[i]);38 39 sort(a+1,a+n+1);40 41 for (int i=1;i<=n;++i) ans+=(i+1)*a[i];42 43 ans-=a[n];44 45 printf("%I64d",ans);46 47 return 0;48 49 }
B：Appleman and Tree
题意：给出一棵树，每个节点有黑色或白色，现在要求删掉一些边后形成的联通块每个块内都恰好有一个黑点，求方案数。
题解：树形dp
dp[i][0]表示节点i所在的子树联通块内有0个黑点时的子树内划分方案数
dp[i][1]表示节点i所在的子树联通块内有1个黑点时的子树内划分方案数
转移：对于i的一个孩子j
考虑：dp[i][0]
若j所在子树联通块也没有黑点，则需要把他和i连起来，要不然永远也不会有黑点。
若j所在子树联通块内有黑点，则根据状态定义把i和j之间的边删除掉。
得到：dp[i][0]=dp[i][0]*dp[j][0]+dp[i][0]*dp[j][0]
考虑：dp[i][1]
若j所在子树联通块内没有黑点，则需要把他和i连起来，要不然永远也不会有黑点。
若j所在子树联通块内有黑点：
①若i所在联通块有黑点，则把i和j断开
②若i所在联通块没有黑点，则把i和j连上
得到：dp[i][1]=dp[i][1]*dp[j][0]+dp[i][1]*dp[j][1]+dp[i][0]*dp[j][1] 至此问题得到解决。
1 #include <cstdio> 2 3 #include <iostream> 4 5 #include <cmath> 6 7 #include <cstring> 8 9 #include <algorithm>10 11 const int mod=1e9+7;12 13 using namespace std;14 15 int n,a[100005],x;16 17 long long dp[100005][5];18 19 int main()20 21 {22 23 memset(dp,0,sizeof(dp));24 25 scanf("%d",&n);26 27 for (int i=1;i<n;++i) scanf("%d",&a[i]);28 29 for (int i=0;i<n;++i)30 31 {32 33 scanf("%d",&x);34 35 dp[i][x]=1;36 37 }38 39 for (int i=n-1;i>=1;--i)40 41 {42 43 dp[a[i]][1]=(dp[a[i]][1]*(dp[i][0]+dp[i][1])+dp[a[i]][0]*dp[i][1])%mod;44 45 dp[a[i]][0]=(dp[a[i]][0]*(dp[i][0]+dp[i][1]))%mod;46 47 }48 49 printf("%I64d\n",dp[0][1]);50 51 return 0;52 53 }
C：Appleman and a Sheet of Paper
题解：一个折纸的过程，有两种操作，第一种是把前X单位的纸折到后半部分的上面，第二种为询问长度L到R区间实际上纸的长度为多少，即那一段纸的厚度为多少。
题意：实际上直接模拟这个过程即可。记录前缀和sum[i]表示到i为止一共有几段纸，然后就是每次模拟这个过程更新sum数组。
对于折超过一半的处理可以等效成将令一半叠上来，记录一个是否翻转过的标记即可，因为随着折叠纸的长度不断变小，复杂度是可以接受的。
1 #include <cstdio> 2 3 #include <cmath> 4 5 #include <iostream> 6 7 #include <cstring> 8 9 #include <algorithm>10 11 12 13 using namespace std;14 15 int n,m,dq,rev,last,sum[200000],z,l,r;16 17 int main()18 19 {20 21 scanf("%d%d",&n,&m);22 23 dq=n;rev=0;last=0;24 25 for (int i=1;i<=n;++i) sum[i]=i;26 27 for (int t=1;t<=m;++t)28 29 {30 31 scanf("%d",&z);32 33 if (z==1)34 35 {36 37 scanf("%d",&l);38 39 if (l>dq-l)40 41 {42 43 l=dq-l;44 45 rev^=1;46 47 }48 49 if (rev) 50 51 {52 53 for (int i=dq-l;i<dq;++i) sum[last+2*(dq-l)-i]+=(n-sum[last+i]);54 55 }56 57 else 58 59 {60 61 last+=l;62 63 for (int i=0;i<l;++i) sum[last+i]-=sum[last-i];64 65 }66 67 dq-=l;68 69 }70 71 else72 73 {74 75 scanf("%d%d",&l,&r);76 77 if (rev)78 79 {80 81 int temp=dq-r;82 83 r=dq-l;84 85 l=temp;86 87 }88 89 printf("%d\n",sum[last+r]-sum[last+l]);90 91 }92 93 //for (int i=1;i<=n;++i) cout<<sum[i]<<endl;94 95 }96 97 return 0;98 99 }
Codeforces Round #263 (Div. 1) 题解