你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

Codeforces Round #712 (Div. 2)

2021-11-13 11:23:21
Codeforces Round #712 (Div. 2)

A Déjà Vu

题目

给定一个字符串,你可以在某个位置插入一个a,问是否有这样一个位置,使得插入后得到的不是回文串.

思路

找到一个不是a的位置,将a插入到对应位置即可,全是a则无解.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int read() {
    int re = 0;
    char c = getchar();
    bool negt = false;
    while(c < '0' || c > '9')
        negt |= (c == '-')  , c = getchar();
    while(c >= '0' && c <= '9')
        re = (re << 1) + (re << 3) + c - '0' , c = getchar();
    return negt ? -re : re;
}
template <char l , char r>
char readc() {
    char c = getchar();
    while(c < l || c > r)c = getchar();
    return c;
}

const int N = 3e5 + 10;
int n;
char s[N];
void solve() {
    scanf("%s" , s + 1);
    n = strlen(s + 1);
    int pos = -1;
    for(int i = 1 ; i <= n ; i++)
        if(s[i] != 'a') {
            pos = n - i + 1;
            break;
        }
    if(pos == -1)puts("NO");
    else {
    	if(pos >= n / 2)++pos;
        puts("YES");
        for(int i = 1 ; i < pos ; i++)
            putchar(s[i]);
        putchar('a');
        for(int i = pos ; i <= n ; i++)
            putchar(s[i]);
        putchar('\n');
    }
}
int main() {
    int T = read();
    while(T--)solve();
    return 0;
}

B Flip the Bits

题目

有长度为 n n n 的两个 01 字符串 a a a b b b。如果对于一个 i i i a a a 的区间 [ 1 , i ] [1,i] [1,i] 中, 0 0 0 的数量等于 1 1 1 的数量,则你可以将这个区间的所有 1 1 1 变成 0 0 0 0 0 0 变成 1 1 1。求是否可以将 a a a 变成 b b b

思路

处理出所有 i i i,使 [ 1 , i ] [1,i] [1,i]中,0的数量等于1的数量.

若有一对 l , r l,r l,r,满足 [ 1 , l ] [1,l] [1,l], [ 1 , r ] [1,r] [1,r]0的数量等于1的数量,则相当于区间 [ l + 1 , r ] [l+1,r] [l+1,r]可以执行变化且不影响其它区间.

代码

#include <iostream>
#include <cstdio>
using namespace std;
int read() {
    int re = 0;
    char c = getchar();
    bool negt = false;
    while(c < '0' || c > '9')
        negt |= (c == '-')  , c = getchar();
    while(c >= '0' && c <= '9')
        re = (re << 1) + (re << 3) + c - '0' , c = getchar();
    return negt ? -re : re;
}
template <char l , char r>
char readc() {
    char c = getchar();
    while(c < l || c > r)c = getchar();
    return c;
}

const int N = 3e5 + 10;
int n;
char s[N] , t[N];
bool flag[N];

bool equ(int l , int r) {
    if(l > r) return true;
    for(int i = l ; i <= r ; i++)
        if(s[i] != t[i])
            return false;
    return true;
}
bool rev_equ(int l , int r) {
    if(l > r) return true;
    for(int i = l ; i <= r ; i++)
        if(s[i] == t[i] && s[i] != 0)
            return false;
    return true;
}
bool solve() {
    n = read();
    for(int i = 0 ; i <= 1 + n ; i++)s[i] = t[i] = flag[i] = 0;
    for(int i = 1 ; i <= n ; i++)s[i] = readc<'0' , '1'>();
    for(int i = 1 ; i <= n ; i++)t[i] = readc<'0' , '1'>();
    int zero = 0 , one = 0;
    for(int i = 1 ; i <= n ; i++) {
        zero += s[i] == '0' , one += s[i] == '1';
        if(zero == one)flag[i] = true;
    }
    int l = 0 , r;
    for(int i = 1 ; i <= n ; i++) {
        r = l + 1;
        while(r <= n && flag[r] == false)++r;
        if(r > n)break;
        if(!equ(l + 1 , r) && !rev_equ(l + 1 , r))
			return false;
        l = r;
    }
    return equ(l + 1 , n);
}
int main() {
    int T = read();
    while(T--)puts(solve() ? "YES" : "NO");
    return 0;
}

C Balance the Bits

题目

给定序列 a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1,a2,,an,问是否存在合法括号序列 s , t s,t s,t a i = 0 a_i=0 ai=0时, s i ≠ t i s_i\neq t_i si=ti,当 a i = 1 a_i=1 ai=1时, s i = t i s_i=t_i si=ti.

若存在,输出 s , t s,t s,t.

思路

首先,如果我们往?中填入左右括号,括号序列((????))一定比()????()安全,即,相同的方案,可能使后一个序列不合法,前一个序列合法.

所以很自然地想到,对于 a i = 1 a_i=1 ai=1,我们可以前面全放左括号,后面全放右括号.

同理,对于 a = 0 a=0 a=0,我们先填可以 s s s序列,为了保证 t t t的安全,我们一开始能放)就放),最后check以下 t t t串的合法性.

然后你发现这个做法不好写.

另外一个做法是在 a = 0 a=0 a=0的位置依次放()()()...,这样, t t t串对应的位置就是)()()(...,只需保证第一个 a = 0 a=0 a=0前面有一个左括号即可,而有解时 a 1 = 1 , a n = 1 a_1=1,a_n=1 a1=1,an=1成立,又因为 a = 1 a=1 a=1是我们先放左括号,故可以保证.

代码

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
int read() {
    int re = 0;
    char c = getchar();
    bool negt = false;
    while(c < '0' || c > '9')
        negt |= (c == '-')  , c = getchar();
    while(c >= '0' && c <= '9')
        re = (re << 1) + (re << 3) + c - '0' , c = getchar();
    return negt ? -re : re;
}
template <char l , char r>
char readc() {
    char c = getchar();
    while(c < l || c > r)c = getchar();
    return c;
}

const int N = 2e5 + 10;

int n;
char a[N] , b[N];
char s[N];

bool check() {
    int cnt = 0;
    for(int i = 1 ; i <= n ; i++) {
        cnt += (b[i] == '(' ? 1 : -1);
        if(cnt < 0)return false;
    }
    return cnt == 0;
}

int sum1[N]  ,sum2[N];
//代码没整理,有些没用的变量请忽略.
stack<int> stk;
void solve() {
	while(stk.size())stk.pop();
    n = read();
    for(int i = 0 ; i <= n + 1 ; i++)a[i] = b[i] = s[i] = sum1[i] = sum2[i] = 0;
    for(int i = 1 ; i <= n ; i++)s[i] = readc<'0' , '1'>();
    int zero = 0 , one = 0;
    for(int i = 1 ; i <= n ; i++)
        zero += (s[i] == '0') , one += (s[i] == '1');
    if(zero & 1) {
        puts("NO");
        return ;
    }
    for(int i = 1 , cnt = 0 ; cnt < one / 2 ; i++)
        if(s[i] == '1')++cnt , a[i] = '(' , sum1[i] = 1;
    for(int i = n , cnt = 0 ; cnt < one / 2 ; i--)
        if(s[i] == '1')++cnt , a[i] = ')' , sum1[i] = -1;
    
    int cnt = 0 , l = zero / 2 , r = zero / 2;
    for(int i = 1 ; i <= n ; i++)
        if(a[i] != 0) {
        	cnt += (a[i] == '(' ? 1 : -1);
        	if(cnt < 0)//右括号比左括号多了,撤回最近一次右括号
        		a[stk.top()] = '(' , cnt += 2 , --l , ++r , stk.pop();
		} 
        else {
            if(cnt > 0 && r > 0)--cnt , a[i] = ')' , --r , stk.push(i);
            else ++cnt , a[i] = '(' , --l;
        }
    for(int i = 1 ; i <= n ; i++)
        b[i] = (a[i] ^ (s[i] - '0') ^ 1);
    if(!check())
        puts("NO");
    else {
        puts("YES");
        puts(a + 1);
        puts(b + 1);
    }
}
int main() {
    int T = read();
    while(T--)solve();
    return 0;
}

D 3-Coloring

题目

交互题,有1,2,3三种颜色和一个 n × n n\times n n×n的网格,每次交互器ban掉一种颜色,你从剩下的两种颜色中选择一种,将一个没图色的格子涂成该颜色,相邻(有公共边)的网格不能涂成相同颜色,你需要将全网格涂色.

可以证明你有必胜策略.

思路

我们先如下将网格编号:

0101010101...
1010101010...
0101010101...
1010101010...
0101010101...
...

我们将编号为0的网格涂成A颜色,编号为1的网格涂成B颜色,至少有一种编号是可以涂完的(每次只会ban一种颜色),我们假设涂完的是A颜色,那我们用BC颜色涂完剩下的网格.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int read() {
    int re = 0;
    char c = getchar();
    bool negt = false;
    while(c < '0' || c > '9')
        negt |= (c == '-')  , c = getchar();
    while(c >= '0' && c <= '9')
        re = (re << 1) + (re << 3) + c - '0' , c = getchar();
    return negt ? -re : re;
}
template <char l , char r>
char readc() {
    char c = getchar();
    while(c < l || c > r)c = getchar();
    return c;
}

const int N = 3e5 + 10;
struct XY {
    int x , y;
} ;
XY make(int x , int y) {
    return (XY) {x , y};
}
int n;
queue <XY> a , b;
int main() {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < n ; j += 2) {
            if((j ^ (i & 1) ^ 1) < n)a.push(make(i + 1 , 1 + (j ^ (i & 1) ^ 1)));
            if((j ^ (i & 1)) < n)b.push(make(i + 1 , 1 + (j ^ (i & 1))));
        }
    int ban;
    while(a.size() && b.size()) {
    	cin >> ban;
    	if(ban != 1) {
    		cout << 1 << ' ' << a.front().x << ' ' << a.front().y << endl;
    		a.pop();
		} else {
			cout << 2 << ' ' << b.front().x << ' ' << b.front().y << endl;
			b.pop();
		}
	}
	while(a.size()) {// use 1 or 3
		cin >> ban;
		cout << (ban == 1 ? 3 : 1) << ' ' << a.front().x << ' ' << a.front().y << endl;
		a.pop();
	}
	while(b.size()) {// use 2 or 3
		cin >> ban;
		cout << (ban == 2 ? 3 : 2) << ' ' << b.front().x << ' ' << b.front().y << endl;
		b.pop();
	}
    return 0;
}

E Travelling Salesman Problem

题目

C 国有 n n n 个城市(编号为 1 1 1 n n n),第 i i i 个城市有美丽值 a i a_i ai 和基价 c i c_i ci

一位旅行商要旅行,他希望从城市 1 1 1 开始,经过其他的每个城市正好一次,然后回到城市 1 1 1

对于任意 i ≠ j i\not=j i=j,从城市 i i i 到达城市 j j j 需要 max ⁡ ( c i , a j − a i ) \max(c_i,a_j-a_i) max(ci,ajai) 个金币。求旅行商完成旅行所需花费的最少金币数。

2 ≤ n ≤ 1 0 5 ; 0 ≤ a i , c i ≤ 1 0 9 ; 2\leq n\leq10^5;0\leq a_i,c_i\leq10^9; 2n105;0ai,ci109;

思路

你能在这里懂算我输,我至今不明不白

由于每个点都要出发一次,每次走的代价至少为 c c c,所以答案至少为 ∑ i = 1 n c i \sum_{i=1}^nc_i i=1nci,且多出来的一部分是 a j − a i a_j-a_i ajai产生的.

所以设遍历城市的顺序为 p p p,答案就是 ∑ c + ∑ max ⁡ ( a p i + 1 − a p i − c p i , 0 ) \sum c+\sum \max(a_{p_{i+1}}-a_{p_i}-c_{p_i},0) c+max(api+1apicpi,0).

然后就是其实从任意一个城市出发都是等价的(每个城市出一次入一次).

a a a从小到大排序,我们考虑从 a 1 a_1 a1出发,第一轮走到 a n a_n an,第二轮从 a n a_n an回到 a 1 a_1 a1.第二轮是从大的 a a a到小的 a a a,相当于全程是免费的(注意我们已经将 c c c分离开了),所以我们最小化第一轮的花费即可.

然后我还没明白.

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int read() {
    int re = 0;
    char c = getchar();
    bool negt = false;
    while(c < '0' || c > '9')
        negt |= (c == '-')  , c = getchar();
    while(c >= '0' && c <= '9')
        re = (re << 1) + (re << 3) + c - '0' , c = getchar();
    return negt ? -re : re;
}
template <char l , char r>
char readc() {
    char c = getchar();
    while(c < l || c > r)c = getchar();
    return c;
}

const int N = 3e5 + 10;
using pr = pair<int , int>;
using ll = long long;
pr city[N];
int f[N];
int main() {
    int n = read();
    ll ans = 0;
    for(int i = 1 ; i <= n ; i++) {
        int a = read() , c = read();
        ans += c;
        city[i] = make_pair(a , c);
    }
    sort(city + 1 , city + n + 1);
    int maxHeigh = city[1].first + city[1].second;
    for(int i = 2 ; i <= n ; i++) {
        ans += max(0 , city[i].first - maxHeigh);
        maxHeigh = max(maxHeigh , city[i].first + city[i].second);
    }
    cout << ans;
    return 0;
}