B.是一个DP
有一群人非常喜欢ACM 比赛，只要是跟ACM 相关的东西他们都非常在意。有一天，他们在鲁东大学的校园里看到了一个仅由”A”、”C”、”M”这三个字符组成的横幅。一时兴起，他们想要知道这个横幅里出现了几次”ACM”，你也是其中的一员，请编写一个程序解决这个问题。
Input
输入只有一行，包含一个字符串ss（length(s)≤1e5 ），只含有A、C、M 这三种字母。
Output
在一行中输出给定的字符串中含有多少个ACM。最终的结果可能比较大，请对结果用1000000007 取余。
Samples
CAACAM
2
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+100; const int mod=1000000007; int main(){ ll a=0,c=0,m=0; string str; cin>>str; for(int i=0;i<str.size();i++){ if(str[i]=='A'){ a++; } else if(str[i]=='C'){ c+=a; } else if(str[i]=='M'){ m+=c; } a=a%mod; c=c%mod; m=m%mod; } cout<<m%mod<<endl; }
最近，一直在IT行业"搬砖"的程序员小张考虑到自己日渐稀疏的发量，决定跳槽去做工地"搬砖"做一名真正的民工，可是小张进入工地的第二天，包工头就交代给了小张另一个对发量极为不利的烧脑任务。现在有MM(1≤M≤20)块工地的石材，高度分别HiHi米(1≤Hi≤1000,000)，这些石材的垒起来的总高度为SS，包工头让小张从这些石材中选出一些石材，垒出一个工作台，要求工作台的高度不能低于N 米(1≤N)，并且高出1≤N)，并且高出N米的长度越少越好，这样方便工人站在该工作台上作业。现在，你能帮小张从这M块石材中找出一个集合，垒起来的高度满足包工头的要求吗？如果不能满足条件，就输出能组成的最大高度。
Input
第一行MM 和NN 分别表示石材的个数和包工头要求的最低高度
第二到M+1M+1 行，H1,H2,…,HMH1,H2,…,HM 表示每块石材的高度
Output
输出一个整数，表示满足包工头要求的石材垒出的高度。
Samples
Source
2020年烟大校赛
一看数据范围1<=M<=20,第一反应就是二进制枚举
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+100; const int mod=1000000007; int a[maxn]; int main(){ int n,m; cin>>n>>m; ll p=0; for(int i=0;i<n;i++){ cin>>a[i]; p+=a[i]; } if(p<=n){ cout<<p<<endl; return 0; } int z=0x3f3f3f; int pp=0x3f3f3f; for(int i=0;i<(1<<n);i++){ ll sum=0; for(int j=0;j<n;j++){ if(i&(1<<j)){ sum+=a[j]; } } if(sum>=m){ if((sum-m)<=pp){ pp=sum-m; z=sum; } } } cout<<z<<endl; }
最近，一直在IT 行业"搬砖"的程序员小张考虑到自己日渐稀疏的发量，决定跳槽去做工地"搬砖"做一名真正的民工，可是小张进入工地的第一天，包工头就交代给了小张一个对发量极为不利的烧脑任务。现在有MM(1≤M≤200001≤M≤20000)块工地的石材，高度分别HiHi米(1≤Hi≤10000)，这些石材的垒起来的总高度为SS，包工头让小张从这些石材中选出一些石材，垒出一个工作台，要求工作台的高度不能低于NN 米(1≤N≤S1≤N≤S)，且石材的数目尽可能少。现在，你能帮小张从这M 块石材中找出一个集合，垒起来的高度满足包工头的要求吗？
Input
输入包含两行：
第一行MM 和NN 分别表示石材的个数和包工头要求的最低高度
第二到M+1M+1 行，H1,H2,…,HMH1,H2,…,HM 表示每块石材的高度
Output
输出一个整数，表示垒出不低于NN 米的最少石材数目。
Samples
Source
贪心：排序就行
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+100; const int mod=1000000007; ll a[maxn]; bool cmp(int a,int b){ return a>b; } int main(){ ll m,n; cin>>m>>n; for(int i=1;i<=m;i++){ cin>>a[i]; } sort(a+1,a+m+1,cmp); int sum=0; for(int i=1;i<=m;i++){ sum+=a[i]; if(sum>=n){ cout<<i<<endl; return 0; } } }
Description
圣诞节快要到了，圣诞老爷爷要打包n 份糖果分给小朋友们，假设圣诞老爷爷已经打包好了m 份糖果了。恰好轮到小明了，小明因为是里面最小的小朋友，所以小明可以要两份，并且可以提出要求，小明希望能分到这n 份糖果中最多糖果的一份和最少糖果的一份，并且里面的糖果恰好为a 和b 个，这可难到圣诞老爷爷了，打包好的不可以拆开，剩下的n−m 份都可以现装糖果，问能否满足小明的要求。
Inpu
输入包含两行：
第一行输入n,m,a,b 其中a 和b 的大小关系不确定。
第二行表示已经打包好的m 份糖果各自数量1≤n,m,a,b≤1000, m≤n
Output
输出YES 或者NO
Samples
Source
2020年烟大校赛
就是考虑的情况比较多（主要是枚举n-m)
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn=1e5+100; const int mod=1000000007; int aa[maxn]; int main(){ int n,m,a,b; cin>>n>>m>>a>>b; if(a>b){ swap(a,b); } int flag=1; for(int i=1;i<=m;i++){ cin>>aa[i]; if(aa[i]!=aa[1]){ flag=0;//有不相同的 } } if(a==b){ if(flag==1&&n>=2){ printf("YES "); } else{ printf("NO "); } return 0; } sort(aa+1,aa+m+1); int mi=aa[1]; int ma=aa[m]; if(n<=1){ printf("NO "); return 0; } else{ if(n-m>=2){//当有大于2个的时候 if(mi<a||ma>b){//只要超过a b就行 printf("NO "); } else{ printf("YES "); } return 0; } else if((n-m)==1){ if(mi<a||ma>b){//超过a b肯定是不行的 printf("NO "); return 0; } else if(mi==a||ma==b){//必须再超过a b的情况下，至少一个端点是a,b printf("YES "); return 0; } else{ printf("NO "); return 0; } } else if(n==m){//不能再加的话，那就是a==mi,b==ma if(a==mi&&b==ma){ printf("YES "); } else{ printf("NO "); } return 0; } } }
你喜欢套娃，根本停不下来。为了终止你的套娃行为，算法之神定义了两个函数f 和g（如下图所示）使得你的套娃行为最终停止下来。
为了惩罚你的套娃行为，算法之神交给了你一项任务：
你需要进行QQ 次查询。在每一次查询中，你将被给予三个数字l,rl,r 和kk。你需要在区间[l,r][l,r]上找到满足公式g(x)=kg(x)=k 的xx 的数量（l≤x≤rl≤x≤r）。
Input
第一行给出整数QQ( 1≤Q≤2∗1e5)表示有Q 次查询。
接下来的QQ 行，每行包括三个整数l,rl,r 和kk（1≤l≤r≤1e6 ，1≤k≤9）
Output
对于每一次查询，输出单独一行，表示本次查询的结果。
Samples
Hint
对于第一次查询，在区间[22,73]上，只有33 这个数字满足g(33)=9
因为g(33)=g(3∗3)=g(9)=9
本题输入量较大，建议使用scanf 函数
Source
2020年烟大校赛
输出的时候肯定要o(1)输出
所以要用前缀和的思想，处理出来
ss[i][k]是指的是前i个数字为k的个数
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<cstring> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; struct ios { inline char gc(){ static const int IN_LEN=1<<18|1; static char buf[IN_LEN],*s,*t; return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++; } template <typename _Tp> inline ios & operator >> (_Tp&x){ static char ch,sgn; ch = gc(), sgn = 0; for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';} for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0'); sgn&&(x=-x); return *this; } }io; const int maxn=1e6+1000; const int mod=1000000007; int a[maxn][11]; int ss[maxn][11]; int s[maxn]; int p[maxn]; void inint(){ for(register int i=1;i<=9;i++){ a[i][i]++; for(register int j=1;j<=9;j++){ ss[i][j]=ss[i-1][j]+a[i][j]; } s[i]=i; } int p; int sum,z; for(register int i=10;i<=1e6;i++){ p=i; sum=1; while(p){ if(p%10!=0){ sum*=(p%10); } p/=10; } z=s[sum]; a[i][z]++; for(register int j=1;j<=9;j++){ ss[i][j]=ss[i-1][j]+a[i][j]; } s[i]=z; } } int main(){ inint(); int t; int l,r,k; scanf("%d",&t); while(t--){ io>>l>>r>>k; printf("%d ",ss[r][k]-ss[l-1][k]); } return 0; }
一位拥有操作天气超能力的少女说道：“呐，现在开始就要放晴了哦~”
于是倾盆大雨停止了，天空放晴了……
她发现一些路边的石柱接住了一些雨水，她很好奇，这些石柱接住了多少雨水呢？如下图所示，这是nn 个石柱的侧视图，请计算按此排列的石柱接住了多少雨水（黑色为石柱，蓝色为雨水）。
Input
第一行，一个非负整数nn（0≤n≤3×1e4 ），表示有nn 个石柱。
第二行，nn 个非负整数组成的序列，表示石柱的高度height[i]（0≤height[i]≤1e5，0≤i<n）。
Output
输出只有一行，包含一个非负整数numnum 表示石柱可以接住的雨水量。
Samples
就是找一个最大值，这个最大值肯定是要有贡献的，两边枚举，
#include<iostream> #include<algorithm> #define INF 2e9+10000 using namespace std; const int maxn=5e6+100; int a[maxn]; int main(){ int n; cin>>n; int ma=0; for(int i=1;i<=n;i++){ cin>>a[i]; ma=max(ma,a[i]); } int p; for(int i=1;i<=n;i++){ if(a[i]==ma){ p=i; break; } } int l=1; int ans=0; for(int i=2;i<=p;i++){ if(a[i]>=a[l]){//比如说1 2 l=i;//那么这个1就没什么贡献了 } else{ ans+=(a[l]-a[i]);//加贡献 } } int r=n; for(int i=n-1;i>=p;i--){ if(a[i]>=a[r]){ r=i; } else{ ans+=(a[r]-a[i]); } } cout<<ans<<endl; }
L:
在杂志社工作的小鹏在休息日突然接到老板丢过来的文本编辑任务，要求将一串漏洞百出的文本A 编辑为小鹏认为合理的文本B，小鹏一次可以对一个字符进行插入、删除和替换操作，每种操作需要耗费的时间分别对应为x，y，z分钟，然而小鹏一心只想看TT 分钟后的英雄联盟S10 全球总决赛，亲眼见证最喜欢的大乌龟战队夺冠。问：小明是否可以准时观看比赛？若可以，请告诉小明完成工作后还有多久开始比赛，否则输出比赛已经开始了多久。
Input
A
B
X Y Z T
Output
Yes （or No） 和一个整数（如果时间准时看比赛，请输出Yes 0）
Samples
Hint
0<|A|,|B|<6000
1<x,y,z<10000
解析：这是一个dp的题，就是这两个字符串可能在更新后不同了，所以就有了
dp[i][j]=0x3f3f3f; dp[i][j]=min(dp[i][j],dp[i-1][j]+y);//删除 有可能不一样长（比如a长） dp[i][j]=min(dp[i][j],dp[i][j-1]+x);//插入 有可能（b长）
想想就知道了，第一个是如果a长的话就要删除，看看是不是最长
第二种就是，如果b长a短的话就是要添加
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=6e3+100; char a[maxn]; char b[maxn]; int dp[maxn][maxn]; int x,y,z,t;//插入、删除和替换 int main(){ scanf("%s",a+1); scanf("%s",b+1); scanf("%d%d%d%d",&x,&y,&z,&t); int lenn=strlen(a+1); int lenm=strlen(b+1); for(int i=1;i<=lenm;i++){ dp[0][i]=i*x; } for(int i=1;i<=lenn;i++){ dp[i][0]=i*y; } for(int i=1;i<=lenn;i++){ for(int j=1;j<=lenm;j++){ dp[i][j]=0x3f3f3f; dp[i][j]=min(dp[i][j],dp[i-1][j]+y);//删除 有可能不一样长（比如a长） dp[i][j]=min(dp[i][j],dp[i][j-1]+x);//插入 有可能（b长） if(a[i]==b[j]){ dp[i][j]=min(dp[i][j],dp[i-1][j-1]); } else{ dp[i][j]=min(dp[i][j],dp[i-1][j-1]+z); } } } int z=dp[lenn][lenm]; if(z<=t){ printf("Yes %d",t-z); } else{ printf("No %d",z-t); } }