A. Cowardly Rooks

在\(n\times n\)的棋盘中有 m 个车，问是否可以在移动任意一个棋子一步后是的m个车不能相互攻击

如果m>n无论如何都会冲突

首先要统计冲突的数量

如果没有冲突的话，如果n==m则移动后一定会导致冲突，反之一定可以

如果只有一个冲突，就一定可以把冲突解决

如果大于一个冲突的话一定不可以

#include <bits/stdc++.h>
using namespace std;


int read(){
    int x = 0 , ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x;
}

void solve(){
    int n = read() , m = read();
    if( m > n ){
        printf("NO\n");
        return;
    }
    vector<pair<int,int>> v(m);
    vector<int> ax(n+1) , ay(n+1);
    for( auto &[ x , y ] : v )
        x = read() , y = read() , ax[x] ++ , ay[y] ++;
    int falg = 0;
    for( int i = 1 ; i <= n ; i ++ ){
        if( ax[i] > 1 ) falg ++;
        if( ay[i] > 1 ) falg ++;
    }
    if( falg == 0 ){
        if( n == m ) printf("NO\n");
        else printf("YES\n");
        return;
    }
    if( falg >= 2 ){
        printf("NO\n");
        return;
    }
    printf("YES\n");
    return;
}

int main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

B. Death's Blessing

首先所有的a都一定会贡献到答案中。

在删除的过程中，如果是在两侧则贡献\(b_i\)，反之贡献\(2b_i\)，所以只删除两侧最优。并且最后一个被删除的贡献是0

所以就是把所有的\(a_i,b_i\)加起来减去最大的\(b_i\)即可

#include <bits/stdc++.h>
#define int long long
using namespace std;


int read(){
    int x = 0 , ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x;
}

void solve(){
    int n = read() , ans = 0 , v = LLONG_MIN;
    for( int i = 1 ; i <= n ; i ++ ) ans += read();
    for( int i = 1 , x ; i <= n ; i ++ )
        x = read() , ans += x , v = max( v , x );
    cout << ans - v << '\n';
}

int32_t main(){
    for( int t = read() ; t ; t -- )
        solve();
    return 0;
}

D. Counting Arrays(补题)

对于一个序列\(a_i\)，可以删除掉\(gcd(a_i,i)=1\)的元素。然后每次删去的元素下标构成了删除序列，删除序列不唯一的序列\(a_i\)是模糊序列。问长度\([1,n]\)元素值为[1,m]的序列有多少个模糊序列。

首先长度为\(n\)序列总个数是\(m^n\)，总序列减去不模糊序列就是模糊序列。

什么序列是不模糊序列呢？首先可以知道\(gcd(a_1,1)\equiv1\)，然后如果序列中出现了两个可以删除的元素，那么序列就一定模糊了。删除一个元素后面的元素不会改变该元素是否能删除，所以如果一个序列不模糊那么他的删除序列一定是\(1,1,1,1\cdots\)

由此可知不模糊序列中的元素\(a_i\)应该满足\(gcd(a_i,j)\ne 1,j\in[2,i]\)恒成立，这样才能保证该元素只有当前面的都被删掉后才可以被删掉，记满足的元素个数为\(cur_i\)

如果知道了长度为\(n\)的不模糊序列个数为\(cnt_n\)，那么\(cnt_{n+1}=cnt_n\times cur_{n+1}\)。那么长度为\(n\)的模糊序列个数为\(m^n-cnt_n\)。这样\(O(n)\)递推就可以求出最后的答案。

那么现在的问题其实就是如何计算\(cnt_i\)或者和准确来说如何计算\(cur_i\)，这个看似很难，令\(p_i\)表示素数序列，那么\(p_k\)是小于等与\(i\)的最大素数，那么\(P=\Pi_{i=1}^{k}p_i\)就与\([2,i]\)中的数都不互质，并且\(P\)还是满足条件的最小值。所以\(P\)的倍数也都满足与\([2,i]\)中的数都不互质。所以$cur_i=\left \lfloor \frac{m}{P}\right \rfloor \(，这样我们在递推的过程中判断一下\)i\(是否是素数，如果是素数更新一下\)P\(和\)cur$就好

然后就是注意取模。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 998244353;

bool prime(int x)
{
    for(int i = 2; i * 1ll * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;
}

int32_t main(){
    int n , m , res = 0;
    cin >> n >> m;
    for( int i = 1 , a = 1 , cur = 1 , cnt = 1 ; i <= n ; i ++ ){
        a = a * (m%mod) % mod , res = ( res + a ) % mod;
        if( cur > m ) continue;
        if( prime(i) ) cur *= i;
        cnt = cnt * ( ( m / cur ) % mod ) % mod , res -= cnt;
    }
    cout << res << "\n";
    return 0;
}

C. Number Game（补题）

可知Alice删除尽可能大的数跟优，并且Bob选择的数Alice是一定不能在之后的回合删除的，所以Bob选择最小的数最优。因为数据范围很小可以直接枚举k然后模拟这个过程就好了。

#include <bits/stdc++.h>
using namespace std;

int read(){
    int x = 0 , ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = x * 10 + ch - '0' , ch = getchar();
    return x;
}

void solve(){
    int n = read() , res = 0;
    vector<int> a(n);
    for( auto & i : a ) i = read();

    for( int k = 1 ; k <= n ; k ++ ){
        multiset<int> s( a.begin() , a.end() );
        for( auto i = 0 ; i < k ; i ++ ){
            auto it = s.upper_bound( k - i );
            if( it == s.begin() ) break;
            s.erase( -- it );
            if( ! s.empty() ){
                int x = * s.begin();
                s.erase( s.begin() ) , s.insert( x + k - i );
            }
        }
        if( s.size() + k == n ) res = k;
    }
    cout << res << '\n';
    return;
}

int32_t main(){
    for( int t = read() ; t ; t -- ) solve();
    return 0;
}