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<<ans<<endl; return 0; }
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 Copy
3 -WW W-W WW-
Output
1 2 3
Input Copy
5 -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<<ans<<endl; return 0; }
