分类存档：默认分类

[BZOJ1006 [HNOI2008]神奇的国度]【弦图】

【题目大意】

给一个弦图。问色数是多少。

【算法】

先是有显然的定理：色数(用最少种颜色涂满图中的点，使得每条边两端的点颜色都不同)>=团数(最大团的点数)

因为是弦图，由完美消除序列的性质可以构造得色数=团数，于是达到下界。

于是直接利用完美消除序列的性质求出团数即可。

【其它】

完美消除序列的性质是：

对于序列中第i个点Vi。

令S={Vj | (j>i) && ((Vi,Vj) in E)}，那么S+Vi成一个团。

>.<还是V^2。虽然O(V+E)也不难写。求不鄙视。

【CODE】

http://ideone.com/vqJlV

[Practice]SRM 490 DIV I

>.<深切感受到自己蒟蒻。

 

250题意

N,M<=10^9

i=N;

j=M;

while (j<=lcm(N,M)){

while (i

ans+=j-i;

j+=M;

}

return (double)ans/(lcm(N,M)/M);(平均数)

、

然后发现其实每次j-i都是gcd(N,M)的倍数，设g=gcd(N,M)，然后j-i刚好是0,g,2*g,3*g,…,(lcm(N,M)/M-1)*g

、

lcm(N,M)/M=N/g

于是ans=(N/g)*(N/g-1)/2 * g  / (N/g)

然后最终代码是

int gcd(int x,int y){return y?gcd(y,x%y):x;}

double Starport::getExpectedTime(int N, int M) {

long long g=gcd(N,M);

long long t=N/g;

return g*(t*(t-1)/2)/(double)(t);

}

 

 

550

弄完以后交FST了….

题目大意就是给定一组字典，再给出一个字符串，让你用手机T9的方式最少要多少次按键把字符串打出来。

对我来说很考验coding啊>.<...

思路不太难，就模拟每次弄一个字典里字符的前缀。然后由于是类似栈的形式，只能从后面删和插入，所以可以F[i]表示前i个弄好最少多少次按键，然后弄个邻接矩阵mat[i][j]表示两两状态间转移最少需要多少步.

最后来个floyd就OK…

个中细节和处理技巧多多= =，请自行体会。。。

2Y。

 

被屠什么的，无所谓的。

Adjust

考完试以后coding感觉各种水.

通常都是想到写不出的样子.

记得watashi说过,想出算法算什么呢,能AC才是真本事.

ACM和OI不一样,速度很重要.

OI中对于一般人的可捉题,如果想出算法,要coding出来一般还是没有太大问题的.

而且通常对拍完时间都还是够的.

ACM难道你还会写个程序对拍吗?

基本都是眼看的吧…

训练OI,也许该不停地切掉1000pt. AK各种省选题.

训练ACM,至少在我这个层次而言,Target应该是比较稳定地搞掉250pt和500pt. 至少先做到这样吧.

1000pt即使能想到,也几乎都不能在现场出掉

 

当然,不会的skill和algorithm也是必须学的.

 

总之,先坚持每天practice一场SRM或者CF或者直接做一场比赛.

至少把250和500写短,快速弄对吧.

 

该出的题都出不了,那凭什么去弄神题呢…

 

…欢迎各位鄙视和指点.

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;

}