[Codeforces #192] Tutorial

Link:

Codeforces #192 传送门

前两天由于食物中毒现在还要每天挂一天的水

只好晚上回来随便找套题做做找找感觉了o(╯□╰)o

A：

看到直接大力模拟了

但有一个更简便的方法，复杂度为$O(被禁止的格子数)$

如果将每个黑格子上下左右四条线都染上色

可以发现一个格子最终无法被“净化”当且仅当其被左右/上下来向都染过色，所以将最终无法净化的格子合并是一个矩形

这样最终答案为：黑格子出现的行的个数*黑格子出现的列的个数

此时复杂度就变成与黑格子个数相关了

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

int n,m,cnt,vis[][];char dat[][];

int main()

{

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

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

        scanf("%s",dat[i]+);

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

    {

        bool f=;

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

            if(dat[i][j]=='S'){f=;break;}

        if(f) continue;

        for(int j=;j<=m;j++) vis[i][j]=;

    }

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

    {

        bool f=;

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

            if(dat[j][i]=='S'){f=;break;}

        if(f) continue;

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

    }

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

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

            cnt+=vis[i][j];

    printf("%d",cnt);

    return ;

}

Problem A

B：

发现菊花树满足任意两点之间距离不超过2

因此只要找到中心点就好了

又发现禁止的对数少于n/2，这样肯定有点没有禁止的点

这样找到没有限制的点作为中心构造菊花树即可

其实这是个结论：

保证任意两点间距离不超过2，只有菊花树满足条件

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

int n,m,x,y,cnt[];

int main()

{

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

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

        scanf("%d%d",&x,&y),cnt[x]++,cnt[y]++;

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

        if(!cnt[i])

        {

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

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

                if(i!=j) printf("%d %d\n",i,j);

            return ;

        }

    return ;

}

Problem B

C：

挺好想的，发现有解必为n个

这样先排除无解情况再以行/列为基准顺次找到n个即可

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

typedef long long ll;

typedef pair<int,int> P;

int n,posr[],posc[];

char dat[][];

int main()

{

    scanf("%d",&n);

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

        scanf("%s",dat[i]+);

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

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

            if(dat[i][j]=='.') posr[i]=j,posc[j]=i;

    bool f1=,f2=;

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

    {

        if(!posr[i]) f1=;

        if(!posc[i]) f2=;

    }

    if(!f1&&!f2) return puts("-1"),;

    if(f1)

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

            printf("%d %d\n",i,posr[i]);

    else

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

            printf("%d %d\n",posc[i],i);

    return ;

}

Problem C

D：

可以将所有中途相遇都转化为终点相遇

这样并不会使得是否相遇收到影响

此时就能推出走最短路必定最优的结论了

将终点设为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 MAXN=;

P S,T;char dat[MAXN][MAXN];

int n,m,res,dist[MAXN][MAXN],mx;

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

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

int main()

{

    memset(dist,-,sizeof(dist));

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

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

        scanf("%s",dat[i]+);

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

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

        {

            if(dat[i][j]=='S') S=P(i,j);

            if(dat[i][j]=='E') T=P(i,j);

        }

    queue<P> q;q.push(T);

    dist[T.X][T.Y]=;

    while(!q.empty())

    {

        P t=q.front();q.pop();

        int x=t.X,y=t.Y;

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

        {

            int fx=x+dx[i],fy=y+dy[i];

            if(fx<||fx>n||fy<||fy>m) continue;

            if(dist[fx][fy]!=-||dat[fx][fy]=='T') continue;

            dist[fx][fy]=dist[x][y]+;

            q.push(P(fx,fy));

        }

    }

    mx=dist[S.X][S.Y];

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

        for(int j=;j<=m;j++)//这里dist[i][j]！=-1不能漏

            if(dat[i][j]>=''&&dat[i][j]<=''&&dist[i][j]!=-&&dist[i][j]<=mx)

                res+=dat[i][j]-'';

    printf("%d",res);

    return ;

}

Problem D

E：

考试时构造了很久确定解都觉得实现不了

最后发现能随机艹过去……

确定解：

寻找确定解时，有一点是我也想到的：将最终解构造成一条链

但还有一个重要性质：>=7时必定有解

那么对于<=7的小数据阶乘暴力即可

找到最大的连通块，将奇数项放前面，偶数项放后面

同时将第一第二项交换位置（如ABCDEF->CAEBDF）

这样就保证即使没有其它连通块，当前情况也能满足要求

接下来将其它连通块不断间隔式插入即可

在讨论里又看到了一个方法：

将序列转换并使其保持如下性质：

对于每个连通块，每一个点原来的相邻点都在其邻近的两格之内

这样将i和i+3连边即可（待填坑……）

随机算法：

其实算一算随机一个序列正确的概率还是很高的

(1-2/n)^n约等于0.135，反正随机100次应该就够了

于是就愉快得不用构造确定解了……

所以说，有时候还是要有点梦想

算算概率说不定随机就能随便过了……

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

map<P,int> mp;

int n,m,x,y,a[];

int main()

{

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

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

        scanf("%d%d",&x,&y),mp[P(x,y)]=,mp[P(y,x)]=;

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

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

    {

        random_shuffle(a+,a+n+);

        bool f=;a[n+]=a[];

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

            if(mp[P(a[j],a[j+])]){f=;break;}

        if(!f) continue;

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

            printf("%d %d\n",a[j],a[j+]);

        return ;

    }

    puts("-1");

    return ;

}

Problem E

巴特西

[Codeforces #192] Tutorial

Link:

A：

B：

C：

D：

E：

确定解：

随机算法：

最新文章

热门文章