本文共 4956 字，大约阅读时间需要 16 分钟。
2021年初寒假训练第41场
A. 复制-粘贴
Description
小y是一个聪明的程序员，但是他懒到了极致，在输入程序时甚至不愿意多打一行代码。有一次，小y发现他的一个程序需要输入n行一模一样的代码，怎么办呢？他首先输入了第1行，然后通过1次“复制-粘贴”命令得到了第2行，再通过1次“复制-粘贴”命令得到了第3-4行，…直到完成这n行代码的输入。小y懒得得意洋洋，正好遇到初学编程的小x，他就想考考小x，顺便为难为难他以炫耀自己的聪明才智和编程水平。于是把“复制-粘贴”的伎俩告诉小x，并让小x编程计算最少通过几次“复制-粘贴”命令可以得到正好n行的代码？
Input
一行一个正整数n,n在long int范围内。Output
一行一个正整数，表示最少的“复制-粘贴”次数。Samples
Input Copy 4 Output 2 要注意： 可以复制任意一段 贪心就好了，首先写1行，复制粘贴后得到2行，复制2行粘贴后得到四行，可以发现满足2的次方 直到总数 > n即可 Main_Code()ll n;int main(){ n = read; ll sum = 1; int ans = 0; while(sum < n){ sum *= 2L; ans ++; } cout< < B. 足球联赛
Description
一个足球联赛由n只球队构成。在一个赛季中，每只球队都要与其它球队各比赛两场。一场比赛在主场，一场在客场。赢一场得3分，输一场不得分，平局两支队伍各得1分。现在，给你一个n∗n的矩阵表示比赛情况。第i行第j列的字母表示在第i只队伍主场的比赛情况，W表示主队赢，L表示主队输，D表示平局。需要你求出得分最高的队伍的编号，如果有分数相同的，在一行中按字典序输出队伍编号。Input
第一行一个整数n，1<n≤50。接下来n行每行n个字符，表示输赢情况。
第i行第i列为 - ,因为一只队伍不可能与自己比赛。
Output
得分最高的队伍编号。如有多个在一行中输出，用一个空格分开。Samples
Input Copy3 -WW W-W WW-
Output
1 2 3 Input Copy5 -DWWD L-WLL DD-WD DDL-L DDLL-
Output
1硬生生的模拟就好了（鄙人代码又臭又长）
在处理最大值的时候，可以先遍历得到最大值，然后在遍历一遍将等于最大值的元素从小到大输出 Main_Code()int n;char a[59][59];int score[59];struct node{ int id; int sc;}b[59];bool cmp(node a,node b){ if(a.sc != b.sc) return a.sc > b.sc; else return a.id < b.id;}int main(){ n = read; for(int i=1;i<=n;i++) cin >> a[i] + 1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) { if(i == j) continue; if(a[i][j] == 'D') score[i] += 1,score[j] += 1; else if(a[i][j] == 'W') score[i] += 3; else score[j] += 3; } } for(int i=1;i<=n;i++){ b[i].sc = score[i]; b[i].id = i; } sort(b+1,b+1+n,cmp); int mx = b[1].sc; for(int i=1;i<=n;i++){ if(b[i].sc == mx) printf("%d ",b[i].id); } return 0;} C. 捕食关系
Description
在海洋中，有食肉类的鱼和食草类的鱼，某种食肉类的鱼捕食食草类的鱼当且仅当自己的体重大于对方。 现在给出两类鱼各自的体重，求有多少对捕食关系。Input
每组测试数据有三行。第一行有两个整数m,n(1≤m,n≤20000)，分别代表食肉类的鱼的种类数和食草类的鱼的种类数。
第二行m个数， 第三行n个数，代表各自的体重。 Output 一个整数，表示有多少对捕食关系。Samples
Input Copy 5 3 8 1 7 3 1 3 6 1 Output 7一个比较朴素的方法就是暴力，单数数据范围不允许，这样就可以直接二分即可
用lower_bound出了点小问题，用upper_bound过了 具体用法来自参考博客： 下面来自引用：从小到大排序后 upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标 Main_Code()ll a[20007],ans,b[20007];int n,m;int main(){ n =read,m=read; for(int i=1;i<=n;i++) a[i] = read; for(itn j=1;j<=m;j++) b[j] = read; sort(a+1,a+1+n); sort(b+1,b+1+m); for(int i=1;i<=m;i++){ ll x = upper_bound(a+1,a+1+n,b[i]) - a - 1; ans += (n - x); } cout< < D. 幻方
Description
大家都知道n阶奇数幻方吧？如下为一个5阶幻方：
现在，输入奇数n，n<1000000，输出该奇数幻方最右下角的元素值。
Input
一行一个数n。Output
一行一个数，表示该奇数幻方右下角的值。Samples
Input Copy 5 Output 9结果可能比较大，爆掉long long
这个是个结论题，记得初一的时候数学老师讲过幻方的一些性质，这个题的答案是(n + 1) * (n - 2) / 2 Main_Code()ll n = read; ll t1 = (n-2); ll t2 = n + 1; t2 /= 2; cout<
E. 求和
Description
小马克今年成为小学生。不久后她将进行她的第一次考试，其中包括数学考试。她非常认真地复习，她认为自己已经准备好了。她的哥哥通过给她提出问题并解决的方式帮助她。他的问题是给定一连串整数：依次由1个1，2个2，3个 3 等组成，即1223334444……。现在他给马克两个整数A和B；他的任务是求出由第A个到第B个数的。如果A是1，B是3，答案为1+2+2=5。
给一个问题，然后计算它们的和，马克的哥哥能够验证答案正确与否。
Input
只有一行，包括正整数A和B，1≤A≤B≤1000 Output 共一行，为和的值。Samples
Input Copy 1 3 Output 5 Input Copy 3 7 Output 15看数据范围可以打表，然后求就完了
很简单的模拟 Main_Code()ll aa[1007];int main(){ int a=read,b=read; ll ans = 0; int cnt = 0; int lim = 1; for(int i=1;i<=1000;i++){ cnt ++; aa[i] = lim; if(cnt == lim){ cnt = 0; lim ++; } } ///for(int i=1;i<=10;i++) cout< < F. 猜歌名
Description
“Guess the song” 是一项在年轻程序员中非常流行的游戏。它是一种集技能、智慧、耐性于一体的游戏。这个游戏给玩游戏的人放音乐，游戏者的目标是尽可能快地猜这首歌的歌名。Mirko可能不是一个很好的程序员，但他是一个世界级的猜歌者。Mirko总是在专辑里的某首歌播放出至少一半歌词的时候猜出歌名。所有歌名的单词是唯一的（没有一个单词会出现一次或更多次）。
写一个程序，给出歌名和专辑名，看看Mirko在这首歌的哪个点上（在多少个单词之后）猜出歌名。
Input
共两行：第一行：包含一个整数N，1≤N≤50，它是一首歌里的单词数目。
接下来的N行每一行包含歌名的一个单词。
第N+2行：包含一个整数M，1≤M≤10000， 它是专辑里的单词数目。
接下来的M行每一行包含专辑里的一个单词 歌名和专辑里的所有单词由1到15个小写英文字母组成。
注：测试数据将会使得Mirko总能从专辑里猜出歌曲名。
Output
共一行，包含一个数，表示Mirko在第几个单词处猜出歌曲名。Samples
Input Copy3 sedam gladnih patuljaka 7 sedam dana sedam noci sedam gladnih godina
Output
6 Input Copy4 moj bicikl mali crveni 11 ja vozim biciklcrvene boje ali je moj moj samo moj
Output
8简单模拟，通过遍历下面的字符串，对上面的字符串进行标记，如果上面的字符串中超过一半被标记过，就可以直接输出当前遍历的字符串的下标
Main_Code()int n,m;int lim;string a[55];string b[10086];int flag[55];bool ck(){ int cnt = 0; for(int i=1;i<=n;i++) if(flag[i]) cnt ++; if(cnt * 2 >= n) return true; return false;}int main(){ int pos = 0; n = read; if(n % 2) lim = n / 2 + 1; else lim = n / 2; for(int i=1;i<=n;i++) cin >> a[i]; m = read; for(int i=1;i<=m;i++) cin >> b[i]; for(int i=1;i<=m;i++){ string temp = b[i]; for(int j=1;j<=n;j++){ if(temp == a[j]){ flag[j] = 1; break; } } if(ck()){ pos = i; break; } } cout< < 转载地址：http://lmoo.baihongyu.com/