[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;

}

ACRush Topcoder问答语录

FameofLight    ACRush: Finally the god of programming arrives 
  
FameofLight    ACRush: do you follow a random practice , or you practice question by topic , in your early days 
ACRush    FameofLight: No, our team practiced 3 or 4 full contests a week. 
  
pt1989    ACRush: Can u tell us whom or what do u credit for ur success? 
ACRush    pt1989: I think more practice is the way. 
  
ktuan    ACRush: how can you arrange your study with 3-4 contests a week ? 
ACRush    ktuan: UVA, SGU , ZJU and PKU is enough. 
  
pt1989    ACRush: what is ur method of practising? random or organised? 
ACRush    pt1989: contest env.  We always solve programs in contest env. 
  
Sunny_05    ACRush: wat is ur daily routine ?? i mean hw do u practice everyday ?? 
ACRush    Sunny_05: We only have weekly routine for practice. 
  
binarywithme    ACRush: what u think about world final problems..level of difficulty 
ACRush    binarywithme: A little harder than 1000p. 
  
MB__    ACRush: Which of these do you do after you submit your solution on TC: test solution, re-read problem statement, check code line by line 
ACRush    MB__: test for at least 10 cases. 
  
martins256    ACRush: how many problems have you solved on OJ ? 
ACRush    martins256: about 2000. 
  
kcm1700    ACRush: How many problems have you proposed on OJ or anything like this competition or something…? 
ACRush    kcm1700: about 2000. 
  
vijay_comc    ACRush: Who is your Arch Rival in Programming ? 😉 
ACRush    vijay_comc: Petr, I think. 
  
SomethingWrong    ACRush: What is your favourite Online Judge? 🙂 
ACRush    SomethingWrong: SGU. 
vexorian    ACRush: Why SGU? 
ACRush    vexorian: More tricky testcases. 
  
Dee2306    ACRush: Being one of top programmers, do u believe its just practice which makes u perfect.. or some of u are born genius ?? 🙂 
ACRush    Dee2306: It’s at least 80% due to practice 
  
stormsky    ACRush: how to practice ACM for a ACM beginner? 
ACRush    stormsky: practice in contest env. 
  
piva    ACRush: Do you train more of one category of problems? Or you just solve problems at random? 
ACRush    piva: I do more practice in the ones I have troubles with. 
  
pt1989    ACRush: what are ur interests other than programming? 
ACRush    pt1989: WarCraft. 
  
vijay_comc    ACRush: Petr is already married. No plans to compete him in that area ? 😀 
ACRush    vijay_comc: ….not yet. 
  
Sarkin    ACRush: Is analyzing algorithms an essential part of learning algorithms? 
ACRush    Sarkin: Not all, I think coding is in practice room is the rest way. 
  
abdessamad    ACRush: can believe it! when i see your challengers 😀 😀 
ACRush    abdessamad: It’s one thing that Petr did much better than me. 
  
stjepan    ACRush: where did/do you practice most and how? 
ACRush    stjepan: And join contest. 
  
binarywithme    ACRush: why u choose c++ as a default programming language 
ACRush    binarywithme: er.. Stl is the first reason. Another one may be efficient. 
  
geekru2    ACRush: during contest, what kind of problems do u enjoy doing? as in type of problem? 
ACRush    geekru2: dp and network-flow. 
  
reginachris    ACRush: What’s the best OJ to start with for practice (UVa, SPOJ, TC, etc.)? 
ACRush    reginachris: USACO 
  
ferry    ACRush: What do you do when you can’t solve a problem or you don’t know what’s wrong? 
ACRush    ferry: I will try to pass it in practice room. I always do that. 
  
geekru2    ACRush: Do you solve puzzles and mind bending questions to improve your problem solving techniques? 
ACRush    geekru2: no. I don’t like such problems like suduko. 
  
Sarkin    ACRush: What algorithm types helped you in the IOI? 
ACRush    Sarkin: dp. 
  
abdessamad    ACRush: did you like chess? 
ACRush    abdessamad: yes. 
  
geekru2    ACRush: when in a team event(IOI etc), do you dominate while programming? 
ACRush    geekru2: yes. I guess. 
  
kcm1700    ACRush: how do you prepare data for the challenge phase? 
ACRush    kcm1700: The trickiest one, of course. 
  
binarywithme    ACRush: sir what is the best way to learn DP. 
ACRush    binarywithme: TC contest. 
  
[dasha]    ACRush: When u were beginning to compete,did u have any problems? Like low speed of sloving, or maybe some particular method u couldn’t understend for a long time, sth else? If yes, how did u get over that? 
ACRush    [dasha]: USACO is a really good place. Especially for the beginners. 
  
frank44    ACRush: how long did the usaco practice take you? 
ACRush    frank44: half one year. 
  
binarywithme    ACRush: what u think math should b strong to become a Gud programmer 
ACRush    binarywithme: The mathematical foundation is helps. 
  
khanhptnk    ACRush: excuse me, do you think what we should prepare before an important contest ? 
ACRush    khanhptnk: relax, and rush some simple problems. And solve some problems in a contest env. is also helpful. 
  
Sarkin    ACRush: Do you recommned reading "Introduction to Algorithms"? if you know? 
ACRush    Sarkin: Really good. 
  
coder29    ACRush: which parts do u advice to read in "Introduction to Algorithms"? 
ACRush    coder29: All parts are perfect. except complexity. 
  
MB__    ACRush: do you do any sports but topcoding? 
ACRush    MB__: soccer. 
  
vijay_comc    ACRush: Complexity in CLRS is flawed ?? 😮 
ACRush    vijay_comc: 7-8 
  
Sarkin    ACRush: What do you mean except comlexity? 
ACRush    Sarkin: That’s only my opinion. 
  
pcaldeira    ACRush: which skill do you consider most important on TCHS/ioi-style contests? 
ACRush    pcaldeira: algorithm skills and coding ability. 
  
coder29    ACRush: I am newbie…which OJ is better fr me…USCO or UVA? 
ACRush    coder29: USACO 
  
hakami    ACRush: Are you useing library or typing from first for SRMs? 
ACRush    hakami: some includes and basic untilities. 
  
vrajesh1989    ACRush: Will you try to prove your algorithms to yourselves during contest time or just believe your intuition and start coding? 
ACRush    vrajesh1989: Yes, it’s very important for me. 
  
Sarkin    ACRush: Do you use algorithm analyzis when solving a problem to see it’s effeciency? 
ACRush    Sarkin: Yes. the effeciency sometimes is more important than correctness in TC contest. 
  
coder29    ACRush: basically i want 2 to do pratice on DP and greedy types…is TCs’ room are sufficient..? 
ACRush    coder29: A bulk of dp tasks in SRMs. TC’s room is good. 
  
rajeshsr    ACRush: In short, what is the strategy for becoming a good coder, according to u? 
ACRush    rajeshsr: Practice is the way. 
  
Lingmum    ACRush: How can we improve our speed of solving the problems,more problems? 
ACRush    Lingmum: More practice. 
  
stormsky    ACRush: do you often practice TC?and how to practice? 
ACRush    stormsky: Yes. But in fact, I prefer to doing past Regionals and finals. 
  
sahiltiwari    ACRush: how many hours you practise per day ? 
ACRush    sahiltiwari: 4-5 
  
MohammadReza    ACRush: What do you do to make your code becomes bugfree although the big size? 
ACRush    MohammadReza: test more tricky cases.(corner cases) 
  
rajeshsr    ACRush: Sorry to be repetitious, But I want to know what is the strategy of practice you employed? U select some random problems from OJs and solve or try to master a particular domain like DP by solving problems based on that or any other thing? 
ACRush    rajeshsr: set problems of past regionals and finals. 
  
puneetkp444    ACRush: Can you suggest some ways to improve problem solving abilities 
ACRush    puneetkp444: practice all kinds of problems. 
  
alft7    ACRush: what do you usually do before a very important competition, practise or something else? 
ACRush    alft7: practice until 3 days before it. 
  
ferry    ACRush: What is the hardest problem you’ve done? 
ACRush    ferry: I in WF2007.