Educational Codeforces Round 51 (Rated for Div. 2)
Educational Codeforces Round 51 (Rated for Div. 2)
attack
发布于 2018-09-21 14:54:02
发布于 2018-09-21 14:54:02
做了四个题。。
A. Vasya And Password
直接特判即可，，为啥泥萌都说难写，，，，
这个子串实际上是忽悠人的，因为每次改一个字符就可以
/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define LL long long
#define ull unsigned long long
#define rg register
#define pt(x) printf("%d ", x);
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
//char obuf[1<<24], *O = obuf;
//void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}
//#define OS *O++ = ' ';
using namespace std;
//using namespace __gnu_pbds;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int T;
char s[MAXN];
void solve() {
int N = strlen(s + 1);
int a = 0, b = 0, c = 0;
for(int i = 1; i <= N; i++) {
if(s[i] >= '1' && s[i] <= '9') a++;
if(s[i] >= 'a' && s[i] <= 'z') b++;
if(s[i] >= 'A' && s[i] <= 'Z') c++;
}
if(a == 0) {
if(b > 1) {
for(int i = 1; i <= N; i++)
if(s[i] >= 'a' && s[i] <= 'z') {s[i] = '1'; break;}
b--;
} else if(c > 1) {
for(int i = 1; i <= N; i++)
if(s[i] >= 'A' && s[i] <= 'Z') {s[i] = '1'; break;}
c--;
}
}
if(b == 0) {
if(a > 1) {
for(int i = 1; i <= N; i++)
if(s[i] >= '1' && s[i] <= '9') {s[i] = 'a'; break;}
a--;
} else if(c > 1) {
for(int i = 1; i <= N; i++)
if(s[i] >= 'A' && s[i] <= 'Z') {s[i] = 'a'; break;}
c--;
}
}
if(c == 0) {
if(a > 1) {
for(int i = 1; i <= N; i++)
if(s[i] >= '1' && s[i] <= '9') {s[i] = 'A'; break;}
a--;
} else if(b > 1) {
for(int i = 1; i <= N; i++)
if(s[i] >= 'a' && s[i] <= 'z') {s[i] = 'A'; break;}
b--;
}
}
printf("%s\n", s + 1);
}
main() {
T = read();
while(T--) {
scanf("%s", s + 1);
solve();
}
return 0;
}
/*
2 2 1
1 1
2 1 1
*/B. Relatively Prime Pairs
很显然，$i$和$i+1$是互质的。
做完了
/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define LL long long
#define ull unsigned long long
#define rg register
#define pt(x) printf("%d ", x);
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
//char obuf[1<<24], *O = obuf;
//void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}
//#define OS *O++ = ' ';
using namespace std;
//using namespace __gnu_pbds;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int l, r;
main() {
l = read(), r = read();
if(l == r) {puts("NO"); return 0;}
puts("YES");
for(int i = l; i <= r - 1; i += 2) {
cout << i << " " << i + 1 << endl;
}
return 0;
}
/*
2 2 1
1 1
2 1 1
*/C. Vasya and Multisets
显然，如果有偶数个优秀的，对半分就可以
如果有奇数个，直接拿出一个$\geqslant 3$的数加到小的里面
否则无解
/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define LL long long
#define ull unsigned long long
#define rg register
#define pt(x) printf("%d ", x);
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
//char obuf[1<<24], *O = obuf;
//void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}
//#define OS *O++ = ' ';
using namespace std;
//using namespace __gnu_pbds;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, A[MAXN], timssssss[MAXN];
main() {
int n=read();
for(int i = 1; i <= n; ++i) ++timssssss[A[i] = read()];
int cnt[5] = {0,0,0,0,0};
for(int i = 1; i <= 100; ++i)
if(timssssss[A[i]] < 3) ++cnt[timssssss[A[i]]];
else ++cnt[3];
if(cnt[1] & 1 && cnt[3] == 0) return puts("NO"),0;
puts("YES");
int mid = cnt[1]>>1;
if(cnt[1]&1) {
int p = 0;
for(int i = 1; i <= n; ++i)
if(timssssss[A[i]] > 2) {
p = i;
break;
}
for(int i = 1 ; i <= n; ++i)
if(timssssss[A[i]] == 1) {
if(mid) putchar('A'), --mid;
else putchar('B');
} else if(i != p) putchar('B');
else putchar('A');
} else {
for(int i = 1; i <= n; ++i)
if(timssssss[A[i]] == 1) {
if(mid) putchar('A'), --mid;
else putchar('B');
} else putchar('B');
}
return 0;
}
/*
2 2 1
1 1
2 1 1
*/D. Bicolorings
普及dp？？。。。
因为只有两行，考虑把列的状态记下来
$f[i][j][sta]$表示到第$i$列，有$j$个连通块的方案，当前列的状态为$sta$，就是“白白” “白黑”“黑白”“黑黑”这四种状态
转移的时候枚举上一行选了啥
/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define LL long long
#define ull unsigned long long
#define rg register
#define pt(x) printf("%d ", x);
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
//char obuf[1<<24], *O = obuf;
//void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}
//#define OS *O++ = ' ';
using namespace std;
//using namespace __gnu_pbds;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 998244353;
const double eps = 1e-9;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, K;
int f[2001][2001][4];
// 0 �װ�
// 1 ��
// 2 �ڰ�
// 3 �ں�
main() {
N = read(); K = read();
f[1][1][0] = 1;
f[1][2][1] = 1;
f[1][2][2] = 1;
f[1][1][3] = 1;
for(int i = 2; i <= N; i++) {//��i���
for(int j = 0; j <= K; j++) {//��j����
(f[i][j][0] += f[i - 1][j][0]) %= mod;
(f[i][j][0] += f[i - 1][j][1]) %= mod;
(f[i][j][0] += f[i - 1][j][2]) %= mod;
(f[i][j][0] += f[i - 1][j - 1][3]) %= mod;
(f[i][j][1] += f[i - 1][j - 1][0]) %= mod;
(f[i][j][1] += f[i - 1][j][1]) %= mod;
(f[i][j][1] += f[i - 1][j - 2][2]) %= mod;
(f[i][j][1] += f[i - 1][j - 1][3]) %= mod;
(f[i][j][2] += f[i - 1][j - 1][0]) %= mod;
(f[i][j][2] += f[i - 1][j - 2][1]) %= mod;
(f[i][j][2] += f[i - 1][j][2]) %= mod;
(f[i][j][2] += f[i - 1][j - 1][3]) %= mod;
(f[i][j][3] += f[i - 1][j - 1][0]) %= mod;
(f[i][j][3] += f[i - 1][j][1]) %= mod;
(f[i][j][3] += f[i - 1][j][2]) %= mod;
(f[i][j][3] += f[i - 1][j][3]) %= mod;
//for(int k = 0; k <= 3; k++)//��ǰ״̬
}
}
int ans = (f[N][K][0] + f[N][K][1] % mod + f[N][K][2] % mod + f[N][K][3] % mod) % mod;
cout << ans;
return 0;
}
/*
2 2 1
1 1
2 1 1
*/F. The Shortest Statement
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-09-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录