A - Yet Another String Game
题意
博弈游戏，每次可以把字串一个字母改成不同的，A想让字串变小，B想让字串变大，问最后字串变成啥样。
题解
显然从前往后改，A把字串改成'a',如果本来就是'a'则改成'b',B同理。
#include <bits/stdc++.h>
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
char c[109];
void work() {
scanf("%s", c);
int n = strlen(c);
for(int i = 0; i < n; i++) {
if(i & 1) {
if(c[i] == 'z') c[i] = 'y';
else c[i] = 'z';
} else {
if(c[i] == 'a') c[i] = 'b';
else c[i] = 'a';
}
}
printf("%s\n", c);
}
signed main()
{
int Case = read();
while(Case--) work();
return 0;
}
View Code
B - The Great Hero
题意
类似魔塔的游戏，英雄每次A对面一下对面和英雄一起掉血。
问能不能杀完。
题解
前面一大堆怪怎么杀无所谓，重点是最后一下平A。
显然问题在于英雄和怪同归于尽，怪物最后一刀溢出越多，我们越赚。
就让攻击力最强的怪排在最后就行了。
#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
struct node {
int a, b;
} p[100009];
int n, a, b;
int cmp(node a, node b) {
return a.a < b.a;
}
void work() {
a = read(); b = read(); n = read();
for(int i = 1; i <= n; i++) p[i].a = read();
for(int i = 1; i <= n; i++) p[i].b = read();
sort(p + 1, p + 1 + n, cmp);
for(int i = 1; i < n; i++) {
int t = (p[i].b - 1) / a + 1;
b -= t * p[i].a;
if(b <= 0) {
printf("NO\n");
return ;
}
}
int t = (p[n].b - 1) / a;
b -= t * p[n].a;
if(b <= 0) printf("NO\n");
else printf("YES\n");
}
signed main()
{
int Case = read();
while(Case--) work();
return 0;
}
/*
最后一只打的肯定是伤害最高的
*/
View Code
C - Searching Local Minimum
题意
交互题，有一列数，每次可以询问一个位置的数是多少，只能问100次，要求找出一个点，它小于两边的点的值，左右两边为正无穷。
\(n\le 1 * 10^5\)
题解
假如一段区间左边端点单调减，右端点单调增，则可以证明区间内一定存在谷底，一开始[1,n]肯定是满足题意的，然后二分就行了。
#include <bits/stdc++.h>
#define int long long
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
int n, vis[100009];
int query(int x) {
if(x <= 0 || x > n) return 0x3f3f3f3f;
if(vis[x] != -1) return vis[x];
int p;
printf("? %d\n", x);
fflush(stdout);
scanf("%d", &p);
vis[x] = p;
return p;
}
int ans(int x) {printf("! %d\n", x); exit(0);}
signed main()
{
memset(vis, -1, sizeof(vis));
scanf("%d", &n);
if(n == 1) ans(1);
if(query(1) < query(2)) ans(1);
if(query(n) < query(n - 1)) ans(n);
int l = 1, r = n;
while(l <= r) {
if(query(Mid) < query(Mid + 1) && query(Mid) < query(Mid - 1)) ans(Mid);
if(query(Mid) < query(Mid + 1)) r = Mid - 1;
else l = Mid + 1;
}
ans(l);
return 0;
}
View Code
D1 - Painting the Array I
题意
类似俄罗斯方块的游戏？
天上依次掉下n个方块，堆在两列上，假如两个方块同色，就会变成1个方块，问最多能剩下多少方块。
题解
比较不好想的贪心。
考虑现在掉下来的方块。
- 假如两个都是同色，那就随意。
- 假如只有一个同色，那就放不同色的那一个地方。
- 假如两个都不同色，判断两个列顶端的这个方块下一次出现在什么时候，放在出现早的那一列顶端。
贪心策略证明：
- 能否当前取一个不优的解，将来会变得更优。
不会，因为方块一定会落在两列中，覆盖掉列顶，也就是说即使当前不贪，接下来多获得的收益也不会大于1，贪就对了。 - 为什么放在更早的一列顶端？
反正都要挑一个放，最近可能影响收益的就是下一个同色的，*才会挑同色的来的迟的那一个放。
#include <bits/stdc++.h>
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
const int N = 1e5 + 1009;
int n, a[N], nxt[N], pos[N];
signed main()
{
n = read();
for(int i = 1; i <= n; i++) a[i] = read(), pos[i] = n + 1;
for(int i = n; i; i--) {
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
int s = -1, t = -1, ns = n + 1, nt = n + 1, cnt = 0;
for(int i = 1; i <= n; i++) {
int f1 = s != a[i];
int f2 = t != a[i];
if(f1 && f2) {
cnt++;
if(ns < nt)
s = a[i];
else t = a[i];
} else {
if(f1) s = a[i], cnt++;
if(f2) t = a[i], cnt++;
}
if(s == a[i]) ns = nxt[i];
if(t == a[i]) nt = nxt[i];
}
printf("%d\n", cnt);
return 0;
}
View Code
D2 - Painting the Array II
题意
与1相似，不过问题变为最少剩多少。
题解
与1相似。
考虑现在掉下来的方块。
- 假如两个都是同色，那就随意。
- 假如只有一个同色，那就放同色的那一个地方。
- 假如两个都不同色，判断两个列顶端的这个方块下一次出现在什么时候，放在出现晚的那一列顶端。
#include <bits/stdc++.h>
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
using namespace std;
int read(){
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
const int N = 1e5 + 1009;
int n, a[N], nxt[N], pos[N];
signed main()
{
n = read();
for(int i = 1; i <= n; i++) a[i] = read(), pos[i] = n + 1;
for(int i = n; i; i--) {
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
int s = -1, t = -1, ns = n + 1, nt = n + 1, cnt = 0;
for(int i = 1; i <= n; i++) {
int f1 = s != a[i];
int f2 = t != a[i];
if(f1 && f2) {
cnt++;
if(ns > nt)
s = a[i];
else t = a[i];
}
if(s == a[i]) ns = nxt[i];
if(t == a[i]) nt = nxt[i];
}
printf("%d\n", cnt);
return 0;
}
View Code