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

【SDOI2016Round1】【解題報告】

編輯：關於C

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. 下一頁:
關於C
遞歸法求斐波那契數列（C語言版）

斐波那契數列： 又稱黃金
通訊錄（C語言）

先定義頭文件#ifndef __CONTACT_H__#de
問題六十: 用篩法求10000內的素數。

print?/* 程序頭部注釋開始（為避免提交博文中遇到的問
C語言編寫的娛樂小工具【小時鐘、猜數字】

1、實現動態顯示當前計算機時間 #include #i
SpringMVC（一）——流程框架總體介紹

SpringMVC屬於SpringFrameWork的後續產
經驗之談—父子控制器（驗證蘋果的一句話）

蘋果官方有一句話說的非常好:當控制器的view互為父子關系，
相關文章
閱讀排行榜
輸入一行字符，分別統計出其中英文字母、空格、數字和其它字符的個數。 C語言之linux內核實現平方根計算算法 [ndk，2]ndk開發案例和錯誤處理 純C語言：遞歸最大數源碼 C語言批量下載文件（含源碼） C語言typedef的四個用途和兩個陷阱 排序算法（二） 插入排序 C語言對數組的各種操作操作 C語言初學者入門 第九講 數組(1) C語言標准I/O_fread/fwrite C語言 實現一個函數，判斷一個數是不是素數
熱門圖文
android-Android：怎麼創建一個沒有title的dialog？ C# 2.0 中Iterators的改進與實現原理淺析 如何解決PHP中的uniqid在高並發下的重復問題 2007-8-23 FastSpring.NET V2.05 RC1 發布 PHP函數eval()介紹和使用示例 PHP創建與解析XML 編碼,charset,亂碼,unicode,utf-8與.net簡單釋義(續) PHP中Exception異常處理類的使用詳解
欄目導航
C語言基礎知識C語言入門知識關於CC練習實例C語言問答
Copyright © 程式師世界 All Rights Reserved