Codeforces Beta Round #73 Div1 A~D

完爆…挫死了.在被屠中成长.

A

可知周期只能是lcm(a,b),而lcm=a*b/gcd(a,b)，所以更替不会超过a+b次，于是直接模拟优先者的更替，计算时间比较即可。

 

B

模拟题。虽然这题很弱，但是给了我教训。

注意对于map

 

C

做的时候头一热，SG都没算直接用胜负表示状态…NIM游戏转化为有向图的模型里面，如果只有一个棋子乱走确实可以这样，但是多个棋子走就必须SG函数了…犯傻了…

本题不只是多个棋子一起走，而且每个棋子还会分裂。但是我们依然可以得出这个性质：若该状态本身各棋子xor和为0，那么无论对方下一步怎么走，我还是能使得xor和为0(NIM游戏的证明方法)。

于是SG+异或前缀和。枚举决策是O(sqrt(n))的，总复杂度O(n*sqrt(n))

 

#include

#include

#include

#include

#include

using namespace std;

const int N=100005;

int sg[N];

int best[N];

int Sum[N];

set

 

int main(){

    int n;

    cin >> n;

    Sum[0]=0;

    sg[0]=1;

    fill(best+1,best+n+1,-1);

    for (int i=1;i<=n;i++){

        Hash.clear();

        for (int k=2;(k+1)*k/2<=i;k++){

            int base=(i-(k+1)*k/2);

            if (base%k) continue;

            base/=k;

            if ( (Sum[base+k]^Sum[base])==0 )

                if (best[i]==-1) best[i]=k;

            Hash.insert(Sum[base+k]^Sum[base]);

        }

        for (int j=0;;j++)

          if (!Hash.count(j)) { sg[i]=j; break; }

        Sum[i]=Sum[i-1]^sg[i];

    }

    cout << best[n] << endl;

}

D

给一棵树，每条边有权值。n<=10^5

每两个点之间都会打一次架(A打了B，B还要打一次A)，打架以后会在路径上边权最大的边上种树。如果多条最大边，每条都种树。

问最多树的是哪些路？

按边从小到大排序，然后逐次合并点块。如果没有同权的边，这个方法就很容易用并查集实现。然后现在我们考虑同权的一块处理，因为之前的小的都合过点了，现在加了一堆同权的边以后，会构成多颗新树。然后分别对这些树DFS求出子树大小然后乘一下就得解。

时间复杂度O(n lg n)

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int N=100005;

struct edge{int x,y,w,label; long long cnt;}g[N*2];

int n,m;

int F[N];

int Size[N];

int sz[N];

int sum_sz[N];

int fa[N];

int v[N];

vector

vector

map

map

set

 

void add(int x,int y,int w,int i){

    g[i].x=x; g[i].y=y; g[i].w=w; g[i].label=i; g[i].cnt=0;

}

 

bool cmp(edge A,edge B){

    return A.w

}

 

int gf(int x){

    if (F[x]==x) return x;

    return F[x]=gf(F[x]);

}

 

void Union(int x,int y){

    int px=gf(x);

    int py=gf(y);

    F[px]=py;

    Size+=Size[px];

}

 

void dfs(int x){

    v[x]=1;

    happ.push_back(x);

    for (vector

        int y=*it;

        if (!v[y]){

            fa[y]=x;

            dfs(y);

            sum_sz[x]+=sum_sz[y];

        }

    }

}

 

void gao(int st,int ed){

    m=0;

    app.clear();

    for (int i=st;i<=ed;i++){

        int x=gf(g[i].x);

        int y=gf(g[i].y);

        if (!app.count(x)) app[x]=++m;

        if (!app.count(y)) app[y]=++m;

    }

    for (int i=1;i<=m;i++)

        To[i].clear();

    for (int i=st;i<=ed;i++){

        int x=gf(g[i].x);

        int y=gf(g[i].y);

        To[app[x]].push_back(app[y]);

        To[app[y]].push_back(app[x]);

        sz[app[x]]=Size[F[x]];

        sz[app[y]]=Size[F[y]];

    }

    for (int i=1;i<=m;i++) { v[i]=0; sum_sz[i]=sz[i]; }

    Ans.clear();

    for (int i=1;i<=m;i++)

      if (!v[i]){

          happ.clear();

          fa[i]=0;

          dfs(i);

          int total=sum_sz[i];

          for (int k=1;k

                int j=happ[k];

                Ans[make_pair(j,fa[j])]=(long long)sum_sz[j]*(total-sum_sz[j]);

                Ans[make_pair(fa[j],j)]=(long long)sum_sz[j]*(total-sum_sz[j]);

          }

      }

    for (int i=st;i<=ed;i++)

        g[i].cnt=Ans[make_pair(app[gf(g[i].x)],app[gf(g[i].y)])];

    for (int i=st;i<=ed;i++)

      Union(g[i].x,g[i].y);

}

 

int main(){

    freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for (int i=1;i

        int x,y,w;

        scanf("%d%d%d",&x,&y,&w);

        add(x,y,w,i);

    }

    sort(g+1,g+n,cmp);

    for (int i=1;i<=n;i++) { F[i]=i; Size[i]=1; }

    long long ans=-1;

    for (int i=1;i

        int st=i;

        while (i

        int ed=i;

        gao(st,ed);

    }

    Ret.clear();

    for (int i=1;i

      if (g[i].cnt>ans) ans=g[i].cnt;

    for (int i=1;i

      if (g[i].cnt==ans) Ret.insert(g[i].label);

    cout << ans*2 << " " << Ret.size() << endl;

    bool first=true;

    for (set

        if (!first) cout << " ";

        cout << *it;

        first=false;

    }

    cout << endl;

}