A. Even But Not Even
签到。
Code
/*
* Author: heyuhhh
* Created Time: 2020/2/2 22:06:33
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 3000 + 5;
int n;
char s[N];
void run(){
cin >> n;
cin >> (s + 1);
int odd = 0, even = 0, f = 1;
vector <char> ans;
for(int i = 1; i <= n; i++) {
if((s[i] - '0') & 1) ++odd;
else ++even;
ans.push_back(s[i]);
if(odd == 2) {
f = 0;
break;
}
}
if(f) cout << -1 << '
';
else {
for(auto it : ans) cout << it;
cout << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
B. Array Sharpening
分几种情况贪心一下即可。
Code
/*
* Author: heyuhhh
* Created Time: 2020/2/2 22:14:58
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 3e5 + 5;
int n;
int a[N];
void run(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int f = 1;
for(int i = 1; i <= n; i++) {
if(f == 1) {
if(a[i] < i - 1) {
if(a[i - 1] <= n - i) f = -1;
else f = 0;
}
}
if(f == 0) {
if(a[i] < n - i) f = -1;
}
}
if(f >= 0) {
cout << "YES" << '
';
} else {
for(int i = 1; i <= n; i++) {
if(a[i] < n - i) {
cout << "NO" << '
';
return;
}
}
cout << "YES" << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
C. Mind Control
题意：
给出(n)个数，现在有(n)个人依次轮流来取走一个数，每次只能取最左边一个或最右边一个。
现在你是第(m)个来取的人。
除你以外的(n-1)个人每次取都是任意从两端取一个，但是现在你可以指定(k)个人从哪端取。
问所有的情况中，你能取到的最大值最小是多少。
思路：
直接枚举即可。
枚举指定(x)个人选左端点，那么就有(k-x)个人选右端点。
再枚举其余人随机选的所有情况，每种情况维护答案即可。
可以用线段树优化到(O(nlogn))。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/2/3 0:18:18
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 3500 + 5;
int n, m, k;
int a[N];
void run(){
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
if(k >= m) k = m - 1;
int d = m - k - 1;
for(int j = 0; j <= k; j++) {
int res = INF;
for(int l = 1; l <= n; l++) {
int r = l + n - d - 1;
if(r > n) break;
int L = l + j, R = r - (k - j);
res = min(res, max(a[L], a[R]));
}
ans = max(ans, res);
}
cout << ans << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
D. Irreducible Anagrams
题意：
如果两个串所有字符出现的次数相同，那么定义这两个串是相似的。
如果两个串是相似的，且满足：(exist kgeq 2)，两个串被划分为(s_1,t_1,s_2,t_2,cdots,s_k,t_k)，满足：
- (s_1,s_2,cdots,s_k)按顺序拼接起来为(s)串，(t)串同理；
- 对于(1leq ileq k)，都有(s_i,t_i)是相似的。
那么称这两个串非常相似。
现在给出一个串(s)，然后给出多个询问，每个询问一个区间([l,r])，回答是否存在串和子串(s_ls_{l+1}cdots s_r)不非常相似。
思路：
显然，我们要找的这个串首先满足和子串是相似的。
如果这两个串不是非常相似，那么就说明对于所有的划分，都不满足上面第二个条件。
接下来考虑构造：
- (s_l ot ={s_r})时，我们将子串中所有为(s_r)的字符放在前面即可。因为至少有两个划分，所以显然这样不存在与其非常相似的串。
- (s_l=s_r)时，若串中含有至少(3)个不同的字符，那么我们将(s)中所有为(s_l)的字符拿出来，然后将最后一个位置字符和剩下没用的字符对换，再将所有拿出来的字符插在倒数第二个位置即可。因为此时划分必然从连续的(s_l)中划分，那么必然最后面的一个划分是不能满足的。
- (s_l=s_r)且串中含有两种不同字符时，假设现在只由(a,b)两种字符构成且(s_l=s_r=a)。那么最终的串一定要以(b)作为开头和结尾。那么(s=acdots a,s'=bcdots b)，注意(a)的数量，(1)~(n-1)中(s)串(a)的变化为([1,tota-1]),(s')的变化为([0,tota])。那么显然无论怎么构造，都存在一个前缀(i)，满足([1,i])中(a,b)个数相等，同理([i+1,n])中的个数也相等。故此时一定是非常相似的。
- (s_l=s_r)且串中只含有一个字符时，这种情况最为简单。
注意(l=r)时的判断。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/2/3 11:14:11
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
char s[N];
int pre[N][26];
void run(){
int n, q;
cin >> (s + 1);
n = strlen(s + 1);
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 26; j++) {
pre[i][j] = pre[i - 1][j];
}
++pre[i][s[i] - 'a'];
}
cin >> q;
while(q--) {
int l, r; cin >> l >> r;
if(l == r || s[l] != s[r]) {
cout << "YES" << '
';
continue;
}
vector <int> cnt(26, 0);
int t = 0;
for(int i = 0; i < 26; i++) {
cnt[i] = pre[r][i] - pre[l - 1][i];
if(cnt[i]) ++t;
}
if(t > 2) cout << "YES" << '
';
else cout << "NO" << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
E. Prefix Enlightenment
题意：
现有(n)个灯泡和(k)个由(1)~(n)组成的集合，并且输入数据保证，对于所有的(1leq i_1<i_2<i_3,A_{i_1}cap A_{i_2}cap A_{i_3}=emptyset)。
每次使用一个集合，都能使得集合里面的开关状态取反。
现在记(m_i)为使得前(i)个灯泡为亮的最少集合使用个数。问(m_1,m_2,cdots,m_n)。
思路：
因为一个位置的灯泡至多受两个集合的控制，假设现在所有的灯泡都受两个集合的控制。
那么如果当前灯泡为(1)，那么显然两个集合要么同时取，要么同时不取；如果当前灯泡为(0)，那么两个集合中只能取一个。
如果现在要确定(m_i)，那么可以根据前(i)个灯泡的状态建图，之后给图染色，颜色数少的结点个数即为答案。
若要确定(m_{i+1})，添加边即可，每次只会添加一条边。
因此可以动态维护答案。
现在考虑某些位置只受一个结点控制，此时打上一个标记就行。
具体实现时，用并查集来实现，将每个集合拆为两个，选与不选。打标记时修改父亲为(0)，然后特判一下这种情况。
细节见代码：
Code
/*
* Author: heyuhhh
* Created Time: 2020/2/3 18:28:54
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 3e5 + 5;
int n, k;
char s[N];
int bel[N][2];
int f[N + N], cnt[N + N];
int find(int x) {
return f[x] == x ? f[x] : f[x] = find(f[x]);
}
int calc(int x) {
int y = x + k;
int fx = find(x), fy = find(y);
if(fx == 0 || fy == 0) return cnt[fx + fy];
return min(cnt[fx], cnt[fy]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx == 0) swap(fx, fy);
f[fx] = fy;
if(fy != 0) cnt[fy] += cnt[fx];
}
void run(){
cin >> (s + 1);
for(int i = 1; i <= k; i++) {
int x; cin >> x;
for(int j = 1; j <= x; j++) {
int t; cin >> t;
if(bel[t][0] == 0) bel[t][0] = i;
else bel[t][1] = i;
}
}
for(int i = 1; i <= k + k; i++) f[i] = i;
for(int i = 1; i <= k; i++) cnt[i] = 1;
int ans = 0;
for(int i = 1; i <= n; i++) {
if(bel[i][1] == 0) {
int x = bel[i][0];
if(x) {
ans -= calc(x);
if(s[i] == '0') {
f[find(x + k)] = 0;
} else {
f[find(x)] = 0;
}
ans += calc(x);
}
} else {
int x = bel[i][0], y = bel[i][1];
if(s[i] == '0') {
if(find(x + k) != find(y)) {
ans -= calc(x) + calc(y);
merge(x + k, y);
merge(x, y + k);
ans += calc(x);
}
} else {
if(find(x) != find(y)) {
ans -= calc(x) + calc(y);
merge(x, y);
merge(x + k, y + k);
ans += calc(x);
}
}
}
cout << ans << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n >> k) run();
return 0;
}
F. Coffee Varieties (easy version)
题意：
交互题。
现有一序列(a_i)，但只知道其长度(n)。然后有一个容量为(k)的队列，当队列长度超过(k)时，会自动弹出队首元素。
现在可以执行最多(frac{2n^2}{k})次操作，每次操作询问(a_i)，并且回答目前队列中是否有元素和(a_i)相等，同时将(a_i)加入队列。
还可以执行至多(30000)次清零操作。
(1leq n,kleq 1024,frac{2n^2}{k}leq 20000)。
思路：
hard版本就是操作次数限制了一下，我就主要说一下easy版本吧。
显然最直接的想法就是，每询问(k)个就清(0)然后再来，即对每个元素(a_i)，看其前面是否有与之相等的数。
现在对序列按照(frac{k}{2})分块，共(frac{2n}{k})个块，然后暴力枚举两两块进行询问，这样也可得出每个数之前所有数是否有与之相同的数。
那么一共的询问次数为(displaystyle kcdotfrac{frac{2n}{k}cdot(frac{2n}{k}-1)}{2}=frac{2n^2-kn}{k})，重置次数为(displaystylefrac{frac{2n}{k}cdot(frac{2n}{k}-1)}{2}=frac{2n^2-kn}{k^2})。因为有(displaystylefrac{2n^2}{k}leq 20000)，所以两个限制都是满足的。
PS：这里插一句，感觉第一种做法和第二种做法都差不多，但第一种写法还是会超限制，而且也不是很好证明。
想过hard版本就需要利用这是一个队列的性质，对(1,2)块询问过后，直接询问第(3)块，就相当于此时询问了(2,3)。
对于其它对都类似这样来即可。限制不是很会证明。
代码细节如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/2/4 11:56:17
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '
'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2000 + 5;
int n, k;
bool chk[N];
int query(int c) {
cout << '?' << ' ' << c << endl;
char t; cin >> t;
if(t == 'Y') return 1;
return 0;
}
void reset() {
cout << 'R' << endl;
}
int block, num;
void add(int x) {
for(int i = (x - 1) * block + 1; i <= min(n, x * block); i++) {
if(query(i)) chk[i] = true;
}
}
void run(){
int ans = 0;
block = max(1, k / 2), num = n / block;
for(int k = 1; k < num; k++) {
for(int i = 1; i <= k; i++) {
if(i + k > num) break;
for(int j = i; j <= num; j += k) add(j);
reset();
}
}
for(int i = 1; i <= n; i++) if(!chk[i]) ++ans;
cout << '!' << ' ' << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n >> k) run();
return 0;
}