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
a
1
,
a
2
,
…
,
a
n
,问是否存在合法括号序列
s
,
t
s,t
s
,
t
当
a
i
=
0
a_i=0
a
i
=
0
时,
s
i
≠
t
i
s_i\neq t_i
s
i
=
t
i
,当
a
i
=
1
a_i=1
a
i
=
1
时,
s
i
=
t
i
s_i=t_i
s
i
=
t
i
.
若存在,输出
s
,
t
s,t
s
,
t
.
思路
首先,如果我们往
?
中填入左右括号,括号序列
((????))
一定比
()????()
安全,即,相同的方案,可能使后一个序列不合法,前一个序列合法.
所以很自然地想到,对于
a
i
=
1
a_i=1
a
i
=
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
a
1
=
1
,
a
n
=
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
a
i
和基价
c
i
c_i
c
i
。
一位旅行商要旅行，他希望从城市
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
(
c
i
,
a
j
−
a
i
)
个金币。求旅行商完成旅行所需花费的最少金币数。
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;
2
≤
n
≤
1
0
5
;
0
≤
a
i
,
c
i
≤
1
0
9
;
思路
你能在这里懂算我输,我至今不明不白
由于每个点都要出发一次,每次走的代价至少为
c
c
c
,所以答案至少为
∑
i
=
1
n
c
i
\sum_{i=1}^nc_i
∑
i
=
1
n
c
i
,且多出来的一部分是
a
j
−
a
i
a_j-a_i
a
j
−
a
i
产生的.
所以设遍历城市的顺序为
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
(
a
p
i
+
1
−
a
p
i
−
c
p
i
,
0
)
.
然后就是其实从任意一个城市出发都是等价的(每个城市出一次入一次).
按
a
a
a
从小到大排序,我们考虑从
a
1
a_1
a
1
出发,第一轮走到
a
n
a_n
a
n
,第二轮从
a
n
a_n
a
n
回到
a
1
a_1
a
1
.第二轮是从大的
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;
}