CF大陆斗C战士（一）

C. Set Construction

题目大意

根据二进制矩阵b需要构造n个集合 A1~An,满足当b[i,j]=1时Ai是Aj的真子集找到此集合并打印题目保证一定有解

题目分析

我们可以先每个集合中各放一个数遍历矩阵当 b[i,j]=1时将 Ai 的元素放到 Aj 中即可

因数据一定有解则不会出现 Ai 在后续被改变的情况只有当 b[i, j] = b[j, i] == 1时才可能改变但是此时不满足真子集的要求

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, k, t;
char b[N][N];

void solve()
{
    set<int>q[N];
    cin >> n;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
            cin >> b[i][j];
        q[i].insert(i);
    }

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
        {
            if(b[i][j] == '1')
            {
                for(auto k : q[i])
                    q[j].insert(k);
            }
        }

    for(int i = 1; i <= n; i ++)
    {
        cout << q[i].size() << " ";
        for(auto k : q[i])
            cout << k << " ";
        puts("");
    }
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}

C. Phase Shift

题目大意

将26个小写英文字母按一定顺序排列成一个圆圈然后将s中的每个字母按顺时针顺序替换为后面的字母这样就得到了字符串t。给定一个字符串t。确定字典上最小的字符串s

题目分析

注意要找的是最小的原型串只需要使每一位对应的字母在满足要求的条件下尽可能小即可不必纠结26个字母的排列顺序。

确定原型时为了使字典序尽可能小所以应使其对应的字母尽可能小所以确定每一位时都要从a~z

遍历一遍。

要使26个字母排成环那么在最后一个字母之前是不可以成环的我们可以通过并查集判断是不是会同根来判断是否成环。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, k, t;
bool st[N], sy[N];
int p[N], w[N];
string s;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void solve()
{
    memset(st, 0, sizeof st);
    memset(sy, 0, sizeof sy);

    cin >> n >> s;
    s = " " + s;

    for(int i = 'a'; i <= 'z'; i ++) p[i] = i;

    int sum = 0;
    for(int i = 1; i <= n; i ++)
    {
        int ch = find(s[i]);
        if(st[s[i]])
        {
            cout << (char)w[s[i]];
            continue;
        }

        for(int j = 'a'; j <= 'z'; j ++)
        {
            if(find(j) == ch && sum < 25) continue;
            if(sy[j]) continue;

            sy[j] = st[s[i]] = true;
            p[s[i]] = find(j);
            w[s[i]] = j;

            cout << char(j) ;

            sum ++;
            break;
        }
    }
    puts("");
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}

C. Doremy’s City Construction

题目大意

城市可以看作是一个简单的有n个顶点的无向图。第i个顶点高度为 ai。正在决定哪对顶点应该与边相连。图中不应该有自环或多边。不存在 au≤av≤aw 的情况下 有边 (u,v)和 (v,w)在这些约束条件下求图中最大可能的边数

题目分析

根据题意可以知道一个点不可以同时连比他大和比他小两种类型的点那么我们可以分成两组来讨论高度小于等于此点的数量A与高度高于此点的数量B

对于一个点u来说比B[u]的任意一个点都可以连A[u]中的点鹅B[u]中的点不可以互连则此时可以连A[u] * B[u]个点

遍历每个点只要出最大值即可。因map容器有自动按键大小排列的特性以下代码用它来求两种点的数量。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
typedef long long ll;

ll n, m, k, t;

void solve()
{
    map<int, int>q;

    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int u;
        cin >> u, q[u] ++;
    }

    ll res = 0, sum = 0;
    ll ans = 0;
    for (auto it = q.begin(); it != q.end(); it++)
	{
	    sum += it->second;
	    ans = max(sum * (n - sum), ans);
	}

	if(!ans) cout << n / 2 << "\n";
	else cout << ans << "\n";
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}