前言：比赛整体体验感还行，13：30的比赛，然后周末的午觉一下睡到两点多，爬下床，打开电脑先看了一波榜单，可能是比赛刚开始，部分题目AC真的少，几乎是个位数的，我惊了，本想签个到跑路的，但是最后接着打下去了，不过这个比赛题目有些英文，有些中文，没搞懂这啥操作。
A.Sumo and Keyboard-Cat
题目：
Sumo家的猫非常喜欢滚键盘，每次Sumo开着电脑离开一小会儿，回来的时候都能在屏幕上看到一串神秘代码。今天，Sumo又得到了这么一串神秘代码。当他盯着屏幕上这串东西沉思的时候，突然发现它只包含大小写英文字母，又想到自己的键盘这几天两个Shift键都坏掉了——也就是说只能通过CAPSLOCK键来切换英文大小写了。于是他很好奇，这次滚键盘的过程中，他家的猫至少摁了几次CAPSLOCK键呢？Sumo记得他刚离开的时候，键盘的大写锁定是开的（也就是说输的是大写字母）。
输入描述:
仅包含一个字符串，表示Sumo家的猫摁出的神秘代码。输入保证字符串仅包含大小写英文字母，且长度不超过105。
输出描述:
仅一个整数，表示这次滚键盘的过程中，Sumo家的猫摁CAPSLOCK键的最少次数。
输入
ZUCCAcmLab
输出
3
输入
MEOWMEOWMEOWGiveMeCatFoodMEOWMEOWMEOW
输出
8
解析：签到题，就两种情况，一开始是大写，做一个标记，然后变小写再换一个标记即可，时间复杂度O（n）。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
char str[maxn];
int main()
{
scanf("%s", str);
int len = strlen(str);
int flag = 1;
int cnt = 0;
for(int i = 0; i < len; i++)
{
if(str[i] >= ‘a‘ && str[i] <= ‘z‘ && flag)
{
cnt ++;
flag = 0;
}
if(str[i] >= ‘A‘ && str[i] <= ‘Z‘ && flag == 0)
{
cnt ++;
flag = 1;
}
}
printf("%d", cnt);
return 0;
}
B.Sumo and His Followers
题目：
Sumo GG is very popular in the laboratory. Many people come to ask Sumo GG for questions.
Now there are n people in line to ask him for advice, as the time for i-th people to ask him questions is ti. In order not to affect everyone‘s lunch, please line up for n people so that the average waiting time of n people is the minimum.
输入描述:
The first line contains T(1≤T≤10) — the number of test cases.
For each test case, the first line contains a single integer n(1≤n≤10 5), the number of people waiting for asking a question.
The next line contains n integers t 1,t 2,...,tn(1≤ti≤1000), the time of ith people required to ask a question.
输出描述:
For each of the test cases, output a single integer, the minimun average waiting time of n people (accurate to two decimal places).
输入
2
1
5
10
56 12 1 99 1000 234 33 55 99 812
输出
0.00
291.90
解析：贪心。题意就是要找最小的平均等待时间，注意一下等待过程是后面每一个人都要算上的，就让问问题时间耗费最少的人先问就行。
时间复杂度O（nlogn + n）.
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int t, n;
int a[maxn];
bool cmp(int b, int c)
{
if(b == c)
return b > c;
else
return b < c;
}
int main()
{
cin >> t;
while(t --)
{
cin >> n;
memset(a, 0, sizeof(0));
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n, cmp);
int cnt = n - 1;
double avgT = 0;
LL sum = 0;
for(int i = 1; i <= n; i++)
{
sum += cnt * a[i];
cnt --;
}
avgT = 1.0 * sum / n * 1.0;
printf("%.2lf\n", avgT);
}
return 0;
}
C.Sumo and Virus
题目：
Sumo生活的小镇有m个居民，小镇的生活和谐而美好。但是，有一天，可怕的事情发生了......
这个故事要从一只蝙蝠讲起。
一个月黑风高的夜晚，Sumo家中闯入了一只迷路的蝙蝠，Sumo在驱赶蝙蝠的过程中一不小心被蝙蝠咬伤了。结果就悲剧了，他感染了一 种传染性很强的病毒。现在发现这种病毒的传染情况如下：
一个病患每天可以传染x个未被感染的人；
潜伏期为7天，期间不发病也不传染别人；
第8天开始发病，并且可以传染；
第14天，被治愈（当天不会传染，且不再具有传染能力）；
治愈之后具有抵抗力，不会被传染。
问：从Sumo感染病毒开始算第一天，第n天过后小镇上有几个传染者（指具有传染能力的人）？
输入描述:
第一行包含一个正整数 T(1≤T≤100)，表示一共有T组数据。
第二行包含三个正整数 x(1≤x≤105)，m(1≤m≤105)，n(1≤n≤10^5)，含义如题目所描述。
输出描述:
输出一个整数代表第n天有几个传染者（指具有传染能力的人）。
输入
3
3 4 7
3 4 12
3 4 16
输出
0
1
3
解析：模拟题。题目感觉一看挺复杂的，不过弄清思路，就挺快的，首先这个病毒会人传人，实际上第八天Sumo才会传染给别人，然后到第14天才会没有传染性，注意一下感染后的人就不会被感染了，开一个数组a[i]来存放当天新出现的潜伏者即可，注释都写代码上了，应该看代码可以更清晰。时间复杂度O（n）。应该也可用dp写。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
LL T, x, m, n;
LL a[maxn]; //第i天新增潜伏者
int main()
{
cin >> T;
while(T --)
{
LL cnt = 0;
memset(a, 0, sizeof(a));
a[1] = 1;
cin >> x >> m >> n;
m--; //减掉Sumo
for(int i = 8; i <= n; i++) //第8天开始才有新的潜伏者
{
cnt += a[i-7]; //加上新的感染者
if(i >= 14)
cnt -= a[i-13]; //减去恢复的人
a[i] = min(m, cnt * x); //新增潜伏者不能大于现有居民人数
m -= a[i]; //减去不会感染的人
}
cout << cnt << endl;
}
return 0;
}
F.Sumo and Luxury Car
题目：
As we all know, Sumo has a lot of luxury cars, Maserati, Porsche, Lincoln, and so on. Countless cars are parked in his garage. He is worried about what kind of car he drives every day. Can you help him?
Sumo has a total of n cars. Every day, he will choose any number of cars from the n cars (the number of cars cannot be 0) to form a team, and then choose one from this team to drive himself. How many options are there?
If the selected team set is different or the car he chooses is different, it is considered to be two different plans.
输入描述:
The first line of the input is a single integer T(1≤T≤10)which is the number of test cases. T test cases follow.
Each test case has a single integer n(1≤n≤10^9), representing the total number of luxury cars in Sumo.
输出描述:
For each test case, print a single line containing an integer modulo 10^9 + 7
输入
2
1
2
输出
1
4
备注:
In the second sample, Sumo has four situations to drive:
Choose cars with numbers 1 and 2, drive the car with number 1,
Choose cars with numbers 1 and 2, drive the car with number 2,
Choose the car with numbers 1, drive the car with number 1,
Choose the car with numbers 2, drive the car with number 2.
So the answer is 4.
解析：数学变化 + 快速幂。其实一开始第一反应就是排列组合比如n = 3，方案数就是C（1，3）* 1 + C(2，3) * 2 + C(3，3) * 3，不过这个明显得O（n^2），绝对T，然后观察一下发现好像有一个规律，就是n = 3的方案数其实是4 * (n = 2的方案数 - n = 1 的方案数)，不过因为数量级太大，要求模，所有n-1的方案数和n-2的方案数会爆掉，中间不好做处理，然后推导一下具体看个大佬的blog，可以得到这个求和实际上就是k * 2 ^(n-1)。然后就是快速幂。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
LL pow(LL x, LL q)
{
LL v = 1;
while(q)
{
if(q & 1)
v = v * x % mod;
x = x * x % mod;
q >>= 1;
}
return v;
}
int main()
{
LL n, t;
cin >> t;
while(t --)
{
cin >> n;
LL temp = 2;
LL cnt = n * pow(temp, n - 1) % mod;
cout << cnt << endl;
}
return 0;
}
L.Sumo and Coins
题目：
There are n coins on Sumo‘s table, each coin has two sides, a(0≤a≤n) of the coins face up, and b(0≤b≤n) of the coins face down. Sumo wants to make these coins have the same side.
Each time he can flip any n-1 of these coins, he can do this operation any number of times(possibly zero).
Please tell him if he can make these coins have the same side.
输入描述:
The first line of the input is a single integer T(1≤T≤10^4), T test cases follow.
Each test case has three integers n(1≤n≤10^4), a, b(a+b=n).
输出描述:
If all the coins can face up or down, output "ALL"(without quotes);
If all the coins can only face up, output "UP"(without quotes);
If all the coins can only face down, output "DOWN"(without quotes);
If all the coins cannot face the same side, output "NULL"(without quotes).
输入
1
2 1 1
输出
ALL
备注:
In the example, Sumo can flip the coin facing up or down so that all the coins are facing the same way after the first operation.
解析：结论题。题意就是有a枚硬币朝上，b枚朝下，每次操作n-1次，问会出现什么情况。自己模拟一下会发现不可能出现所有硬币不在同一面的情况，当硬币总数为偶数时，总可以把所有硬币翻成正面或反面，若硬币总数为奇数且a为奇数，那就只能将所有硬币翻到正面，若硬币总数为奇数且a不为奇数，那就只能将所有硬币翻到反面。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int main()
{
int t, n, a, b;
cin >> t;
while(t --)
{
cin >> n >> a >> b;
if(n % 2 == 0)
cout << "ALL" << endl;
else
{
if(a % 2 != 0)
cout << "UP" << endl;
else
cout << "DOWN" << endl;
}
}
return 0;
}
原文：https://www.cnblogs.com/K2MnO4/p/13060755.html