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;
}