题目跳转链接

A. Simply Strange Sort

题意

定义一个函数\(f_{i}\) : 如果\(a_i \ge a_{i+1}\) swap(\(a_i\) \(a_{i+1}\))
定义一个操作：
第奇数次是 执行 \(f_1\) \(f_3\)... \(f_{n-2}\)
第偶数次是 执行 \(f_2\) \(f_4\)... \(f_{n-1}\)

求出进行多少次操作可以使原数组变得有序

思路

模拟上述操作即可 判断符合条件也可以用 is_sorted函数

AC_CODE

#include <bits/stdc++.h>
#define x first    
#define y second    
#define pb push_back
#define mk make_pair
#define debug(x) cout<<#x" ----> "<<x<<endl
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define pre(i, b, s) for(int i = (b); i >= (s); --i)

//#define int long long 
#define endl '\n' 
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define all(v) (v).begin(),(v).end()

using namespace std;
 
typedef unsigned long long ULL;
typedef pair<int, int> PII ;
typedef pair<double, double> PDD ;
typedef long long LL;
const int INF = INT_MAX;
const int mod = 1e9 + 7;
const double eps = 1e-10;
const double pi = acos(-1.0);
   
int lowbit(int x){return x&-x;} 
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}
LL ksm(LL a, LL b) {if (b == 0) return 1; LL ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
template < typename T >
inline void read(T &x)
{
    x = 0; bool f = 0; char ch = getchar();
    while(!isdigit(ch)){f ^= !(ch ^ 45);ch=getchar();}
    while(isdigit(ch)) x= (x<<1)+(x<<3)+(ch&15),ch=getchar();
    x = f ? -x : x;
}
 
void solve() {
    int n; read(n);
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i ++ ) {
        read(a[i]);
        b[i] = i;
    }
    int cnt = 0;
    for(int i = 1; i <= n; i ++ ) {
        if(a == b) {
            break;
        }

        //// if(is_sorted(all(a))) break;
    
        if(i & 1) {
            for(int j = 1; j <= n - 2; j += 2)
                if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); 
        }
        else {
            for(int j = 2; j <= n - 1; j += 2) 
                if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
        }
        cnt ++;
        
    }
    printf("%d\n", cnt);
    
}
 
signed main() 
{
    int T = 1;  scanf("%d",&T);
    while(T -- ) {
        solve();
    }
 
    return 0;
}

B. Charmed by the Game

题意

题目背景: 乒乓球比赛

规定乒乓球发球为两方选手交替发球
如果本场A选手发球
- A赢了 被称为 A hold
- B赢了 被称为 B break
如果本场B选手发球
- B赢了 被称为 B hold
- A赢了 被称为 A break
给出 A 和 B 赢得次数
求出有多少种 break

思路

我们可以发现赢得场次是固定的, 因此我们只需要枚举A在发球场次赢得个数 就可以的到全部的break
reason 我们枚举了A在发球场次赢得个数 因此我们可以得到另外三种情况,就可以求出所有的break
注意: 第一场发球可能是A 也可能是B 因此 我们只需要求出A先发球 所有的break
然后用a+b-i 就是B先发球的break

AC_CODE

#include <bits/stdc++.h>
#define x first    
#define y second    
#define pb push_back
#define mk make_pair
#define debug(x) cout<<#x" ----> "<<x<<endl
#define rep(i, b, s) for(int i = (b); i <= (s); ++i)
#define pre(i, b, s) for(int i = (b); i >= (s); --i)

//#define int long long 
#define endl '\n' 
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define all(v) (v).begin(),(v).end()

using namespace std;
 
typedef unsigned long long ULL;
typedef pair<int, int> PII ;
typedef pair<double, double> PDD ;
typedef long long LL;
const int INF = INT_MAX;
const int mod = 1e9 + 7;
const double eps = 1e-10;
const double pi = acos(-1.0);
   
int lowbit(int x){return x&-x;} 
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}
LL ksm(LL a, LL b) {if (b == 0) return 1; LL ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
template < typename T >
inline void read(T &x)
{
    x = 0; bool f = 0; char ch = getchar();
    while(!isdigit(ch)){f ^= !(ch ^ 45);ch=getchar();}
    while(isdigit(ch)) x= (x<<1)+(x<<3)+(ch&15),ch=getchar();
    x = f ? -x : x;
}
const int N = 2e5 + 10;
bool num[N];
int cnt, mid, px;
void solve() {
    int a, b;
    read(a); read(b);
    px = a + b;
    for(int i = 0; i <= px + 5; i ++ ) num[i] = false;
    if(a < b) swap(a, b);
    mid = (px + 1) / 2;
    for(int i = mid; i >= mid - b; i -- ) { //i是A在他发球的场次赢得次数
        cnt = mid - i + a - i;
        num[cnt] = true;
        num[px - cnt] = true;
    }
    vector<int> ans;
    for(int i = 0; i <= px; i ++ )
        if(num[i]) 
            ans.pb(i);
    printf("%d\n", ans.size());
    for(int p : ans) printf("%d ", p);
    puts("");
}
 
signed main() 
{
    int T = 1;  scanf("%d",&T);
    while(T -- ) {
        solve();
    }
 
    return 0;
}