源汇区建设局网站,网页设计培训机构学什么好,网站建设服务商的网站建设流程,做楼房信息网站的作用今天下午也是小小的做了一下#xff0c;OI#xff0c;也是感觉手感火热啊#xff0c;之前无意间看到的那个哥德巴赫定理今天就用到了#xff0c;我以为根本用不到的#xff0c;当时也只是感兴趣看了一眼#xff0c;还是比较激动啊
话不多说#xff0c;直接开始看题
Wo…今天下午也是小小的做了一下OI也是感觉手感火热啊之前无意间看到的那个哥德巴赫定理今天就用到了我以为根本用不到的当时也只是感兴趣看了一眼还是比较激动啊
话不多说直接开始看题
World Fragments I 题意就是说给你两个二进制的数然后有一个变化规则就是从x中选择一位数其实也就是选择1然后x可以选择减去或者加上这个数然后问你最少多少次可以让x变成y如果不可能变成则输出-1
思路这题是个签到题但是我当时以为不能存在-1导致错了两发
首先什么时候是-1呢就是x为0但是y不为0因此没法从x中选出1导致没法产生变化因此输出-1
但是对于别的情况直接输出x和y的差值的绝对值即可
#includebits/stdc.h
using namespace std;
#define int long long
string x;
string y;
signed main()
{ cin x y; reverse(x.begin(), x.end()); reverse(y.begin(), y.end()); int sum1 0, sum2 0; for (int i 0; i x.length(); i) { if (x[i] 1) { sum1 (1LL i); } } for (int i 0; i y.length(); i) { if (y[i] 1) { sum2 (1LL i); } } if(sum10sum2!0)cout-1\n;elsecout abs(sum1 - sum2)\n; return 0;
}
Until the Blue Moon Rises 题意就是说给你n个数然后每两个数之间都可以自行一个加一一个减一然后问你最后能否让这n个数都变成素数如果可以输出YES不行就是NO
思路这题其实才是我第一个做出来的因为是英文提面所以我这个英语贵物只能先看题目比较短的进行翻译了思路就是强哥德巴赫定理——任意一个大于2的偶数都可以拆分成两个质数的和
我们因此分三种情况
1.只有一个数我们只需要判断那一个数是否是质数如果是则是yes否则是no
2.有两个数我们需要所有数的和sum是奇数还是偶数如果是偶数那么根据强哥德巴赫定理来说一定可以拆分成功为yes如果是奇数那么一定是一个偶数一个奇数偶数只有2是质数如果sum-2也是质数那么就说明是yes否则是no
3.大于等于三个数如果sum2*n那么就是yes最小的质数就是n个2的情况根据若哥德巴赫定理就可以推出来 任何一个大于7的奇数都能被表示成三个奇质数的和。一个质数可以被多次使用
#includebits/stdc.h
using namespace std;
#define int long long
int n;
int a[200005];
int sum0;
signed main()
{cinn;for(int i1;in;i){cina[i];suma[i];}if(n1){if(a[1]1){coutNO\n;return 0;}for(int i2;isqrt(a[1]);i){if(a[1]%i0){coutNO\n;return 0;}}coutYES\n;}else if(n2){if(sum%20){if(sum2){coutYES\n;return 0 ;}else{coutNO\n;return 0 ;}}else{int qsum-2;if(q1){coutNO\n;return 0;}for(int i2;isqrt(q);i){if(q%i0){coutNO\n;return 0;}}coutYES\n;}}else{if(sum2*n)coutYES\n;elsecoutNO\n;}return 0;
}
Ama no Jaku 题意是说让所有的第i行的最小值大于 第i列的最大值
思路仔细分析一下就会发现我只要让整个矩阵都变成一个数就可以完成这项操作了因此我们再细推会发现如果第一位相同的话那么后面每一个数都相同第一位不同的话后续每一位都不同然后去计算最小改变次数即可
#includebits/stdc.h
using namespace std;
#define int long long
int n;
char s[2005][2005];
int cnth,cntl;
signed main()
{cinn;for(int i1;in;i){for(int j1;jn;j){cins[i][j];}}for(int i2;in;i){if(s[i][1]s[1][1]){for(int j2;jn;j){if(s[i][j]!s[1][j]){cout-1\n;return 0;}}}else{cnth;for(int j2;jn;j){if(s[i][j]s[1][j]){cout-1\n;return 0;}}}}for(int i2;in;i){if(s[1][i]!s[1][1]){cntl;}}coutmin(cnth,n-cnth)min(cntl,n-cntl)\n;return 0;
}Koraidon, Miraidon and DFS Shortest Path 题意就是说用dfs去实现bfs的思路去找到单源最短路径
思路深搜跑一遍看看到了同一个点是否会出现不同的值如果存在不同那就是no否则就是yes
#includebits/stdc.h
using namespace std;
int t;
int n,m;
int d[500005];
int u,v;
bool flag,vis[500005];
vectorint e[500005];
void dfs(int v)
{if(!flag) return;vis[v]true;for (auto u:e[v]){if (vis[u])continue;if (!d[u])d[u]d[v]1;else if(d[u]!d[v]1)flagfalse;dfs(u); }vis[v]false;
}
void solve()
{flagtrue;for (int i1;in;i){e[i].clear();vis[i]false;d[i]0;}cinnm;for(int i1;im;i){cinuv;e[u].push_back(v);}dfs(1);cout(flag?Yes:No)endl;
}
signed main()
{int t;cin t;while(t--) solve();return 0;
}
