# CodeCraft-20 (Div. 2)

CodeCraft-20 (Div. 2)

A. Grade Allocation

• 思路 : 无脑水题
• 代码

#include
#include
#include
using namespace std;const int Len = 1e3 + 5;
int ar[Len];int main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//freopen("A.txt","r",stdin);int t;cin >> t;while(t --){int n,m;cin >> n >> m;int sum = 0;for(int i = 1; i <= n; i ++){cin >> ar[i];sum += ar[i];}cout << min(m, sum) <<endl ;}return 0;
}

B. String Modification

• 题意: 对一个 字符传， 选取一个长度k，然后从左到右开始，依次从 第一位置开始的长度为k的连续字符串，进行颠倒，颠倒之后获得一个新的字符串，接着从从这个字符串的第二个位置开始选取接下来的k个字符的长度，进行颠倒，，，，这样一直颠倒到最后，会产生出一个 最终的字符串。问当我们选取的 k 为多少事可以 让 的出来的 “最终的字符串” 按字典序 最小，，如果有多个k能得到最小，那么 输出最小的k就行了

• 思路 ：其实这一题答案给的方法挺暴力的，首先在做这一题的时候，我们要找出来一些 在字符串 翻滚前后的规律， 举个例子大概说一下吧：设有字符串
  e r t y q w,我们假设要翻滚的长度 k 为3 ，那么翻滚完折之后的结果字符串为
  t y q w e r, 可以观察到 在原字符串 中 [ k , 6] 部分的字符串原封不动的到了最终字符串的前边，而[1, k - 1] 的字符串到了最终字符串的后边（ 【1， k - 1】的字符串没有 颠倒），自己在多写几个例子模拟一下，会有规律：设原始字符串长度为n ， 则【k， n】的部分成为最终字符串的前缀（前半部分），而 【1，k - 1】的部分，在 k、n 同奇偶的时候 颠倒到过顺序 作为最终字符串的 后缀（后半部分），如果不满足 k、n同奇偶，则则直接作为 最终的字符串的后半部分，
  剩下的就是 根据规律暴力枚举每一个（枚举的时候 可以通 strig 类来偷懒） k ，去找最优解

• 代码

#include using namespace std;string modified(string& s, int n, int k) {string result_prefix = s.substr(k - 1, n - k + 1);string result_suffix = s.substr(0, k - 1);if (n % 2 == k % 2)reverse(result_suffix.begin(), result_suffix.end());return result_prefix + result_suffix;
}int main () {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);string s, best_s, temp;int t, n, best_k;cin >> t;while (t--) {cin >> n >> s;best_s = modified(s, n, 1);best_k = 1;for (int k = 2; k <= n; ++k) {temp = modified(s, n, k);if (temp < best_s) {best_s = temp;best_k = k;}}cout << best_s << '\n' << best_k << '\n';}return 0;
}

C. Primitive Primes（数学规律）

• 题意 给两个 本原多项式:形如：f（x）= a0 + a1 * x^1 + a2 * x^1 + … + an * x^n , 那么这个连个 本原多项式相乘以有 又产生一个 本原多项式h(x)，在这个多项式中随便找出一个 系数 满足 让该系数不能被所制定的数p 整除。

• 思路： 分别找出在前两个多项式中，第一个不能被 p整除的系数，这这两个系数的位置相加，就是最终的 h(x) 的一个位置
  证明： 我们可以得到：答案一项的表示是为：
  (a0∗bi+j+a1∗bi+j−1+…)+ai∗bj+(ai+1∗bj−1+ai+2∗bj−2+…），
  其中 由于ai，bi分别是第一个不能被整除的，那么我们就可以断定，在 ari、bi系数之前的 系数 a0，a1…ai-1 、 b0，b1 … bj-1, 均是可以被整除的，所以在上柿子中，左右两个括号的内的 都可以被整除， 而只有中间项 ai*bj 是不能被整除的，两可以被整除的数 + 一个不能被整除的数 == 一个不能被整除的数

• 代码

#include
using namespace std;#define ll long long int
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll n,i,m,x,a,p,fir,sec;cin >> n >> m >> p;a=0;for(i=0;i<n;i++){cin >> x;if(x%p && !a){a=1;fir=i;}}a=0;for(i=0;i<m;i++){cin >> x;if(x%p && !a){a=1;sec=i;}}cout << fir+sec << endl;return 0;
}

D. Nash Matrix （dfs/bfs + 分析）

• 题意：给我一个 nxn的表格，让我们在表格上填 U 、D、 L、 R、 X （终点）五个字符来完成这个表格，然后有给了每个表格中位置的终点（有的点是可能是无限循环，没有终点用 -1 -1 来表示），问怎么填写这个字符才可以，符合 上述要求

• 思路 ： 这一题我们可以把 格子坐标分为两大类，第一类是格点坐标是组成无线循环路径的点；而第二列为不是组成无线循环路径中的点（这些点是有确定的终点的）

•   注意重点的是 这两类格点的关系是互相不干扰的，也就是说如果是第二类格点，那么他一定不会出现在 循环路径中，同样如果是在 循环路径中的点 一定不会走到
  

•   非循环的路径中去（因为一旦 走到非循环路径中去的话，那个 这个在循环路径中的格点，就有了“终点”, 而这与题意是不符合的）, 所以我从这里得出的结论就是
  

•   这两类格点我们可以分开去处理，例如：我们可以先用 bfs/dfs 根据“终点”逆向求解 第二类格点中应该填写的符号，然后在单独考虑第一类节点就行了;
  

•   当然也可以把这两类 一起考虑，分开讨论
  

*/

• 代码

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;const int maxn = 1e3 + 5;
int n;
int x[maxn][maxn], y[maxn][maxn];
char maze[maxn][maxn];int connect(int i, int j, int r, int s, char c1, char c2)
{if(x[r][s] == -1){maze[i][j] = c1;if(maze[r][s] == '\0') maze[r][s] = c2;return 1;}return 0;
}void dfs(int i, int j, char c)
{if(maze[i][j] != '\0') return;  //如果不是非空字符，说明这个节点周围的点都已经被搜索过了maze[i][j] = c;//⬇️ 下面的过程都是从逆向推倒 正向路径的过程 (符合逆向推答案的条件是 这个格点与周围的那个格点拥有相同的 “终点”, 这里一定要千万注意啊～～～～～)if(x[i + 1][j] == x[i][j] && y[i + 1][j] == y[i][j]) dfs(i + 1, j, 'U');if(x[i - 1][j] == x[i][j] && y[i - 1][j] == y[i][j]) dfs(i - 1, j, 'D');if(x[i][j + 1] == x[i][j] && y[i][j + 1] == y[i][j]) dfs(i, j + 1, 'L');if(x[i][j - 1] == x[i][j] && y[i][j - 1] == y[i][j]) dfs(i, j - 1, 'R');
}int main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//freopen("A.txt","r",stdin);cin >> n;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)cin >> x[i][j] >> y[i][j];for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++){if(x[i][j] == -1)  //如果在该格点是第一类格点{bool res = (maze[i][j] != '\0');//如果res == 0 判读这个点与周围其它的点是否联通, 尝试让它们联通！！！if(! res) res = connect(i, j, i + 1, j, 'D', 'U');if(! res) res = connect(i, j, i, j + 1, 'R', 'L');if(! res) res = connect(i, j, i - 1, j, 'U', 'D');if(! res) res = connect(i, j, i, j - 1, 'L', 'R');if(! res){cout << "INVALID\n";return 0;}}else if(x[i][j] == i && y[i][j] == j)   //如果是第二类节点并且是第二类节点的“终点”dfs(i, j, 'X');}//当图中有些点没有 被填上符号的时候，就说明给的条件有问题。。。for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++){if(maze[i][j] == '\0')     {cout << "INVALID\n";return 0;}}cout << "VALID\n";for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++)cout << maze[i][j];cout << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！