标签存档：Codeforces

A

把直角的那个顶点放在原点，枚举其中一条边的横坐标，然后勾股定理得到纵坐标。旋转90度得到另外一个直角边的方向向量，伸缩到对应长度，看看是否整点。唯一的trick是除了直角边的那条边平行与坐标轴要注意。

代码

B

令f[i][j]表示现在才在i上，i上的次数是奇数，其它位置都是偶数的情况下，从i走到j所需要的步数。
f[i][j] = f[i][j-1] + f[a[j-1]][j-1] + 2
记忆化递归求解f[0][n]即可。

代码

C

先考虑单次操作的情况，f[i][0] = C[k + i – L][k] = 要求的答案。
对这个f[i][0]做一次差分，那么f[i][1] = f[i + 1][0] – f[i][0]，可以看做这是i处的导数。
然后f[i][2]视为对f[i][1]这个数列作差分，一直往上。
然后由于C[m][n] = C[m – 1][n] + C[m – 1][n – 1]，所以你会发现f[i][j] = C[k + i – L][k – j]。
那么现在变换一下f的递推关系得到f[i + 1][j] = f[i][j] + f[i][j + 1]。
也就是说，如果我知道到第i个数字的各阶导数，那么我可以一个一个数字往后推，得到其它数字以及他们的各阶导数。
又因为f[i][j] = C[k + i – L][k – j]，k不超过100，所以j只要算到100阶就行了，再高后面的都是0。
由于这个递推式里面是加法，和答案里的求和相吻合，所有可以把各个询问叠在一起往后加着算。

于是得到这么一个算法，对于每个询问，求出他在l处的各阶导数，放进f[l][0..k]里面，在r出也求出各阶导数，放到f[r][0..k]里面(这里是为了抵消，用减法放进去)。
最后，大家一起从前往后推就好了。

代码

D

令f[i][j][k]表示第i行到第j行这个子矩阵里，左边界选择第k列，右边界最远能到第几列。
首先f[i][j][k] ≤ min(f[i][j – 1][k], f[i + 1][j][k], f[i][j][k + 1])
除了这几个限制外，可能产生新冲突的就只可能是”第i行k列和第j行k列上的元素”与”第i行后面的元素和第j列后面的元素”。
那么按j – i的大小枚举i, j，再倒着枚举k，就可以用一个桶记录每个元素在第i行以及第j行最前出现的列是多少。
这样就可以处理掉这两个元素产生的冲突。
桶的清空稍微用一些编码技巧，就能O(n^3)写过去。

代码

CodeForces

…昨天晚上碰到拿数据结构作E的CF- -,就大涨了一把。

然后今天颓然发现…

rating混进了前100

– -太不容易了额.连续3场靠RP进前50…

首先是那场D作数据结构题的…

然后是过了AB + 3个hack居然能混进前50的…

再接着就是这次E作数据结构题的…

。。。

真心觉得都是运气啊…感觉很快要掉回黄的样子…不截图留念可能今后都达不到了…= =|||

曲线图：

———————————————————————————————————————–

这几场ACM组队训练下来、发现自己不太静得下心来…而且有避开麻烦的心理…特别是队友在搞某些比较烦,或者自己不是非常熟悉的题目的时候.就抱有放给队友搞的心理…然后就不管了…于是往往在后面是各种打酱油,浪费时间.

其实能明显感觉到我们3个的想东西的方向差别很大,有时候一个人各种难搞的时候,另一个人可能推推就出来了。

然后无论是ACM组队还是CF…都能感觉自己有点静不下来…可能和最近的小感冒有点关系>.<

希望接下来做事都可以专注一点，投入一点。。。

A

Cnt[26]表示每个字母出现次数，然后sort一下，贪心地从个数少的开始删，删剩下的就是必须有的。

B

离散化以后就各种好搞- -。写圡了，按ti排序以后发现ti相同的那些转移有点问题。于是直接开个

map

CF上第一个hack…成功了叉了一个n^2都敢交的…

C

=_=经lcc指点后顿时泪流满面。

旋转原来那个东东，就相当于把一路上加的C向量和原来的向量都跟着一起旋转再叠加。

于是乎把目标的B向量旋转到4个方向，分别看看能不能用C旋转4个方向的向量拼出B-A.

然后C旋转4个方向的向量由于是90 180 270度的，所以可以只取其中两个垂直的。然后就是看是否存在整数(x,y)满足

x*C + Rotate90(C)*y = B-A

这个化出来以后就和两直线求交一个样- -，套个模板或者推一推就好了。

D

这个题要是当时看了就好了…卡了C以后没去搞这个…好经典的0_0

dfs的时候，按照这个函数对当前结点的儿子排下序

bool cmp(int x,int y){
     return Size[y]*Sum[x]}

其中Size表示子树下结点的数目，Sum[x]表示子树以及x与父亲相连的所有边的权和*2的值。

然后这样模拟算一算延迟的值就好了.

          sort(Q.begin(),Q.end(),cmp);
          long long tmp=0;
          for(int i=1;i              tmp+=Sum[Q[i-1]];
              ret+=tmp*Size[Q[i]];
          }

ret初始为从当前结点直接跑各个子树时的时间和…

代码：http://ideone.com/UsOfC

E

还不会捉。

题意就是

F[0,0]=(a[0]+b[0])%p

F[i,j]=max(F[i-1,j],F[i,j-1])+(a[i]+b[j])%p

输出F[n-1,m-1]以及取的方案…

n,m<=20000.

时限15S

空间限制 45MB

 

=_=rating涨了一点点…

 

—————————————————————————————————————

E

看了官方题解。问题相当于找一个从(0,0)走到(n-1,m-1)的路线。pick完路上的权，最后权最大。只能向上或右走。

路径长度必然是(n-1 – 0)+(m-1 – 0)。然后把路径分为均匀的前后两半，于是可以确定一个最优解的中介点。递归下去。就得到了答案。

令r=n+m-2，那么复杂度这么算：r*r + 2*(r*r)/4 + 4*(r*r)/16 ….  k*(r*r)/(k*k)  … <= r*r + r*r

代码：http://ideone.com/XgoR1

 

update@8.7

A

就是加个Next[i][26]的数组来转移，基本上理清题意以后，5分钟内都出想法了吧

B

按a[i]排个序，然后顺序扫描，看最后的是谁就行了。= =脑抽写了线段树，本身线段树的话也不会写多久，但是又跑去尝试新写法。。。然后就写了巨久。。。

C

这个，看了watashi的代码，想了一下。

首先就是如果一个边集能符合题目，充要条件是每个点度数为偶数。

每当添加一条边连接两个不连通的块时，不可能会存在新的欧拉回路通过这条新加的边。所以显然答案不变。

而当添加一条边连接了两个本已连通的块时，假如是一开始只有一条边，答案必然还是0，然后接下来，每次出现这样的边，ans+=2^(k-1)。其中k代表这是第k条连接已连通的两个块的边。

为什么会这样呢？从结论往回看。。。本身的ans是不包含新加边的方案数，而2^(k-1)是包含新加边的方案数。

假设用一个mask代表那k-1条边的使用情况，那么极有可能是每个mask都对应了一种且仅一种方案。

继续YY

除去所有这k条边以后，其实图上是几棵树组成的森林！

然后假定现在这个第k条必取、、、然后前面k-1条组成的每个mask确实就唯一地对应了一种方案。

也就是说假设mask确定，我们森林边的取舍情况也就确定了。这个自行YY一下，明白过来会发现很显然

 

D

不会>.<

求指导。

 

E

这种放在省选NOI什么的就是送分题，裸考线段树

就是建一棵线段树，然后线段树每个节点里套一个线性表，以前我写这种比较疼，现在用vector简直好写到爆。。。

然后这个线性表的内容嘛，就是随着t的增长，看看这个线段里的老大是谁。

大概就是表示这样更替情况的一个队列。

然后嘛，假如区间里有i,j满足a[i]<=a[j] && b[i]<=b[j]，那么i肯定就没用了。

剔除这些以后，按a[i]递减排序，变成了b[i]递增的序列。(我的Code中的Select())

然后就是利用决策单调弄这个队列了。由于b[i]递增，所以随着t的递增，必然是越来越倾向于选后面的。

我们现在构建一个栈，使得栈内元素满足Meet_Time(Q[i],Q[i+1])>Meet_Time(Q[i],Q[i-1])，其中Meet_Time(x,y)就是使得a[x]+b[x]*t=a[y]+b[y]*t的t值。

这个很容易扫一遍得出来。(我的Code中的Form())

构建完以后，对于每个询问l,r,t。

直接在线段树里找到l,r对应区间，然后可以三分得当前的t对应的老大是谁(我还是写得二分，Code中的Get_Best())。

按Solution Size排我的还是比较靠前的= =，我也觉得写得还是比较清楚，于是推荐一下。

时间复杂度O(n lg^2 n + q lg ^2 n)

【CODE】http://ideone.com/Aga48

【update】

按照猛犸学长的指示，构造部分可以通过归并排序避免那个sort的调用。

后面可以先对答案排序，然后用指针滑的方法得到均摊的n lg n。

于是总时间复杂度可以做到O(n lg n + q lg n)。

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

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;

}