# CodeCraft-20 (Div. 2)
CodeCraft-20 (Div. 2)
A. Grade Allocation
- 思路 : 无脑水题
- 代码
#include<iostream>
#include<algorithm>
#include<vector>
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 <bits/stdc++.h>
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<bits/stdc++.h>
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<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<string>
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;
}
最新文章
- HP网络打印机--如何添加打印机
- C#编程利器之三:接口(Interface)【转】
- LSMW应用
- php变量那些事:php引擎对变量声明、存储简要分析(ZVAL)
- Unity3D TestTool Part _1
- python中跟字符串相关的一些操作
- NET MVC过滤器
- 利用JavaScript实现动态显示表格且对应改变按键的value值
- 对比 Git 与 SVN，这篇讲的很易懂
- Neo4j安装&入门&一些优缺点
- 用github搭建网站
- property属性[Python]
- (转）浅谈AIX下IPFilter防火墙
- [翻译] RBBAnimation，让你使用关键帧动画更便利
- python的接口
- 防止开放重定向，恶意篡改returnUrl
- Linux系统中的一些重要的目录
- Service stopSelf(int statId)和onStartcommand(Intent intent,int flags,int startId)
- [Android] 通过Menu实现图片怀旧、浮雕、模糊、光照和素描效果
- groupadd