AcWing第80场周赛
目录
1.末尾字母
2.寻找数字
3.摆放棋子
1.末尾字母
题目描述
给定一个由大小写字母，空格和问号组成的字符串。请你判断最后一个字母是否为元音字母，我们认为元音字母共有六个：A,E,I,O,U,Y（当然还有他们的小写）。
输入格式
一个由大小写字母，空格和问号组成的字符串。
输出格式
如果字符串中最后一个字母是元音字母输出YES，否则输出NO。
样例输入1
Is it melon?
样例输出1
NO
样例输入2
Is it apple?
样例输出2
YES
样例输入3
Is it an banana?
样例输出3
YES
样例输入4
Is it an apple and banana simultaneouSLY?
样例输出4
YES
思路：先找到最后一个字母，再判断是否为元音。
#include
#include
#include
using namespace std;int main()
{string x;while(getline(cin,x));int ans=0;for(int i=x.size()-1;i>=0;i--){if(x[i]>='a'&&x[i]<='z'||x[i]>='A'&&x[i]<='Z'){if(x[i]=='a'||x[i]=='A'||x[i]=='e'||x[i]=='E'||x[i]=='i'||x[i]=='I'||x[i]=='o'||x[i]=='O'||x[i]=='u'||x[i]=='U'||x[i]=='y'||x[i]=='Y'){cout<<"YES"< 2.寻找数字
题目描述
给定一个正整数n，请你找到一个正整数x，要求：
x>=n,x的各个位均不包含4和7以外的其他数字，且4和7的数量相等，满足这两个条件下x尽可能小。
输入描述
输入一个正整数n。
数据范围
1<=n<=1e9
样例输入1
4500
样例输出1
4747
样例输入2
47
样例输出2
47
思路：dfs思想，枚举每一位4和7，表示是否放4或者7，因为要求尽可能小，我们把所有符合条件的数取一个最小值即可，就是我们要找的数。
#include
#include
#include
using namespace std;typedef long long LL:LLn,ans=1<<60;
void dfs(LL num,int cnt4,int cnt7)
{if(num>=n&&cnt4==cnt7) ans=min(ans,num);if(num>n*100) return ;dfs(nums*10+4,cnt4+1,cnt7); //放4,4的数量加1dfs(nums*10+7,cnt4,cnt7+1); //放7,7的数量加1
}int main()
{cin>>n;dfs(0,0,0);cout< 3.摆放棋子
题目描述
给定n1个完全相同的黑子和n2个完全相同的白子，请你将所有的棋子摆成一排。
所有的棋子摆放完毕后需要满足：
1.不得有超过k1个黑子相邻。
2.不得有超过n2个白子相邻。
请问一共有多少种摆放方法。
样例输入1
2 1 1 10
样例输出1
1
样例输入2
2 3 1 2
样例输出2
5
样例输入3
2 4 1 1
样例输出3
0
思路1：dp问题，f[i][j][k][u]:表示用了i个黑子，j个白子，最后一段有k个黑子，u个白子的集合。
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=110;
const int mod=1e8;int f[N][N][20][20];int main()
{int n1,n2,k1,k2;cin>>n1,n2,k1,k2;f[0][0][0][0]=1;for(int i=0;i<=n1;i++)for(int j=0;j<=n2;j++)for(int k=0;k<=k1;k++)for(int u=0;u<=k2;u++){if(k>0&&i>0) f[i][j][k][0]=(f[i][j][k][0]+f[i-1][j][k-1][u])%mod;if(u>0&&j>0) f[i][j][0][u]=(f[i][j][0][u]+f[i][j-1][k][u-1])%mod;}ll ans=0;for(int k=0;k<=k1;k++) ans=(ans+f[n1][n2][k][0])%mod;for(int u=0;u<=k2;u++) ans=(ans+f[n1][n2][0][u])%mod;cout< 思路2：dfs思想。类似于第二题的方法。
#include
#include
#include
using namespace std;typedef long long LL;
typedef pair PII;const int N=1e6+10,mod=1e8;int n1,n2,k1,k2;
int mp[110][110][20][20];int dfs(int u,int v,int w,int x)
{if(!u&&!v) return 1; //如果黑子和白子都放完了，那么就是一种方案if(mp[u][v][w][x]!=-1) return mp[u][v][w][x];//如果已经是放过的一种方案，那么返回即可。int res=0;if(u&&w+1<=k1) res=(res+dfs(u-1,v,w+1,0))%mod; // 放黑子if(v&&x+1<=k2) res=(res+dfs(u,v-1,0,x+1))%mod; // 放白子mp[u][v][w][x]=res; //更新答案return res; //返回数目
}int main()
{cin>>n1>>n2>>k1>>k2;memset(mp,-1,sizeof mp);cout<