A. Vasya And Password
题意:给你N个字符串,要你将所有的字符串变化为包含大写字母、小写字母、数字的字符串
题解:模拟。。我写的好复杂。。。
#include <bits/stdc++.h>
const int MAXN = 1000;
using namespace std;
int T,low,upe,dig,ze;
char s[MAXN];
inline void solve(){
int len = strlen(s);
if(dig >= low && low > upe){//dig > low > upe
for(int i = 0;i < len;i++){
if('0' <= s[i] && s[i] <= '9') {
s[i] = 'A';
return;
}
}
}
if(dig >= upe && upe > low){//dig > upe > low
for(int i = 0;i < len;i++){
if('0' <= s[i] && s[i] <= '9') {
s[i] = 'a';
return;
}
}
}
if(upe >= dig && dig > low){//upe > dig > low
for(int i = 0;i < len;i++){
if('A' <= s[i] && s[i] <= 'Z') {
s[i] = 'a';
return;
}
}
}
if(upe >= low && low > dig){//upe > low > dig
for(int i = 0;i < len;i++){
if('A' <= s[i] && s[i] <= 'Z') {
s[i] = '1';
return;
}
}
}
if(low >= dig && dig > upe){//low > dig > upe
for(int i = 0;i < len;i++){
if('a' <= s[i] && s[i] <= 'z') {
s[i] = 'A';
return;
}
}
}
if(low >= upe && upe > dig){//low > upe > dig
for(int i = 0;i < len;i++){
if('a' <= s[i] && s[i] <= 'z') {
s[i] = '1';
return;
}
}
}
}
inline void solve_1()
{
int len = strlen(s);
if(dig){
for(int i = 0;i < len;i++){
if('0' <= s[i] && s[i] <= '9'){
if(!low){
s[i] = 'a';
low++;
continue;
}
if(!upe){
s[i] = 'A';
upe++;
continue;
}
}
}
return;
}
if(low){
for(int i = 0;i < len;i++){
if('a' <= s[i] && s[i] <= 'z'){
if(!dig){
s[i] = '1';
dig++;
continue;
}
if(!upe){
s[i] = 'A';
upe++;
continue;
}
}
}
return;
}
if(upe){
for(int i = 0;i < len;i++){
if('A' <= s[i] && s[i] <= 'Z'){
if(!dig){
s[i] = '1';
dig++;
continue;
}
if(!low){
s[i] = 'a';
low++;
continue;
}
}
}
}
}
int main(){
cin>>T;
while(T--)
{
scanf("%s",s);
int len = strlen(s);dig = low = upe = ze = 0;
for(int i = 0;i < len;i++)
{
if('0' <= s[i] && s[i] <= '9') dig++;
if('a' <= s[i] && s[i] <= 'z') low++;
if('A' <= s[i] && s[i] <= 'Z') upe++;
}
if(!dig) ze++;if(!low) ze++;if(!upe) ze++;
if(ze == 1) solve();
if(ze == 2) solve_1();
printf("%s\n",s);
}
}
B. Relatively Prime Pairs
题意:要求你输出L~R中尽量多的互质的数对
题解:任何一对连续的自然数都是互质的
#include <bits/stdc++.h>
using namespace std;
long long L,R;
int main()
{
cin>>L>>R;
printf("YES\n");
for(long long i = L;i < R;i += 2){
printf("%lld %lld\n",i,i+1);
}
return 0;
}
C. Vasya and Multisets
题意:给你一个集合,然后将集合中的数分成两个集合,是的两个集合中间【好数】的数量相同,如果一个数在一个集合中只出现了一次,那么我们认为这个数是好数
题解:如果一个数只出现了一次,那么这么数一定会成为某一个集合的好数,而如果一个数如果出现了两次,那么这个数一定不会使某一个集合中的好数数量多于另外一个集合。如果一个数出现了超过三次,则可能产生一个好数或者是不产生。于是我们统计出现了一次的和三次及以上次数的数,然后对出现次数为1的数分奇偶讨论就好了
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,suma,sumb;
int sum[105];
bool t[105],flag;
vector<int>num[105];
int main()
{
scanf("%d",&n);
int v;
for(int i = 1;i <= n;i++){
scanf("%d",&v);
sum[v]++;
num[v].pb(i);
}
for(int i = 1;i <= 100;i++)
{
if(sum[i] == 1) {suma++;continue;}
if(sum[i] == 2) continue;
if(sum[i] >= 3) {sumb++;continue;}
}
if(suma & 1 && !sumb){printf("NO");return 0;}
if(suma & 1){
suma /= 2;flag = true;
for(int i = 1;i <= 100;i++){
if(sum[i] == 1 && suma) {
t[num[i][0]] = true;
suma--;
}
if(sum[i] >= 3 && flag){
t[num[i][0]] = true;
flag = false;
}
}
}
else {
suma /= 2;
for(int i = 1;i <= 100;i++){
if(sum[i] == 1 && suma) {
t[num[i][0]] = true;
suma--;
}
}
}
printf("YES\n");
for(int i = 1;i <= n;i++) if(t[i]) printf("A");else printf("B");
return 0;
}
D. Bicolorings
题意:在两行N列的方块上填上A和B字母,而如果A(B)字母四方向联通上还有A(B)字母,则认为所有的这些方块位于同一个区块上,要求你统计一共含有K个区块的方案数是多少
题解:很容易想到状压动规,因为每一列的方案数太固定,而且数量不大.
我们用dp[i][j][k]记录从第一列到第i行含有j个区块最后一列的状态为k的方案数。而我将状态作如下定义。
0 :A 1:B 2:A 3:B
A A B B
#include <bits/stdc++.h>
const int MOD = 998244353;
using namespace std;
int dp[1005][2005][4],n,m;
int main()
{
scanf("%d%d",&n,&m);
dp[1][1][0] = 1;dp[1][1][3]= 1;//0 :A 1:B 2:A 3B
dp[1][2][1] = 1;dp[1][2][2]= 1;// A A B B
for(int i = 1;i < n;i++)
for(int j = 1;j <= m;j++)
for(int k = 0;k <= 3;k++){
switch(k){
case 0: {
dp[i+1][j][0] += dp[i][j][k];
dp[i+1][j+1][1] += dp[i][j][k];
dp[i+1][j+1][2] += dp[i][j][k];
dp[i+1][j+1][3] += dp[i][j][k];
dp[i+1][j][0] %= MOD;
dp[i+1][j+1][1] %= MOD;
dp[i+1][j+1][2] %= MOD;
dp[i+1][j+1][3] %= MOD;
break;
}
case 1: {
dp[i+1][j][1] += dp[i][j][k];
dp[i+1][j][0] += dp[i][j][k];
dp[i+1][j][3] += dp[i][j][k];
dp[i+1][j+2][2] += dp[i][j][k];
dp[i+1][j][1] %= MOD;
dp[i+1][j][0] %= MOD;
dp[i+1][j][3] %= MOD;
dp[i+1][j+2][2] %= MOD;
break;
}
case 2: {
dp[i+1][j][2] += dp[i][j][k];
dp[i+1][j][0] += dp[i][j][k];
dp[i+1][j][3] += dp[i][j][k];
dp[i+1][j+2][1] += dp[i][j][k];
dp[i+1][j][2] %= MOD;
dp[i+1][j][0] %= MOD;
dp[i+1][j][3] %= MOD;
dp[i+1][j+2][1] %= MOD;
break;
}
case 3: {
dp[i+1][j][3] += dp[i][j][k];
dp[i+1][j+1][1] += dp[i][j][k];
dp[i+1][j+1][2] += dp[i][j][k];
dp[i+1][j+1][0] += dp[i][j][k];
dp[i+1][j][3] %= MOD;
dp[i+1][j+1][1] %= MOD;
dp[i+1][j+1][2] %= MOD;
dp[i+1][j+1][0] %= MOD;
break;
}
}
}
long long ans = 0;
ans += dp[n][m][0];ans += dp[n][m][1];
ans += dp[n][m][2];ans += dp[n][m][3];
ans %= MOD;
printf("%lld\n",ans);
return 0;
}