1、C题《小沙の不懂》
题目描述
小沙作为著名的数学差生，今天又学不会数学了，所以想请你帮帮他。
小沙有两个数字 , ，同时他还有个下标从 开始数字为 到 的长度为 的排列 ，在将这两个数字给你之前，他会对这两个数的每一位数进行一次 操作。
你能帮小沙分辨出这两个数在进行 之前谁大谁小吗？
由于你不知道小沙手中的排列，所以你需要分辨出所有可能的情况下原来的数字 和 的大小关系是否相同。
注：小沙原来的数字可能存在前导零。
输入描述
输入两个整数 , ，。
输出描述
如果在每一种情况中 ，则输出 “>”。
如果在每一种情况中 ，则输出 “<”。
如果在每一种情况中 ，则输出 “=”。
否则 ，则输出 “!”。
示例1
输入：
45 54
输出：
！
分析
符号在本题中表示一种映射关系。
分类讨论，, 长度不相等时，一般情况下会有 ，但是要考虑一下前导 的情况，具体就是：
当a.size() > b.size()时，看 的前导部分是否相等，如果不相等，那么 一定大于 ；否则，就看 中是否先出现0，使得 一定小于 的情况出现。注意如果去除前导部分(即 与 长度相等的部分，从前往后扫描，如果出现一位 并且 对应的数字不是 ，那么就应该 ，因为此时已经可以确定是 “!”)。
AC代码
#include <bits/stdc++.h>
using namespace std;
string a, b;
int main(){
cin >> a >> b;
if(a.size() == b.size()){
if(a == b) puts("=");
else puts("!");
}
else{
set<char> s;
int cha = 0;
if(a.size() > b.size()){
cha = a.size() - b.size();
bool flag = true;
for(int i = 0; i < cha; i++){ //判断前缀的数字是否都相等
if(a[0] != a[i]){
flag = false;
break;
}
}
if(!flag) puts(">");
else{
//长串的前导数字相等，最小的情况是前导的数字代表0
for(int i = cha, j = 0; i < a.size(); i++, j++){
if(a[i] != b[j]){
if(b[j] == a[0]){
puts(">");
return 0;
}
break; //注意这里的break很重要，此时已经可以确定是！
}
}
puts("!");
}
}
else if(a.size() < b.size()){
cha = b.size() - a.size();
bool flag = true;
for(int i = 0; i < cha; i++){
if(b[0] != b[i]){
flag = false;
break;
}
}
if(!flag) puts("<");
else{
for(int i = cha, j = 0; i < b.size(); i++, j++){
if(b[i] != a[j]){
if(a[j] == b[0]){
puts("<");
return 0;
}
break; //注意这里的break很重要, 此时已经可以确定是！
}
}
puts("!");
}
}
}
return 0;
}
2、D题《小沙の赌气》
小沙の赌气
题目描述
小沙和小雅在一起打游戏，因为赌气，他们想要比比看谁打通的关卡数更多，在游戏过程中，他们两个人都可以获得一些奇怪的道具来帮助他们通关，假设小沙和小雅都从第一关开始，他们必须一关一关通，只有通过了第 关，第 关才会解锁。每次同时卡关他们各自会获得了一个道具，第 个道具可以使他们通过 之间的每一关，在获得每个道具之后，小沙想询问你目前已有的道具游玩下去，谁会领先，领先多少。
输入描述
第一行输入一个数 ，代表 个发放道具，。
接下来 行，每行输入两个整数 ，代表小沙获得的游戏道具能帮助他通过哪些关卡。
接下来 行，每行输入两个整数 ，代表小雅获得的游戏道具能帮助她通过哪些关卡。
输出描述
对于每一次获得道具后，目前的领先状况。
每次询问共输出两行
第一行输出一行字符串代表答案。
如果小沙通过的更多输出 ”sa_win!" (不包含引号);
如果小雅通过的更多输出 ”ya_win!" (不包含引号);
如果通过的一样多输出 ”win_win!" (不包含引号)。
第二行输出一个整数代表多通过的关卡数。
示例1
输入：
3
1 3
4 7
9 10
1 5
3 8
7 9
输出：
ya_win!
2
ya_win!
1
ya_win!
2
说明
第一次下发道具之后：
小沙的道具可以让他通过 ，，关，小雅的道具可以让她通过 ，，，，关。
小沙通过了前 关，小雅通过了前 关，所以小雅更多，多通过 关。
第二次下发道具之后：
小沙的道具可以让他通过 ，，，，，，关，小雅的道具可以让她通过 ，，，，，，，关。
小沙通过了前7关，小雅通过了前 关，所以小雅更多，多通过 关。
第三次下发道具之后：
小沙的道具可以让他通过，，，，，，，，关，小雅的道具可以让她通过，，，，，，，，关。
由于小沙没有通过第 关，所以后面的关卡没有解锁。
故小沙通过了前 关，小雅通过了前 关，所以小雅更多，多通过 关。
分析
这题用set或者优先队列模拟一下即可，比赛的时候用了线段树，调到结束还没调出来，被这题害死了。。。后来发现是维护的内容根本就是不可行的。
错误原因：我想的是用一个变量flag代表这个区间是否被完全覆盖，然后通过左右儿子相与来更新自己。但是这题数据范围很大，需要离散化，而离散化后的下标是0, 1, 2...都是连续的，所以相当于每个都出现了，所以必定会出现“全覆盖”的假象，我在这里面绕圈绕死了呜呜。赛后改变思路，借鉴线段树加速扫描线的思路，用cnt来表示被完全覆盖次数，用len来表示线段树维护区间实际代表的区间中覆盖了多少个数，然而还是没调出来，暂告一段落吧。。
本题用线段树或者并查集也能做，不过目前自己都没有成功AC。。。
AC代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10;
set<PII> s1, s2;
PII a[N], b[N];
int n;
void calc(set<PII>& s, int l, int r, int& pos){
s.insert({l, r});
auto cur = *s.begin();
while(cur.x <= pos){
pos = max(pos, cur.y + 1);
s.erase(s.begin());
if(s.empty()) return;
cur = *s.begin();
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
for(int i = 1; i <= n; i++) scanf("%d%d", &b[i].x, &b[i].y);
int pos1 = 1, pos2 = 1;
for(int i = 1; i <= n; i++){
calc(s1, a[i].x, a[i].y, pos1);
calc(s2, b[i].x, b[i].y, pos2);
if(pos1 == pos2) puts("win_win!");
else if(pos1 > pos2) puts("sa_win!");
else puts("ya_win!");
printf("%d\n", abs(pos1 - pos2));
}
return 0;
}
3、L题《小沙の抱团 hard》
L题.小沙の抱团 hard
题目描述
小沙在玩一个抱团游戏，最开始有 个人，每次小沙有 条指令可以下达，对于第 条指令可以花费 的代价，要求以 人为单位抱团，每个人只能在一个团里，若一个人不属于某一个恰好 个人的团则将被淘汰，抱团需要所有参与抱团的人全部同意。假设参加游戏的人都足够聪明，都希望自己不被淘汰。如果你是小沙，你最少需要花费多少的代价才能使得剩余的人数最少。
每个指令都可以重复使用。
每次要求拥抱人数不能超过当前人数。例：剩余 人时不能要求 个人拥抱在一起。
输入描述
第一行输入二个整数 ，代表人数以及指令个数，。
随后 行，每行两个整数 ，，分别代表代价以及指令的内容，。
输出描述
输出一个整数代表小沙最少花费的代价。
示例1
输入：
7 3
10 2
5 3
3 4
输出：
18
分析
解决即可
表示减少到 个人，所花费的最小代价。
因此本题的 顺序是 从大到小
转移方程：
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL f[N];
int x[N], b[N];
int n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++) scanf("%d%d", &b[i], &x[i]);
for(int i = 0; i <= n; i++) f[i] = 1e18;
f[n] = 0;
//坑点：这里i要取到1的原因是因为可能题目给能的n就等于1。
//否则如果n > 1,那么最少减到2人。
for(int i = n; i >= 1; i--){
for(int j = 1; j <= m; j++){
if(i < x[j]) continue;
int cnt = i % x[j];
f[i - cnt] = min(f[i - cnt], f[i] + b[j]);
}
}
for(int i = 1; i <= n; i++){
if(f[i] != 1e18){
printf("%lld\n", f[i]);
return 0;
}
}
return 0;
}