codeforces round 338まとめ&&題解

A:
勝手にやる.楽しければいい
B:
まずこの問題は英語の読解問題です.
私たちは発見することができます.各点の最長上昇シーケンスの長さは固定であり、出度入度は固定である
では、dpしてもいいですか?たぶん1枚からnまで挙げて彼とつながっている点で更新しますか?
どうせspfaを書きました.のfstがなくて楽しかった
C:
n<=3000、これは私たちがむやみにやることができることを意味します.
最初の列をひっくり返して、真ん中に勝手に文字を挿入して、暴力kmpのたびにいいです.
しかし、この問題は線形にすることができて、さっきのように反転してSAMをすればいいです.
でもこの時Cは見逃しましょう
D:
BC原題、高速べき乗?オラ関数?乗算逆元?玄学?
E:
二つの答え、そして暴力的にどこにあるか判断すればいい.
詳細はちょっとお父さん
A:

bool a[100010];
int main()
{
    //freopen("xxx.in","r",stdin);
    //freopen("xxx.out","w",stdout); 
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        int m;cin>>m;
        for(int j=1;j<=m;j++){
            int x;cin>>x;
            a[x]=true;
        }
    }
    for(int i=1;i<=k;i++){
        if(!a[i])puts("NO"),exit(0);
    }
    puts("YES"),exit(0);
}

B:

struct Edge{
    int to,next;
}edge[4000010];
int size;
int first[1000010];
int n,m;
int du[1000010];
bool exsit[1000010];
int dl[1000010];
int dis[1000010];
void addedge(int x,int y){
    size++;
    edge[size].to=y;
    edge[size].next=first[x];
    first[x]=size;
    du[x]++;
}
long long ans;
void spfa(){
    
}
int main()
{ 
    R(n),R(m);
    for(int i=1;i<=m;i++){
        int x,y;R(x),R(y);
        addedge(x,y),addedge(y,x);
    }
    int head=0,tail=0;
    //dis[1]=1;dl[1]=1;
    for(int i=1;i<=n;i++){
        dis[i]=1,dl[++tail]=i,exsit[i]=true;
    }
    while(head!=tail){
        head++;if(head==200001)head=1;
        int v=dl[head];exsit[v]=false;
        for(int u=first[v];u;u=edge[u].next){
            if(edge[u].to>v&&dis[edge[u].to]<dis[v]+1){
                dis[edge[u].to]=dis[v]+1;
                if(!exsit[edge[u].to]){
                    tail++;if(tail==200001)tail=1;
                    dl[tail]=edge[u].to;exsit[edge[u].to]=0;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,(long long)du[i]*(long long)dis[i]);
    }
    cout<<ans<<endl;
}

C:

char s[10010];
char T[10010];
char t[10010];
int tot=0;
int fail[10010];
int id[10010];
int t1[10010];
#include<vector>
vector < pair<int,int> >Ans;
int main()
{
    scanf("%s%s",s+1,T+1);
    int n=strlen(s+1),m=strlen(T+1);
    for(int i=1;i<=n;i++)t1[s[i]]=1;
    for(int i=1;i<=m;i++)if(!t1[T[i]])puts("-1"),exit(0);
    for(int i=1,j=n*2+1;i<=n;i++,j--){
        s[j]=s[i];
        id[j]=id[i]=i;
    }
    s[n+1]=1;n=n*2+1;
    int l,r,preans;
    for(int F=1;F<=m;){
        t[++tot]=T[F];int ans=0;
        for(int i=2,j=0;i<=tot;i++){
            while(j&&t[i]!=t[j+1])j=fail[j];
            if(t[i]==t[j+1])j++;
            fail[i]=j;
        }
        for(int i=1,j=0;i<=n;i++){
            while(j&&s[i]!=t[j+1])j=fail[j];
            if(s[i]==t[j+1])j++;
            if(j==tot){
                ans=i-tot+1;
                break;
            }
        }
        if(ans){
            F++;
            if(F==m+1){
                Ans.push_back(make_pair(ans,ans+tot-1));
                break;
            }
            preans=ans;
            //cerr<<preans<<endl; 
        }
        else{
            Ans.push_back(make_pair(preans,preans+tot-2));
            tot=0;
        }
    }
    cout<<Ans.size()<<endl;
    for(int i=0;i<Ans.size();i++){
        printf("%d %d
",id[Ans[i].first],id[Ans[i].second]);
    }   
}

D:

int k[1000010];
long long q_pow(long long a,long long n,long long mod)
{
    long long tmp=1;
    while(n){
        if(n&1) tmp=(tmp*a)%mod;
        a=(a*a)%mod;
        n/=2;
    }
    return tmp;
}

void fuck()
{
    int i,j,v;
    long long pro=1,ans=1;
    bool flag=0;
    memset(b,0,sizeof(b));
    
    for(i=1;i<=n;i++){
        int x;R(x);k[x]++;
    }
    n=200000;
    for(i=1;i<=n;i++){
        a[i]=k[i];
    }
    for(i=1;i<=n;i++){
        v=i;
        for(j=2;j*j<=i;j++){
            if(v%j==0)
                while(v%j==0){
                    b[j]+=a[i];
                    v/=j;
                }
            }
        if(v>1) b[v]+=a[i];
    }
    for(i=1;i<=n;i++){
        if(!b[i]) continue;
        if(!flag&&b[i]%2){
            flag=true;
            pro=(pro*(b[i]+1)/2)%phi;
        }
        else pro=(pro*(b[i]+1))%phi;
    }
    for(i=1;i<=n;i++){
        if(!b[i]) continue;
        if(!flag) b[i]/=2;
        ans=(ans*q_pow(i,b[i]*pro%phi+phi,mod))%mod;
    }
    printf("%I64d
",ans);
}


int main()
{
    while(~scanf("%I64d",&n))
        fuck();
    return 0;
}

E:

//Copyright(c) 2015 liuchenrui
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
long long ansx=0,ansy=0,n,l=1,r=1ll<<30;
#define print cout<<ansx<<' '<<ansy,exit(0)
#define t1 if(n<=l)ansx-=n,ansy+=2ll*n,print;else ansx-=l,ansy+=2ll*l,n-=l;
#define t2 if(n<=l)ansx-=2ll*n,print;else ansx-=2ll*l,n-=l;
#define t3 if(n<=l)ansx-=n,ansy-=2ll*n,print;else ansx-=l,ansy-=2ll*l,n-=l;
#define t4 if(n<=l)ansx+=n,ansy-=2ll*n,print;else ansx+=l,ansy-=2ll*l,n-=l;
#define t5 if(n<=l)ansx+=2ll*n,print;else ansx+=2ll*l,n-=l;
#define t6 if(n<=l)ansx+=n,ansy+=2ll*n,print;else ansx+=l,ansy+=2ll*l,n-=l;
int main(){
    scanf("%I64d",&n);
    if(n==0)printf("0 0
"),exit(0);
    while(l!=r){
        long long mid=(l+r)>>1ll;
        if(mid*(mid+1)*3ll<n)l=mid+1ll;
        else r=mid;
    }
    //t1 t2 t3 t4 t5 t6
    ansx=2ll*l,ansy=0;
    n-=(l-1)*(l)*3ll;
    t1 t2 t3 t4 t5 t6
} 

初めてAKしました..どうじせき