首页 > 其他分享 >codeforce Round 934 div2 个人题解（A~C）

codeforce Round 934 div2 个人题解（A~C）

时间：2024-03-17 11:57:23浏览次数：30  
标签：map typedef int 题解 queue vector codeforce include Round

A. Destroying Bridges

时间限制: 1秒
内存限制: 256兆
输入: 标准输入
输出: 标准输出

有 $n$ 个岛屿，编号为 $1,2,…,n$。最初，每对岛屿都由一座桥连接。因此，一共有 $\frac{n(n-1)}{2}$ 座桥。

Everule 住在岛屿 $1$ 上，喜欢利用桥梁访问其他岛屿。Dominater 有能力摧毁最多 $k$ 座桥梁，以尽量减少 Everule 可以使用(可能是多座)桥梁到达的岛屿数量。

如果 Dominater 以最佳方式摧毁桥梁，求 Everule 可以访问的岛屿(包括岛屿 $1$)的最少数量。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \leq t \leq 10^3$) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行也是唯一一行包含两个整数 $n$ 和 $k$ ($1 \leq n \leq 100$, $0 \leq k \leq \frac{n \cdot (n-1)}{2}$)。

输出

针对每个测试案例，输出如果 Dominater 以最佳方式摧毁桥梁，Everule 可以访问的最少岛屿数量。

示例

输入

6
2 0
2 1
4 1
5 10
5 3
4 4

输出

2
1
4
1
5
1

注意

在第一个测试案例中，由于无法摧毁桥梁，所以所有岛屿都可以到达。

在第二个测试案例中，您可以摧毁 $1$ 岛和 $2$ 岛之间的桥梁。Everule 将无法访问岛屿 $2$，但仍然可以访问岛屿 $1$。因此，Everule 可以访问的岛屿总数为 $1$。

在第三个测试案例中，尽管 Dominater 做了什么，Everule 总是有办法到达所有的岛屿。例如，如果 "多米那 "摧毁了岛屿 $1$ 和 $2$ 之间的桥梁，由于 $1$ 和 $3$ 之间以及 $3$ 和 $2$ 之间的桥梁没有被摧毁，埃弗鲁勒仍然可以通过 $1→3→2$ 到达岛屿 $2$。

在第四个测试案例中，你可以摧毁 $k = \frac{n \cdot (n-1)}{2}$ 之后的所有桥梁。Everule 将只能访问 $1$ 岛($1$ 岛)。

解题思路

$n$个岛屿，每个岛屿之间相互连接，那么一座岛屿最多有$n-1$座桥连接，如果$k>=n-1$，直接把1岛上的所有桥全拆了，只能经过一座岛。如果$k<n-1$，那么无论怎么拆所有岛都是联通的。

题解

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>

#define endl '\n'

#define ft first
#define sd second

#define yes std::cout<<"Yes\n"
#define no std::cout<<"No\n"


using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;

typedef vector<vi> vvi;
typedef vector<vl> vvl;

typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <pll> qpll;
typedef queue <psi> qpsi;
typedef queue <psl> qpsl;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;

typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<string, int> msi;
typedef map<string, ll> msl;

typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;


void cinv(vi vec, int n)
{
    for (int i = 1; i <= (n); i++)
        cin >> (vec)[i];
}
void rcinv(vi vec, int n)
{
    for (int i = (n); i >= 1; i--)
        cin >> (vec)[i];
}
void coutv(vi vec, int n)
{
    for (int i = 1; i <= (n); i++)
        cout << (vec)[i] << " ";
    cout << '\n';
}
void rcoutv(vi vec, int n)
{
    for (int i = (n); i >= 1; i--)
        cout << (vec)[i] << " ";
    cout << '\n';
}


void solve()
{
    int n, k;
    cin >> n >> k;
    if (k >= n - 1)
        cout << 1 << endl;
    else
        cout << n << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B. Equal XOR

时间限制: 1秒
内存限制: 256兆
输入: 标准输入
输出: 标准输出

给你一个长度为 $2n$ 的数组 $a$，它由 $1$ 到 $n$ 的每个整数组成，每个整数包含次。

同时给你一个整数 $k$ ($1 \leq k \leq \lfloor \frac{n}{2} \rfloor$)。

你需要找出两个长度分别为 $2k$ 的数组 $l$ 和 $r$，使得：

  • $l$ 是 $[a_1,a_2,…,a_n]$ 的子集
  • $r$ 是 $[a_{n+1},a_{n+2},…,a_{2n}]$ 的子集
  • $l$ 元素的位向 XOR 等于 $r$ 元素的位向 XOR；换句话说，$l_1 \oplus l_2 \oplus … \oplus l_{2k} = r_1 \oplus r_2 \oplus … \oplus r_{2k}$

可以证明，至少有一对 $l$ 和 $r$ 总是存在的。如果有多个解，可以输出其中任意一个。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \leq t \leq 5000$) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含 $2$ 个整数 $n$ 和 $k$ ($2 \leq n \leq 5 \times 10^4$, $1 \leq k \leq \lfloor \frac{n}{2} \rfloor$)。

第二行包含 $2n$ 个整数 $a_1,a_2,…,a_{2n}$ ($1 \leq a_i \leq n$)。保证从 $1$ 到 $n$ 的每个整数在 $a$ 中恰好出现两次。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^4$。

输出

每个测试用例输出两行。

在第一行输出中，输出 $2k$ 个整数 $l_1,l_2,…,l_{2k}$。

在第二行输出中，输出 $2k$ 个整数 $r_1,r_2,…,r_{2k}$。

如果有多个解，可以输出其中任意一个。

示例

输入

4
2 1
1 2 2 1
6 1
6 4 2 1 2 3 1 6 3 5 5 4
4 1
1 2 3 4 1 2 3 4
6 2
5 1 3 3 5 1 2 6 4 6 4 2

输出

2 1
2 1
6 4
1 3
1 2
1 2
5 1 3 3
6 4 2 4

注意

在第一个测试案例中，我们选择 $l=[2,1]$ 和 $r=[2,1]$。 $[2,1]$ 是 $[a_1,a_2]$ 的子集，$[2,1]$ 是 $[a_3,a_4]$ 的子集，$2 \oplus 1 = 2 \oplus 1 = 3$。

在第二个测试案例中，我们选择 $6 \oplus 4 = 1 \oplus 3 = 2$。

解题思路

根据$A\oplus A = 0$和$B\oplus 0 = B$即可知道，左半部分和右半部分只能形成$a,a,b$和$b,c,c$或$a,b,c$和$a,b,c$这两种组合方式。所以只要将左半中分成，在左半中只有一个的数字和在左半中只要两个的数字，即$l1=[a,a]$和$l2=[b]$然后再依次输出$2k$个即可。右半同理。

题解

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>

#define endl '\n'

#define ft first
#define sd second

#define yes std::cout<<"Yes\n"
#define no std::cout<<"No\n"


using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;

typedef vector<vi> vvi;
typedef vector<vl> vvl;

typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <pll> qpll;
typedef queue <psi> qpsi;
typedef queue <psl> qpsl;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;

typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<string, int> msi;
typedef map<string, ll> msl;

typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;


void cinv(vi vec, int n)
{
    for (int i = 1; i <= (n); i++)
        cin >> (vec)[i];
}
void rcinv(vi vec, int n)
{
    for (int i = (n); i >= 1; i--)
        cin >> (vec)[i];
}
void coutv(vi vec, int n)
{
    for (int i = 1; i <= (n); i++)
        cout << (vec)[i] << " ";
    cout << '\n';
}
void rcoutv(vi vec, int n)
{
    for (int i = (n); i >= 1; i--)
        cout << (vec)[i] << " ";
    cout << '\n';
}


void solve()
{
    int n, k;
    cin >> n >> k;
    vi l(n+1);
    vi r(n+1);
    mii mp;
    vi ansl1;
    vi ansl2;
    vi ansr1;
    vi ansr2;
    for(int i=1;i<=n;i++)
    {
        cin >> l[i];
        mp[l[i]]++;
        if (mp[l[i]] == 2)
        {
            ansl2.push_back(l[i]);
            ansl2.push_back(l[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cin >> r[i];
        if (mp[r[i]] == 1)
        {
            ansl1.push_back(r[i]);
            ansr1.push_back(r[i]);
        }
        else if(mp[r[i]]==0)
        {
            ansr2.push_back(r[i]);
            ansr2.push_back(r[i]);
            mp[r[i]]+=2;
        }
    }
    sort(ansl1.begin(), ansl1.end());
    sort(ansr1.begin(), ansr1.end());

    int len = ansl2.size();
    for (int i = 0; i < 2 * k; i++)
    {
        if (i < len)
            cout << ansl2[i] << " ";
        else
            cout << ansl1[i - len] << " ";
    }
    cout << endl;
    for (int i = 0; i < 2 * k; i++)
    {
        if (i < len)
            cout << ansr2[i] << " ";
        else
            cout << ansr1[i - len] << " ";
    }
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C. MEX Game 1

时间限制: 2秒
内存限制: 256兆
输入: 标准输入
输出: 标准输出

爱丽丝和鲍勃在一个大小为 $n$ 的数组 $a$ 上玩另一场游戏。爱丽丝从一个空数组 $c$ 开始。双方轮流行动，爱丽丝先行动。

轮到爱丽丝时，她从数组 $a$ 中选择一个元素，将其追加到 $c$ 中，然后从 $a$ 中删除。

轮到鲍勃时，他从 $a$ 中选择一个元素，然后从 $a$ 中删除。

当数组 $a$ 为空时，游戏结束。游戏的得分定义为 $c$ 的 MEX†。爱丽丝希望最大化得分，而鲍勃希望最小化得分。找出双方都以最优方式进行游戏时的爱丽丝的最终得分。

† 整数数组的 MEX (最小排除数) 定义为数组中不出现的最小非负整数。例如：

  • [2,2,1] 的 MEX 是 0，因为 0 不属于数组。
  • [3,1,0,1] 的 MEX 是 2，因为 0 和 1 属于数组，但 2 不属于数组。
  • [0,3,1,2] 的 MEX 是 4，因为 0、1、2 和 3 属于数组，但 4 不属于数组。

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \leq t \leq 2 \times 10^4$) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \times 10^5$)。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ ($0 \leq a_i < n$)。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出

对于每个测试用例，找出如果双方都以最佳方式进行游戏时，爱丽丝的得分。

示例

输入

3
4
0 0 1 1
4
0 1 2 3
2
1 1

输出

2
1
0

注意

在第一个测试用例中，得分为 2 的可能游戏如下：

  • 爱丽丝选择元素 1。这一步之后是 $a=[0,0,1]$ 和 $c=[1]$。
  • 鲍勃选择元素 0。这一步之后是 $a=[0,1]$ 和 $c=[1]$。
  • 爱丽丝选择元素 0。之后是 $a=[1]$ 和 $c=[1,0]$。
  • 鲍勃选择元素 1。这一步之后是 $a=[]$ 和 $c=[1,0]$。
  • 最后是 $c=[1,0]$，其 MEX 为 2。请注意，这只是一个实例对局，并不一定代表双方的最优策略。

解题思路

Alice的最优策略一定是从0开始从小到大拿，Bob的最优策略一定是想办法从中间断掉Alice递增序列。那么拿什么数字一定可以段掉Alice的递增序列呢？只要一个的数字。所以Bob要优先拿只有一个的数字中最小的那一个。由于Alice先手，所以最小的那个Alice一定会第一时间拿走，所以第二小的只有一个的数字Bob一定可以拿走，那个数字就是答案。

题解

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>

#define endl '\n'

#define ft first
#define sd second

#define yes std::cout<<"Yes\n"
#define no std::cout<<"No\n"


using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;

typedef vector<vi> vvi;
typedef vector<vl> vvl;

typedef queue <int> qi;
typedef queue <ll> ql;
typedef queue <pii> qpii;
typedef queue <pll> qpll;
typedef queue <psi> qpsi;
typedef queue <psl> qpsl;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;

typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<string, int> msi;
typedef map<string, ll> msl;

typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;


void cinv(vi vec, int n)
{
    for (int i = 1; i <= (n); i++)
        cin >> (vec)[i];
}
void rcinv(vi vec, int n)
{
    for (int i = (n); i >= 1; i--)
        cin >> (vec)[i];
}
void coutv(vi vec, int n)
{
    for (int i = 1; i <= (n); i++)
        cout << (vec)[i] << " ";
    cout << '\n';
}
void rcoutv(vi vec, int n)
{
    for (int i = (n); i >= 1; i--)
        cout << (vec)[i] << " ";
    cout << '\n';
}


void solve()
{
    int n; cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    mii mp;
    for (int i = 0; i < n; i++)
    {
        mp[a[i]]++;
    }
    int ans = 0;
    bool flag = true;
    for (int i = 0; i <= n; i++)
    {
        if (mp[i] == 0)
        {
            ans = i;
            break;
        }
        else if (mp[i] == 1)
        {
            if (flag)
                flag = false;
            else
            {
                ans = i;
                break;
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

一个小时就写完了前三题，D题搓了一个小时没写出了，麻了。这场出的不咋地，难度跨度太大了，A,B,C基本上算签到题，D题又是一道2000的题。

标签：map,typedef,int,题解,queue,vector,codeforce,include,Round
From： https://www.cnblogs.com/extractstars/p/18078378

相关文章

  • AtCoder-abc345_f题解
    题意简述给定一个无向图。你要在其中选出一些边，使得选出的边所构成的图中，度数为奇数的点有\(K\)个。如果可以，输出选了哪些边，否则输出-1。思路首先在选一条边时，边两端点度数的奇偶性一定都会改变，即要么都变为奇数，要么两个点的奇偶性交换过来，要么都变为偶数。这三种情况时满足......
  • P2633 Count on a tree 题解
    题目链接：Countonatree大概可以认为是树上主席树的板子我在之前的某些题解提到了，主席树一般来说有两个基本功能：可持久化功能，可以选择回退或者新增版本。对于可差性问题，可以有更好的转化为前缀和做法，常见的问题为权值类型问题。在树上的路径第\(k\)大，显然如果我们能......
  • 【洛谷 P8661】[蓝桥杯 2018 省 B] 日志统计 题解（滑动窗口+优先队列+双端队列+集合）
    [蓝桥杯2018省B]日志统计题目描述小明维护着一个程序员论坛。现在他收集了一份“点赞”日志，日志共有NNN行。其中每一行的格式是tsid，表示在......
  • 【洛谷 P8602】[蓝桥杯 2013 省 A] 大臣的旅费 题解（图论+深度优先搜索+树的直径+链式
    [蓝桥杯2013省A]大臣的旅费题目描述很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同......
  • [CF1943C] Tree Compass 题解
    不会2300，完蛋了/lh题目链接题目分析容易想到先求出直径，然后以直径中点为圆心画\({d\over2}+O(1)\)个圆。具体地，设直径点数为\(d\)。当\(d\)为奇数时，上述构造需要\(d+1\over2\)次操作；当\(d\)为偶数时，上述构造需要\({d\over2}+1\)次操作。尝试证明上述......
  • AT_abc345_d 题解
    是个逆天搜索。最开始：爆搜，启动！然后TLE到飞起。赛后：我【数据删除】这么简单的吗？！dfs每个位置，试着把没放过的块放到以这个位置为左上角的区域里面。好了没了，就是这么简单！对了记得这个块可以旋转！#include<stdio.h>#include<bits/stdc++.h>#defineN1000010#defineMOD9......
  • 关于nvim插件telescope-fzf-native在windows下未构建的问题解决
    关于nvim插件telescope-fzf-native在windows下未构建的问题解决首先进入文件夹（没有就自己创建注意文件夹名就是telescope-fzf-native.nvim）C:\Users\...\AppData\Local\nvim-data\site\pack\packer\start\telescope-fzf-native.nvim进入此路径的powershell或者cmd命令行，执行......
  • 启动应用程序出现cmdial32.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题，如果是新手第一时间会认为是软件或游戏出错了，其实并不是这样，其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库，这时你可以下载这个cmdial32.dll文件(挑选合适的版本文件)把它......
  • 启动应用程序出现comcat.dll找不到问题解决
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题，如果是新手第一时间会认为是软件或游戏出错了，其实并不是这样，其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库，这时你可以下载这个comcat.dll文件(挑选合适的版本文件)把它放......
  • CF56D Changing a String 题解
    双倍经验：P2758。令\(dp_{i,j}\)表示\(s\)前\(i\)个字符要变成\(t\)前\(j\)个字符所需的最少移动次数。答案即为\(dp_{\lverts\rvert,\lvertt\rvert}\)。显然有初始状态\(dp_{i,0}=dp_{0,i}=i\)。因为我们只可能从添、删、替三种操作转移而来，于是有转移方程：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99