首页 > 其他分享 >codeforce Round 935 div3 个人题解（A-E）

codeforce Round 935 div3 个人题解（A-E）

时间：2024-03-19 21:34:54浏览次数：27  
标签：map typedef int 题解 queue vector codeforce include div3

A. Setting up Camp

时间限制：每个测试1秒
内存限制：每个测试256兆字节
输入：标准输入
输出：标准输出

组委会计划在游览结束后带领奥林匹克运动会的参赛选手进行徒步旅行。目前，正在计算需要搭帐篷的数量。已知每顶帐篷最多可容纳3人。

在参赛选手中，有a个内向型，b个外向型和c个综合型：

  • 每个内向的人都想独自住在帐篷里。因此，内向者的帐篷里必须只有一个人--只有内向者自己。
  • 每个外向者都希望与另外两个人住在一个帐篷里。因此，一个外向者的帐篷里必须正好有三个人。
  • 每个综合型可以接受任何方式（独居、与一人同住或与两人同住）。
    组委会非常尊重每位参赛者的意愿，因此他们希望满足所有参赛者的愿望。

告诉我们至少需要多少顶帐篷，以满足所有参赛者的愿望。如果无法满足，则输出-1。

输入

每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤104）--测试用例的数量。接下来是测试用例的描述。

每个测试用例由一行描述，其中包含三个整数a、b、c（0≤a,b,c≤109）--分别是内向型、外向型和综合型的数量。

输出

对于每个测试用例，输出一个整数--最少需要的帐篷数，如果无法容纳参赛者，则输出-1。

示例1

input

10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000

output

3
-1
3
-1
3
28
0
7
8
1666666667

说明

在第一个测试用例中，1顶帐篷将分配给内向者，1顶帐篷将由两名外向者和一名综合型共享，最后一顶帐篷将由两名综合型共享。总共需要3顶帐篷。

在第二个测试用例中，三个外向者将使用1个帐篷，1个帐篷将由一个内向者使用。然后，剩下一个外向者和一个综合型。这个外向者将无法与另外两个人一起生活。

解题思路

a一人一顶，b三人一顶，剩下的人和c进行组合，如果总人数小于3则无法组合。

题解

#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 a, b, c;
    cin >> a>>b>>c;
    int cnt = a + (b + c + 2) / 3;
    if (b % 3 != 0 && c + b % 3 < 3)
        cnt = -1;
    cout << cnt << 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. Fireworks

时间限制：每个测试$1$秒
内存限制：每个测试$256$兆字节
输入：标准输入
输出：标准输出

徒步旅行的其中一天恰逢节假日，因此决定晚上在营地安排一场节日焰火表演。为此，徒步旅行的组织者购买了两个烟花发射装置和大量的发射炮弹。

两个装置同时开启。第一个装置每隔$a$分钟(即发射后$a,2⋅a,3⋅a,\dots$分钟)发射一次烟花。第二个装置每$b$分钟(即发射后$b,2⋅b,3⋅b,\dots$分钟)发射一次烟花。

每个烟花在发射后的$m+1$分钟内都可以在天空中看到，也就是说，如果一个烟花是在装置开启后的$x$分钟后发射的，那么从$x$到$x+m$(包括首尾两分钟)的每一分钟都可以看到该烟花。如果一个烟花在另一个烟花$m$
分钟后发射，则两个烟花都将在一分钟内可见。

天空中最多可以同时看到多少枚烟花？

输入

每个测试包含多个测试用例。第一行包含一个整数$t$（$1≤t≤10^4$）--测试用例的数量。接下来是测试用例的说明。

每个测试用例的第一行也是唯一一行包含整数$a$、$b$、$m$($1≤a,b,m≤10^{18}$)--第一次安装、第二次安装的发射频率，以及烟花在天空中可见的时间。

输出

对于每组输入数据，输出一个数字--可同时看到的最大烟花数量。

示例1

input

6
6 7 4
3 4 10
7 8 56
5 6 78123459896
1 1 1
1 1 1000000000000000000

output

2
7
17
28645268630
4
2000000000000000002

说明

在第一组输入数据中，烟花在天空中的可见时间为$5$分钟。由于第一个装置每$6$分钟发射一次烟花，第二个装置每$7$分钟发射一次烟花，因此同一装置发射的两个烟花不会同时出现在天空中。同时，在节日开始$7$分钟后，从第一个营地和第二个营地各发射一个烟花。因此，可以同时看到的烟花不会超过$2$个。

在第三组输入数据中，$112$分钟后可以看到$17$个烟花：

烟花从第一个装置发射的时间为$[ 56,63,70,77,84,91,98,105,112 ]$；
在$[ 56,64,72,80,88,96,104,112 ]$时从第二个装置发射的烟花。

解题思路

照亮时间除以发射间隔即一个装置最多同时存在的烟花数量，由于发射时也算同时存在，所以要额外加2。

题解

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#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 a,b,m;
    cin>>a>>b>>m;
    int temp=2;
    temp+=m/b;
    temp+=m/a;
    cout<<temp<<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. Left and Right Houses

时间限制：每个测试$2$秒
内存限制：每个测试$256$兆字节
输入：标准输入
输出：标准输出

在莱托沃村有$n$栋房子。村民们决定修建一条大路，将村子分为左右两边。每个居民都想住在街道的右侧或左侧，这可以用序列$a_1,a_2,\dots,a_n$来描述，其中$a_j=0$如果$j$th房子的居民想住在街道的左侧；否则，$a_j=1$。

道路将从两栋房子之间穿过。它左边的房子将被宣布为左侧，右边的房子将被宣布为右侧。更正式地说，让道路从房屋$i$和$i+1$之间通过。那么位于$1$和$i$之间的房子将位于街道的左侧，位于$i+1$和$n$之间的房子将位于街道的右侧。道路也可以经过第一栋房屋之前和最后一栋房屋之后；在这种情况下，整个村庄分别被宣布为右侧或左侧。

为了使设计公平，我们决定在铺设道路时，至少要让村子两边各一半的居民对选择感到满意。也就是说，在一侧的$x$个居民中，至少有$\lceil\frac{x}{2}\rceil$个居民愿意住在这一侧，其中$\lceil x\rceil$表示四舍五入的实数$x$。

在路的左边，会有$i$座房子，在相应的$a_j$中，至少要有$\lceil\frac{i}{2}\rceil$个零。路的右边有$n-i$座房子，在相应的$a_j$中至少要有$\lceil\frac{n-i}{2}\rceil$个一。

确定在哪座房子$i$之后铺设道路，以满足所述条件，并尽可能靠近村庄中央。从形式上看，在所有合适的位置$i$中，尽量减少$|n/2-i|$。

如果有多个合适的位置$i$，输出较小的一个。

输入

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

每个测试用例的第一行包含一个整数$n$($3≤n≤3⋅10^5$)。每个测试用例的下一行包含一个长度为$n$的字符串$a$，该字符串仅由$0$和$1$组成。

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

输出

对于每个测试用例，输出一个数字$i$--道路应该铺设在房屋之后的位置(如果道路应该铺设在第一栋房屋之前，则输出$0$)。我们可以证明答案总是存在的。

示例1

input

7
3
101
6
010111
6
011001
3
000
3
110
3
001
4
1100

output

2
3
2
3
0
1
0

说明

让我们来看第一个输入数据的例子。

如果我们在第一栋房屋后铺设道路，那么街道左侧将有一栋房屋$a_1=1$，其居民希望住在街道右侧。那么在偶数边上的$1$户居民中，$0$户居民会对这一选择感到满意，这意味着道路不能铺设在$1$户之后。

如果我们在第二栋房屋后铺设道路，左侧$2$户居民中的$1$户(偏好$a_1=1$，$a_2=0$)和右侧$1$户居民中的$1$户(偏好$a_3=1$)将对选择感到满意。两边各有一半以上的居民对选择感到满意，这意味着道路可以铺设在房屋$2$之后。我们可以证明这是最优答案。

解题思路

使用前缀和数组存储每个区间$1$的数量，然后判断$1$或$0$是否符合条件即可。注意，房子为奇数个的时候村庄中心的坐标并非整数。

题解

#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;
    string s;
    cin >> s;
    s = "0" + s;
    vi sums(n + 2);
    for (int i = 1; i <= n + 1; i++)
    {
        sums[i] = int(s[i] - '0') + sums[i - 1];
    }
    vi ans;
    for (int i = 0; i <= n; i++)
    {
        if (sums[i] <= (i - (i + 1) / 2) && (sums[n] - sums[i]) >= ((n - i + 1) / 2))
            ans.push_back(i);
    }
    int res = ans[0];
    double mid = double(n) / 2.0;
    for (int i = 1; i < ans.size(); i++)
    {
        if (abs(double(ans[i]) - mid) < abs(double(res) - mid))
            res = ans[i];
    }
    cout << res << 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. Seraphim the Owl

时间限制：每个测试$2$秒
内存限制：每个测试$256$兆字节
输入：标准输入
输出：标准输出

大家排成$n$号队，从$i=1$号开始，向猫头鹰谢拉菲姆请教生命的意义。不巧的是，基里尔正忙着为这个问题编写传说，所以他来得晚了一些，站在了$n$号人之后的队尾。基里尔对这种情况完全不满意，于是他决定贿赂一些排在他前面的人。

对于队列中的第$i$th人，基里尔知道两个值：$a_i$和$b_i$。如果此刻基里尔站在位置$i$上，那么他可以选择任意一个位置$j$，比如$j<i$，然后与位置$j$上的人交换位置。在这种情况下，基里尔需要支付他$a_j$个硬币。而对于$j<k<i$的每一个$k$，基里尔都要向位置$k$的人支付$b_k$个硬币。

基里尔很节俭，所以他想花尽可能少的硬币，但是他又不想等太久，所以基里尔认为他应该排在第一个$m$人中。

请帮助基里尔确定，为了不等太久，他最少需要花费多少金币。

输入

每个测试由几组输入数据组成。第一行包含一个整数$t$($1≤t≤104$) - 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数$n$和$m$($1≤m≤n≤200000$)--分别是除基里尔外排队人数和基里尔最终位置的最大允许值。

第二行包含$n$个整数$a_1,a_2,…,a_n$，中间用空格隔开($1≤a_i≤10^9$)。

第三行包含$n$个整数$b_1,b_2,…,b_n$，用空格隔开($1≤b_i≤10^9$)。

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

输出

对于每个测试用例，输出一个整数 - Kirill 需要花费的最少金币数。

示例1

input

4
4 2
7 3 6 9
4 3 8 5
6 2
6 9 7 1 8 3
5 8 8 1 4 1
7 7
7 2 9 2 6 5 9
9 1 10 7 1 4 9
2 1
2 3
1 1

output

14
22
9
3

解题思路

为了找到最少花费的金币数，从队伍的末尾开始向前遍历。对于每个位置 $i$，我们计算排在第 $i$ 个人后面的所有人中的最小 $m-i$ 个人的金币花费之和，并加上排在第 $i$ 个人前面的人与他交换位置所需的金币数。在遍历中不断更新最小金币花费数。

题解

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#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()
{
    ll n, m;
    cin >> n >> m;
    vl a(n);
    vl b(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    ll s = 0;
    ll ans = INT64_MAX;
    for (int i = n - 1; i >= 0; i--)
    {
        if (i + 1 <= m)
        {
            ans = min(ans, s + a[i]);
        }
        s += min(a[i], b[i]);
    }
    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;
}

E. Binary Search

时间限制：每个测试$2$秒
内存限制：每个测试$256$兆字节
输入：标准输入
输出：标准输出

安东在徒步旅行中感到无聊，想解决一些问题。他问基里尔有没有新问题，基里尔当然有。

给你一个大小为$n$的排列数$p$和一个需要求出的数字$x$。长度为$n$的排列是由$n$个不同的整数组成的数组，这些整数从$1$到$n$依次排列。例如，$[2,3,1,5,4]$是一个排列数组，但$[1,2,2]$不是排列数组($2$在数组中出现了两次)，$[1,3,4]$也不是排列数组($n=3$但数组中有$4$)。

你认为自己是一个很酷的程序员，所以你将使用一种高级算法进行搜索--二分查找。但是，你忘了二分查找必须对数组进行排序。

为了得到正确的答案，你可以在运行算法之前执行以下操作不超过$2$次：选择索引$i$，$j$($1≤i,j≤n$)并交换位置$i$和$j$上的元素。

然后，执行二分查找。在算法开始时，声明两个变量$l=1$和$r=n+1$。然后执行下面的循环：

  • 如果$r-l=1$，结束循环
  • $m=\left\lfloor\frac{r+l}{2}\right\rfloor$
  • 如果$p_m\leq x$，赋值$l=m$，否则$r=m$

我们的目标是在算法之前重新排列排列组合中的数字，以便在算法执行之后，$p_l$等于$x$。可以证明$2$操作总是足够的。

输入

每个测试由多个测试用例组成。第一行包含一个整数$t$($1≤t≤2⋅10^4$) - 测试用例的数量。然后是测试用例的说明。

每个测试用例的第一行包含两个整数$n$和$x$($1≤x≤n≤2⋅10^5$)--排列的长度和要找到的数字。

第二行包含由空格分隔的排列$p$($1≤p_i≤n$)。

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

输出

对于每个测试用例，在第一行输出一个整数$k$($0≤k≤2$) - 您执行的操作数。在接下来的$k$行中，输出$2$个整数$i$、$j$($1≤i,j≤n$) 用空格隔开，表示正在交换位置$i$和$j$的元素。

请注意，您不需要尽量减少操作次数。

示例

input

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

output

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

解题思路

先将$x$放在边界上，然后不断循环二分，直到终止在某一位置，然后将在边界上的$x$与这个位置互换。由于$x$存放在边界上，所以不会影响二分的循环。

题解

#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, x;
    cin >> n >> x;
    vi a(n);
    int loc = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] == x)
            loc = i + 1;
    }
    int l = 0;
    int r = n;
    int cnt = 0;
    vpii ans;
    if (loc != n) 
    {
        cnt++;
        swap(a[loc - 1], a[n - 1]);
        ans.push_back({ loc, n });
    }
    while ((r - l) > 1)
    {
        int m = (r + l) / 2;
        if (a[m] <= x)
            l = m;
        else
            r = m;
    }
    if (l != n - 1)
    {
        cnt++;
        ans.push_back({ l + 1, n });
    }

    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) 
    {
        cout << ans[i].first << " " << ans[i].second<<endl;
    }
}

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

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

相关文章

  • 20240319每日一题题解
    20240319每日一题题解Problem判断一个数的结构是否为某个数重复两遍得到。例如，\(123123\)是重复两遍的数，而\(333\)，\(809680\)​则不是保证输入的数字不超过longlong型范围。若是，则输出yes；否则输出no。Solution从数字的角度要想解决这个问题也不是不可以，但是不如将给定的数......
  • 【蓝桥杯选拔赛真题70】python最短路径和 第十五届青少年组蓝桥杯python选拔赛真题 算
    目录python最短路径和一、题目要求1、编程实现2、输入输出二、算法分析三、程序编写四、程序说明五、运行结果六、考点分析七、 推荐资料1、蓝桥杯比赛2、考级资料3、其它资料python最短路径和第十五届蓝桥杯青少年组python比赛选拔赛真题一、题目要求（注：i......
  • CodeForces 1945H GCD is Greater
    洛谷传送门CF传送门感觉是这场唯一比较有趣的题？首先明确一点：先手只会选\(2\)个数，因为数多了\(\gcd\)会变小，而且对方的\(\text{and}\)会变大。所以对于某一位，若\(0\)的个数\(\ge3\)那么对方的按位与这一位一定是\(0\)。所以若\(0\)的个数\(\le2\)，那么可能会......
  • Codeforces Round 923 (Div. 3) D. Find the Different Ones!
    写点简单的思维题https://codeforces.com/problemset/problem/1927/D思路：用两个数组，一个存储原始数据，一个用nex存该位置第一次不一样的下标#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<str......
  • [ABC345F] Many Lamps 题解
    题意：给定一个\(n\)个点\(m\)条边的无向图，每个点的初始颜色为\(0\)。一次操作是将一条边的两个端点的颜色翻转。求是否能通过若干次操作使得最终有\(k\)个颜色为\(1\)的点。首先考虑什么情况下无解。会发现每一次操作，颜色为\(1\)的点的数量变化一定是\([0,+2,-2]\)......
  • CF1935 A-C题解
    A设\(s\)翻转后的字符串为\(t\)，考虑进行\(n\)次操作可能生成出哪些字符串：只进行翻转操作——\(s\)；先复制再\(n-1\)次翻转——\(s+t\)；先翻转，再复制，再翻转\(n-2\)次，\(t+s\)；多次复制的情况。情况2显然劣于情况1；情况4得到的字符串的开头一定是\(s\)或者\(t\)......
  • 初三多项式的运算练习 题解
    初三多项式的运算练习题解美好的下午时光要拿来写题解呜呜呜，一篇一篇地鸽得了。有些题要用到GF的知识，或许我可以找时间讲一下？贴一份我的FFT和NTT的板子。FFT：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn,m,limit,f[1<<22],g[1......
  • 洛谷 P2934 [USACO09JAN] Safe Travel G 题解
    前话貌似别人都是使用并查集维护的方法，然而由于排序、最短路等算法瓶颈，以下令\(n\)和\(m\)同阶，总的时间复杂度依然是\(\Theta(n\logn)\)的，那么并查集是否有点大材小用了。事实上，在建完最短路径树后，我给出了两种带\(\log\)的数据结构完成此题。题目分析翻译里已经把问......
  • 腾讯春招内参：2024最全Spring Boot面试题解析，技术精英必备！
    随着2024年春季招聘季的来临，腾讯再次开启了对富有才华和创新精神的技术人才的寻找之旅。作为一家全球领先的互联网科技公司，腾讯在寻找那些不仅拥有扎实的技术基础，而且能够适应快速发展和变化的行业环境的候选人。在众多技术栈中，SpringBoot作为简化Spring应用开发的工具，因其......
  • 1948.Educational Codeforces Round 163 - sol
    202403补题效率低下。场上发挥并不是很好，A~E都是简单的，而场上没有去推F的式子，只是找了找规律，然后发现是一个不可做的东西就下播了。如果直接推式子就会很快地做出来，还是非常可惜。A.SpecialCharactersYouaregivenaninteger\(n\).Yourtaskistobuildast......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99