AGC046

• A - Takahashikun, The Strider
  • 题意：一个人在原点，每次逆时针转X度，问需要转多少此会回到原点。
  • 题解：暴力！
  • 代码：https://atcoder.jp/contests/agc046/submissions/17367533
• B - Extension
  • 题意：给一个[a,b]矩阵，每次可以水平或者竖直增加一行或者一列，然后选择增加的点中的一个染成黑色，问最终变成[c,d]矩阵的时候，一共有多少种染色方案。
  • 题解：上来的想法就是dp[i][j]从dp[i-1][j] * j和dp[i][j-1] * i递推过来，但是这样递推会有重复，因为dp[i-1][j]和dp[i][j-1]有重复的，那不重复的方式是dp[i][j] = dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)，类似于矩阵差分，最后一个被减项是因为[i,1~(j-1)]和[1~(i-1),j]被计算了两次。
  • 代码：https://atcoder.jp/contests/agc046/submissions/18282184
• C - Shift
  • 题意：给一个0-1 string，和k个操作，每次操作选择i,j && i < j && s[i]==0 && s[j]==1，然后删除s[j]，在i前面插入一个1。
  • 题解：我们首先计算相邻两个0之间有多少个1，存在数组a里面，那么每次操作相当于a[j]--，a[i]++。用sum数组表示a数组的后缀和，然后我们做dp，因为i<j，所以dp要从后向前dp，我们令dp[i][j][k]表示后i个元素，操作了j次，且当前还有k个1移动到了前面。那么最终的结果就是sum(dp[n][1的个数][i])，转移的时候考虑贡献来转移，即dp[i][j][k]可以贡献哪些状态。我们注意到j，k因为最多N个1，且和操作次数无关，同时可贡献的状态，最多只有sum[i+1]个。因为最坏n的大小是150，所以整体的转移复杂度是150 ^ 4。
  • 代码：https://atcoder.jp/contests/agc046/submissions/18368770
  • 总结：计数类dp，nice，need rethinking