程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 【SDOI2016Round1】【解題報告】

【SDOI2016Round1】【解題報告】

編輯:關於C語言

【SDOI2016Round1】【解題報告】


Day1

T1:

題意:求∑n?1i=0∑m?1j=0max((ixorj)?k,0)
因為是抑或操作,每一位都是獨立的,所以可以一位一位的算貢獻。
f[i][a][b][c]表示第i位時,每個數跟n,m,k的大小關系,0表示小於,1表示i位之前都相等,2表示大於。轉移的時候美劇當前這一位的數是什麼,從高位向低位轉移就行了。
復雜度是O(nlogn)
code:

#include
#include
#include
#include
using namespace std;
#define LL long long 
const int N=100;
int T,Mod,ni[N],mi[N],ki[N],len;
LL n,m,K,f[N][2][2][3],g[N][2][2][3];
inline void calc(){
    int i,a,b,c,o0,o1,x,y,z,o;
    g[0][1][1][1]=1;
    for(i=0;ini[i+1]) continue;
                    if(o0==ni[i+1]) x=1;
                    if(o0mi[i+1]) continue;
                        if(o1==mi[i+1]) y=1;
                        if(o1ki[i+1]) z=2;
                        if(o==ki[i+1]) z=1;
                        if(o>=1) ni[++ni[0]]=x&1LL;
        for(x=m;x;x>>=1) mi[++mi[0]]=x&1LL;
        for(x=K;x;x>>=1) ki[++ki[0]]=x&1LL; 
        len=max(ni[0],max(mi[0],ki[0]));
        for(i=1;i<=(len>>1);++i){
            swap(ni[i],ni[len-i+1]);
            swap(mi[i],mi[len-i+1]);
            swap(ki[i],ki[len-i+1]);
        }
        calc();
        printf("%lld\n",(f[len][0][0][2]-(K%Mod*g[len][0][0][2])%Mod+Mod)%Mod);
    }
}

T2:

題意:給出n種數字,第i個是ai,個數是bi,權值是ci。如果ai|aj而且aiaj是一個質數,那麼這兩個數字就能獲得ci?cj的價值,要求總價值不小於0的情況下求最多的配對數。
配對關系是一個二分圖,所以建出費用流的圖來,當跑到費用小於0的時候,處理一下當前的流量,退出就行了。
code:

#include
#include
#include
#include
using namespace std;
#define T n+2
#define D 795
#define LL long long 
#define inf 1000000000
#define INF 10000000000000LL
const int N=800;
const int M=100000;
const int O=2000000;
bool flag[M+10],use[N],f[N];
struct S{int st,en,va;LL co;}aa[O];
int n,a[N],b[N],c[N],prime[M+10],d[N],va,point[N],pre[N],next[O],map[N][N],tot=1,co[N];
int l[N],to[N];
LL dis[N];
inline void prepare(){
    int i,j;
    for(i=2;i<=M;++i){
        if(!flag[i]) prime[++prime[0]]=i;
        for(j=1;j<=prime[0]&&i*prime[j]<=M;++j){
            flag[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
inline void add(int x,int y,int z,LL co){
    next[++tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;aa[tot].co=co;
    next[++tot]=point[y];point[y]=tot;
    aa[tot].st=y;aa[tot].en=x;aa[tot].va=0;aa[tot].co=-co;
}
inline bool check(int x,int y){
    int i,j,now,num=0;
    if((a[x]%a[y])||(a[x]==a[y])) return false;
    now=a[x]/a[y];
    for(i=1;i<=prime[0];++i){
        while(now%prime[i]==0) ++num,now/=prime[i];
        if(num>1) return false;
        if(now==1) return true;
    }
    if(now!=1) ++num;
    return num==1;
}
inline void paint(int x,int kind){
    int i;
    co[x]=kind;
    for(i=1;i<=n;++i)
      if(map[x][i]&&!co[i])
        paint(i,kind==1?2:1);
}
inline LL SPFA(int x,int y){
    int h=0,t=1,i,u;
    l[t]=x;
    for(i=1;i<=T;++i) dis[i]=-INF;
    dis[x]=0;
    while(h!=t){
        h=h%D+1;u=l[h];f[u]=true;
        for(i=point[u];i;i=next[i])
          if(aa[i].va>0&&dis[aa[i].en]

T3:

題意:給出一棵樹,有點權和邊權,有兩種操作,一種是將一條路徑上的點權修改成min(v[x],a?dis[x]+b)dis[x] 表示x到起點的距離(只算邊權)。另一種是詢問a到b路徑中最小的點權。
第一種修改可以看成是往樹上的一段區間中加入一個線段。這個東西可以用線段樹維護。用線段樹維護這個區間的線段的斜率和截距。每次向這個區間中加入一條新的線段的時候,看一下這段區間中原來的線段和新加入的線段哪一個對這段區間的影響更大,將影響小的線段下放到它有影響的子樹,每次一直這樣下放到葉子節點。這樣每次插入的復雜度是O(log2n)
每次查詢的時候只需要看一下這段區間中的最小值和這段區間中所保存的線段的兩個端點的情況就行了,復雜度是O(logn)
這道題每次的dis數組還是不知道的,可以在加入線段的時候順便將lca傳進去(常數大了好多。。。)
再加上鏈剖,總的復雜度就是O(nlog3n)
code:

#include
#include
#include
#include
using namespace std;
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
#define LL long long
#define D 123456789123456789LL
const int N=100010;
LL dis[N],a,b;
struct S{int st,en,va;}aa[N<<1];
struct T{int lca,st,kind;LL k,b,minn;}tr[N<<2];
int n,m,point[N],next[N<<1],tot,deep[N],siz[N],son[N],belong[N],fa[N][21],q[N],pos[N],dfsn,cur[N],lca,to[N],flag[N<<2];
inline int in(){
    int f=1,x=0;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;
}
inline int IN(){
    LL f=1,x=0;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;
}
inline void add(int x,int y,int z){
    next[++tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;
    next[++tot]=point[y];point[y]=tot;
    aa[tot].st=y;aa[tot].en=x;aa[tot].va=z;
}
inline void prepare(){
    int h=1,t=1,u,i,j;
    q[h]=1;
    while(h<=t){
        u=q[h];
        for(i=point[u];i;i=next[i])
          if(aa[i].en!=fa[u][0]){
            q[++t]=aa[i].en;
            deep[aa[i].en]=deep[u]+1;
            fa[aa[i].en][0]=u;
            dis[aa[i].en]=dis[u]+(LL)aa[i].va;
            for(j=1;j<=20;++j)
              fa[aa[i].en][j]=fa[fa[aa[i].en][j-1]][j-1];
          }
        h+=1;
    }
    for(i=t;i;--i){
        u=q[i];siz[u]=1;
        for(j=point[u];j;j=next[j])
          if(aa[j].en!=fa[u][0]){
            siz[u]+=siz[aa[j].en];
            if(siz[aa[j].en]>siz[son[u]]) son[u]=aa[j].en;
          }
    }
    int now=1;
    for(i=1;i<=n;++i) cur[i]=point[i];
    while(now){
        if(!pos[now]){
            pos[now]=++dfsn;
            to[dfsn]=now;
            belong[now]=(now==son[fa[now][0]] ? belong[fa[now][0]] : now);
            now=(son[now] ? son[now] : fa[now][0]);
        }
        else{
            for(i=cur[now];i&&(aa[i].en==fa[now][0]||aa[i].en==son[now]);i=next[i]);
            cur[now]=next[i];
            belong[aa[i].en]=aa[i].en;
            now=(i ? aa[i].en : fa[now][0]);
        }
    }
}
inline int LCA(int x,int y){
    if(deep[x]=r){
        LL minn=D;
        minn=min(minn,calc(l,now.lca,now.st,now.kind)*now.k+now.b);
        minn=min(minn,calc(r,now.lca,now.st,now.kind)*now.k+now.b);
        now.minn=tr[k].minn=min(tr[k].minn,minn);
        if(!flag[k]){
            flag[k]=1;
            tr[k]=now;
            return ;
        }
        int o1=calc(l,now.lca,now.st,now.kind)*now.k+now.bmid) insert(R,x,y,now);
    tr[k].minn=min(tr[k].minn,min(tr[k<<1].minn,tr[k<<1|1].minn));
}
inline LL query(int k,int l,int r,int x,int y){
    LL minn=D;
    if(x<=l&y>=r){
        LL o_l=calc(l,tr[k].lca,tr[k].st,tr[k].kind);
        LL o_r=calc(r,tr[k].lca,tr[k].st,tr[k].kind);
        return min(tr[k].minn,min(o_l*tr[k].k+tr[k].b,o_r*tr[k].k+tr[k].b));
    }
    minn=min(minn,calc(max(x,l),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b);
    minn=min(minn,calc(min(y,r),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b);
    if(x<=mid) minn=min(minn,query(L,x,y));
    if(y>mid) minn=min(minn,query(R,x,y));
    return minn;
}
inline void change(int x,int y,int st,int kind){
    int i,j;
    T now=(T){lca,st,kind,a,b,D};
    while(belong[x]!=belong[y]){
        insert(1,1,n,pos[belong[x]],pos[x],now);
        x=fa[belong[x]][0];
    }
    insert(1,1,n,pos[y],pos[x],now);
}
inline LL ask(int x,int y){
    LL minn=D;
    while(belong[x]!=belong[y]){
        minn=min(minn,query(1,1,n,pos[belong[x]],pos[x]));
        x=fa[belong[x]][0];
    }
    minn=min(minn,query(1,1,n,pos[y],pos[x]));
    return minn;
}
int main(){
    int i,j,x,y,t,z;
    n=in();m=in();
    for(i=1;i

Day2:

T1:

題意:每次向一個字符串的結尾加一個字符,輸出當前有多少種不同的非空子串。
先將這個字符串全讀進來,然後把字符串反過來建後綴數組。總的答案就是n?(n+1)2?∑n?1i=1height[i]
因為要動態的查詢,所以維護一個rank的權值線段樹,每次加入一個之後查詢一下前驅和後繼,每次更新的答案就是:n?i?lcp(now,pre)?lcp(now,sub)+lcp(pre,sub)
code:

#include
#include
#include
#include
using namespace std;
#define LL long long
#define inf 0x7fffffff
const int N=100010;
struct S{int minn,maxn;}tr[N<<2];
int n,a[N],b[N],m,t1[N],t2[N],sa[N],rank[N],c[N],height[N],st[N][21],Log[N];
inline int in(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline bool cmp(int *y,int p,int q,int k){
    int o0,o1;
    o0=(p+k>=n)?-1:y[p+k];
    o1=(q+k>=n)?-1:y[q+k];
    return o0==o1&&y[p]==y[q];
}
inline void build_sa(){
    int i,k,p,*x=t1,*y=t2;
    for(i=0;i=k) y[p++]=sa[i]-k;
        for(i=0;i=n) break;
    }
}
inline void build_height(){
    int i,j,k=0;
    for(i=0;i=r) return tr[k];
    if(x<=mid) ans1=query(L,x,y),f1=true;
    if(y>mid) ans2=query(R,x,y),f2=true;
    if(f1&&f2) return update(ans1,ans2);
    else return f1?ans1:ans2;
}
int main(){
    int i;
    n=in();
    for(i=n-1;~i;--i) a[i]=b[i]=in();
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(i=0;i

T2:

題意:求有多少長度為n的序列,滿足1~n只出現過一次,而且恰好有m個數滿足a[i]=i
答案就是C(n,m)?f[n?m]
C(n,m)表示m個滿足條件的數怎樣選的方案數,再乘上剩下的所有n?m個數都不在多對應的位置上的方案數,也就是錯排。
錯拍的公式就是:f[i]=(i?1)?(f[i?1]+f[i?2])
求c的時候預處理一下階乘。
code:

#include
#include
#include
using namespace std;
#define LL long long
#define Mod 1000000007LL
const int M=1000000;
LL f[M+10],g[M+10];
int T,n,m;
inline int in(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline LL quickpow(LL x,LL y){
    LL ans=1;
    while(y){
        if(y&1LL) ans=(ans*x)%Mod;
        y>>=1LL; x=(x*x)%Mod;
    }
    return ans;
}
int main(){
    int i;  
    T=in();
    for(f[1]=0LL,f[2]=1LL,f[0]=1LL,i=3;i<=M;++i) f[i]=(LL)(i-1)*((f[i-1]+f[i-2])%Mod)%Mod;
    for(g[1]=g[0]=1LL,i=2;i<=M;++i) g[i]=(g[i-1]*(LL)i)%Mod;
    while(T--){
        n=in();m=in();
        if(m>n){
            printf("0\n");
            continue;
        }
        LL ans=f[n-m]*((g[n]*quickpow(g[m],Mod-2)%Mod)*quickpow(g[n-m],Mod-2)%Mod)%Mod;
        printf("%lld\n",ans);
    }
}

T3:

題意:有一個長度為n的序列,每個節點都有一個權值,分成m份,求m份的最小的方差是多少。答案要求?m2
ans=m?∑mi=1(xi?xˉ)2
=m?∑mi?1(xi2+xˉ2?2xi?xˉ)
拆開之後,後面兩項都是常數,就相當於求每段的平方和的最大。這個東西可以斜率優化。
code:

#include
#include
#include
using namespace std;
#define LL long long
const int N=3010;
LL f[N][N],a[N];
int n,m,h[N],t[N],q[N][N];
inline LL pow(LL x){return x*x;}
inline LL get_son(int x,int y,int z){
    return f[z][x]+pow(a[x])-f[z][y]-pow(a[y]);
}
inline LL get_fa(int x,int y){
    return a[x]-a[y];
}
inline LL calc(int x,int y,int z){
    return f[z][x]+pow(a[y]-a[x]);
}
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i) 
      scanf("%lld",&a[i]),a[i]+=a[i-1];
    memset(f,127/3,sizeof(f));
    for(j=0;j<=m;++j) f[j][0]=0,q[j][h[j]=t[j]=1]=0;
    for(j=1;j<=m;++j)
      for(i=1;i<=n;++i){
        while(h[j-1]

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved