[Codeforces #188] Tutorial

Link:

A:

先全转为正数，后面就全是指数级增长了

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

ll x,y,m,res;

int main()

{

    cin>>x>>y>>m;

    if(max(x,y)<m&&max(x,y)<=)

        return puts("-1"),;

    while(x<m&&y<m)

    {

        if(x>y) swap(x,y);

        ll t=(y-x)/y+;

        res+=t;x+=t*y;

    }

    cout<<res;

    return ;

}

Problem A

不断将$(x,y)$改为$(x+y,x)$要分类，在一数为负数时为线性增长

B:

首先要发现最终不为0的点的$x,y$的范围仅不到$[-100,100]$

又由于最终状态和操作顺序无关，因此每次将可能区域内的点暴力更新即可

不过我一开始使用了$bfs$，导致同一个位置可能每次进栈多次从而TLE……

以后$bfs$在同一层时一定要控制每个数的进栈次数！能每个位置暴力就不要$bfs$

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int ZERO=;

int n,t,x,y,a[*ZERO][*ZERO],flag=;

int dx[]={,,,-},dy[]={,-,,};

int main()

{

    scanf("%d%d",&n,&t);

    a[ZERO][ZERO]=n;

    while(flag)

    {

        flag=;

        for(int i=ZERO-;i<=ZERO+;i++)

            for(int j=ZERO-;j<=ZERO+;j++)

                if(a[i][j]>=)

                {

                    flag=;

                    for(int k=;k<;k++)

                        a[i+dx[k]][j+dy[k]]+=a[i][j]/;

                    a[i][j]%=;

                }

    }

    while(t--)

        scanf("%d%d",&x,&y),printf("%d\n",abs(x)<=ZERO&&abs(y)<=ZERO?a[ZERO+x][ZERO+y]:);

    return ;

}

Problem B

C:

其实是一道不算难的模拟题？可能当时被吓到了……

只要每个连通块里保证收支平衡就保证有解

接下来可以暴力枚举点对转移，保证是将多出的转入少的中，这样就可以忽略上限这个条件了

但也可以总共$O(n^2)$得做：

由于转移次数上限为$O(2*n^2)$，因此可以仅将每个连通块连成一棵树

将一个当前不够的点作为根先做一个预处理，只要$O(n)$的遍历就能使该点符合条件

过程中注意保证已经符合条件的点不能改变，将当前多出的转移

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=2e5+;

struct edge{int nxt,to;}e[MAXN<<];

struct result{int x,y,val;}res[MAXN<<];

int n,v,m,x,y,a[MAXN],b[MAXN],f[MAXN],head[MAXN],tot,cnt;ll sum[MAXN];

int find(int x)

{return f[x]==x?x:f[x]=find(f[x]);}

void add_edge(int x,int y)

{e[++tot]={head[x],y};head[x]=tot;e[++tot]={head[y],x};head[y]=tot;}

void add_res(int x,int y,int val)

{a[x]-=val,a[y]+=val,res[++cnt]={x,y,val};}

void dfs(int x,int anc)

{

    sum[x]=a[x]-b[x];

    for(int i=head[x];i;i=e[i].nxt)

        if(e[i].to!=anc) dfs(e[i].to,x),sum[x]+=sum[e[i].to];

}

void solve(int x,int anc,int val)

{

    for(int i=head[x];i;i=e[i].nxt)

    {

        if(e[i].to==anc||sum[e[i].to]<=) continue;

        int w=sum[e[i].to]<val?sum[e[i].to]:val,tmp=a[e[i].to];

        if(tmp>=w)

        {

            add_res(e[i].to,x,w);

            if(a[e[i].to]<b[e[i].to]&&tmp>=b[e[i].to])

                solve(e[i].to,x,b[e[i].to]-a[e[i].to]);

        }

        else

        {

            add_res(e[i].to,x,tmp);

            if(tmp<b[e[i].to]) solve(e[i].to,x,w-tmp);

            else solve(e[i].to,x,w-tmp+b[e[i].to]);

            add_res(e[i].to,x,w-tmp);

        }

        val-=w;if(!val) return;

    }

}

int main()

{

    scanf("%d%d%d",&n,&v,&m);

    for(int i=;i<=n;i++) f[i]=i;

    for(int i=;i<=n;i++) scanf("%d",&a[i]);

    for(int i=;i<=n;i++) scanf("%d",&b[i]);

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

    {

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

        int posx=find(x),posy=find(y);

        if(posx!=posy) add_edge(x,y),f[posx]=posy;

    }

    for(int i=;i<=n;i++) sum[find(i)]+=a[i]-b[i];

    for(int i=;i<=n;i++) if(sum[i]) return puts("NO"),;

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

        if(a[i]<b[i]) dfs(i,),solve(i,,b[i]-a[i]);

    printf("%d\n",cnt);

    for(int i=;i<=cnt;i++)

        printf("%d %d %d\n",res[i].x,res[i].y,res[i].val);

    return ;

}

Problem C

D:

很明显的一道博弈论

找到所有极大的集合${X^s}$，对每个集合求$SG$值最后异或即可

其中数量大于2的集合可以$sqrt(n)$得找出，剩下数量为1的$SG=1$，可以统一计算

同时$SG$值仅和集合内数量相关，可以预处理+打表

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

const int mx=,MAXN=1e5+;

//unordered_map<int,int> mp;

int n,k,pre[],vis[MAXN],rem,res;

int sg[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

/*

int solve(int x)

{

    int &tmp=mp[x];

    if(tmp) return tmp;

    int ret=(1<<mx)-1;

    for(int i=1;(1<<(i-1))<=x;i++)

        if(x&(1<<(i-1)))

            ret&=~solve(x&~pre[i]);

    return tmp=ret&(-ret);

}

*/

int main()

{

/*

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

        for(int j=i;j<=mx;j+=i)

            pre[i]|=(1<<(j-1));

    mp.max_load_factor(0.30);

    mp.reserve(750000);

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

        sg[i]=__builtin_ctz(solve((1<<i)-1));

*/

    scanf("%d",&n);

    rem=n;res=;

    for(int i=;i*i<=n;i++)

        if(!vis[i])

        {

            k=;

            for(ll j=i;j<=n;j*=i,k++)

                if(j*j<=n) vis[j]=;

            rem-=k;res^=sg[k];

        }

    res^=(rem&);

    puts(res?"Vasya":"Petya");

    return ;

}

Problem D

与次方相关的注意将大于1的和1次方分开考虑

注意该题各种位运算技巧和$unordered\_ map$以及$builtin\_ ctz,reserve(),max\_load\_factor$的使用

巴特西

[Codeforces #188] Tutorial

Link:

A:

B:

C:

D:

E:

最新文章

热门文章