Cydiater

嗡嘛呢叭弥叭弥买买哞


  • 首页

  • 关于

  • 标签

  • 归档

  • 笔记

  • 伙伴

  • 搜索

LOJ Beta Round #4

发表于 2017-09-03 | 阅读次数:

游戏

可以发现,如果有数字可以填,那么最后一个填的一定获胜。然后特判一下不能填的情况。

#include <bits/stdc++.h>

using namespace std;

#define up(i,j,n)        for(int i=j;i<=n;i++)
#define down(i,j,n)    for(int i=j;i>=n;i--)

const int MAXN=1e5+5;

char s[30];
int a[MAXN],top=0,num[MAXN],cnt=0;

namespace BIT{
    int c[MAXN];
    int lowbit(int i){return i&(-i);}
    int calc(int x){
        int res=0;
        for(int i=x;i<=cnt;i+=lowbit(i))res+=c[i];
        return res;
    }
    void upd(int x){
        for(int i=x;i>=1;i-=lowbit(i))c[i]++;
    }
}using namespace BIT;

int main(){
//    freopen("input.in","r",stdin);
    int N;
    scanf("%d",&N);
    int ans=0;
    up(o,1,N){
        scanf("%s",s);
        if(s[0]=='X')ans++;
        else{
            int len=strlen(s),x=0,f=1;
            if(s[0]=='-')f=-1;
            up(i,0,len-1)if(s[i]!='-')
                x=x*10+s[i]-'0';
            a[++top]=x*f;
            num[++cnt]=a[top];
        }
    }
    if(N==1&&ans==1){
        puts("L");
        return 0;
    }
    if(ans==0){
        sort(num+1,num+cnt+1);
        cnt=unique(num+1,num+cnt+1)-(num+1);
        up(i,1,top)a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
        up(i,1,top){
            ans+=calc(a[i]);
            upd(a[i]);
        }
    }
    puts(ans%2?"W":"L");
    return 0;
}

多项式

根据广义欧拉定理,对于任意的$n\geq \phi(k)$有$x^n\equiv x^{n\ mod\ \phi(k) + \phi(k) }\pmod k$。
所以我们构造$n=2\phi(k)+1$,则多项式为$x^n+(k-1)x^{n-\phi(k)}$。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)        for(int i=j;i<=n;i++)
#define down(i,j,n)    for(int i=j;i>=n;i--)
#define cmax(a,b)        a=max(a,b)
#define cmin(a,b)        a=min(a,b)

const int MAXN=3e4+5;
const int oo=0x3f3f3f3f;

int k,phi=1;

namespace solution{
    void Solve(){
        scanf("%d",&k);
        if(k==1){
            puts("-1");
            return;
        }
        int num=k;
        for(int i=2;i*i<=k;i++)if(num%i==0){
            int tmp=1;
            while(num%i==0){
                num/=i;
                tmp*=i;
            }
            phi*=(tmp-tmp/i);
        }    
        if(num>1)phi*=(num-1);
        int n=2*phi+1;
        printf("%d\n",n);
        up(i,0,n){
            if(i==n-phi)printf("%d ",k-1);
            else if(i==n)printf("1 ");
            else printf("0 ");
        }
        puts("");
    }
}

int main(){
//    freopen("input.in","r",stdin);
    using namespace solution;
    Solve();
    return 0;
}

子集

把数字按奇偶分成$S,T$,然后连边,求最大独立集即可。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)        for(int i=j;i<=n;i++)
#define down(i,j,n)    for(int i=j;i>=n;i--)
#define cmax(a,b)        a=max(a,b)
#define cmin(a,b)        a=min(a,b)
#define SZ(x)        (int)x.size()

const int MAXN=505;
const int oo=0x3f3f3f3f;

ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}

ll N,a[MAXN],ans=0,nxt[MAXN];
vector<int>G[MAXN];
bool vis[MAXN];

bool DFS(ll node){
    up(i,0,SZ(G[node])-1)if(!vis[G[node][i]]){
        vis[G[node][i]]=1;
        if(!nxt[G[node][i]]||DFS(nxt[G[node][i]])){
            nxt[G[node][i]]=node;
            return 1;
        }
    }
    return 0;
}

int main(){
//    freopen("input.in","r",stdin);
    scanf("%lld",&N);
    up(i,1,N)scanf("%lld",&a[i]);
    up(i,1,N)if((a[i]&1)==0)
        up(j,1,N)if((a[j]&1)==1){
            if(gcd(a[i],a[j])!=1||gcd(a[i]+1,a[j]+1)!=1)continue;
            G[i].push_back(j);
        }
    up(i,1,N)if((a[i]&1)==0){
        memset(vis,0,sizeof(vis));
        ans+=DFS(i);
    }
    printf("%d\n",N-ans);
    return 0;
}
阅读全文 »

CC上的一些分块题

发表于 2017-09-02 | 更新于 2019-07-09 | 阅读次数:

Chef and Churu

Problem: 有$N$个数$a_i$,$N$个函数$f_i=\sum\limits_{L\leq i \leq R} a_i$,单点修改,区间询问$f$。
Solution: 把$f$按下标分块,每个块的大小为$B=\sqrt{N}$,对于每个块预处理出来每个数的出现次数。于是整块的修改与查询$O(1)$实现。考虑每次询问零碎的部分,对于一个$f$我们可以用BIT维护,但是这样的话复杂度还要乘个$log$,我们考虑我们需要的只是每次查询,所以我们对这个同样分块,修改$O(\sqrt N)$,查询$O(1)$。总复杂度$O(N\sqrt N)$。
Code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)        for(int i=j;i<=n;i++)
#define down(i,j,n)    for(int i=j;i>=n;i--)
#define cmax(a,b)        a=max(a,b)
#define cmin(a,b)        a=min(a,b)
#define pii            pair<int,int>
#define fi            first
#define se            second

const int MAXN=1e5+5;
const int oo=0x3f3f3f3f;

int N,B,a[MAXN],blo[MAXN],Q,c[405][MAXN],st[MAXN],ed[MAXN];
pii squ[MAXN];
ll ans[MAXN],pre[MAXN],d[MAXN];

namespace solution{
    ll calc(pii s){return (pre[s.se]+d[blo[s.se]])-(pre[s.fi-1]+d[blo[s.fi-1]]);}
    void Modify(int pos,int v){
        up(i,1,blo[N])ans[i]+=1LL*c[i][pos]*v;
        up(i,blo[pos]+1,blo[N])d[i]+=v;
        up(i,pos,ed[blo[pos]])pre[i]+=v;
    }
    void Prepare(){
        scanf("%d",&N);
        up(i,1,N)scanf("%d",&a[i]);
        B=sqrt(N);
        up(i,1,N)blo[i]=(i+B-1)/B;
        up(i,1,N)ed[blo[i]]=i;
        down(i,N,1)st[blo[i]]=i;
        up(i,1,N)pre[i]=pre[i-1]+a[i];
        up(i,1,N){
            scanf("%d%d",&squ[i].fi,&squ[i].se);
            ans[blo[i]]+=calc(squ[i]);
        }
        up(i,1,blo[N]){
            up(j,st[i],ed[i]){
                c[i][squ[j].se+1]--;
                c[i][squ[j].fi]++;
            }
            up(j,1,N)c[i][j]+=c[i][j-1];
        }
    }
    void Solve(){
        scanf("%d",&Q);
        while(Q--){
            int op;
            scanf("%d",&op);
            if(op==1){
                int pos,v;
                scanf("%d%d",&pos,&v);
                Modify(pos,-a[pos]);
                a[pos]=v;
                Modify(pos,a[pos]);
            }
            if(op==2){
                int le,ri;
                ll cur=0;
                scanf("%d%d",&le,&ri);
                up(i,blo[le]+1,blo[ri]-1)cur+=ans[i];
                if(blo[le]==blo[ri])up(i,le,ri)cur+=calc(squ[i]);
                else{
                    up(i,le,ed[blo[le]])cur+=calc(squ[i]);
                    up(i,st[blo[ri]],ri)cur+=calc(squ[i]);
                }
                printf("%lld\n",cur);
            }
        }
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}
阅读全文 »

一种特殊的最大权闭合图的优化建图

发表于 2017-08-22 | 阅读次数:

详见胡波涛的论文吧《最小割模型在信息学竞赛中的应用》,我只是搬运一下。

阅读全文 »

一般图匹配的随机算法

发表于 2017-05-31 | 阅读次数:

带花树?线性代数? Naive!
随机匹配岂不美滋滋?

阅读全文 »

51nod 算法马拉松 #25

发表于 2017-05-31 | 阅读次数:

二分答案

排列组合+二分+打表

//A
//by Cydiater
//2017.5.26
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)    for(ll i=j;i<=n;i++)
#define down(i,j,n)    for(ll i=j;i>=n;i--)
#define cmax(a,b)    a=max(a,b)
#define cmin(a,b)    a=min(a,b)

const ll mod=1e9+7;

ll N,M,K,cdown=0,cup=0;
ll a[110]={1,682498929,491101308,76479948,723816384,67347853,27368307,
625544428,199888908,888050723,927880474,281863274,661224977,623534362,
970055531,261384175,195888993,66404266,547665832,109838563,933245637,
724691727,368925948,268838846,136026497,112390913,135498044,217544623,
419363534,500780548,668123525,128487469,30977140,522049725,309058615,
386027524,189239124,148528617,940567523,917084264,429277690,996164327,
358655417,568392357,780072518,462639908,275105629,909210595,99199382,
703397904,733333339,97830135,608823837,256141983,141827977,696628828,
637939935,811575797,848924691,131772368,724464507,272814771,326159309,
456152084,903466878,92255682,769795511,373745190,606241871,825871994,
957939114,435887178,852304035,663307737,375297772,217598709,624148346,
671734977,624500515,748510389,203191898,423951674,629786193,672850561,
814362881,823845496,116667533,256473217,627655552,245795606,586445753,
172114298,193781724,778983779,83868974,315103615,965785236,492741665,
377329025,847549272,698611116};

namespace solution{
    ll A(ll a,ll b){
        ll res=1;
        if(b>a)return 0;
        cmin(b,a-b);
        up(i,1,b)(res*=(a-i+1))%=mod;
        return res;
    }
    ll fac(ll n){
        ll res=1,p=n/10000000;
        res=a[p];
        up(i,p*10000000+1,n)(res*=i)%=mod;
        return res;
    }
    void Prepare(){
        scanf("%lld%lld%lld",&N,&M,&K);
        ll le=1,ri=N,mi=(le+ri)/2;
        while(le<=ri){
            if(mi<=K){
                le=mi+1;
                cdown++;
            }else{
                ri=mi-1;
                cup++;
            }
            mi=(le+ri)/2;
        }
    }
    void Solve(){
        printf("%lld\n",A(M,cdown)%mod*A(N-M,cup)%mod*fac(N-(cup+cdown))%mod);
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}

完美序列

简单DP。

//B
//by Cydiater
//2017.5.27
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)    for(ll i=j;i<=n;i++)
#define down(i,j,n)    for(ll i=j;i>=n;i--)
#define cmax(a,b)    a=max(a,b)
#define cmin(a,b)    a=min(a,b)

const ll MAXN=3e4+5;
const ll oo=1LL<<60;
const ll mod=1e9+7;

ll N,a[MAXN],num[MAXN],top,cnt[MAXN],f[MAXN][105][3];
ll fac[MAXN],inv[MAXN],ans=0;

namespace solution{
    ll C(ll a,ll b){
        if(b>a)return 0;
        return fac[a]*inv[b]%mod*inv[a-b]%mod;
    }
    bool check(){
        sort(a+1,a+N+1);
        up(i,2,N)if(a[i]-a[i-1]>1)return 0;
        return 1;
    }
    void Prepare(){
        scanf("%lld",&N);
        up(i,1,N)scanf("%lld",&a[i]);
        if(!check()){
            puts("0");
            exit(0);
        }
        up(i,1,N)num[++top]=a[i];
        sort(num+1,num+top+1);
        top=unique(num+1,num+top+1)-(num+1);
        up(i,1,N)a[i]=lower_bound(num+1,num+top+1,a[i])-num;
        up(i,1,N)cnt[a[i]]++;
        fac[0]=1;
        up(i,1,N)fac[i]=fac[i-1]*i%mod;
        inv[1]=1;
        up(i,2,N)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        inv[0]=1;
        up(i,1,N)(inv[i]*=inv[i-1])%=mod;
    }
    void Solve(){
        f[1][cnt[1]-1][2]=1;
        up(i,2,top)up(j,0,cnt[i-1])up(k,0,2)if(f[i-1][j][k]){
            up(h,0,j)up(z,0,k)if(cnt[i]>=(h+z))
                (f[i][cnt[i]-h-z][z]+=C(k,z)*C(j,h)*f[i-1][j][k]%mod*C(cnt[i]-1,h+z-1)%mod)%=mod;
        }
        up(j,0,cnt[top])up(k,0,2)(ans+=f[top][j][k])%=mod;
        cout<<ans<<endl;
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}

区间计数

分治+单调队列

//C
//by Cydiater
//2017.5.26
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)    for(int i=j;i<=n;i++)
#define down(i,j,n)    for(int i=j;i>=n;i--)
#define cmax(a,b)    a=max(a,b)
#define cmin(a,b)    a=min(a,b)

const int MAXN=4e5+5;
const int oo=0x3f3f3f3f;

int N,num[MAXN][2],q[MAXN][2],top[2],suf[MAXN];
ll ans=0;

namespace solution{
    void Work(int L,int R){
        if(L>R)return;
        int mi=(L+R)>>1;
        top[0]=top[1]=0;
        up(i,mi,R)up(j,0,1)if(top[j]==0||num[i][j]>num[q[top[j]][j]][j])
            q[++top[j]][j]=i;
        q[top[0]+1][0]=q[top[1]+1][1]=R+1;
        int p=top[1];
        suf[top[0]+1]=0;
        down(i,top[0],1){
            suf[i]=suf[i+1];
            while(p&&num[q[p][1]][1]>num[q[i][0]][0])p--;
            if(num[q[p][1]][1]==num[q[i][0]][0]){
                int st=mi,ed=R;
                cmax(st,q[i][0]);
                cmin(ed,q[i+1][0]-1);
                cmax(st,q[p][1]);
                cmin(ed,q[p+1][1]-1);
                suf[i]+=max(0,ed-st+1);
            }
        }
        int mx[2],lim[2];
        mx[0]=mx[1]=-oo;
        lim[0]=lim[1]=0;
        down(i,mi,L){
            up(j,0,1)cmax(mx[j],num[i][j]);
            int Mx=max(mx[0],mx[1]);
            up(j,0,1)while(lim[j]<top[j]&&num[q[lim[j]+1][j]][j]<=Mx)lim[j]++;
            ans+=suf[lim[0]+1];
            if((mx[0]==Mx||num[q[lim[0]][0]][0]==Mx)&&(mx[1]==Mx||num[q[lim[1]][1]][1]==Mx)){
                int st=mi,ed=R;
                up(j,0,1){
                    if(mx[j]!=Mx)cmax(st,q[lim[j]][j]);
                    cmin(ed,q[lim[j]+1][j]-1);
                }
                ans+=max(ed-st+1,0);
            }
        }
        Work(L,mi-1);
        Work(mi+1,R);
    }
    void Prepare(){
        scanf("%d",&N);
        up(j,0,1)up(i,1,N)scanf("%d",&num[i][j]);
    }
    void Solve(){
        Work(1,N);
        cout<<ans<<endl;
    }
}

int main(){
    using namespace solution;
    Prepare();
    Solve();
    return 0;
}
阅读全文 »

APIO2017&CTSC2017

发表于 2017-05-06 | 更新于 2017-05-16 | 阅读次数:

不问,不等,不犹豫,不回头

阅读全文 »

Educational Codeforces Round 18

发表于 2017-03-28 | 阅读次数:

A. New Bus Route

贪心

#include <bits/stdc++.h>

using namespace std;

int N,a[200005];
int main(){
    //freopen("input.in","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%d",&a[i]);
    sort(a+1,a+N+1);
    int delta=2000000000;
    for(int i=2;i<=N;i++){
        delta=min(delta,a[i]-a[i-1]);
    }
    int ans=0;
    for(int i=2;i<=N;i++)if(a[i]-a[i-1]==delta)ans++;
    cout<<delta<<' '<<ans<<endl;
    return 0;
}

B. Counting-out Rhyme

模拟

#include <bits/stdc++.h>

using namespace std;

bool vis[105];
int N,K,siz,now;
int main(){
    //freopen("input.in","r",stdin);
    scanf("%d%d",&N,&K);
    siz=N;
    while(K--){
        int a;
        scanf("%d",&a);
        (now+=a)%=siz;
        int cnt=0;
        for(int i=0;i<N;i++){
            if(!vis[i])cnt++;
            if(cnt==now+1){
                printf("%d ",i+1);
                vis[i]=1;
                break;
            }
        }
        siz--;
        //(now+=1)%=siz;
    }
    puts("");
    return 0;
}
阅读全文 »
1…45
Cydiater

Cydiater

Blog

47 日志
88 标签
© 2017 — 2020 Cydiater
由 Hexo 强力驱动 v3.7.1
|
主题 — NexT.Gemini v6.3.0