题意:
给出一个字符串,?表示待填字母。问有多少种方式使得长度为偶数的子串都满足元音字母和辅音字母个数相同。
元音字母为a , e , i , o , u , y
字符串长度< = 100
思路:
显然只需要按照元音-辅音-元音-辅音这样依次构造就好。
先排除几种不合法的情况,对于剩下的情况尝试着计算的同时,也要判断构造出的字符串是否合法。
代码:
张巨的简短代码:
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 2e5 + 7; const double pi = 3.14159265358979; ll n,m; string str; bool check(char c){ if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='y') return 1; return 0; } ll ju(bool flag){ ll res=1; for(int i=1;i<=n;i++){ if(str[i]=='?'){ if(flag) res=res*6; else res=res*20; flag=!flag; continue; } if(check(str[i])==flag){ flag=!flag; }else { return 0; } } return res; } int main() { cin>>str; n=str.size(); str=" "+str; ll ans=0; ans+=ju(1); ans+=ju(0); /*if(str[1]=='?'){ } if(check(str[1])) flag=1; */ cout<<ans<<endl; return 0; }
我的垃圾代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int>PII; inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} #define read read() #define debug(x) cout<<#x<<":"<<x<<endl; const int maxn=35050,inf=0x3f3f3f3f; const double PI=3.14159265358979; char s[110]; int check(char ch){ if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u'||ch=='y') return 1; return 0; } int main(){ cin>>s+1; int n=strlen(s+1); int cnt=0; for(int i=1;i<=n;i++) if(s[i]=='?'){ cnt++; } if(cnt==n){ ll t1=n/2,t2=n-t1; ll ans=pow(6,t1)*pow(20,t2)+pow(6,t2)*pow(20,t1); cout<<ans<<endl; return 0; } bool flag=1; for(int i=2;i<n;i++){ if(s[i]=='?'){//该位待填 if(s[i+1]!='?'&&s[i-1]!='?'&&check(s[i-1])&&!check(s[i+1])){ flag=0;break; } if(s[i-1]!='?'&&s[i+1]!='?'&&!check(s[i-1])&&check(s[i+1])){ flag=0;break; } } else{ if(s[i]!='?'&&s[i-1]!='?'&&check(s[i])==check(s[i-1])){ flag=0;break; } if(s[i]!='?'&&s[i+1]!='?'&&check(s[i])==check(s[i+1])){ flag=0;break; } } } if(!flag){ puts("0");return 0; } ll ans=1; int pos=-1; for(int i=1;i<=n;i++) if(s[i]!='?'){ pos=i;break; } for(int i=pos-1;i>=1;i--) if(s[i]=='?'){ if(check(s[i+1])){ ans=ans*20;s[i]='b'; } else{ ans=ans*6;s[i]='a'; } } else{ if(check(s[i])==check(s[i+1])){ flag=0;break; } } if(!flag){ puts("0");return 0; } for(int i=pos+1;i<=n;i++) if(s[i]=='?'){ if(check(s[i-1])){ ans=ans*20;s[i]='b'; } else{ ans=ans*6;s[i]='a'; } } else{ if(check(s[i])==check(s[i-1])){ flag=0;break; } } if(!flag){ puts("0");return 0; } write(ans); return 0; }