A. Vasya And Password
模拟题,将所缺的种类依次填入“出现次数$ >1 $”的位置,替换掉Ta即可。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110;
char str[N];
int sum[3][N], n;
int inline get(char x){
if(x <= '9' && x >= '0') return 0;
else if(x >= 'a' && x <= 'z') return 1;
return 2;
}
void change(int pos, int x){
if(x == 0) str[pos] = '0';
else if(x == 1) str[pos] = 'a';
else str[pos] = 'A';
}
int main(){
int T; scanf("%d", &T);
while(T--){
scanf("%s", str + 1);
n = strlen(str + 1);
for(int i = 1; i <= n; i++){
for(int j = 0; j < 3; j++) sum[j][i] = sum[j][i - 1];
sum[get(str[i])][i]++;
}
int cnt = 0;
for(int i = 0; i < 3; i++) if(!sum[i][n]) cnt++;
if(cnt){
int tot = 0, l = 1, r = 1 + cnt - 1;
for(int i = l; i <= r; i++){
if(sum[get(str[i])][n] == 1) {
r++; continue;
}
while(sum[tot][n]) tot ++;
change(i, tot++);
}
}
printf("%s
", str + 1);
}
return 0;
}
B. Relatively Prime Pairs
两个相邻的整数必然是互质的。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
LL l, r, tot;
int main(){
cin >> l >> r;
if(l == r) puts("NO");
else{
puts("YES");
tot = (r - l + 1) >> 1;
for(LL i = l, j = 0; j < tot; j++, i+=2){
printf("%lld %lld
", i, i + 1);
}
}
return 0;
}
C. Vasya and Multisets
模拟题,调了无数次,发现是自己没有理解题意。存在次数为(1)的数记为(tot_1),存在次数(>2)的数记为(tot_2)
(tot_1)个数不管划分到哪个集合,都会使那个集合的(good number + 1)。
这时候如果(tot_1)为奇数,则在(tot_2)中找一个数拆成(1 + (x - 1))的模式分配即可。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 110;
int n, a[N], cnt[N], tot = 0, tot2 = 0, num = 0, st[N], cnt2[2][N];
bool vis[N];
char ans[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", a + i), cnt[a[i]]++;
for(int i = 1; i <= 100; i++){
if(cnt[i] == 1) tot++;
if(cnt[i] > 2) tot2++;
}
if((tot & 1) && (tot2)) tot++;
if(tot & 1) puts("NO");
else{
puts("YES"); tot >>= 1;
for(int i = 1; i <= n; i++){
if(cnt[a[i]] == 1){
if(num < tot)
ans[i] = 'A', num++, cnt2[0][a[i]]++;
else if(num < tot * 2)
ans[i] = 'B', num++, cnt2[1][a[i]]++;
}
}
for(int i = 1; i <= n; i++){
if(cnt[a[i]] != 1){
if(cnt[a[i]] == 2) ans[i] = 'A', cnt2[0][a[i]]++;
else if(vis[a[i]]) ans[i] = 'A' + st[a[i]], cnt2[st[a[i]]][a[i]]++;
else if(num < tot && (!vis[a[i]]))
ans[i] = 'A', vis[a[i]] = true, st[a[i]] = 1, num++, cnt2[0][a[i]]++;
else if(num < tot * 2 && (!vis[a[i]]))
ans[i] = 'B', st[a[i]] = 0, vis[a[i]] = true, num++, cnt2[1][a[i]]++;
else ans[i] = 'A', cnt2[0][a[i]]++;
}
}
for(int i = 1; i <= n; i++) printf("%c", ans[i]);
}
return 0;
}
D. Bicolorings
#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 998244353, N = 1010;
typedef long long LL;
int n, k;
LL f[N][N << 1][4];
/* f[i][j][k] 代表前i列有j个联通快, type = k;
type = 0:
0
0
type = 1:
0
1
type = 2:
1
0
type = 3:
1
1
*/
int main(){
cin >> n >> k;
f[1][1][0] = f[1][2][1] = f[1][2][2] = f[1][1][3] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i * 2; j++){
(f[i][j][0] += f[i - 1][j][0] + f[i - 1][j][1] + f[i - 1][j][2] + f[i - 1][j - 1][3]) %= mod;
(f[i][j][1] += f[i - 1][j - 1][0] + f[i - 1][j][1] + (j >= 2 ? f[i - 1][j - 2][2] : 0) + f[i - 1][j - 1][3]) %= mod;
(f[i][j][2] += f[i - 1][j - 1][0] + (j >= 2 ? f[i - 1][j - 2][1] : 0) + f[i - 1][j][2] + f[i - 1][j - 1][3]) %= mod;
(f[i][j][3] += f[i - 1][j - 1][0] + f[i - 1][j][1] + f[i - 1][j][2] + f[i - 1][j][3]) %= mod;
}
}
LL res = 0;
for(int i = 0; i < 4; i++) (res += f[n][k][i]) %= mod;
cout << res;
return 0;
}