https://codeforces.com/contest/1972

A-Contest Proposal

题意：给定两个数组a,b,每次可以添加一个数到数组a中,同时删除一个最大的数,问对于每个i,使得均有$a_i$<=$b_i$的最小操作数.

最优情况为每次添加1,使得后面的数均后移一位,ans最多情况为把原数组的全删掉,即ans = n.

定义偏移量diff,则当前数组的第i个数为a[i-diff],如果a[i-diff]>b[i],则在最前面添加1->diff+1,ans+1,枚举n次即可

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define int long long
#define pb push_back
#define N 110
#define PII pair<int,int>
using namespace std;
const double pi = acos(-1);
ll n,m,q;
int T;
int ans;
int a[N],b[N];
void solve()
{
    cin>>n;
    for(int i = 0; i < n; i ++ )
    {
        cin>>a[i];
    }
    ans = 0;
    for(int i = 0; i < n; i ++ )
    {
        cin>>b[i];
    }
    int diff = 0;
    for(int i = 0; i < n; i ++ )
    {
        if(a[i-diff] > b[i])
        {
            ans ++;
            diff++;
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>T;
    while(T -- )
    {
        solve();
    }
    return 0;
}

B-Coin Games

桌子上有 $n$ 枚硬币围成一个圆圈，每枚硬币要么朝上，要么朝下。爱丽丝和鲍勃轮流玩下面的游戏，爱丽丝先玩。

在每次操作中，玩家选择一枚正面朝上的硬币，取出硬币，然后翻转与之相邻的两枚硬币。如果只剩下两枚硬币，则取出一枚，另一枚不翻转(因为会翻转两次)。如果只剩下一枚硬币，则不会翻转任何硬币。如果没有正面朝上的硬币，玩家就输了。

决定如果两人都以最佳方式进行游戏，谁会赢。可以证明，游戏将在有限次的操作中结束，其中一人将获胜。

思路:注意到必败态的U个数为0。不管怎么操作都会改变当前U总数的奇偶性，而要从非零数变到零只能由奇数变到偶数，而不可能由偶数经过变换奇偶性变到零，所以手上是奇数的人必胜,反之必败。
只需枚举一遍，如果U的个数是奇数，则Alice必胜，反之必败

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define int long long
#define pb push_back
#define N 110
#define PII pair<int,int>
using namespace std;
const double pi = acos(-1);
ll n,m,q;
int T;
int cnt;
void solve()
{
    cin>>n;
    string s;
    cin>>s;
    cnt = 0;
    for(int i = 0; i < n; i ++ )
    {
        if(s[i] == 'U') cnt++;
    }
    if(cnt & 1) cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>T;
    while(T -- )
    {
        solve();
    }
    return 0;
}

C- Permutation Counting

你有几张牌。每张卡片上都写着一个介于 $1$ 和 $n$ 之间的整数：具体来说，从 $1$ 到 $n$ 的每张 $i$ ，你们有 $a_i$ 张写着数字 $i$ 的卡片。

还有一个商店，里面有无限量的各种类型的卡片。你有 $k$ 枚金币，因此你总共可以购买 $k$ 张新卡片，你购买的卡片可以包含 $1$ 到 $n$ 之间的任意整数。

购买新牌后，您要将所有牌重新排列成一行。重新排列的得分是长度为 $n$ 的(连续)子数组中 $[1, 2, \ldots, n]$ 的排列数。你能得到的最高分是多少？

思路:直觉上凑够最多的排列应该是12341234之类的,因为这样利用率最高,令l为完整排列至多的个数,n为数组长度。
如果凑完后没有多余的数字,答案应该为$n+(l-1)·(n-1) = (l-1)·n+1$
但是对于多余的数字应该如何处理呢，我们可以把出现较多次数的数字排序靠前，假设k加完后，数组为4 4 5 4
按照顺序:3124312431243可以得到最多的数量,对应$(l-1)·n+1+cnt,cnt$为多余的数量
问题来了,完整排列至多个数如何去求,注意到具有二段性,对于能够满足的排列个数i,其更小的i一定也能满足,因此二分l即可，下界设置为0,上界设置为$(sum+k)/n+1$(极限情况刚好为$(sum+k)/n)$

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define int long long
#define pb push_back
#define N 200010
#define PII pair<int,int>
using namespace std;
const double pi = acos(-1);
ll n,k;
int T;
int ans;
int a[N];
int sum;
bool check(int x)
{
    int res = 0;
    for(int i = 0; i < n; i ++ )
    {
        if(a[i] < x)
        {
            res += x-a[i];
        }
        if(res > k) return false;
    }
    return true;
}
void solve()
{
    cin>>n>>k;
    sum = 0;
    for(int i = 0; i < n; i ++ )
    {
        cin>>a[i];
        sum += a[i];
    }

    int l = 0,r = (sum+k)/n+1;
    while(l < r)
    {
        ll mid = l + r + 1>> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    for(int i = 0; i < n; i ++ )
    {
        if(a[i] < l)
        {
            k-=l-a[i];
            a[i] = 0;
        }else 
        {
            a[i] -= l;
        }
    }
    int cnt = k;
    for(int i = 0; i < n; i ++ )
    {
        if(a[i] > 0) cnt ++;
    }
    cout<<(l-1)*n+1+cnt<<'\n';

}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>T;
    while(T -- )
    {
        solve();
    }
    return 0;
}

D1-Reverse Card (Easy Version)

两个版本的问题不同。您可能需要同时阅读两个版本。只有两个版本的问题都解决了，您才能进行破解。

给你两个正整数 $n$ ， $m$ 。

计算满足以下条件的有序数对 $(a, b)$ 的个数：

• $1\le a\le n$ , $1\le b\le m$ ;
• $a+b$ 是 $b \cdot \gcd(a,b)$ 的倍数。

思路:将 $\gcd(a,b)$ 表示为 $d$。假设 $a=pd$ 和 $b=qd$，那么我们知道 $\gcd(p,q)=1$.

$(b\cdot\gcd(a,b))\mid (a+b)\iff (qd^2)\mid (pd+qd)\iff (qd)\mid (p+q)$.

假设 $p+q=kqd$，则 $p=（kd-1）q$。因为 $gcd(p,q)=1$,则$q=1$。

其实分析到这里,已经可以写出ac的代码了,由于$b=d,a=(k·d-1)·q·d=(k·b-1)·b,$

第一维枚举b,范围1~m,第二维枚举满足条件的k,

注意到$(k·d-1)$须非0,累加即可,时间复杂度：$\mathcal O(mlogn)$.

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define int long long
#define pb push_back
#define N 2000010
#define PII pair<int,int>
using namespace std;
const double pi = acos(-1);
ll n,m,q;
int T;
int ans;
void solve()
{
    cin>>n>>m;
    ans = 0;
    for(int b = 1; b <= m; b ++ )//枚举b也是枚举d
    {
        for(int k = 1; (k*b-1)*b<=n; k ++)//枚举所有满足条件的a的系数k
        {
            if((k*b-1))ans++;//系数不为0
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>T;
    while(T -- )
    {
        solve();
    }
    return 0;
}

还可以继续分析下去
由于$ a = pd \le n,p \le\lfloor\frac{n}{d}\rfloor$
枚举 $1$ 到 $m$ 的 $d$，我们知道 $p+1=kd\le\lfloor\frac{n}{d}\rfloor+1$，所以对于每一个d,
其满足条件的k都可以用添加$\left\lfloor\frac{\lfloor\frac{n}{d}\rfloor+1}{d}\right\rfloor$ 来回答。

在这种方法中，$p=0，k=1，d=1$ 也会包含在答案中，所以我们应该从答案中减去 $1$。

时间复杂度：$\mathcal O(\sum m)$.

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define int long long
#define pb push_back
#define N 2000010
#define PII pair<int,int>
using namespace std;
const double pi = acos(-1);
ll n,m,q;
int T;
int ans;
void solve()
{
    cin>>n>>m;
    ans = 0;
    for(int d = 1; d <= m; d ++ )//枚举d
    {
        ans += (n/d+1)/d;//累加符合条件的a
    }
    cout<<ans-1<<'\n';
}
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>T;
    while(T -- )
    {
        solve();
    }
    return 0;
}