Codeforces Round #617 (Div. 3)

目录
A. Array with Odd Sum
链接
题意
解法
代码
B. Food Buying
链接
题意
解法
模拟
代码
C.Yet Another Walking Robot
链接
题意
解法
代码
D.Fight with Monsters
链接
题意
解法
代码
E. String Coloring (easy version)
链接
题意
解法
代码

A. Array with Odd Sum
链接
https://codeforces.com/contest/1296/problem/A

题意
通过赋值操作问是否能将数组和变成奇数

解法
（2n+1）奇 = 奇

（2n）奇 = 偶

所以只需要判断数组长度和奇数和偶数的出现情况就好了

代码

const int maxn = 1e5+50;
int arr[maxn];
int main(){
    int t; RD(t);
    while(t--){
        int n; RD(n);
        bool flago = false, uflago = false;
        int x; REP(i, n){ RD(x); if (x & 1) flago = true;else uflago = true;}
        if (n%2 == 1 && flago) OT("YES");
        else if (!flago) OT("NO");
        else if (n%2 == 0 && uflago){OT("YES");}
        else OT("NO");
    }
}

B. Food Buying
链接
https://codeforces.com/contest/1296/problem/B

题意
每花x钱可以得到 x/10 (下取整) ，求解最后一共能花费多少钱

解法
模拟
注意每花10元得到的1元是要算进去的，整除后要记得加上余数

代码

int main(){
    int t; RD(t);
    while(t--){
        LL n; RD(n);LL ans = 0;
        while(n >= 10){
            LL temp = n/10;
            n = n/10 + n%10;
            ans += temp*10;
        }
        ans+=n;
        OT(ans);
    }
}

C.Yet Another Walking Robot
链接
https://codeforces.com/contest/1296/problem/C

题意
优化机器人的路径，如果s[i] ~ s[j]的路径可以省略则输出，并且输出所有的可能的i和j

解法
pari<int, int> cur 设为一个位置，通过判断是否有重复经过一个位置，来进行输出，如果重复经过一个地方说明之间的路径是可以省略的

题外话，考察了map,pair<>的应用，不足够熟悉，pair实际上就相当于于是一个结构体

代码

int main(){
    int t; RD(t);
    while(t--){
        int n; RD(n);
        string s; cin >> s;
        map< pair<int,int>, int> vis; //判断该点是否被访问过 make_pair<int, int> ,int
        pair<int, int> cur = { 0, 0};
        vis[cur] = 0; //初始化
        int l = -1, r = n;
        REP( i, n){
            s[i] == 'L' ? --cur.fi : s[i] == 'R' ? ++cur.fi : s[i] == 'U' ? ++cur.se : --cur.se;
            if (vis.count(cur)){
                //如果这个这个位置有数的话说明被访问过
                if(i -  vis[cur] + 1 < r - l + 1){
                    l = vis[cur];
                    r = i;
                }
            }
            vis[cur] = i + 1;
        }
        if (l == -1) OT(-1); else printf("%d %d\n", l+1, r+1);
    }
}

D.Fight with Monsters
链接
https://codeforces.com/contest/1296/problem/D

题意
一共有n个怪物，每个怪物有ai滴血。两个人平a一下分别是a滴血和b滴血，最后一个击杀掉怪物的人获得一个积分，问你最多能获得多少积分

你可以进行k次特殊操作使敌人跳过他的回合而不进行攻击

注：每个怪物都是你先平a

解法
设每个怪物的血量是h，h%(a+b) = 0的时候说明最后攻击的人是敌人，那么我们就需要使用一次特殊操作

你攻击一次对手攻击一次，总共的伤害是(a+b)，h%（a+b）= s，s如果是1~a的值那么最后攻击的就是你，而如果 a+1 <= s <= (a+b),就需要s/a上取整-1次特殊操作

代码

int main(){
    int n, a, b, k; RD(n, a, b, k);
    vector<int> h(n);
    for(int i = 0; i < n; i++){
        RD(h[i]);
        h[i] %= (a + b);
        if (h[i] == 0) h[i] += a + b;
        h[i] = ((h[i] + a - 1) / a) - 1; // 计算需要使用几次特殊技能
    }
    sort( h.begin(), h.end());
    int ans = 0;
    FOR(i, 0, n){
        if (k - h[i] < 0) break;
        ans++, k -= h[i];
    }
    OT(ans);
}

E. String Coloring (easy version)
链接
https://codeforces.com/contest/1296/problem/E1

题意
给你一个长度为n的字符串，进行涂色，有两种颜色可以进行选择，0色或着是1色，只有不同颜色的两个位置可以进行交换，问是否存在一个0|1序列能使字符串交换成上升子序列

解法
greedy solution

上升子序列，若存在‘a‘则一定是第一个字符，若a是第一个出现的必然是不需要交换的，由于只能交换相邻的不同颜色的色块，如果是当前的字符大于上一个字符，符合条件就直接涂同一种颜色，有两种颜色可以选择

代码

const int maxn = 220;
char s[maxn];
int main(){
    int n; RD(n); scanf("%s", s);
    string ans = "";
    char lst0 = 'a', lst1 = 'a';
    for(int i = 0; i < n; i++){
        if (s[i] >= lst0){
            ans += '0', lst0 = s[i];
        }
        else if (s[i] >= lst1){
            ans += '1', lst1 = s[i];
        }
        else {OT("NO");return 0;}
    }
    OT("YES");OT(ans);
}