A 咪咪游戏

题意：判断一个字符串是否由只mq构成(之前在中石大OJ上做过一个类似的，比这个难些，然后我就按着上次那样去做，结果wa了。。嘤嘤嘤... (其实这道题还是蛮简单的。

代码 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return 1ll*x*f;
}
const int maxn=1e5+5;
int n;
char s[maxn]; 
int main(){
    n=read();//不用快读的话可以换成cin或者scanf
    while(n--){
        scanf("%s",s);
        int len=strlen(s),flag=1;//flag起记录作用
        if(len&1) printf("No\n");//字符串的长度必须为偶数
        else{
            for(int i=0;i<len-1;i+=2) 
                if(s[i]!='m'||s[i+1]!='q'){//碰到不是以mq循环的
                    flag=0;//记录下来
                    break;//终止循环
                }
            if(flag) printf("Yes\n");
            else printf("No\n");
        }                
    }
    return 0;
}

B 三角形

题意：有n个箱子，每个箱子里有a[i][0]件物品，给出每件物品的价值，每个箱子中选一件物品，求前k项最小价值的和。

思路：这道题只需要算出不同价值对应的方案数就可以了，用f[i][j]表示取i件总价值为j的物品的方案数，然后从小到大按价值枚举相加就行了。

代码 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return 1ll*x*f;
}
const int maxn=1e4+5;
ll n,k,ans,a[105][105],f[105][maxn];
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i][0]=read();//该箱子里的物品数
        for(int j=1;j<=a[i][0];j++) a[i][j]=read();
    }
    f[0][0]=1;//好多题都是这样规定的
    for(int i=1;i<=n;i++)
        for(int j=1;j<=a[i][0];j++)
            for(int p=a[i][j];p<=10000;p++){
                f[i][p]+=f[i-1][p-a[i][j]];
                f[i][p]=min(f[i][p],k);//方案数不能超过k
            }
    ll minn;
    for(int i=1;i<=10000;i++)//价值从1到10000
        if(f[n][i]){//如果存在该方案
            minn=min(k,f[n][i]);
            k-=minn;
            ans+=minn*i;
        }
    printf("%lld\n",ans);
    return 0;
}

C 区间加

题意：给定一个序列，每次对序列的一个区间加一，最后使得区间内的所有数都等于m，求有多少种方法。

思路：每一个区间都有左端点和右端点，且每个点只能用一次，用cnt记录现在还没有匹配的区间左端点的个数，用a[i]表示第i个点到m还需要加多少。则有以下结论：
1、a[i]-a[i-1]=-1,说明第i个点比第i-1个点需要加的次数少，则把右端点放在i-1处，此时左面有cnt个左端点，结果乘cnt，放后少了一个左端点，cnt--；
2、a[i]-a[i-1]=1,说明第i个点比第i-1个点需要加的次数多，则把左端点放在i处，++cnt；
3、a[i]==a[i-1],说明第i个点比第i-1个点需要加的次数相等，那么可以在i-1处放左端点，在i处放右端点，也可以不什么都不放，因此结果乘cnt+1。因为左端点数减一，右端点数加一，所以cnt不变。

代码 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return 1ll*x*f;
}
const int maxn=2e3+5;
const ll mod=998244355;
ll n,m,ans=1,cnt,a[maxn];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=m-read();
    for(int i=n+1;i>=1;i--) a[i]-=a[i-1];
    for(int i=1;i<=n;i++){
        if(abs(a[i])>1){//不能有差大于2的，因为任意两次区间加的起始，结束位置各不相同
            printf("0\n");
            return 0;
        }
        if(a[i]==-1) ans=(ans*cnt--)%mod;
        else if(a[i]==1) ++cnt;
        else ans=(ans*(cnt+1))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
  • 未完，待续...