A.方格游戏

仔细看题!!!这题就是一个大分类讨论

140行让我给调出来了。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=1000000007;
const int inv2=500000004;
const int inv3=333333336;
int sum1(int x,int y){return 1ll*(x+y)*(y-x+1)%mod*inv2%mod;}
int S(int x){return 1ll*x*(x+1)%mod*(2*x+1)%mod*inv2%mod*inv3%mod;}
int sum2(int x,int y){return (S(y)-S(x-1)+mod)%mod;}
int i,j,k,n,m,x,y,t,p,ans;
int S1[100010],S2[100010];
struct matrix{int u,d,l,r;}M[100010];
int calc1(int n,int m){
    int ret1=1ll*n*m%mod*m%mod*sum1(0,n-1)%mod-1ll*m*m%mod*sum2(0,n-1)%mod;
    if (ret1<0)ret1+=mod;
    int ret2=1ll*n*m%mod*n%mod*sum1(0,m-1)%mod-1ll*n*n%mod*sum2(0,m-1)%mod;
    if (ret2<0)ret2+=mod;
    return (ret1+ret2)%mod;
}
bool cmp1(const matrix &a,const matrix &b){
    return a.l<b.l;
}
bool cmp2(const matrix &a,const matrix &b){
    return a.u<b.u;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for (i=1;i<=p;i++)scanf("%d%d%d%d",&M[i].u,&M[i].d,&M[i].l,&M[i].r);
    ans=calc1(n,m);
//    printf("1----%d\n",ans);
    //-----ok-----
    for (i=1;i<=p;i++){
        int s1,s2;
        s1=1ll*m*(M[i].r-M[i].l+1)%mod;
        s2=((sum2(M[i].u,M[i].d)-1ll*(n+1)*sum1(M[i].u,M[i].d)%mod)%mod
        +1ll*n*(n+1)%mod*inv2%mod*(M[i].d-M[i].u+1)%mod)%mod;
        ans=(ans-1ll*s1*s2%mod)%mod;
        if (ans<0)ans+=mod;
//        printf("1.5---->%d\n",ans);
        s1=1ll*n*(M[i].d-M[i].u+1)%mod;
        s2=((sum2(M[i].l,M[i].r)-1ll*(m+1)*sum1(M[i].l,M[i].r)%mod)%mod
        +1ll*m*(m+1)%mod*inv2%mod*(M[i].r-M[i].l+1)%mod)%mod;
        ans=(ans-1ll*s1*s2%mod)%mod;
        if (ans<0)ans+=mod;
    }
    for (i=1;i<=p;i++)ans=(ans+calc1(M[i].d-M[i].u+1,M[i].r-M[i].l+1))%mod;
//    printf("2----%d\n",ans);
    sort(M+1,M+1+p,cmp1);
    for (i=1;i<=p;i++)S1[i]=(S1[i-1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
    for (i=p;i>=1;i--)S2[i]=(S2[i+1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
    int cnt1=0;
    for (i=2;i<=p;i++){
        int s1,s2,s3,ret;
        s1=1ll*(M[i].r-M[i].l+1)*inv2%mod;
        s2=1ll*(M[i].l+M[i].r)*(M[i-1].r-M[i-1].l+1)%mod;
        s3=2ll*sum1(M[i-1].l,M[i-1].r)%mod;
        ret=1ll*s1*(s2-s3)%mod*(M[i-1].d-M[i-1].u+1)%mod*(M[i].d-M[i].u+1)%mod;
        ret=(ret+1ll*S1[i-2]*sum1(M[i].l-M[i-1].l,M[i].r-M[i-1].l)%mod*(M[i].d-M[i].u+1)%mod)%mod;
        if (i!=p){
            ret=(ret+1ll*S2[i+1]*S1[i-2]%mod*(M[i].l-M[i-1].l)%mod)%mod;
            ret=(ret+1ll*S2[i+1]*sum1(M[i].l-M[i-1].r,M[i].l-M[i-1].l)%mod*(M[i-1].d-M[i-1].u+1)%mod)%mod;
        }
//        printf("ret:%d\n",ret);
        ans=(ans+ret)%mod;
    }
//    printf("2.5----%d\n",ans);
    sort(M+1,M+1+p,cmp2);
    for (i=1;i<=p;i++)S1[i]=(S1[i-1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
    for (i=p;i>=1;i--)S2[i]=(S2[i+1]+1ll*(M[i].d-M[i].u+1)*(M[i].r-M[i].l+1)%mod)%mod;
    int cnt2=0;
    for (i=2;i<=p;i++){
        int s1,s2,s3,ret;
        s1=1ll*(M[i].d-M[i].u+1)*inv2%mod;
        s2=1ll*(M[i].u+M[i].d)*(M[i-1].d-M[i-1].u+1)%mod;
        s3=2ll*sum1(M[i-1].u,M[i-1].d)%mod;
        ret=1ll*s1*(s2-s3)%mod*(M[i-1].r-M[i-1].l+1)%mod*(M[i].r-M[i].l+1)%mod;
//        printf("ret0.5:%d\n",ret);
        ret=(ret+1ll*S1[i-2]*sum1(M[i].u-M[i-1].u,M[i].d-M[i-1].u)%mod*(M[i].r-M[i].l+1)%mod)%mod;
        if (i!=p){
            ret=(ret+1ll*S2[i+1]*S1[i-2]%mod*(M[i].u-M[i-1].u)%mod)%mod;
            ret=(ret+1ll*S2[i+1]*sum1(M[i].u-M[i-1].d,M[i].u-M[i-1].u)%mod*(M[i-1].r-M[i-1].l+1)%mod)%mod;
        }
//        printf("ret:%d\n",ret);
        ans=(ans+ret)%mod;
    }
//    printf("3----%d\n",ans);
    for (i=1;i<=p;i++){
        int RET=0,RET1=0,RET2=0,RET3=0,ret1,ret2,ret3;
        //RET1:2lx~lx+rx
        //RET2:lx+rx+1~2*rx
        //RET3:|i2-i1|
        //-------part1
        ret1=sum2((M[i].l+M[i].l)%mod,(M[i].l+M[i].r)%mod);
        ret2=1ll*(3-4ll*M[i].l%mod)
        *sum1((M[i].l+M[i].l)%mod,(M[i].l+M[i].r)%mod)%mod;
        ret3=1ll*(M[i].r-M[i].l+1)
        *(4ll*M[i].l%mod*M[i].l%mod-6ll*M[i].l%mod+2)%mod;
        RET1=((ret1+ret2)%mod+ret3)%mod;
//        printf("RET1:%d\n",RET1);
        if (RET1<0)RET1+=mod;
        ret1=sum2((M[i].l+M[i].r+1)%mod,(M[i].r+M[i].r)%mod);
        ret2=1ll*(4ll*M[i].r%mod+3)%mod
        *sum1((M[i].l+M[i].r+1)%mod,(M[i].r+M[i].r)%mod)%mod;
        ret3=1ll*(M[i].r-M[i].l)*(M[i].r+M[i].r+2)%mod*(1+2*M[i].r)%mod;
        RET2=((ret1-ret2)%mod+ret3)%mod;
//        printf("RET2:%d\n",RET2);
        if (RET2<0)RET2+=mod;
        RET3=2ll
        *(1ll*(M[i].r-M[i].l+1)*sum1(1,M[i].r-M[i].l)%mod
        -sum2(1,M[i].r-M[i].l))%mod;
        if (RET3<0)RET3+=mod;
//        printf("RET3:%d\n",RET3);
        RET=(RET1+RET2-RET3)%mod;if (RET<0)RET+=mod;
        ans=(ans+1ll*RET*(M[i].u-1)%mod*(n-M[i].d)%mod)%mod;
        //--------part2
        ret1=sum2((M[i].u+M[i].u)%mod,(M[i].u+M[i].d)%mod);
        ret2=1ll*(3-4ll*M[i].u%mod)
        *sum1((M[i].u+M[i].u)%mod,(M[i].u+M[i].d)%mod)%mod;
        ret3=1ll*(M[i].d-M[i].u+1)
        *(4ll*M[i].u%mod*M[i].u%mod-6ll*M[i].u%mod+2)%mod;
        RET1=((ret1+ret2)%mod+ret3)%mod;
        if (RET1<0)RET1+=mod;
        ret1=sum2((M[i].u+M[i].d+1)%mod,(M[i].d+M[i].d)%mod);
        ret2=1ll*(4ll*M[i].d%mod+3)%mod
        *sum1((M[i].u+M[i].d+1)%mod,(M[i].d+M[i].d)%mod)%mod;
        ret3=1ll*(M[i].d-M[i].u)*(M[i].d+M[i].d+2)%mod*(1+2*M[i].d)%mod;
        RET2=((ret1-ret2)%mod+ret3)%mod;
        if (RET2<0)RET2+=mod;
        RET3=2ll
        *(1ll*(M[i].d-M[i].u+1)*sum1(1,M[i].d-M[i].u)%mod
        -sum2(1,M[i].d-M[i].u))%mod;
        if (RET3<0)RET3+=mod;
        RET=(RET1+RET2-RET3)%mod;if (RET<0)RET+=mod;
        ans=(ans+1ll*RET*(M[i].l-1)%mod*(m-M[i].r)%mod)%mod;
    }
    if (ans<0)ans+=mod;
    printf("%d\n",ans);
    return 0;
}

B.切切糕

有趣的博弈论。

考虑从小到大切,让对手为难。。。

考虑n=1,m=1时,直接把一个糕平均分成两块

我们可以联想到最佳的时候应该是无论用不用优先权最后结果应该是一样的

然后DP

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int i,j,k,n,m,x,y,t;
int a[5010];
double f[5010][5010];
bool cmp(int a,int b){return a>b;}
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n,cmp);
    for (i=1;i<=n;i++)f[i][0]=f[i-1][0]+a[i];
    for (i=1;i<=n;i++)
        for (j=1;j<=min(i,m);j++){
            double x=(f[i-1][min(j,i-1)]-f[i-1][j-1]+a[i])/2.0;
            if (x<0.0)f[i][j]=a[i]+f[i-1][min(i-1,j)];else f[i][j]=x+f[i-1][j-1];
        }
    printf("%.6lf\n",f[n][m]);
    return 0;
}

E.区间矩阵乘法

嘛坑点在题目没有直接告诉你d<=sqrt(n)。。。。

求sqrt(n)个前缀和什么的就行了

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int i,j,k,n,m,x,y,t,d,p1,p2;
unsigned int p[N],sum[N][450],a[N];
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;i++)scanf("%d",&a[i]);
    for (i=1;i<=n;i++)p[i]=p[i-1]+a[i];
    int s=sqrt(n);
    for (i=1;i<=s;i++){
        for (j=1;j<=n;j++)
            sum[j][i]=sum[max(0,j-i)][i]+a[j];
    }
    scanf("%d",&m);
    while (m--){
        scanf("%d%d%d",&d,&p1,&p2);
        unsigned int ans=0;
        for (j=0;j<=d-1;j++)
            ans+=(p[p2+d*j+d-1]-p[p2+d*j-1])*(sum[p1+d*(d-1)+j][d]-sum[max(0,p1+j-d)][d]);
        printf("%u\n",ans);
    }
    return 0;
}

F.棋盘

一开始想成网络流了。。。

其实比较麻烦的是两列只有一种填法且列号差为奇数的情况

考虑黑白染色,从上往下填黑,从下往上填白,尽量多填白格就行了

题解的图
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int i,j,k,n,m,x,y,t;
int ans[310][310];
int a[310],b[310];
bool check(int x,int y){
    if (ans[x][y]||ans[x-1][y]||ans[x][y-1]||ans[x][y+1]||ans[x+1][y])return 0;
    return 1;
}
int color(int x,int y){return (x^y)&1;}
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d",&a[i]);
        if (a[i]>(n+1)/2){printf("No\n");return 0;}
    }
    if (n%2==0){
        for (j=1;j<=m;j++)
            for (i=1;i<=n;i++)
                if (a[j]&&check(i,j)){a[j]--;ans[i][j]=1;}
    }
    else{
        for (j=1;j<=m;j++)
            if (a[j]==(n+1)/2){
                b[++b[0]]=j;
                for (i=1;i<=n;i++)
                    if (check(i,j)&&a[j]){
                        ans[i][j]=1;a[j]--;
                    }
            }
        for (j=b[1]-1;j>=1;j--){
            for (i=1;i<=n;i++)
                if (check(i,j)&&a[j]){
                    ans[i][j]=1;a[j]--;
                }
        }
        for (k=1;k<b[0];k++){
            if ((b[k+1]-b[k])%2==0){
                for (j=b[k]+1;j<b[k+1];j++)
                    for (i=1;i<=n;i++)
                        if (a[j]&&check(i,j)){
                            ans[i][j]=1;a[j]--;
                        }
            }
            else{
                for (j=b[k]+1;j<b[k+1];j++){
                    int t=0;
                    for (i=n;i>=1;i--)
                        if (check(i,j)&&color(i,j-b[k])==0&&a[j]){
                            ans[i][j]=1;a[j]--;t++;
                        }
                    for (i=1;i<=n;i++)
                        if (check(i,j)&&color(i,j-b[k])==1&&a[j]){
                            ans[i][j]=1;a[j]--;
                        }
                }
            }
        }
        for (j=b[b[0]]+1;j<=m;j++)
            for (i=1;i<=n;i++)
                if (check(i,j)&&a[j]){
                    ans[i][j]=1;a[j]--;
                }
        for (j=1;j<=m;j++)if (a[j]){printf("No\n");return 0;}
    }
    printf("Yes\n");
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)printf("%d",ans[i][j]);
        printf("\n");
    }
    return 0;
}

G.密集子图

一道普普通通的状压DP。。。

点分成三类讨论,按照BFS顺序更新。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[15][600000];
int w[15][15];
const int mod=998244353;
int mi(int x,int y){
    if (y==0)return 1;
    int t=mi(x,y>>1);
    t=1ll*t*t%mod;
    if (y&1)t=1ll*t*x%mod;
    return t;
}
int i,j,k,n,m,x,y,t,p,q,K;
int id1[15],id2[15],ID[15],M[15];
bool check(int x){
    for (int i=1;i<=n;i++,x/=3)
        if (x%3==0)return 0;
    return 1;
}
int main(){
    scanf("%d%d",&n,&K);
    M[0]=1;for (i=1;i<=12;i++)M[i]=3*M[i-1];
    for (i=1;i<=n*(n-1);i++){
        scanf("%d%d%d%d",&x,&y,&p,&q);
        w[x][y]=1ll*p*mi(q,mod-2)%mod;
    }
    int NUM=mi(3,n);f[0][2]=1;p=q=0;
    for (i=0;i<K;i++)
        for (int P=0;P<NUM;P++)
            if (f[i][P]){
                y=P;id1[0]=0;id2[0]=0;x=0;memset(ID,0,sizeof ID);
                for (q=1;q<=n;q++,y/=3)
                    if (y%3==2)id1[++id1[0]]=q,ID[q]=1;
                    else if (y%3==1)id2[++id2[0]]=q,ID[q]=1;
                    else if (y%3==0)x=x+(1<<(q-1));
                for (j=x;j;j=(j-1)&x){
                    y=j;p=1;int ww=0;
                    for (q=1;q<=n;q++,y>>=1){
                        int W;
                        if (!(y&1)){ww=ww+ID[q]*M[q-1];continue;}
                        ww=ww+2*M[q-1];
                        W=1;for (k=1;k<=id1[0];k++)W=1ll*W*(1-w[id1[k]][q])%mod;p=1ll*p*(1-W)%mod;
                        W=1;for (k=1;k<=id2[0];k++)W=1ll*W*(1-w[id2[k]][q])%mod;p=1ll*p*W%mod;
                        if (p<0)p+=mod;
                    }
                    f[i+1][ww]=(f[i+1][ww]+1ll*f[i][P]*p%mod)%mod;
                }
            }
    int ans=0;
    for (i=0;i<=K;i++)
        for (j=0;j<NUM;j++)
            if (check(j)&&f[i][j]){
                ans=(ans+f[i][j])%mod;
            }
    printf("%d\n",ans);
    return 0;
}

H.线段树

就先处理左右两个子树自己内部的贡献,再处理左子树对右子树的贡献和右子树对左子树的贡献,记忆化搜索即可。

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T;
long long n;
const int mod=1000000007;
struct data{
    long long sumL,sumR;
    int mark;
    long long ans;
};
map<long long,data>mp;
void dfs(long long n){
    if (mp[n].mark)return;
    mp[n].mark=1;
    long long R=n>>1,L=n-R;
    dfs(L);dfs(R);
    mp[n].ans=(mp[L].ans+mp[R].ans+1)%mod;
    mp[n].ans=(mp[n].ans+1ll*mp[L].sumR*(R%mod)%mod)%mod;
    mp[n].ans=(mp[n].ans+1ll*mp[R].sumL*(L%mod)%mod)%mod;
    mp[n].sumL=(mp[L].sumL+mp[R].sumL)%mod;mp[n].sumL=(mp[n].sumL+R%mod)%mod;
    mp[n].sumR=(mp[L].sumR+mp[R].sumR)%mod;mp[n].sumR=(mp[n].sumR+L%mod)%mod;
    mp[n].ans=(mp[n].ans+n-2)%mod;
    return ;
}
int main(){
    scanf("%d",&T);
    mp[1].mark=1;mp[1].ans=1;
    while (T--){
        scanf("%lld",&n);
        dfs(n);
        printf("%lld\n",mp[n].ans);
    }
    return 0;
}

J.合法序列

暴力枚举前(1<<k)位,然后DP

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod=998244353;
int i,j,k,n,m,x,y,t;
int f[510][16],a[16],ans;
int main(){
    scanf("%d%d",&n,&k);
    for (int p=0;p<(1<<(1<<k));p++){
        t=p;int flag=0;
        for (i=0;i<(1<<k);i++)a[i]=t&1,t>>=1;
        for (i=0;i<=(1<<k)-k;i++){
            t=0;for (j=i;j<=i+k-1;j++)t=t*2+a[j];
            if (a[t]==0){
                flag=1;break;
            }
        }
        if (flag)continue;
        memset(f,0,sizeof f);
        t=0;for (j=(1<<k)-k;j<=(1<<k)-1;j++)t=t*2+a[j];
        f[(1<<k)-1][t]=1;
        for (i=(1<<k);i<n;i++)
            for (j=0;j<(1<<k);j++){
                if (f[i-1][j]){
                    for (int num=0;num<=1;num++){
                        t=((j<<1)&((1<<k)-1))+num;
                        if (a[t])f[i][t]=(f[i][t]+f[i-1][j])%mod;
                    }
                }
            }
        for (i=0;i<(1<<k);i++)ans=(ans+f[n-1][i])%mod;
    }
    printf("%d\n",ans);
    return 0;
}

K.独立

注意输入的是随机数据!!!

反正就是找环然后暴力枚举选还是不选

注意环上的点不要多加!!!

#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
const int q=101;
const int b=137;
const int p=1000000007;
int i,j,k,n,m,x,y,t,w[N],B[N];
int a[N],c[N],fi[N],ne[N],la[N];
int s[N],cir[N],ins[N];
map<pair<int,int>,int>mp;
long long f[N][2],ans;
void add(int x,int y,int t){
    k++;a[k]=y;c[k]=t;
    if (fi[x]==0)fi[x]=k;else ne[la[x]]=k;
    la[x]=k;
}
void dfs1(int x,int fa){
    B[x]=1;s[++s[0]]=x;ins[x]=1;
    for (int i=fi[x];i;i=ne[i])
        if (a[i]!=fa){
            if (ins[a[i]]==1&&B[a[i]]==1){
                B[a[i]]=2;
                cir[++cir[0]]=a[i];
            }
            else if (!B[a[i]]){
                dfs1(a[i],x);
            }
        }
    ins[x]=0;
}
long long DP(int x,int fa){
    B[x]=3;f[x][0]=0;f[x][1]=w[x];
    for (int i=fi[x];i;i=ne[i])
        if (a[i]!=fa){
            if (B[a[i]]==1)DP(a[i],x);
            f[x][0]+=max(f[a[i]][0],f[a[i]][1]);
            f[x][1]+=max(f[a[i]][0],f[a[i]][1]-c[i]);
        }
    return max(f[x][0],f[x][1]);
}
long long work(int x){
    s[0]=0;cir[0]=0;
    dfs1(x,-1);
    long long mx=0;
    for (int P=0;P<(1<<cir[0]);P++){
        int t=P;long long tmp=0;
        for (int i=1;i<=s[0];i++)if (B[s[i]]==3)B[s[i]]=1;
        for (int i=1;i<=cir[0];i++){
            int u=t&1;t>>=1;
            if (u==0){
                f[cir[i]][0]=0;f[cir[i]][1]=-(1ll<<60);
            }
            else{
                f[cir[i]][0]=-(1ll<<60);f[cir[i]][1]=0;tmp+=w[cir[i]];
            }
        }
        for (int i=1;i<=s[0];i++)if (B[s[i]]==1)tmp+=DP(s[i],-1);
        mx=max(mx,tmp);
    }
    return mx;
}
int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&x,&y,&w[0],&t);
    for (i=1;i<=n;i++)w[i]=(1ll*q*w[i-1]%p+b)%p;
    for (i=1;i<=m;i++){
        x=(1ll*x*q%p+b)%p;y=(1ll*y*q%p+b)%p;t=(1ll*t*q%p+b)%p;
        int xx=x%n+1,yy=y%n+1;
        if (xx>yy)swap(xx,yy);
        if (xx!=yy&&!mp[make_pair(xx,yy)]){
            mp[make_pair(xx,yy)]=1;
            add(xx,yy,t);
            add(yy,xx,t);
        }
    }
    for (i=1;i<=n;i++)if (B[i]==0)ans+=work(i);
    printf("%lld\n",ans);
    return 0;
}

M.自白书

都不好意思说这是一道题。。。

#include <cstdio>
using namespace std;
int main() {
    printf("kecheng");
}


告别纷扰,去寻找生活的宝藏。