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;
}