【LGR-063】洛谷11月月赛 I & MtOI2019 Ex Div.2 (A-C)

[MtOI2019]黑蚊子多 ：

按题意模拟

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,t,q,nw;
bool w[1005];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    while(k--) scanf("%d",&q),w[q]=1; 
    while(nw<n){
        nw+=m; ++t;
        if(w[nw]) ++m;
    }printf("%d",t);
    return 0;
}

 

[MtOI2019]膜Siyuan：

枚举前两个，后面一个可以推出来

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int abs(int x){return x<0?-x:x;}
int n,m,t,v,w,g1,g2;
int x[7],y[7],z[7];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&x[i],&y[i],&z[i]);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=m;++j){
            w=abs(x[1]-i)^abs(y[1]-j)^9;
            g1=z[1]-w; g2=z[1]+w;
            if(g1==g2) g2=-1; //注意不要重复算
            if(g1>0&&g1<=m){
                v=1;
                for(int k=1;v&&k<=n;++k)
                    if(abs(x[k]-i)^abs(y[k]-j)^abs(z[k]-g1)^9) v=0;
                t+=v;
                //if(v) printf("%d %d %d
",i,j,g1);
            }
            if(g2>0&&g2<=m){
                v=1;
                for(int k=1;v&&k<=n;++k)
                    if(abs(x[k]-i)^abs(y[k]-j)^abs(z[k]-g2)^9) v=0;
                t+=v;
                //if(v) printf("%d %d %d
",i,j,g2);
            }
        }
    printf("%d",t);
    return 0;
}

 

[MtOI2019]时间跳跃：

不合法的方案满足的条件：最大边大于其余边的和

考虑求：总方案$-$不合法的方案

设$f[j]$为选择的边和为$j$的方案数

$w[j]$为选择的边和为$j$的方案的权值和

从小到大枚举边长$i$，累计最大边为$i$时不合法方案的权值和，然后跑01背包

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define N 5000
const int P=1e9+7;
int T,n;ll f[N+5],w[N+5],s[N+5];
ll Pow(ll x,int y){
    ll re=1;
    for(;y;y>>=1,x=x*x%P) if(y&1) re=re*x%P;
    return re;
}
void sol(){
    f[0]=1;
    for(int i=1;i<=N;++i){
        s[i]=s[i-1];
        for(int j=0;j<=i;++j) s[i]=(s[i]+(f[j]+w[j])%P)%P;
        for(int j=N;j>=i;--j){
            f[j]=(f[j]+f[j-i])%P; 
            w[j]=(w[j]+f[j-i]+w[j-i])%P;
        }
    }
}
int main(){
    sol(); scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        ll Q=Pow(Pow(2,n),P-2),K=1ll*n*Pow(2,n-1)%P;
        printf("%lld
",Q*((K-s[n])%P+P)%P);
    }return 0;
}