Codeforces Round #761 (Div. 2)

A. Forbidden Subsequence

题目

知识点

排序

解题思路

​ 根据题意，我们很容易知道当 T = a b c T = abc T=abc 时且我们 S S S 中 a , b , c a,b,c a,b,c都有出现时，我们最小的 S ′ S' S′ 按照 a c b d e f g . . . z acbdefg...z acbdefg...z 进行排序是最优的, 否则按照字典序 a b c d e . . . z abcde...z abcde...z是最优的 。

​ 所以我们只要判断 T T T 是否为 a b c abc abc, S S S 中 a , b , c a,b,c a,b,c是否全都有出现，然后写一下cmp函数就行了。

​ （详细见代码）

代码

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n'
#define between(x, l, r) (x >= l && x <= r)
#define point(a, b, m) ((a - 1) * m + b)
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define y second
#define x first
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int N = 3e5 + 10, M = 2 * N, mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

bool cmp(char a, char b)
{
    if(a == 'b' && b == 'c') return 0;
    if(b == 'b' && a == 'c') return 1;
    return a < b;
}

void solve()
{
    string s, t;
    cin >> s >> t;
    int num[100] = {0};
    for (auto &it : s) num[it - 'a'] ++ ;
    
    if(t == "abc" && num[0] && num[1] && num[2]) sort(all(s), cmp);
    else sort(all(s));
    
    cout << s << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.precision(2), cout.setf(ios::fixed);
    int t;
    cin >> t;
    while (t -- )
    solve();
    return 0;
}

B. GCD Problem

题目

知识点

数论

解题思路

​ 如果 n n n 是偶数

​ 我们可以构造 c = 1 c = 1 c=1, a = ( n − 1 ) / 2 a = (n - 1) / 2 a=(n−1)/2 , b = n − 1 − a b = n - 1 - a b=n−1−a

​ 由于 ∣ a − b ∣ = 1 |a - b| = 1 ∣a−b∣=1， 所以 g c d ( a , b ) = 1 gcd(a, b) = 1 gcd(a,b)=1

​ 如果 n n n 为偶数

​ 我们令 c = 1 c = 1 c=1， 然后暴力的遍历 a , b a, b a,b ，寻找满足 g c d ( a , b ) = 1 , a + b = n − 1 gcd(a, b) = 1, a+b=n - 1 gcd(a,b)=1,a+b=n−1 的一对 ( a , b ) (a, b) (a,b)

​ 我们打表可以发现 g c d ( a , n − 1 − a ) = 1 gcd(a, n - 1 - a) = 1 gcd(a,n−1−a)=1 的数的间隔不会太大，所以暴力不会超时。

​ （详细见代码）

代码

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n'
#define between(x, l, r) (x >= l && x <= r)
#define point(a, b, m) ((a - 1) * m + b)
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define y second
#define x first
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int N = 3e5 + 10, M = 2 * N, mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

/*
gcd(a, b) = c
a + b + c = n
(k + 1) * c == n
c =

如果 n是偶数
c = 1
a = (n - 1) / 2
b = n - 1 - a
*/

void solve()
{
    int n;
    cin >> n;
    if(n % 2 == 0)
    {
        int a = (n - 1) / 2, b = n - 1 - a;
        int c = 1;
        cout << a << ' ' << b << ' ' << c << '\n';
    }
    else
    {
        for (int i = 3; i * 2 <= n; i += 2)
        {
            if(__gcd(i, n - 1 - i) != 1 || i == n - 1 - i) continue;
            cout << i << ' ' << n - (1 + i) << ' ' << 1 << '\n';
            return;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.precision(2), cout.setf(ios::fixed);
    int t;
    cin >> t;
    while (t -- )
    solve();
    return 0;
}

C. Paprika and Permutation

题目

知识点

思维，贪心

解题思路

​ 该题中要求我们求取模操作的最小次数，使得数组 a a a 成为一个 [ 1 , n ] [1, n] [1,n] 的排列。

​ 我们分析可知，一个数 X X X 进行取模操作可以得到的数 X ′ ∈ [ 0 , ⌊ X − 1 2 ⌋ ] X' ∈[0, \lfloor \frac{X - 1}{2} \rfloor] X′∈[0,⌊2X−1​⌋] （模数大于 X X X 无意义，不考虑）。

​ 然后我们首先把 数组 a a a 中已经出现过的 [ 1 , n ] [1, n] [1,n] 中的数去掉，比如 a : [ 1 , 100 , 5 , 2 , 24 , 8 , 5 ] → a : [ 100 , 24 , 8 , 5 ] a:[1, 100, 5, 2, 24,8, 5] → a:[100,24,8,5] a:[1,100,5,2,24,8,5]→a:[100,24,8,5] , 然后与还未被匹配的数的数组 b : [ 7 , 6 , 4 , 3 ] b:[7,6,4,3] b:[7,6,4,3] 从大到小一 一进行匹配，设剩下未被匹配的数字有 m m m 个，判断是否满足对于 ∀ i ∈ [ 1 , m ] , a [ i ] ≤ ⌊ b [ i ] − 1 2 ⌋ ∀i∈[1, m], a[i]≤\lfloor \frac{b[i] - 1}{2} \rfloor ∀i∈[1,m],a[i]≤⌊2b[i]−1​⌋, 如果不满足就输出 − 1 -1 −1 , 满足就输出 m m m 。 (在剩余未被匹配的数中大的和大的匹配一定是最优的)

​ （详细见代码）

代码

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n'
#define between(x, l, r) (x >= l && x <= r)
#define point(a, b, m) ((a - 1) * m + b)
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define y second
#define x first
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int N = 3e5 + 10, M = 2 * N, mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int a[N];
int st[N];

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) st[i] = 0; // 该数是否已经被匹配了

    sort(a + 1, a + n + 1);

    int res = n;
    for (int i = 1; i <= n; i ++ )
    {
        if(a[i] <= n && !st[a[i]])
        {
            st[a[i]] = 1;
            res -- ;
            a[i] = 0; // 直接删去
        }
    }

    sort(a + 1, a + n + 1, greater<int>());
    
    //从大到小遍历需要被匹配的数
    for (int i = n, j = 1; i >= 1; i -- )
    {
        if(st[i]) continue;
        int t = a[j] / 2 + 1, r = a[j] % t; //r 为 a[j] 可以通过取模得到的最大值
        
        if(r < i) // 不能得到
        {
            cout << -1 << '\n';
            return;
        }
        
        j ++ ;
    }

    cout << res << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.precision(2), cout.setf(ios::fixed);
    int t;
    cin >> t;
    while (t -- )
    solve();
    return 0;
}

D. Too Many Impostors

题目

知识点

思维

解题思路

​ easy：

​ 我们设 q u e r y ( a , b , c ) query(a,b,c) query(a,b,c) 代表三元组 ( a , b , c ) (a, b, c) (a,b,c) 中哪种人比较多。

​ 我们先通过遍历去寻找满足 q u e r y ( i , i + 1 , i + 2 ) ! = q u e r y ( i + 1 , i + 2 , i + 3 ) query(i, i+1,i+2) != query(i+1,i+2,i+3) query(i,i+1,i+2)!=query(i+1,i+2,i+3) 的一个 i i i 的位置, 可以得到 i , i + 3 i, i+3 i,i+3 是两种不同的人，然后我们通过 q u e r y ( i , i + 3 , x ) query(i, i+3, x) query(i,i+3,x) 就可以得到 x x x 位置上是哪种人了。

​ 上限次数 : 2 ∗ n 2 * n 2∗n

​ hard：

​ 我们先把人分成 n 3 \frac{n}{3} 3n​ 个块，即 [ 1 , 2 , 3 ] , [ 4 , 5 , 6 ] , . . . , [ n − 2 , n − 1 , n ] [1, 2, 3],[4, 5, 6],...,[n - 2, n - 1, n] [1,2,3],[4,5,6],...,[n−2,n−1,n]块，并且得到每个块的 q u e r y query query 值

​ 由于 n 3 < k < 2 n 3 \frac{n}{3}<k<\frac{2n}{3} 3n​<k<32n​ , 所以至少会有一个块 q u e r y query query 值为 1 1 1，一个为 0 0 0。

​ 我们选出一个 q u e r y query query 值为 0 0 0 的块的第一个下标 x x x , q u e r y query query 值为 1 1 1 的块的第一个下标 y y y 。

​ 我们可以通过两次询问 q 1 = q u e r y ( x , x + 1 , y ) q_1 = query(x, x+1, y) q1​=query(x,x+1,y) , q 2 = q u e r y ( x , x + 1 , y + 1 ) q_2 = query(x, x+1, y + 1) q2​=query(x,x+1,y+1) 来得到一个 0 0 0 的位置（ 1 1 1 的位置同理）

​ 因为 q u e r y ( y , y + 1 , y + 2 ) = 1 query(y, y + 1, y + 2) = 1 query(y,y+1,y+2)=1, 所以 y , y + 1 y, y+1 y,y+1 中至少有一个为 1 1 1, 所以如果 q 1 , q 2 q_1,q_2 q1​,q2​ 全是0，那么说明 x , x + 1 x, x+1 x,x+1 全都是 0 0 0，否则说明 x , x + 1 x,x+1 x,x+1 中有一个为 1 1 1, 由于 q u e r y ( x , x + 1 , x + 2 ) = 0 query(x,x+1,x+2) = 0 query(x,x+1,x+2)=0，那么 x + 2 x+2 x+2 必然为 0 0 0。

​ 在找出一个 1 , 0 1, 0 1,0 的位置后，我们令 a a a 为 0 0 0 的位置， b b b 为 1 1 1 的位置。

​ 我们遍历每个块，每个块我们可以通过两次 q u e r y query query 得到三个元素的种类，下面以 q u e r y query query 值为 1 1 1 的块为例。

​ [ 1 , 1 , 0 ] [1, 1, 0] [1,1,0] 有 q u e r y ( i , i + 1 , a ) = 1 , q u e r y ( i + 1 , i + 2 , a ) = 0 query(i,i+1,a) = 1, query(i+1, i+2,a) = 0 query(i,i+1,a)=1,query(i+1,i+2,a)=0

​ [ 1 , 0 , 1 ] [1, 0, 1] [1,0,1] 有 q u e r y ( i , i + 1 , a ) = 0 , q u e r y ( i + 1 , i + 2 , a ) = 0 query(i,i+1,a) = 0, query(i+1, i+2,a) = 0 query(i,i+1,a)=0,query(i+1,i+2,a)=0

​ [ 0 , 1 , 1 ] [0, 1, 1] [0,1,1] 有 q u e r y ( i , i + 1 , a ) = 0 , q u e r y ( i + 1 , i + 2 , a ) = 1 query(i,i+1,a) = 0, query(i+1, i+2,a) = 1 query(i,i+1,a)=0,query(i+1,i+2,a)=1

​ [ 1 , 1 , 1 ] [1, 1, 1] [1,1,1] 有 q u e r y ( i , i + 1 , a ) = 1 , q u e r y ( i + 1 , i + 2 , a ) = 1 query(i,i+1,a) = 1, query(i+1, i+2,a) = 1 query(i,i+1,a)=1,query(i+1,i+2,a)=1

​ 到此我们就能把所有数的种类的分出来了。

​ 上限次数 ： n + 4 n + 4 n+4

​ （详细见代码）

代码

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << '\n'
#define between(x, l, r) (x >= l && x <= r)
#define point(a, b, m) ((a - 1) * m + b)
#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define y second
#define x first
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

const int N = 3e5 + 10, M = 2 * N, mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

/*
*/
vector<int> g[2];
int p[N], ans[N];

int query(int a, int b, int c)
{
    int res;
    cout << "? " << a << ' ' << b << ' ' << c << endl;
    cin >> res;
    return res;
}

void EasySolve()
{
    int n;
    cin >> n;
    int last = -1, ans, a, b;
    g[0].clear(), g[1].clear();
    /*
    可以得到不同的数字a, b
    然后我们可以通过这个来确定其他的数字
    然后我们选择其他两个不同的,来判断a与b
    */

    for (int i = 1; i <= n - 2; i ++ )
    {
        ans = query(i, i + 1, i + 2);
        if(last != -1 && ans != last)
        {
            a = i - 1, b = i + 2;
            g[ans].push_back(i + 2);
            g[!ans].push_back(i - 1);
            break;
        }
        last = ans;
    }

    for (int i = 1; i <= n; i ++ )
    {
        if(i == a || i == b) continue;
        ans = query(a, b, i);
        g[ans].push_back(i);
    }

    sort(all(g[0]));
    cout << "! " << g[0].size();
    for (auto &it : g[0]) cout << ' ' << it;
    cout << endl;
}

void HardSolve()
{
    int n;
    cin >> n;
	int x, y;  // 骗子多的块, 好人多的块
    for (int i = 1; i <= n; i ++ ) ans[i] = 0;
    for (int i = 1; i <= n; i += 3)
    {
		p[i] = query(i, i + 1, i + 2);
		if (p[i] == 0) x = i;
		else y = i;
	}

	int a, b;// 骗子, 好人位置
	if (query(x, x + 1, y) || query(x, x + 1, y + 1)) a = x + 2;
	else a = x;

	if (query(y, y + 1, x) && query(y, y + 1, x + 1)) b = y;
	else b = y + 2;
	
    // 遍历块
	for (int i = 1; i <= n; i += 3)
    {
		if (p[i] == 1)//坏<好
        {
			ans[i] = ans[i + 1] = ans[i + 2] = 1;

			int t1 = query(a, i, i + 1), t2 = query(a, i + 1, i + 2);
			if (t1 == 0 && t2 == 0) ans[i + 1] = 0;
			else if (t1 == 0) ans[i] = 0;
			else if (t2 == 0) ans[i + 2] = 0;
		}
        else //好<坏
        {
			int t1 = query(b, i, i + 1), t2 = query(b, i + 1, i + 2);
            if(t1 == 1 && t2 == 1) ans[i + 1] = 1;
			else if (t1 == 1 && t2 == 0) ans[i] = 1;
			else if (t2 == 1 && t1 == 0) ans[i + 2] = 1;
        }
	}
	
    // 统计答案
	int cnt = 0;
	for (int i = 1; i <= n; i ++ ) cnt += 1 - ans[i];

    // 输出答案
    cout << "! " << cnt;
    for (int i = 1; i <= n; i ++ )
        if(ans[i] == 0) cout << " " << i;
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.precision(2), cout.setf(ios::fixed);
    int t;
    cin >> t;
    while (t -- ) HardSolve();
    return 0;
}