2015 Multi-University Training Contest

orz hhw posted @ 2015年8月01日 00:50 in 做题记录 with tags 比赛 游记 做题记录 多校 , 695 阅读

2015多校赛,历年来最屌的镇海代表队出征了,除了主力队,连人都凑不齐

由于蒟蒻水平太低,英语太烂,只好去蒟蒻队,每次都被主力队碾压,现在连高一都打不过啦

由于爆OJ的癖好,每次都在A题相同的队中排名倒数QAQ

总做题数:36

2015 Multi-University Training Contest 1

开场看T1,看了将近半小时不会,但已经有一堆人A了。。

然后看了会T7,虽然看不太懂英文,但感觉是一道最短路+网络流裸题。。

这时已经过去将近一个小时了,黈力告诉我T9就是虚树裸题,看了一下,发现果然是这样

正当我准备拿个板子去做T9时,YY大爷说T2是RMQ,不过有T组数据要T,我说你**吗,RMQ询问O(1)你不造吗,但他还是弃疗了

于是拉了个RMQ板秒了T2,但由于姿势不太对,CE了两发

然后把T9写完了,WA了两发,只好把数组一个一个清空,总算A了

然后LX翻译了T7,果然是最短路+网络流裸题,马上秒了

然后1001竺主力做了,但他RE了,我看来十多分钟,虽然没看懂他程序什么意思,但还是发现了错误。。

然后发现1006就是黈力那天的JOI原题,把他的程序借鉴了一下

然后一直在弄1012,但没想出来,后来发现T12是LZN树裸题。。

这场主力队RANK12,我们蒟蒻队RANK23。。。发现我除了拉板似乎什么都不会。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define N 111111
using namespace std;
typedef long long LL;
LL T,n,i,j,k,ans,head,tail,a[N],l2[N],er[20],f[N][20],g[N][20];
LL getmax(LL x,LL y){
    LL k=l2[y-x+1];
    return max(g[x][k],g[y-er[k]+1][k]);
}
LL getmin(LL x,LL y){
    LL k=l2[y-x+1];
    return min(f[x][k],f[y-er[k]+1][k]);
}
int main(){
    scanf("%I64d",&T);
    while(T--){
        memset(f,0,sizeof(f));memset(g,0,sizeof(g));
        scanf("%I64d%I64d",&n,&k);ans=0;
        for(i=1;i<=n;i++)scanf("%I64d",&a[i]);
        for(i=1;i<=n;i++)f[i][0]=g[i][0]=a[i];
        er[0]=1;for(i=1;i<20;i++)er[i]=er[i-1]*2;
        l2[0]=-1;  
         for(i=1;i<=n;i++)l2[i]=(i&(i-1))?l2[i-1]:l2[i-1]+1;  
        for(j=1;j<20;j++)
            for(i=1;i+er[j]-1<=n;i++){
                f[i][j]=min(f[i][j-1],f[i+er[j-1]][j-1]);
                g[i][j]=max(g[i][j-1],g[i+er[j-1]][j-1]);
            }
        head=1;ans=1;
        for(i=2;i<=n;i++){
            while(head<=i&&getmax(head,i)-getmin(head,i)>=k)head++;
            ans+=i-head+1;
        }
        printf("%I64d\n",ans);
    }
}
#include<cstdio>
#include<cstring>
#define N 2222
#define M 222222
#define inf 1e16
using namespace std;
long long n,m,k,i,j,tot,tot2,max,flow,tmp,s,t,u,head,tail,p,last[M],value[M],next[M],first[N],first2[N],cur[N],dist[N],dis[N],pre[N],lj[N],numb[N],x[M],y[M],z[M],last2[M],cost[M],next2[M],q[M<<4];
bool v[N];
void insert2(long long x,long long y,long long z){
    last2[++tot2]=y;cost[tot2]=z;next2[tot2]=first2[x];first2[x]=tot2;
    last2[++tot2]=x;cost[tot2]=z;next2[tot2]=first2[y];first2[y]=tot2;
}
void insert(long long x,long long y,long long z){
    last[tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot++;
    last[tot]=x;value[tot]=0;next[tot]=first[y];first[y]=tot++;
}
long long ISAP(){
    memset(pre,-1,sizeof(pre));memset(numb,0,sizeof(numb));memset(dist,0,sizeof(dist));
    for(i=0;i<=n;i++)cur[i]=first[i];
    u=s;numb[0]=n;max=0;
    while(dist[s]<n){
        if(u==t){
            flow=inf;
            for(i=s;i!=t;i=last[cur[i]])if(value[cur[i]]<flow)flow=value[cur[u=i]];
            for(i=s;i!=t;i=last[cur[i]]){
                value[cur[i]]-=flow;
                value[cur[i]^1]+=flow;
            }
            max+=flow;
        }
        for(i=cur[u];i!=-1;i=next[i])if(value[i]&&dist[last[i]]+1==dist[u])break;
        if(i!=-1){
            cur[u]=i;
            pre[last[i]]=u;
            u=last[i];
        }else{
            if(0==--numb[dist[u]])break;
            for(tmp=n,i=cur[u]=first[u];i!=-1;i=next[i])
                if(value[i]&&dist[last[i]]<tmp)tmp=dist[last[i]];
            ++numb[dist[u]=tmp+1];
            if(u!=s)u=pre[u];
        }
    }
    return max;
}
int main(){
    while(scanf("%lld%lld",&n,&m)!=EOF){
    tot=2;tot2=0;
    memset(first2,0,sizeof(first2));
    memset(last,0,sizeof(last));
    memset(value,0,sizeof(value));
    memset(next,0,sizeof(next));
    memset(last2,0,sizeof(last2));
    memset(cost,0,sizeof(cost));
    memset(next2,0,sizeof(next2));
    memset(first,-1,sizeof(first));
    memset(lj,0,sizeof(lj));
    for(i=1;i<=m;i++){
        scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
        insert2(x[i],y[i],z[i]);
    }
    for(i=1;i<=n;i++)dis[i]=inf;
    for(i=1;i<=n;i++)lj[i]=inf;
    head=0;tail=1;s=1;t=n;dis[s]=0;q[1]=s;v[s]=1;lj[s]=0;
    while(head<tail)
        for(i=first2[p=q[++head]],v[p]=0;i;i=next2[i])
            if(dis[p]+cost[i]<dis[j=last2[i]]||(dis[p]+cost[i]==dis[j]&&lj[p]+1<lj[j])){
                dis[j]=dis[p]+cost[i];
                lj[j]=lj[p]+1;
                if(!v[j])v[q[++tail]=j]=1;
            }
    for(i=1;i<=m;i++){
        if(dis[x[i]]+z[i]==dis[y[i]])insert(x[i],y[i],1);
        if(dis[y[i]]+z[i]==dis[x[i]])insert(y[i],x[i],1);
    }
    s=1;t=n;u=s;n=t;
    printf("%lld %lld\n",ISAP(),m-lj[n]);
    }
}
#include<cstdio>
#include<iostream>
#include<set>
#include<cstring> 
#define N 222222
#define inf 1e16
using namespace std;
set<long long> st;
long long T,p,n,m,k,i,x,y,z,u,l,r,f,tot,sz,now,head,cas,id[N],pos[N],high[N],fir[N],val[N<<1],la[N<<1],ne[N<<1],fa[N][18];
long long ans,tmp,deep[N];
bool mark[N];
void ins(long long x,long long y,long long z){la[++tot]=y;val[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(long long x,long long z){
    id[x]=++sz;pos[sz]=x;
    for(long long i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(long long i=fir[x];i;i=ne[i]){
        long long y=la[i];
        if(y!=z){
            deep[y]=deep[x]+val[i];
            high[y]=high[x]+1;
            fa[y][0]=x;
            dfs(y,x);
        }
    }
}
long long lca(long long x,long long y){
    if(high[x]<high[y])swap(x,y);
    long long t=high[x]-high[y];
    for(long long i=0;i<=17;i++)if(t&(1<<i))x=fa[x][i];
    for(long long i=17;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;else return fa[x][0];
}
long long dis(long long x,long long y){return deep[x]+deep[y]-2*deep[lca(x,y)];}
void change(long long i,long long f){
    long long l=*--st.lower_bound(id[i]),r=*st.upper_bound(id[i]);
    if(r!=inf)ans+=f*dis(i,pos[r]);
    if(l!=-inf)ans+=f*dis(i,pos[l]);
    if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
    if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;
    now=1+((ans+tmp)>>1);
}
int main(){
    scanf("%I64d",&T);
    while(T--){
        printf("Case #%lld:\n",++cas);
        memset(mark,0,sizeof(mark));
        memset(pos,0,sizeof(pos));
        memset(fir,0,sizeof(fir));
        memset(fa,0,sizeof(fa));
        memset(deep,0,sizeof(deep));
        memset(ne,0,sizeof(ne));
        memset(val,0,sizeof(val));
        memset(la,0,sizeof(la));
        memset(id,0,sizeof(id));
        st.clear();ans=0;tmp=0;
        sz=0;tot=0;
    scanf("%I64d%I64d",&n,&m);
    for(i=1;i<n;i++)scanf("%I64d%I64d%I64d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
    dfs(1,0);st.insert(inf);st.insert(-inf);
    while(m--){
        scanf("%I64d%I64d",&p,&x);
        f=0;
        if(p==1){
            if(!mark[x])st.insert(id[x]),f=1;
            mark[x]=1;
        }else{
            if(mark[x])st.erase(id[x]),f=-1;
            mark[x]=0;
        }
        if(f){
        long long l=*--st.lower_bound(id[x]),r=*st.upper_bound(id[x]);
        if(r!=inf)ans+=f*dis(x,pos[r]);
        if(l!=-inf)ans+=f*dis(x,pos[l]);
        if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
        if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;}
        printf("%I64d\n",(ans+tmp)/2);
    }
    }
}

2015 Multi-University Training Contest 2

看到主力队开场拿了1006的一血,问一下果然是暴力,于是把1006秒了

然后觉得1002还稍微简单点,就去弄,发现只要枚举删除点的四边判断答案就可以了,但还是爆了2发OJ

然后看了下1009,觉得就是道码农题,太烦了,于是看1004

发现可以先把大于K的果子去掉,然后剩下的贪心取就可以了,不过一开始没有考虑环状的情况,想了一会发现环状取的一定是一整段的区间,于是可以考虑判断每个果子作为两边的分界线

然后LX说他做T9,说>47的数已经弄好了,于是帮他弄<47的数,弄了好久总算弄完了,然后发现自己真是个SB,后面的数直接乘0就行了,+1-1+1-1什么劲啊、、第一发WA了,写了个CHECK,发现了一个小BUG,改一下就A了,ORZORZ

这场主力队RANK10,我们蒟蒻队RANK18

#include<cstdio>
#include<algorithm>
#include<cstring>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int T,i,n,m,ans,h1[10],h2[10],u[10];
struct EG{int x,y;}eg[110];
bool cmp(EG a,EG b){return(a.x<b.x)||(a.x==b.x&&a.y<b.y);}
void dfs(int x){
    if(x>m){ans++;return;}
    if(h1[eg[x].x]&&h1[eg[x].y]){
        h1[eg[x].x]--;h1[eg[x].y]--;
        dfs(x+1);h1[eg[x].x]++;h1[eg[x].y]++;
    }
    if(h2[eg[x].x]&&h2[eg[x].y]){
        h2[eg[x].x]--;h2[eg[x].y]--;
        dfs(x+1);h2[eg[x].x]++;h2[eg[x].y]++;
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(gs,0,sizeof(gs));ans=0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++){
            scanf("%d%d",&eg[i].x,&eg[i].y);
            u[eg[i].x]++;u[eg[i].y]++;
            if(eg[i].x>eg[i].y)swap(eg[i].x,eg[i].y);
        }
        for(i=1;i<=n;i++)if(u[i]&1)break;else h2[i]=h1[i]=u[i]>>1;
        if(i<=n){puts("0");continue;}
        sort(eg+1,eg+m+1,cmp);
        dfs(1);printf("%d\n",ans);
    }
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
#define N 222222
using namespace std;
typedef long long LL;
int T,n,m,x,y,now;
int main(){
    while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){
        now=1;
            now=max(min(min(m-y+1,y),n-x),now);
            now=max(min(min(n-x+1,x),m-y),now);
            now=max(min(min(m-y+1,y),x-1),now);
            now=max(min(min(n-x+1,x),y-1),now);
        if((n&1)&&(m&1)&&(2*x==n+1)&&(2*y==m+1)&&(n==m)){
            now=n>>1;
        }else now=max(now,(min(n,m)+1)>>1);
        printf("%d\n",now);
    }
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e16
#define N 222222
using namespace std;
long long T,n,i,j,L,K,u,d,ans,tot,tmp,a[N],dl[N],dr[N],q[N];
struct EG{long long x,y;}eg[N];
bool cmp(EG a,EG b){return a.x<b.x;}
int main(){
    scanf("%I64d",&T); 
    while(T--){
        memset(dl,0,sizeof(dl));memset(dr,0,sizeof(dr));
        memset(q,0,sizeof(q));
        scanf("%I64d%I64d%I64d",&L,&n,&K);tmp=inf;ans=0;tot=0;
        for(i=1;i<=n;i++){
            scanf("%I64d%I64d",&eg[i].x,&eg[i].y);
            if(eg[i].x==L||eg[i].x==0)eg[i].y=0;
        }
        for(i=1;i<=n;i++){
            if(eg[i].y>=K){
                u=eg[i].y/K;
                eg[i].y%=K;
                d=min(eg[i].x,L-eg[i].x);
                ans+=u*d;
            }
        }
        sort(eg+1,eg+n+1,cmp);
        for(i=1;i<=n;i++)
            for(j=eg[i].y;j;j--)q[++tot]=eg[i].x;
        for(i=1;i<=tot;i++)dl[i]=dl[max(i-K,(long long)0)]+q[i]+min(L-q[i],q[i]);
        for(i=tot;i;i--)dr[i]=dr[min(i+K,tot+1)]+L-q[i]+min(L-q[i],q[i]);
        for(i=0;i<=tot;i++)tmp=min(tmp,dl[i]+dr[i+1]);
        printf("%I64d\n",ans*2+tmp);
    }
}

2015 Multi-University Training Contest 3

开场发现T11是傻逼题,但再次由于姿势不太对CE了两发,现在想想要是当时不那么倔强,现在也没那么遗憾

然后就去弄T2了,发现RMQ随便搞搞就可以了,然后就MLE了,发现空间必须要O(n)。。

于是写了发线段树,再次MLE,连4*n的空间都不让开。。。

然后发现高一的小盆友都会做。。于是觉得肯定不是线段树什么的、、然后发现可以维护一个前缀和啊。。

然后终于A了,不过还是落后于高一小盆友。。

然后就去做数据结构题T1了,一开始以为是维修数列弱化版,然后发现自己太天真了

然后发现写平衡树实在是太坑爹了,于是乖乖地写了个线段树,1A了爽~

然后T10想了很久没有结果,但已经有很多人A了,感觉自己没有希望了,交了个判LCA的WA了、

然后发现可以树上DP搞搞,总算A了不容易

然后看1009很多人A,就是求二维LIS,觉得树套树没希望就弃疗了

今天发现竟然是二维偏序,要用CDQ分治+树状数组,非常简单的模板题。。

T3、T4、T8都被强力队友A了,YY大爷一改往日睡觉的颓势,强势回归

这场主力队RANK13,我们蒟蒻队RANK51,正好掉出了第一版~

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 222222
#define M 222222
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,k,x,y,i,tot,ans,size[N],a[N],last[M],ne[M],first[N];char ch;
void ins(int x,int y){last[++tot]=y;ne[tot]=first[x];first[x]=tot;}
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void dfs(int x,int la){
    size[x]=1;
    for(int i=first[x];i;i=ne[i]){
        int y=last[i];
        if(y!=la){
            dfs(y,x);
            size[x]+=size[y];
        }
    }
}
int main(){
    while(scanf("%d%d",&n,&k)!=EOF){
        memset(first,0,sizeof(first));tot=0;
        memset(size,0,sizeof(size));
        rep(i,1,n-1)read(x),read(y),ins(x,y);
        dfs(1,0);
        for(ans=0,i=1;i<=n;i++)if(size[i]-1==k)ans++;
        printf("%d\n",ans);
    }
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
int T,x,y,i,j,k,n,p,ans,R,prime[N>>1],cnt[N],now[8],sum[N][8];
bool f[N];
int main(){
    n=1000000;
    for(i=2;i<=n;i++){
        if(!f[i]){
            prime[++p]=i;
            cnt[i]=1;
        }
        for(j=1;j<=p&&i*prime[j]<=n;j++){
            f[i*prime[j]]=1;
            if(i%prime[j]==0){
                cnt[i*prime[j]]=cnt[i];
                break;
        }else{
            cnt[i*prime[j]]=cnt[i]+cnt[prime[j]];
        }
        }
    }
    for(i=2;i<=n;i++){
        for(j=1;j<=7;j++)sum[i][j]=sum[i-1][j];
        sum[i][cnt[i]]++;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&x,&y);
        for(i=1;i<=7;i++)now[i]=sum[y][i]-sum[x-1][i];
        if(now[7]>=2)puts("7");else{
            if(now[6]>=2)puts("6");else{
                if(now[5]>=2)puts("5");else{
                    if(now[4]>=2)puts("4");else{
                        if(now[3]+now[6]>=2)puts("3");else{
                            if(now[2]+now[4]+now[6]>=2)puts("2");else{
                                puts("1");
                            }
                        }
                    }
                }
            }
        }
    }
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e16
#define N 111111
using namespace std;
typedef long long LL;
LL T,n,m,x,y,i,p,a[N];char ch;
struct Tr{LL l,r,v[4];}t[N*4],ans;
void pushup(LL k){//0jj 1jo 2 oj 3 oo
    for(LL i=0;i<4;i++)t[k].v[i]=max(t[k<<1].v[i],t[k<<1|1].v[i]);
    t[k].v[0]=max(t[k].v[0],max(t[k<<1].v[0]+t[k<<1|1].v[2],t[k<<1].v[1]+t[k<<1|1].v[0]));
    t[k].v[1]=max(t[k].v[1],max(t[k<<1].v[0]+t[k<<1|1].v[3],t[k<<1].v[1]+t[k<<1|1].v[1]));
    t[k].v[2]=max(t[k].v[2],max(t[k<<1].v[2]+t[k<<1|1].v[2],t[k<<1].v[3]+t[k<<1|1].v[0]));
    t[k].v[3]=max(t[k].v[3],max(t[k<<1].v[2]+t[k<<1|1].v[3],t[k<<1].v[3]+t[k<<1|1].v[1]));
}
Tr update(Tr a,Tr b){
    Tr c;
    for(LL i=0;i<4;i++)c.v[i]=max(a.v[i],b.v[i]);
    c.v[0]=max(c.v[0],max(a.v[0]+b.v[2],a.v[1]+b.v[0]));
    c.v[1]=max(c.v[1],max(a.v[0]+b.v[3],a.v[1]+b.v[1]));
    c.v[2]=max(c.v[2],max(a.v[2]+b.v[2],a.v[3]+b.v[0]));
    c.v[3]=max(c.v[3],max(a.v[2]+b.v[3],a.v[3]+b.v[1]));
    return c;
}
void change(LL k,LL x,LL key){
    LL l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(l==r){
        if(x&1)t[k].v[0]=key;else t[k].v[3]=key;
        return;
    }
    if(x<=mid)change(k<<1,x,key);else change(k<<1|1,x,key);
    pushup(k);
}
Tr query(LL k,LL x,LL y){
    LL l=t[k].l,r=t[k].r,mid=(l+r)>>1;
    if(x<=l&&r<=y){
        return t[k];
    }
    if(x>mid)return query(k<<1|1,x,y);
    else if(y<=mid)return query(k<<1,x,y);
    else return update(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
void buildtree(LL k,LL l,LL r){
    t[k].l=l;t[k].r=r;
    if(l==r){
        for(LL i=0;i<4;i++)t[k].v[i]=-inf;
        if(l&1)t[k].v[0]=a[l];else t[k].v[3]=a[l];
        return;
    }
    LL mid=(l+r)>>1;
    buildtree(k<<1,l,mid);
    buildtree(k<<1|1,mid+1,r);
    pushup(k);
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&m);
        for(i=1;i<=n;i++)scanf("%lld",&a[i]);
        buildtree(1,1,n);
        while(m--){
            scanf("%lld%lld%lld",&p,&x,&y);
            if(!p){
                ans=query(1,x,y);
                printf("%lld\n",max(max(ans.v[0],ans.v[1]),max(ans.v[2],ans.v[3])));
            }else change(1,x,y);
        }
    }
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 555555
#define M 1111111
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,tot,tmp,now,ans,a[N],fa[N],last[M],ne[M],first[N],size[N],sz2[N];char ch;
void ins(int x,int y){last[++tot]=y;ne[tot]=first[x];first[x]=tot;}
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void dfs(int x){
    size[x]=1;
    for(int i=first[x];i;i=ne[i]){
        int y=last[i];
        if(y!=fa[x]){
            fa[y]=x;
            dfs(y);
            if(a[x]<a[y])size[x]+=size[y];
        }
    }
}
void dfs2(int x,int w){
    sz2[x]=size[x];
    if(a[fa[x]]>a[x])sz2[x]+=w;
    ans=max(ans,sz2[x]);
    for(int i=first[x];i;i=ne[i]){
        int y=last[i];
        if(y!=fa[x]){
            int tmp;
            if(a[y]>a[x])tmp=size[y];else tmp=0;
            dfs2(y,sz2[x]-tmp);
        }
    }
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(first,0,sizeof(first));tot=0;ans=0;
        memset(fa,0,sizeof(fa));
        memset(size,0,sizeof(size));
        memset(sz2,0,sizeof(sz2));
        rep(i,1,n)read(a[i]);
        rep(i,1,n-1)read(x),read(y),ins(x,y),ins(y,x);
        dfs(1);dfs2(1,0);
        printf("%d\n",ans);
    }
}

2015 Multi-University Training Contest 4

开场就发现T1是大水题,就秒了

然后发现T2也是大水题,但RE了一发又没开LL WA了一发。。

然后看T5,写了发二分图WA了,后来发现的确是不对的,如果离线可以树形DP,但在线似乎没啥办法啊

然后T9想了一会觉得就是先能走0就走0然后判断,但感觉直接记忆化是存不下的

一开始想Bitset,但觉得就算bitset也肯定MLE了。。。。

然后发现可以逐步判断哪些格子是可以走的,而且对答案输出没有影响,因为答案是一样的。。

但还是由于一些小问题WA了3发。。。。

然后看T12分解置换A的人挺多,但我连样例都没搞懂怎么弄,又重新研究了下置换,还是没搞懂,于是弃疗了

然后T10由于英文太差并没有看懂,于是就去翻讨论版,整合了一下讨论的信息差不多懂了是什么题了

然后写了发模拟,虽然理论时间复杂度是可行的,但还是TLE了。。加了读入优化也无济于事

只好用SET优化了一下,总算A了。。。。

然后T8被LX大爷A了,LX大爷太强了,这题我看都没看懂。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 222222
#define M 222222
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,ff,now,sum[N];char ch;
bool f[10];
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
    for(i=1;i<=100000;i++){
        now=i;memset(f,0,sizeof(f));ff=0;
        while(now>0){
            if(f[now%10])ff=1;
            f[now%10]=1;
            now/=10;
        }
        if(!ff)sum[i]=sum[i-1]+1;else sum[i]=sum[i-1]; 
    }
    read(T);
    while(T--){
        read(x);read(y);
        printf("%d\n",sum[y]-sum[x-1]);
    }
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 1111111
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,ans,h1,h2,q1[N],q2[N],a[N];char ch;
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
    read(T); 
    while(T--){
        scanf("%d",&n);rep(i,1,n)read(a[i]);
        if(n==1){puts("1");continue;}
        if(n==2){puts("2");continue;}
        q1[1]=1;q1[2]=2;h1=2;
        q2[1]=1;q2[2]=2;h2=2;
        ans=2;
        rep(i,3,n){
            if(a[i]-a[q1[h1]]==a[q1[h1]]-a[q1[h1-1]])q1[++h1]=i;else{
                q1[1]=i-1;q1[2]=i;h1=2;
            }
            if((long long)a[i]*(long long)a[q2[h2-1]]==(long long)a[q2[h2]]*(long long)a[q2[h2]])q2[++h2]=i;else{
                q2[1]=i-1;q2[2]=i;h2=2;
            }
            ans=max(h1,ans);ans=max(h2,ans);
        }
        printf("%d\n",ans);
    }
}
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 1111
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,m,x,y,i,j,w,tmp,now,a[N][N];char s[N],ch;
bool vis[N][N],wil[N][N];
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void dfs(int x,int y){
    now=max(now,x+y);
    vis[x][y]=1;
    if(a[x][y]==1)return;
    if(x>1&&a[x-1][y]==0&&!vis[x-1][y])dfs(x-1,y);
    if(x<n&&a[x+1][y]==0&&!vis[x+1][y])dfs(x+1,y);
    if(y>1&&a[x][y-1]==0&&!vis[x][y-1])dfs(x,y-1);
    if(y<m&&a[x][y+1]==0&&!vis[x][y+1])dfs(x,y+1);
}
int main(){
    read(T); 
    while(T--){
        memset(vis,0,sizeof(vis));memset(wil,0,sizeof(wil));memset(a,0,sizeof(a));now=0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++){
            scanf("%s",s+1);
            for(j=1;j<=m;j++)
                a[i][j]=s[j]-'0';
        }
        dfs(1,1);
        if(a[1][1]==1)printf("1"),now=2;else if(now==n+m){puts("0");continue;}
        for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(i+j==now&&vis[i][j])wil[i][j]=1;//,printf("%d %d\n",i,j);
        for(w=now;w<=m+n-1;w++){
            tmp=2;
            for(i=1;i<=n;i++){
                j=w-i;
                if(j<=0||j>m)continue;
                if(wil[i][j]){
                    if(i<n)tmp=min(tmp,a[i+1][j]);
                    if(j<m)tmp=min(tmp,a[i][j+1]);
                }
            }
            for(i=1;i<=n;i++){
                j=w-i;
                if(j<=0||j>m)continue;
                if(wil[i][j]){
                    if(j<m)if(a[i][j+1]==tmp)wil[i][j+1]=1;//,printf("%d %d\n",i,j+1);
                    if(i<n)if(a[i+1][j]==tmp)wil[i+1][j]=1;//,printf("%d %d\n",i+1,j);
                }
            }
            printf("%d",tmp);
        }
        puts("");
    }
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define inf 1e9
#define N 222
#define M 222
#define MOD 1000000007
using namespace std;
typedef long long LL;
int T,n,x,y,z,i,j,k,r,c,w,a[N][N],pos[N][N],lx[N],time[N],xx[5],yy[5];char ch;
struct EG{int x,y;}eg[N];
set<pair<pair<int,int>,int> >st,st2;
set<pair<pair<int,int>,int> >::iterator it;
pair<pair<int,int>,int>tmp;
void read(int &x){
    for(ch=getchar();ch<'0';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
    xx[0]=1;xx[1]=-1;yy[2]=1;yy[3]=-1;
    while(scanf("%d%d%d%d",&r,&c,&n,&T)!=EOF){
        memset(a,0,sizeof(a));
        memset(pos,0,sizeof(pos));
        memset(time,0,sizeof(time));
        st.clear();
        for(i=1;i<=n;i++){
            read(eg[i].x);read(eg[i].y);read(z);
            a[eg[i].x][eg[i].y]=z;
            pos[eg[i].x][eg[i].y]=i;
        }
        memset(lx,1,sizeof(lx));
        read(x);read(y);
        for(i=0;i<=3;i++)st.insert(make_pair(make_pair(x,y),i));
        for(w=1;w<=T;w++){
            st2=st;st.clear();
            for(it=st2.begin();it!=st2.end();it++){
                tmp=*it;tmp.first.first+=xx[tmp.second];tmp.first.second+=yy[tmp.second];
                if(tmp.first.first<1||tmp.first.first>r||tmp.first.second<1||tmp.first.second>c)continue;
                if(pos[tmp.first.first][tmp.first.second]&&lx[pos[tmp.first.first][tmp.first.second]]){
                    if(++a[tmp.first.first][tmp.first.second]>4){
                        a[tmp.first.first][tmp.first.second]=0;
                        for(i=0;i<=3;i++)st.insert(make_pair(make_pair(tmp.first.first,tmp.first.second),i));
                        lx[pos[tmp.first.first][tmp.first.second]]=0;
                        time[pos[tmp.first.first][tmp.first.second]]=w;
                    }
                }else st.insert(tmp);
            }
        }
        for(i=1;i<=n;i++)if(lx[i])printf("1 %d\n",a[eg[i].x][eg[i].y]);else printf("0 %d\n",time[i]);
    }
}

2015 Multi-University Training Contest 5

中午吃完饭到机房已经11:59了,只好赶紧上,但还是没恢复过来。。

开局看水题,先发现T7是水题,但写SET由于姿势不太对总是调不出,弄了将近20分钟,然后队友早就把三道水题全切了。。

然后看T4,想了一会觉得n^3DP还是挺简单的,但是n^2就死也想不出来啦

然后已经过了将近两个小时了,我还是0贡献,然后黄主力T6会做但是WA了,就听了下他的思路,感觉挺对的,看了下T6和他的代码

写了个CHECK,发现黈力程序的错误挺严重的。。然后黈力改好错误就A了。。我也蹭了他的程序“A”了。。

然后想T4也想不出,然后T10看不懂就去问了下YY大爷题意,把题目转化了一下

一开始想状压,但N=200明显不可能啊。。然后我跟YY大爷说了下我的想法,他提到了网络流,我瞬间领悟过来,这题网络流一下第一问不是秒出吗

虽然从来没写过字典序的网络流,但没办法别的题不会做了还是要试试看,于是写了发,尝试顺着流倒着流,发现倒着流再反边就对啦,然后一交竟然1A啦

然后看了下T1,觉得肯定是SAM之类的,想把字符单个算,但手算就错了,然后就觉得没有办法了

然后只有半小时了,就开始爆T3,一开始没随机化,后来又发现输错了,然后再爆也没有结果。然后发现卡下时间也许可以出解,但卡到第10个时时间已经不够了。。

最后就只做了1道题滚粗啦。。不过我们队排名还不错,排到了RANK18,主力队更是怒肏RANK6

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#define fon(i,n) for(int i=0;i<n;i++)
#define frn(i,n) for(int i=1;i<=n;i++)
#define drn(i,n) for(int i=n;i;i--)
#define don(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define mjj(i,x) for(int i=fir[x];i;i=ne[i])
#define X first
#define Y second
#define MAX(a,b) a=max(a,b)
#define MIN(a,b) a=min(a,b)
#define mp make_pair
#define rlr son[son[root][1]][0] 
#define gi(a) scanf("%d",&a);
#define gi2(a,b) scanf("%d%d",&a,&b);
#define gi3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define gl(a) scanf("%I64d",&a);
#define gs(s) scanf("%s",s);
#define pi(a) printf("%d\n",a);
#define pi2(a,b) printf("%d %d\n",a,b);
#define pl(a) printf("%I64d\n",a);
#define spr(x) (x*x)
#define pie acos(-1) 
#define CP(a,b) memcpy(a,b,sizeof(a))
#define CL(a) memset(a,0,sizeof(a))
#define N 707
#define M 99999
#define MOD 1000000007
#define inf 1e9
#define eps 1e-8
using namespace std;

typedef long long LL;typedef unsigned long long ULL;typedef double LF;typedef long double LD;
typedef pair<int,int>pii;typedef pair<int,LL>pil;typedef pair<LL,int>pli;typedef pair<LL,LL>pll;typedef pair<LF,LF>pff;
const int xx[]={1,-1,0,0},yy[]={0,0,1,-1};
map<pii,int>ma;
map<pii,int>::iterator it;
int T,n,m,x,y,i,j,tot,tot2,po,k,p;
bool vv[1111][222],fr[1111];
int la2[1111],ne2[1111],fir2[1111],to[1111];void ins(int x,int y){la2[++tot2]=y;ne2[tot2]=fir2[x];fir2[x]=tot2;ma[mp(x,y)]=tot2;}
void del(int x,int y){fr[ma[mp(x,y)]]=fr[ma[mp(x,y)]^1]=1;}
void ISAP(){memset(numb,0,sizeof(numb));memset(dist,0,sizeof(dist));memset(pre,0,sizeof(pre));for(i=1;i<=t;i++)cur[i]=fir[i];u=s;numb[0]=t;while(dist[s]<t){if(u==t){now=inf;for(i=s;i!=t;i=la[cur[i]])if(va[cur[i]]<now)now=va[cur[u=i]];for(i=s;i!=t;i=la[cur[i]]){va[cur[i]]-=now;va[cur[i]^1]+=now;}flow+=now;}for(i=cur[u];i;i=ne[i])if(va[i]&&dist[la[i]]+1==dist[u])break;if(i){cur[u]=i;pre[la[i]]=u;u=la[i];}else{if(0==--numb[dist[u]])break;for(i=cur[u]=fir[u],tmp=t;i;i=ne[i])if(dist[la[i]]<tmp&&va[i])tmp=dist[la[i]];++numb[dist[u]=tmp+1];if(u!=s)u=pre[u];}}}
void find(int x){
	vv[po][x]=1;
	for(int i=fir2[x];i;i=ne2[i])
		if(!fr[i]){
			int y=la2[i];
			if(!vv[po][y]){
				vv[po][y]=1;
				find(y);
			}
		}
}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
	scanf("%d",&T);
	while(T--){
		tot=tot2=1;
		CL(fir);CL(fir2);CL(vv);CL(fr);CL(ne);CL(ne2);CL(la);CL(la2);
		u=po=s=t=now=tmp=flow=0;
		scanf("%d%d%d",&n,&m,&k);
		for(int w=1;w<=m;w++){
			scanf("%d",&p);
			if(p==1){
				po++;
				scanf("%d",&x);find(x);
			}else if(p==2){
				scanf("%d%d",&x,&y);
				ins(x,y);ins(y,x);
			}else{
				scanf("%d",&p);
				for(i=1;i<=p;i++)scanf("%d%d",&x,&y),del(x,y),del(y,x);
			}
		}
		s=n+po+1;t=s+1;
		for(i=1;i<=n;i++)ins(po+i,t,1);
		for(int w=po;w;w--){
			ins(s,w,k);to[w]=tot;
			for(int o=1;o<=n;o++)if(vv[w][o])ins(w,po+o,1);
			u=s;
			ISAP();
		}
		printf("%d\n",flow);
		for(i=1;i<=po;i++)
		if(i==1)printf("%d",va[to[i]]);else printf(" %d",va[to[i]]);puts(""); 
	}
}

然后1001其实挺简单的,后缀自动机直接上就行啦。。

#include<cstdio>
#include<cstring>
#define frn(i,n) for(int i=1;i<=n;i++)
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define drn(i,n) for(int i=n;i;i--)
#define CL(a) memset(a,0,sizeof(a))
#define N 200000
typedef unsigned long long LL;
int T,n,m,i,j;char s[N];LL ans,dp[27];bool vis[N];
struct SAM{
	int S,p,q,np,nq,last,cnt,son[N][26],fa[N],step[N],to[N];
	void init(){
		S=last=cnt=1;
		memset(to,-1,sizeof(to));
		CL(son);CL(step);CL(fa);
		step[0]=-1;
	}
	void add(int c){
		p=last;last=np=++cnt;step[np]=step[p]+1;to[np]=c;
		for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
		if(!p)fa[np]=S;else{
			q=son[p][c];
			if(step[p]+1==step[q])fa[np]=q;else{
				nq=++cnt;step[nq]=step[p]+1;
				memcpy(son[nq],son[q],sizeof son[q]);
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
			}
		}
	}
}A,B;
int main(){
	scanf("%d",&T);
	while(T--){
		ans=0;A.init();B.init();CL(dp);CL(vis);
		scanf("%s",s+1);n=strlen(s+1);
		frn(i,n)A.add(s[i]-'a');
		scanf("%s",s+1);m=strlen(s+1);
		drn(i,m)B.add(s[i]-'a');
		for(vis[B.S]=i=1;i<=B.cnt;i++)if(B.to[i]>=0&&!vis[i])
			for(j=i;!vis[j];vis[j]=1,j=B.fa[j])if(B.to[B.fa[j]]==-1)B.to[B.fa[j]]=B.to[i];else break;
		fr(i,2,B.cnt)dp[B.to[i]]+=(LL)(B.step[i]-B.step[B.fa[i]]);
		frn(i,A.cnt){
			LL num=(LL)(A.step[i]-A.step[A.fa[i]]);
			ans+=num;
			for(int j=0;j<26;j++)if(!A.son[i][j]){
				ans+=num*dp[j];
			}
		}
		printf("%I64u\n",ans);
	}
}

然后1008是合并果子也是醉了,代码不到1K,比赛时我看没多少人做看都没看、

2015 Multi-University Training Contest 6

开场发现主力队马上肏了T11,于是发现T11是一道傻逼题,拉个板秒掉了

然后看了下别的题,一开始弄T7,感觉就是模板题,但似乎找不到求有向图割边的模板

然后觉得T6还是可以做的。。于是开始肏T6。。

一开始写了个nlgnlgΣai的算法,写了挺久,然后觉得太坑爹肯定T

于是开始写nlgΣai的算法,我调了好久总算调出来了,可是竟然T了。。

我想我这复杂度也已经最低了吧。。然后这时候主力队和高一都4题了。。我还在摞T6摞不出、

然后各种卡常数,卡了7发总算卡过去了

然后看T3做对的人挺多的,我觉得贪心挺对,但YY大爷一口否定。。

于是只好写了个网络流,写到一半发现肯定没希望的,就弃疗了、、

后来发现T3A的人实在太多了,然后就乱写了一个贪心,竟然A了

然后T8也被鏼出来了,然后看T9作对的人挺多的,开始弄T9

然后发现就是黈力昨天给我出的题,虽然当时我T了最大的数据,但这里的N比较小,应该能过吧

可是我写完SPFA后发现T了。。然后各种卡常数,改成Dijkstra也没用

调了好久,大约爆了30多发OJ,然后想了会,发现有的点比较多余,只需要2*N个点就够啦。。

结果爆了20多发还是T,我只好弃疗了、、

最后10分钟发现T9可以线段树+Dijkstra肏掉,可是时间不够来不及写了。。

这场被高一摞翻啦,排名掉到了88名,高一都RANK36啦。。主力队也拿了RANK18、

LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
int T,n,m,x,y,i,j,tot,a[N];
long long ans;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		ans=pow(2,n-1,MOD);
		ans--;if(ans<0)ans+=MOD;
		printf("%lld\n",ans);
	}
}
int T,n,m,x,y,i,j,tot,top,fl,a[N],q[N];bool v[N];
int main(){
	scanf("%d",&T);
	while(T--){
		CL(v);
		scanf("%d%d",&n,&m);
		tot=n*(n+1)/2;
		if(tot%m!=0||n>(tot/m))puts("NO");else{
			puts("YES");
			for(i=1;i<=m;puts(""),i++){
				fl=tot/m;top=0;
				for(j=n;j;j--)if(!v[j]&&fl>=j)fl-=j,q[++top]=j,v[j]=1;
				printf("%d ",top);
				for(j=top;j;j--)printf("%d ",q[j]);
			}
		}
	}
}
#include<cstdio>
#include<cstring>
#define N 100100
char ch;void read(long long &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
long long ans,nv,a[N],f[N],now,er[36];
int T,n,t,i,j,la[N];bool flag;
int main(){
	scanf("%d",&T); 
	er[0]=1;for(i=1;i<=34;i++)er[i]=er[i-1]*2;
	while(T--){
		memset(f,0,sizeof(f));
		scanf("%d",&n);ans=0;
		for(i=1;i<=n;i++){
			read(a[i]),a[i]+=a[i-1];f[0]=i;
			for(j=0;j<=34;j++){
				while(a[i]-a[f[j]]>=er[j])f[j]++;
                ans+=(f[j-1]-f[j])*((long long)i*2+(f[j]+1+f[j-1]))*(long long)j;
			}
		}
		printf("%I64d\n",ans/2);
	}
}

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 400102
#define inf 1e16
using namespace std;
int T,i,x,y,l,r,n,m,tot,w,to[N],X[N],Y[N];
long long Z[N],dis[N];struct Tr{long long mv,lazy;int l,r,from;bool sel;}t[N*4];
void pushup(int k){
    t[k].lazy=inf;
    if(t[k<<1].sel&&t[k<<1|1].sel){t[k].sel=1,t[k].mv=t[k].lazy=inf;return;}
    if(t[k<<1].sel){t[k].mv=t[k<<1|1].mv;t[k].from=t[k<<1|1].from;return;}
    if(t[k<<1|1].sel){t[k].mv=t[k<<1].mv;t[k].from=t[k<<1].from;return;}
    if(t[k<<1].mv<t[k<<1|1].mv)t[k].from=t[k<<1].from,t[k].mv=t[k<<1].mv;
    else t[k].from=t[k<<1|1].from,t[k].mv=t[k<<1|1].mv;
}
void pushdown(int k){
    t[k<<1].mv=min(t[k<<1].mv,t[k].lazy);
    t[k<<1|1].mv=min(t[k<<1|1].mv,t[k].lazy);
    t[k<<1].lazy=min(t[k<<1].lazy,t[k].lazy);
    t[k<<1|1].lazy=min(t[k<<1|1].lazy,t[k].lazy);
    if(t[k].sel)t[k<<1].sel=t[k<<1|1].sel=1;
    t[k].lazy=inf;
}
void build(int k,int l,int r){
    t[k].l=l;t[k].r=r;t[k].lazy=inf;t[k].sel=0;t[k].mv=inf;
    if(l==r){t[k].from=l;if(l==1)t[k].mv=0;to[l]=k;return;}
    int mid=(l+r)>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    pushup(k);
}
void modify(int k,int x,int y,long long key){
	if(t[k].sel)return;
    int l=t[k].l,r=t[k].r;
    pushdown(k);
    if(x<=l&&r<=y){
        if(key<t[k].mv)t[k].mv=key,t[k].from=x;
        t[k].lazy=min(t[k].lazy,key);
        return;
    }
    int mid=(l+r)>>1;
    if(x>mid)modify(k<<1|1,x,y,key);
    else if(y<=mid)modify(k<<1,x,y,key);
    else modify(k<<1,x,mid,key),modify(k<<1|1,mid+1,y,key);
    pushup(k);
}
void go(int k,int w){
	pushdown(k);
	int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
	if(l==r){t[k].mv=t[k].lazy=inf;t[k].sel=1;return;}
	if(w<=mid)go(k<<1,w);else go(k<<1|1,w);
	pushup(k);
}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
void Read(long long &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
    read(T);
    while(T--){
    	read(n);
    	build(1,1,n);
    	for(i=1;i<=n;i++)read(X[i]);
    	for(i=1;i<=n;i++)read(Y[i]);
    	for(i=1;i<=n;i++)Read(Z[i]);
    	for(i=1;i<=n;i++)dis[i]=inf;
    	for(int k=1;k<=n;k++){
     	   i=t[1].from;
        	dis[i]=t[1].mv;
        	go(1,i);
        	l=max(min(i+X[i],n+1),i+1);r=min(i+Y[i],n);
        	if(l<=n&&l<=r)modify(1,l,r,dis[i]+Z[i]);
        	l=max(i-Y[i],1);r=min(max(i-X[i],0),i-1);
        	if(r>=1&&l<=r)modify(1,l,r,dis[i]+Z[i]);
    	}
    	for(i=1;i<=n;i++)if(dis[i]==inf)printf("-1 ");else printf("%lld ",dis[i]);puts("");
    }
}

2015 Multi-University Training Contest 7

由于YY大爷在螺杆螺杆,我11:57还在校门外溜达,发现了以后赶紧往机房跑,差不多十二点多几秒跑到了机房,赶紧开题看。。

然后看了会觉得没有什么题能做的,然后chorme又爆了就颓了一会儿。。

然后发现有人A了T5,就发现这是一道傻逼题,马上就艹掉了

然后似乎T7也有人做出来了,百度了一下格雷码,说是二进制转格雷码就是两位两位异或。。

然后想了一会就把DP想出来了,然后就秒了。。不过这时主力队已经4题领板了、

然后看了一会觉得T11对的人挺多的,拿到翻译以后就开始摞,YY了很多不同情况,但最后还是连样例都没过,主力队都已经7题了。。

大约14:30的时候发现我们队已经A了,于是也就弃疗了

然后摞那道最长1.5回文串T3,我想我曾经做过最长双回文串,于是就翻了翻那道题的题解、

然后发现只要改动一个小小的地方就可以啦,于是改了一下试试看,试了几组数据就交了,竟然A啦

然后颓了一会开始摞T5,一开始发现这是一道二维树状数组裸题,于是写了个MAP+树状数组去作死,毫不意外MLE了

然后发现可以统计在该线段左边和右边端点的个数得到答案,但是一直TLE。。然后只有二十多分钟了、

最后才发现题目看错了一点,他改的时候需要的是修改操作的次数不是总次数,然后赶紧写但是又WA了。。

然后没有办法最后一分钟赶紧把主力队程序弄下来,就当我会做了、

这场主力队9题怒肏RANK3,仅仅是惜败于杜教领衔的学车代表队,我们队仅仅拿到了RANK68.。

int T,n,m,x,y,i,j,tot,now,ws,top,sum,ans1,ans2,pp,cas,a[N],b[N];
char s[N];
int main(){
	while(scanf("%s%d",s+1,&n)!=EOF){
		if(n==-1)return 0;
		printf("Case #%d: ",++cas);
		ws=strlen(s+1);sum=0;ans1=0;ans2=0;
		for(i=1;i<=ws;i++)a[i]=s[i]-'0',sum+=a[i];
		while(n--){
			now=sum;top=0;
			while(now){
				b[++top]=now%10;
				sum+=now%10;
				now/=10;
			}
			for(i=1;i<=top;i++)a[++ws]=b[top-i+1];
		}
		for(i=1;i<=ws;i++)if(i&1)ans1+=a[i];else ans2+=a[i];
		pp=ans1-ans2;
		if(pp<0)pp=-pp;
		if(pp%11==0)puts("Yes");else puts("No");
	}
}
int T,n,m,x,y,i,j,tot,cas,a[N],dp[N][2];char s[N];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);n=strlen(s+1);
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		dp[1][0]=0;dp[1][1]=a[1];
		if(s[1]=='0')dp[1][1]=-inf;
		if(s[1]=='1')dp[1][0]=-inf;
		for(i=2;i<=n;i++){
			if(s[i]=='?'){
				dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]);
				dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
			}else if(s[i]=='0'){
				dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]);
				dp[i][1]=-inf;
			}else{
				dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
				dp[i][0]=-inf;
			}
		}
		printf("Case #%d: %d\n",++cas,max(dp[n][0],dp[n][1]));
	}
}
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define mod 1000000007
#define inf 1000000000
using namespace std;
int read(){
	int 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*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,ans,T,cas,ch[500005],p[500005],q[500005];
set<int> t;
void manacher(){
	memset(p,0,sizeof(p));
	int mx=0,id=0;
	for(int i=1;i<=n;i++){
		if(mx>=i)p[i]=min(mx-i,p[2*id-i]);else p[i]=0;
		for(;ch[i+p[i]+1]==ch[i-p[i]];p[i]++);
		if(p[i]+i>mx)id=i,mx=p[i]+i;
	}
}
bool cmp(int a,int b){return (a-p[a])<(b-p[b]);}
int main(){
	scanf("%d",&T);
	while(T--){
		ans=0;t.clear();
		n=read();
		for(int i=1;i<=n;i++)ch[i]=read();
		ch[0]=1000000001;
		manacher();
    	for(int i=1;i<=n;i++)q[i]=i;
		sort(q+1,q+n+1,cmp);
		int now=1;
		for(int i=1;i<=n;i++){
			while(now<=n&&q[now]-p[q[now]]<=i){
				t.insert(q[now]);
				now++;
			}
			set<int>::iterator tmp=t.upper_bound(i+p[i]);
			if(tmp!=t.begin())ans=max(ans,(*--tmp-i)*3);
		}
		printf("Case #%d: %d\n",++cas,ans);
	}
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define CL(a) memset(a,0,sizeof(a))
#define M 411114
using namespace std;
int f,x,sum,cnt,pp,p[M],c1[M],c2[M],v[M],to[M],w,top,n,i,cas;
struct EG{int l,r;}eg[M];char ch;
void read(int &x){
	for(f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=1;
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';if(f)x=-x;
}
void add(int c[],int x,int y){for(;x<=top*2+1;x+=x&-x)c[x]+=y;}
int query(int c[],int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
int main(){
	while(scanf("%d",&n)!=EOF){
		printf("Case #%d:\n",++cas);top=0;pp=0;
		CL(c1);CL(c2);CL(v);CL(eg);CL(p);cnt=0;
		for(i=1;i<=n;i++){
			read(p[i]);read(x);
			if(!p[i]){
				pp++;eg[pp].l=x;eg[pp].r=x+pp;
				v[++top]=x;v[++top]=x+pp;
				to[i]=pp;
			}else to[i]=x;
		}
		sort(v+1,v+top+1);cnt=unique(v+1,v+top+1)-(v+1);
		for(i=1;i<=pp;i++)eg[i].l=lower_bound(v+1,v+top+1,eg[i].l)-v,eg[i].r=lower_bound(v+1,v+top+1,eg[i].r)-v;
		for(i=1;i<=n;i++){
			w=to[i];
			if(!p[i]){
				printf("%d\n",query(c2,eg[w].r)-query(c1,eg[w].l-1));
				add(c1,eg[w].l,1);add(c2,eg[w].r,1);
			}else add(c1,eg[to[i]].l,-1),add(c2,eg[to[i]].r,-1);
		}
	}
}

2015 Multi-University Training Contest 8

开场发现T8是一道普及难度的模拟,就开始摞,摞来摞去摞了20分钟第一发交上去PE了,但发现我们队已经A了

颓了一会,然后T10把表打出来发现了明显的规律,想了一会觉得DP一下就好了,但由于一些特殊情况没有处理好WA了三发才A。。

然后看T7 A的人挺多的,就开始写暴力,但30分钟过编译后发现我们队又已经A了。。

然后就开始弄AC自动机题T5,弄了一个多小时1A了,但发现我们队还是已经A了、、

然后看来看去觉得都挺难的,就游走了一会。然后开始弄T6,弄了一会弄出来了

然后看T2挺多人A的,想了好久但也没有想出怎么做。。最后摞T3也没有摞出来

这场只有2贡献,排到了55名,主力队创造了第二名的最佳战绩

int T,n,m,a,b,c,x,y,i,j,tot,fz,sz,mz,aa,bb,cc,ga,gb,gc,fm,mm,sm;
char s[9];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",s);
		a=(s[0]-'0')*10+(s[1]-'0');
		b=(s[3]-'0')*10+(s[4]-'0');
		c=(s[6]-'0')*10+(s[7]-'0');
		if(a>=12)a-=12;
		mz=c*60*12;fm=mm=sm=43200;
		fz=(c+b*60)*12;
		sz=c+b*60+a*3600;
		aa=abs(sz-fz);
		bb=abs(sz-mz);
		cc=abs(fz-mz);
		aa*=360;bb*=360;cc*=360;
		if(aa>7776000)aa=2*7776000-aa;
		if(bb>7776000)bb=2*7776000-bb;
		if(cc>7776000)cc=2*7776000-cc;
		ga=gcd(aa,43200);gb=gcd(bb,43200);gc=gcd(cc,43200);
		aa/=ga;fm/=ga;bb/=gb;mm/=gb;cc/=gc;sm/=gc;
		printf("%d",aa);if(fm!=1)printf("/%d",fm);printf(" ");
		printf("%d",bb);if(mm!=1)printf("/%d",mm);printf(" ");
		printf("%d",cc);if(sm!=1)printf("/%d",sm);puts(" ");
	}
}
int T,n,m,now,pp,x,y,i,j,k,tot,A,B,ans,a[N],dp[10],g[10];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&A,&B);
		now=0;CL(dp);CL(g);
		dp[0]=1;
		for(i=1;i<=n;i++){
			CL(g);
			scanf("%d",&x);now=(now+x)%9;
			for(j=0;j<9;j++)g[(j+x)%9]=(dp[j]+dp[(j+x)%9])%MOD;
			for(j=0;j<9;j++)dp[j]=g[j];
		}
        ans=0;if(now==(A+B)%9)ans=dp[A%9];
        if(now==A%9&&B!=9)ans++;if(now==B%9&&A!=9)ans++;
        printf("%d\n",ans%MOD);
	}
}
#include<cstdio>
#include<cstring>
#include<vector>
#define N 111111
#define M 11111
#define CL(a) memset(a,0,sizeof(a))
using namespace std;
int T,n,m,cnt,ans2[N],q[N],fail[N],st[N],to[N][26];
vector<int> a[N];char s[M];
struct data{
    void insert(int id){
        scanf("%s",s+1);
        int L=strlen(s+1);
        int now=1;
        for(int i=1;i<=L;i++){
            int x=s[i]-'a';
            if(!to[now][x])to[now][x]=++cnt;
            now=to[now][x];
        }
        st[now]++;
    }
    void buildfail(){
        int head=1,tail=1;
        for(int i=0;i<26;i++)
            if(to[1][i]){
                fail[to[1][i]]=1;
                q[++tail]=to[1][i];
            }
        while(head<tail){
            int x=q[++head];
            for(int i=0;i<26;i++){
                int v=to[x][i];
                if(!v)continue;
                int k=fail[x];
                while(!to[k][i])k=fail[k];
                fail[v]=to[k][i];
                q[++tail]=v;
            }
        }
    }
    void get(int id,int x){for(int i=x;i;i=fail[i])ans2[id]+=st[i];}
    void solve(int x){
        int now=1;
        for(int i=0;i<a[x].size();i++){
            int t=a[x][i];
            while(!to[now][t])now=fail[now];
            now=to[now][t];get(x,now);
        }
    }
}trie;
int main(){
    scanf("%d",&T);
    while(T--){
        CL(ans2);CL(to);CL(fail);CL(st);
        fail[1]=0;for(int i=0;i<26;i++)to[0][i]=1;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)a[i].clear();
        int L,x;cnt=1;
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);int u=strlen(s+1);
            for(int j=1;j<=u;j++)a[i].push_back(s[j]-'a');
        }
        for(int i=1;i<=m;i++)trie.insert(i);
        trie.buildfail();
        for(int i=1;i<=n;i++)trie.solve(i);
        for(int i=1;i<=n;i++)printf("%d\n",ans2[i]);
    }
}
int T,n,m,x,y,l,r,i,tot,dis[N],pre[N];
int la[M],ne[M],og[M],fir[N];void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;og[tot]=x;}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);tot=0;
        CL(fir);CL(pre);
        for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y);
        for(i=fir[1];i;i=ne[i])pre[la[i]]=1;
        l=2;r=n;tot=0;
        while(l<=r){
            if(pre[l]){
                for(i=fir[l];i;i=ne[i])pre[la[i]]=l;
                dis[l++]=++tot;
            }else if(pre[r]){
                for(i=fir[r];i;i=ne[i])pre[la[i]]=r;
                dis[r--]=++tot;
            }
        }
        for(i=1;i<=m;i++)if(dis[la[i]]-dis[og[i]]<=0)printf("%d\n",n);else printf("%d\n",dis[la[i]]-dis[og[i]]);
    }
}

2015 Multi-University Training Contest 9

这场我中途有两个小时要去上课,于是就比较坑。。

开场先看了T7,虽然看上去挺简单但觉得挺难写的就先放到一边。。然后看T5挺水的,原来以为能水过的,没想到WA了、、

查了好久才发现原来d1=d2的时候要特判一下,不然就痿了、、

然后看T4也是挺简单的,赶在上课前交了几发,可是都WA了。。

上课回来差不多是三点多,就继续交,还是交不过。。觉得哪里都没错了,和主力队代码还对了一遍还是觉得都考虑到了、、最后没办法了交了主力队的、

然后开始弄T7,画了一会发现有些点不能挖,后来发现奇数点都不能挖,然后就觉得两列两列做是没有什么问题的

就写了发,然后WA了,然后调出了一些小错误,但还是WA。。

然后Marscat来帮助我,马上就又发现了一个小错误,最后终于A了。。

毫不意外地创造历史最低成绩,同时也是A4题中罚时最多的队伍

LL ans;
int T,n,m,x,y,i,j,tot,now,fg,d1,d2,q[N],t1[N],t2[N],a[N];
int main(){
	while(scanf("%d%d%d",&n,&d1,&d2)!=EOF){
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		ans=0;
		if(d1==d2){
			now=1;
			for(i=2;i<=n;i++)if(a[i]-a[i-1]!=d1)ans+=((LL)now*(LL)(now+1)/2),now=1;else now++;
			ans+=((LL)now*(LL)(now+1)/2);
			printf("%lld\n",ans);
			continue;
		}
		fg=0;
		for(i=1;i<=n-1;i++)if(a[i+1]-a[i]!=d2)q[++fg]=i;q[++fg]=n;
		for(now=1,i=1;i<=n;i++){
			while(i>q[now])now++;
			t1[i]=q[now];
		}
		fg=0;
		for(i=n;i>=2;i--)if(a[i]-a[i-1]!=d1)q[++fg]=i;q[++fg]=1;
		for(now=1,i=n;i>=1;i--){
			while(i<q[now])now++;
			t2[i]=q[now];
		}
		for(i=1;i<=n;i++)ans+=((LL)(i-t2[i]+1)*(LL)(t1[i]-i+1));
		printf("%I64d\n",ans);
	}
}
LL po,ans;bool flag,jj,jk,v[N];
int T,n,m,x,i,j,pp,to[N],a[N][N],now[N];
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		po=1;pp=0;jj=0;
		for(i=1;i<=n;i++)to[i]=i,po=po*i%MOD;
		for(i=1;i<=m;i++){
			scanf("%d",&a[i][1]);
			if(a[i][1]==-1)pp++;else{
				CL(v);jk=0;v[a[i][1]]=1;
				for(j=2;j<=n;j++)scanf("%d",&a[i][j]),v[a[i][j]]=1;
				for(j=1;j<=n;j++)if(!v[j])jk=1;
				if(jk)jj=1;
			}
		}
		if(jj){puts("0");continue;}
		if(!pp){
			for(i=m;i;i--){
				for(j=1;j<=n;j++)now[a[i][j]]=to[i];
				for(j=1;j<=n;j++)to[i]=now[i];
			}
			for(i=1;i<=n;i++)if(to[i]!=i)break;
			if(i<=n){puts("0");continue;}
		}
		ans=1;
		for(i=1;i<pp;i++)ans=ans*po%MOD;
		printf("%I64d\n",ans);
	}
}
int T,n,m,x,y,i,j,tot,nx,ny,sum,a[N][N];bool flag;
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		sum=0;flag=0;
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
		if(n%2==0&&m%2==0){
			nx=1;ny=2;
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++)
					if((i+j)%2==1){
						if(a[i][j]<a[nx][ny])nx=i,ny=j;
					}
			printf("%d\n",sum-a[nx][ny]);
			for(i=1;i<=m/2;i++){
				if(ny==i*2||ny==i*2-1){
					flag=1;
					for(j=1;j<nx;j++){
						if(j%2==1)printf("RD");
						else printf("LD");
					}
					if(nx!=n)printf("D");
					for(j=nx+1;j<n;j++){
						if(j%2==1)printf("LD");
						else printf("RD");
					}
					if(nx!=n)printf("R");
				}else{
					for(j=1;j<n;j++)if(flag)printf("U");else printf("D");
					printf("R");
					for(j=1;j<n;j++)if(flag)printf("D");else printf("U");
				}
				if(i!=m/2)printf("R");
			}
		}else{
			printf("%d\n",sum);
			if(n%2==1){
				for(i=1;i<=n/2;i++){
					for(j=1;j<m;j++)printf("R");
					printf("D");
					for(j=1;j<m;j++)printf("L");
					printf("D");
				}
				for(i=1;i<m;i++)printf("R");
			}else{
				for(i=1;i<=m/2;i++){
					for(j=1;j<n;j++)printf("D");
					printf("R");
					for(j=1;j<n;j++)printf("U");
					printf("R");
				}
				for(i=1;i<n;i++)printf("D");
			}
		}
		puts("");
	}
}

2015 Multi-University Training Contest 10

最后一场多校了哈哈,这回估计又要滚出100名啦

开场就发现T7是一道裸题+原题,就去网上找,找了一个改好交上去,但怎么改也改不对,要不然WA要不然TLE,不过毛主力已经爆了20多发了,才爆了不到10发的我还是很自豪的

差不多爆了20多分钟,终于弃疗了。。然后看T5,马上就秒了

然后又继续摞T7,又摞了20多分钟,还是没摞出来,这时主力队已经6题领板了

然后就摞T11,想了一会还是想出来了,然后写出来A了

然后我就开始颓,颓了1个多小时YY大爷走了进来,看了T9,说这不是傻逼题吗,然后他马上就秒了,跪跪跪

然后继续弄想了很久没想出来的T2,受到了数国队的启发,去oeis网站输入了数列,马上就得到要求的是LCM{1,2,...,n}/n,马上就会了,但还是因为没取模爆了两发OJ

然后就弄T6,虽然看了好久没看懂,但猜一猜总是矩阵之类的,就写了一发乱搞的,乱改一会就过了样例,交一发竟然A啦

又颓了一会,最后半小时才开始摞T1,但是到最后由于太弱也没有摞出来。。这场竟然没有掉出100名,真是可喜可贺

int T,n,m,x,y,i,j,tot,a,b,w,dp[N];
int main(){
	scanf("%d",&T);
	while(T--){
		CL(dp);
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++){
			scanf("%d%d%d",&w,&a,&b);
			for(j=m;j>=w;j--)dp[j]=max(dp[j],dp[j-w]+a+b);
			for(j=w;j<=m;j++)dp[j]=max(dp[j],dp[j-w]+a);
		}
		printf("%d\n",dp[m]);
	}
}
void dfs(int x,int fa){
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(y!=fa){
			sum[y]=sum[x]^va[i];
			dfs(y,x);
		}
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		CL(fir);tot=0;CL(cnt);CL(sum);
		scanf("%d",&n);
		for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
		dfs(1,0);
		for(i=1;i<=n;i++)cnt[sum[i]]++;
		scanf("%d",&Q);
		while(Q--){
			scanf("%d",&x);ans=0;
			for(i=1;i<=n;i++)ans+=(LL)cnt[x^sum[i]];
			if(!x)ans+=n;
			printf("%I64d\n",ans/2);
		}
	}
}
LL T,p,i,j,n,w,prime[N];
bool f[N];LL ans,now,x,y;
void gprime(){
	w=1000000;
	for(i=2;i<=w;i++){
		if(!f[i])prime[++p]=i;
		for(j=1;j<=p&&i*prime[j]<=w;j++){
			f[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
LL pow(LL a,LL b,LL p){LL sum=1;for(a%=p;b;a=a*a%p,b>>=1)if(b&1)sum=sum*a%p;return sum;}
void exgcd(LL a,LL b,LL &x,LL &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=x*(a/b);}
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
char ch;void read(int &x){for(ch=getchar();ch<'0';ch=getchar());for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';}
int main(){
	scanf("%I64d",&T);
	gprime();
	while(T--){
		scanf("%I64d",&n);n++;
		ans=1ll;
		for(i=1;i<=p;i++)if(prime[i]<=n)ans=ans*pow(prime[i],floor(log(n)/log(prime[i])),MOD)%MOD;
		else break;
		exgcd(n,MOD,x,y);if(x<0)x+=MOD;
		printf("%I64d\n",ans*x%MOD);
	}
}
struct JZ{int x,y,m[N][N];}ans,now;JZ cheng(JZ a,JZ b){JZ c;memset(c.m,0,sizeof c.m);c.x=a.x;c.y=b.y;for(int i=1;i<=a.x;i++)for(int j=1;j<=b.y;j++)for(int k=1;k<=a.y;k++)c.m[i][j]=(c.m[i][j]+(a.m[i][k]%MOD)*(b.m[k][j]%MOD))%MOD;return c;}
int T,n,m,x,y,i,j,k,sum;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);m--;
		memset(now.m,0,sizeof now.m);
		memset(ans.m,0,sizeof ans.m);
		for(i=1;i<=n;i++){
			scanf("%d",&k);
			for(j=1;j<=k;j++)scanf("%d",&x),now.m[i][x]=1;
		}
		n++;for(i=1;i<=n;i++)now.m[i][n]=1;
		for(i=1;i<=n;i++)ans.m[i][i]=1;
		ans.x=ans.y=now.x=now.y=n;
		for(;m;m>>=1){
			if(m&1)ans=cheng(ans,now);
			now=cheng(now,now);
		}
		sum=0;
		for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum=(sum+ans.m[i][j])%MOD;
		printf("%d\n",sum);
	}
}
Avatar_small
nbdhhzh 说:
2015年8月05日 10:05

为什么你一定要打肏而不是艹呢,多不文雅

Avatar_small
hhw 说:
2015年8月13日 16:49

"我12:57还在校门外溜达,发现了以后赶紧往机房跑,差不多十二点多几秒跑到了机房"
膜能逆着时间走的李泊宁大爷


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter