Codeforces Round #700 题解(A-D)

A - Yet Another String Game

题意

博弈游戏,每次可以把字串一个字母改成不同的,A想让字串变小,B想让字串变大,问最后字串变成啥样。

题解

显然从前往后改,A把字串改成'a',如果本来就是'a'则改成'b',B同理。

Codeforces Round #700 题解(A-D)
#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。
显然问题在于英雄和怪同归于尽,怪物最后一刀溢出越多,我们越赚。
就让攻击力最强的怪排在最后就行了。

Codeforces Round #700 题解(A-D)
#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]肯定是满足题意的,然后二分就行了。

Codeforces Round #700 题解(A-D)
#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. 能否当前取一个不优的解,将来会变得更优。
    不会,因为方块一定会落在两列中,覆盖掉列顶,也就是说即使当前不贪,接下来多获得的收益也不会大于1,贪就对了。
  2. 为什么放在更早的一列顶端?
    反正都要挑一个放,最近可能影响收益的就是下一个同色的,*才会挑同色的来的迟的那一个放。
Codeforces Round #700 题解(A-D)
#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相似。
考虑现在掉下来的方块。

  • 假如两个都是同色,那就随意。
  • 假如只有一个同色,那就放色的那一个地方。
  • 假如两个都不同色,判断两个列顶端的这个方块下一次出现在什么时候,放在出现的那一列顶端。
Codeforces Round #700 题解(A-D)
#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

 

上一篇:Codeforces Round #700 (Div. 2)


下一篇:Codeforces Round #700 Div. 2