汉中北京网站建设,教材资源网站建设,如何制作微信小程序商城,wordpress免费服务器A - 一方通行和最大公约数I CodeForces - 664A 作为学园都市最强的lv5#xff0c;一方通行必须解决一道数学题才能接触last order身上植入的病毒#xff0c;请你帮他解决这个问题。给出两个整数a,b 求出[a,b]区间中所有整数的最大公约数。输入输入包括一行#xff0c;一… A - 一方通行和最大公约数I CodeForces - 664A 作为学园都市最强的lv5一方通行必须解决一道数学题才能接触last order身上植入的病毒请你帮他解决这个问题。给出两个整数a,b 求出[a,b]区间中所有整数的最大公约数。输入输入包括一行一行中有两个数字a,b1《a《b《10^100)输出输出一个整数代表问题中所求的最大公约数样例Input1 2
Output1
Input61803398874989484820458683436563811772030917980576 61803398874989484820458683436563811772030917980576
Output61803398874989484820458683436563811772030917980576 相邻两数的最大公约数必为1所以若输入两数相等直接输出不相等输出1。#include cstdio
#include iostream
#include string
using namespace std;int main()
{string s1,s2;cin s1 s2;if (s1s2) cout s1;else cout 1;return 0;
}B - 大霸星祭 CodeForces - 934A 学园都市一年一度的大霸星祭开始了现在我们把视线转移到赛场现在正在进行的是抢灯笼比赛的现场有来自常盘台中学的御坂美琴选手对阵……啊不好意思比赛已经开始了抢灯笼比赛的规则是这样的对阵双方分别拥有N,M个灯笼每个灯笼都有一个亮度值其中一个人要把其中一个灯笼藏起来而他的对手则要从自己的灯笼和对手的灯笼中个选择一个得分是这两个灯笼亮度之积。我们回到比赛现场现在御坂美琴选手是藏灯笼的一方她能否拿下决胜局赢得比赛呢因为一些不可告人的目的御坂美琴必须赢得这场比赛于是她向你求助请你告诉她如何藏灯笼才能让对手获得分数最小对阵双方都会选择对自己最有利的灯笼。Input输入第一行有两个整数n,m 代表御坂美琴和对手两个人拥有的灯笼2《n,m《50接下来两行第一行n个数是御坂美琴的灯笼的亮度值第二行m个数是对手的灯笼亮度值 灯笼的亮度值的绝对值不会超过10^9Output输出对手在御坂美琴选择藏起来她选择的灯笼后能获得的最大值。ExampleInput2 2
20 18
2 14
Output252
Input5 3
-1 0 1 2 3
-1 0 1
Output2
Note第一个例子里御坂选手藏起来 20 对手会从她那里选择18 然后从自己这边选择14的二个例子中御坂选手藏起来3然后 对手会选择 御坂选手的2和自己的1 题意从自己地方去掉一个数对方从两堆数中各选一个数相乘求乘积最大。注意有负数可以先去掉最大最小的都试一下然后从计算如何能使对方获得的最大乘积最小。#include cstdio
#include iostream
#include algorithm
typedef __int64 ll;
using namespace std;
int n,m;
ll a[55],b[55];
ll s1,s2,ans0;int main()
{cin n m;for (int i0;in;i)cin a[i];for (int i0;im;i)cin b[i];sort(a,an);//a排序sort(b,bm);//b排序s1max(max(a[1]*b[0],a[n-1]*b[m-1]),max(a[1]*b[m-1],a[n-1]*b[0]));//去掉最小值s2max(max(a[0]*b[0],a[n-2]*b[m-1]),max(a[0]*b[m-1],a[n-2]*b[0]));//去掉最大值ansmin(s1,s2);cout ans;return 0;
} C - 初春的烦恼 CodeForces - 909A 初春接到了风纪委员的工作指令要求把一些能力者的名字缩写表示出来。一个人的名字缩写由姓氏的前缀名字的前缀组成这两个部分都不能为空。这样的话就让一个人会有多个缩写很不方便。初春需要把每个人的名字缩写中字典序最小的找出来。但是她想和朋友们一起去玩请你帮帮她吧。一个字符串的前缀是指从字符串的第一个位置开始的子串比如“abcde”的前缀就有“ab,abc” 但是“bcc”不是前缀。如果字符串a比字符串b的字典序小有两种情况要么a是b的前缀要么在a和b第一个不同的地方a串的字符要比b串的字符在字母表的顺序靠前。Input输入一个人的名字由两个字符串组成中间用一个空格分隔开。姓氏名字的长度大于1小于等于10仅由小写英文字母组成Output输出字典序最小的缩写ExampleInputharry potter
Outputhap
Inputtom riddle
Outputtomr用substr可以比较轻松解决。#include cstdio
#include iostream
#include string
using namespace std;int main()
{string s1,s2,s3,s4,s,m ;cin s1 s2;for (int i1;is1.length();i){s3s1.substr(0,i); //姓的前缀for (int j1;js2.length();j){s4s2.substr(0,j); //名的前缀ss3s4; //姓名的前缀相连if (sm||m ) ms;}}cout m;return 0;
} D - 黑子的惩罚 CodeForces - 821A 黑子又晚归了这次舍监并没有拧断她的脖子而是要求她整理厨房。厨房可以表示成N行N列的方形区域每个格子中都有一个整数舍监要求可怜的黑子按照如下规则整理厨房对于任何一个格子中数字不等于1的格子a[x][y],都能找到两个位置s,t 使得a[x][y] a[s][y]a[x][t]。黑子想尽快投入姐姐大人逃的怀抱于是想先判断现在的厨房是否已经满足上述条件。请你帮帮她吧~Input第一行是一个整数n (1n50) 接下来的n行n列代表每个格子中的数字。Output如果厨房是整理好的输出“YES”否则输出“NO”ExampleInput3
1 1 2
2 3 1
6 4 1
OutputYes
Input3
1 5 2
1 1 1
1 2 3
OutputNo
Note在第二个例子中5不能被同一行和同一列的数字来表示 暴力每个位置都检测一遍就行。#include cstdio
#include iostream
using namespace std;
int a[55][55],n,flag1,flag11,i,j,s,t;int main()
{cin n;for (i0;in;i)for (j0;jn;j)scanf(%d,a[i][j]);for (i0;in;i){for (j0;jn;j){if (a[i][j]!1){flag0;for (s0;sn;s){for (t0;tn;t)if (a[i][j]a[s][j]a[i][t]){flag1; break; }}}if (!flag) {flag10; break;}}if (flag10) break;}if (flag1) cout Yes;else cout No;return 0;
} E - 御坂美琴的自制饼干 CodeForces - 799A “御坂学姐突然要来我家烤饼干一定是有男朋友了这次一定要问出来”泪子这样想着一边准备烤饼干的炉子。佐天泪子家里有两个炉子烤k个饼干需要t秒她们要至少烤制n块饼干。第一个炉子已经预热好了但是第二个炉子没有。第二个炉子预热需要d秒。k个饼干在t秒同时烤好第二个炉子在预热的时候只能用第一个炉子第二个炉子预热结束之后两个炉子可以同时用。因为炉子的预热很是麻烦请你帮帮她判断应不应该用第二个炉子泪子会选择最快的一种方案。Input四个整数n,t,k,d 1《n,t,k,d《1000Output如果预热第二个炉子会加快这个过程输出“YES”否则输出“NO”ExampleInput8 6 4 5
OutputYES
Input8 6 4 6
OutputNO
Input10 3 11 4
OutputNO
Input4 2 1 4
OutputYES
Note在第一个例子中一个炉子在12分钟能烤8块饼干。5分钟后第二个炉子可以使用6秒后第一个炉子烤出来4块饼干11分钟后第二个炉子将剩下的饼干烤完所以预热第二个炉子更快 第二个例子中无论使用第二个炉子与否都不会让进程加快 第三个例子只用一个炉子3分钟可以烤11个饼干已经达到要求但是要使用第二个炉子反而会让时间变长所以不需要第二个炉子 题意烤饼干一个炉子可以直接用另一个需要预热炉子t秒k块饼干。问要不要用第二个炉子。可以直接判断一下不用第二个炉子和只用第二个炉子烤k块饼干的时间然后看需不需要第二个炉子。#include cstdio
#include iostream
#include algorithm
using namespace std;
int n,t,k,d,s1,s2;int main()
{cinntkd;s1((n-1)/k1)*t; //不用第二个炉子s2max(dt,(n-1)/k*t); //用第二个炉子烤k块饼干if (s1s2) printf(NO);else printf(YES);return 0;
} F - [item]的特殊任务 CodeForces - 893C 听说了吗最新的都市传说“ 学园都市有很多都市传说有些是真的但有些是假的。都市传说的传播方式主要通过人们口口相传。现在你知道有N个人愿意传播都市传说只要你支付客观的价钱。在你支付一定金钱之后这位神秘人就会向他的朋友传播他的朋友也向朋友的朋友传播不要钱……。芙兰达按照麦野的指令向这N个人传播一个都市传说是真是假呢~请你告诉她能完成任务的最少花费。Input第一行有两个整数n,m代表n个人m对朋友。1n10^5,0m10^5接下来的一行有n个数代表第i个人愿意传播都市传说所需要的钱数(0i10^9)接下来的m行每行有两个整数,ab代表a,b是朋友(1a,bn,a≠b)Output输出最小的花费ExampleInput5 2
2 5 3 4 8
1 4
4 5
Output10
Input10 0
1 2 3 4 5 6 7 8 9 10
Output55
Input10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
Output15 题意给n个人传话给每个人传话都要一定费用一部分人是朋友给其中一个人传话所有人都会知道这件事。问最小花费。存成一个图然后用bfs搜索一下就行记住是无向图一开始因为这个wa了好几次。好像还可以用并查集不会用可以思考一下。#include cstdio
#include iostream
#include cstring
#include vector
#include queue
typedef long long ll;
using namespace std;
ll n,m,x,y,mini-1,ans0;
ll a[100005][2];
vectorll v[100005];void bfs(int i)
{queueint q;q.push(i);while(!q.empty()){int nowq.front();q.pop();if (a[now][0]mini) minia[now][0];a[now][1]1;for (int j0;jv[now].size();j)if (!a[v[now][j]][1]) q.push(v[now][j]);}
}int main()
{memset(a,0,sizeof(a));cin n m;for (int i1;in;i)scanf(%lld,a[i][0]);for (int i1;im;i){scanf(%lld%lld,x,y);v[x].push_back(y);v[y].push_back(x); //无向图记得要连回来 }for (int i1;in;i){if (a[i][1]) continue;minia[i][0];bfs(i);ansmini;}cout ans;return 0;
}并查集做法递归比bfs(dfs)更快#include cstdio
#include iostream
#define MAX_N 100005
typedef long long ll;
using namespace std;
int co[MAX_N],pre[MAX_N];
int n,m,a,b;
ll ans0; //注意ans要用ll否则会waint find(int x) //找x的根节点
{if (pre[x]x)return x; //前一项就是自己-找到根节点else return pre[x]find(pre[x]); //往前找一项
}void inline combine(int p,int q)
{int xfind(p),yfind(q); //x为p的根节点y为q的根节点if (xy) return; //在一棵树上不做任何操作if (co[x]co[y]) //x树的花费大于y树的花费pre[x]y; //将x树的根节点加入为y树的根节点的子节点即将xy合并为一棵树else pre[y]x; //同理
}int main()
{cin n m;for (int i1;in;i){pre[i]i; //一开始所有的树根节点都是自己scanf(%d,co[i]);}for (int i1;im;i){scanf(%d%d,a,b);combine(a,b);}for (int i1;in;i)if (pre[i]i) ansco[i]; //ans加根节点为自身的花费cout ans;return 0;
}G - 上条当麻的暑假作业 CodeForces - 902B “我的暑假作业可怎么办啊……真不幸”上条当麻的暑假作业还有很多。但他还要忙着拯救世界喂食index请你帮他做一道吧, 小萌老师可不好惹。题目给出一颗有根树请你输出将这棵树上每个节点v染成对应的颜色Cv所需要的最少的操作。这棵树的树根是节点1标号从1到n染色操作是这样的选择一个节点v和颜色x一次染色操作会把节点v所在的子树的所有节点都染成x。树的定义https://baike.baidu.com/item/%E6%A0%91/2699484?fraladdinfromid12062173fromtitle%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%A0%91Input第一行是一个整数n代表树的节点个数2n10^4)第二行有n-1个整数p2,p3…pn(1《pi《i)代表i节点和pi有一条边第三行有n个整数c1,c2,c3,…cn 代表每个节点需要被染成的颜色保证数据是一个合法的树Output输出最小的步骤ExampleInput6
1 2 2 1 5
2 1 1 1 1 1
Output3
Input7
1 1 2 3 1 4
3 3 1 1 1 2 3
Output5
Note这是第一个例子的图第一步我们把节点1的子树染色成颜色2(数字代表颜色):下一步我们将节点5的子树变成颜色1第三步染色节点2:题意一开始没看懂这个树是怎么输入的结束后仔细看发现是从1开始然后第二行是后面每个节点的父节点第三行是最后要涂成的颜色。这个题看了大神的做法其实有一个比较方便的方法就是遍历颜色如果某节点颜色和父节点一样说明只需操作父节点即可而如果颜色不一样说明这个节点也需要操作则操作数1。也可以用dfs搜索麻烦又耗时。以下为第一种方法的代码。#include cstdio
#include iostream
#define MAX_N 10005
using namespace std;
int a[MAX_N],b[MAX_N];
int n,cnt0;int main()
{ cin n; for(int i2;in;i) scanf(%d,a[i]);for(int i1;in;i) scanf(%d,b[i]); for(int i1;in;i) if(b[i]!b[a[i]]) cnt; cout cnt endl; return 0;
} I - 御坂美琴的噩梦 HDU - 5914 “只要我摧毁了这个工厂实验就不会进行了吧……”学园都市排名第三的Lv5【超电磁炮】御坂美琴站在一座秘密工厂的房顶上准备潜入。“我首先要破解这里的安保系统可恶……这是什么问题嘛”工厂的安保系统要求接入者解决这个问题有一个数列1,2,3,4,5,…,n现在要求从这个数列中删除最小个数的数字使得剩下的任何三个数都不能形成三角形。 请你帮助御坂美琴结束她的噩梦Input第一行有一个整数T代表T组测试样例 接下来T行,每行有一个整数(1《n《20)Output输出“Case #x: y“代表第x个测试样例的结果是y占一行Sample Input3
4
5
6Sample OutputCase #1: 1
Case #2: 1
Case #3: 2题意题意很明显满足这个条件的数列为1,2,3,5,8,13,21。由于数据范围较小可以直接打表。#include cstdio
#include iostream
using namespace std;
int t,n,cnt0;
int a[25]{0,0,0,0,1,1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14};int main()
{cin t;while (t--){cin n;printf(Case #%d: %d\n,cnt,a[n]);}return 0;
} K - 一方通行和最大公约数II CodeForces - 798C 一方通行学院最强的Lv5在被“幻想杀手“上条当麻制裁友情破颜拳之后变成了萝莉控……“来和我玩游戏吧御坂御坂用期待的口气说道““好吧就陪你玩一会”“last order想让一个数组的最大公约数超过1她可以进行一个操作选定一个 i(0in)将a[i],a[i1]替换成a[i]-a[i1],a[i]a[i1]顺序不变请问她最少能用多少次操作就能达成目的或者告诉她不可能达到。Input第一行是一个整数n代表有n个数2n100 000)下面一行有n个数代表数字ai1ai10^9)Output如果可以让数组的最大公约数超过1输出“YES”下一行输出最小操作次数。 如果不能输出“NO”ExampleInput2
1 1
OutputYES
1
Input3
6 2 4
OutputYES
0
Input2
1 3
OutputYES
1 题意让一个数列的最大公约数大于1可以让这个数列都变成偶数。这里有一个操作a[i],a[i1]替换成a[i]-a[i1],a[i]a[i1]。即为两偶不用换两奇换一次一奇一偶换两次。 注意换完之后最后一个数可能仍为奇数需要额外判断。如果一开始最大公约数就大于1直接输出0。#include cstdio
#include iostream
using namespace std;
int n,a[1000005],sum0,t;int gcd(int a,int b) //求最大公约数
{int t;while(b){tb;ba%b;at;}return a;
}int main()
{cin n;for (int i0;in;i)scanf(%d,a[i]);ta[0];for (int i1;in;i){tgcd(t,a[i]);}if (t1) {cout YES endl 0; return 0;} // 一开始最大公约数大于1直接输出0for (int i0;in-1;i){if (a[i]%2){if (a[i1]%2) sum;else sum2;a[i]a[i1]2; // 将两个数置为偶数只要置为偶数就行}}if (a[n-1]%2) sum2; // 最后仍为奇数的情况cout YES endl sum;return 0;
} 转载于:https://www.cnblogs.com/Radium1209/p/10415388.html
