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,aj−ai) 个金币。求旅行商完成旅行所需花费的最少金币数。
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≤105;0≤ai,ci≤109;
思路
你能在这里懂算我输,我至今不明不白
由于每个点都要出发一次,每次走的代价至少为 c c c,所以答案至少为 ∑ i = 1 n c i \sum_{i=1}^nc_i ∑i=1nci,且多出来的一部分是 a j − a i a_j-a_i aj−ai产生的.
所以设遍历城市的顺序为 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+1−api−cpi,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;
}
