涵盖知识点：思维、前缀和、组合数学
比赛链接：传送门
A - Road To Zero
题意： 给定(x,y,a,b)，花费(a)可以使(x,y)其中一个加一或者减一，花费(b)可以使(x,y)同时加一或者减一。问最少花费多少使得(x=y=0)。
题解： 判断(2a)和(b)的大小贪心。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;cin>>t;
while(t--){
int a,b,x,y;
cin>>x>>y>>a>>b;
if(x>y)swap(x,y);
cout<<1ll*min(2*a,b)*x+1ll*a*(y-x)<<"
";
}
return 0;
}
B - Binary Period
题意： 给定01串(t)，要求构造一个(s)满足(t)是(s)的子序列且(|s|le 2|t|)，并且拥有尽量小的周期。
题解： 若(t)全同：(s=t)，否则(s=01010101ldots)
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;cin>>t;
while(t--){
string s;
cin>>s;
bool f[2]={false,false};
for(char i:s)f[i-'0']=true;
if(!f[0]||!f[1])cout<<s<<"
";
else{
for(int i=0;i<s.length();i++)cout<<"01";
cout<<"
";
}
}
return 0;
}
C - Yet Another Counting Problem
题意： 问(iin[l,r])中有多少数满足(i\% a\%b
ot =i\%b\%a) 。
题解： 式子具有周期性。计算([0,ab))区间内满足数量的前缀和处理一下就行了。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e4+10;
int sum[maxn];
ll a,b,q;
ll calc(ll x){
return 1ll*x/(a*b)*sum[a*b]+1ll*sum[x%(a*b)];
}
int main(){
int t;cin>>t;
while(t--){
memset(sum,0,sizeof sum);
cin>>a>>b>>q;
for(int i=1;i<=a*b;i++)sum[i]+=sum[i-1]+(i%a%b!=i%b%a);
while(q--){
ll l,r;
cin>>l>>r;
cout<<calc(r)-calc(l-1)<<" ";
}
cout<<"
";
}
return 0;
}
D - Multiple Testcases
题意： 尽可能少的拆分给定序列，使得每个序列内大于等于(k)的数的个数不超过(c_k)。
题解： 假设原有序列大于等于(k)的数为(s_k)，则(ans=displaystylemax_{1le ile k}{lceilfrac{s_i}{c_i}
ceil})。确定(ans)以后从小到大依次分配即可。
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int s[maxn],m[maxn],c[maxn];
vector<int> v[maxn];
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)cin>>m[i],s[m[i]]++;
sort(m,m+n);
for(int i=1;i<=k;i++)cin>>c[i];
for(int i=k-1;i>=1;i--)s[i]+=s[i+1];
int ans=0;
for(int i=1;i<=k;i++)ans=max(ans,(s[i]-1)/c[i]+1);
for(int i=0,j=0;j<n;i=(i+1)%ans,j++)v[i].push_back(m[j]);
cout<<ans<<"
";
for(int i=0;i<ans;i++){
cout<<v[i].size();
for(auto j:v[i])cout<<" "<<j;
cout<<"
";
}
return 0;
}
E - Placing Rooks
题意： 在一个(n*n)的棋盘上放置(n)个车，满足以下两个条件：
- 棋盘上的每一个空格子都能被至少一只车走到
- 恰好存在(k)对车可以相互攻击
询问所有车的摆放方案数
题解： 要满足第一个条件，则每一行/每一列都有一个车，两者至少满足其一。对于这两种情况是等价的，下面只考虑每一行都有车，最终结果乘(2)即可
在满足第二个条件的情况下，可以发现至少有(k)列是空着的，那么问题就相当于把(n)个不同的车放入(n-k)个不同的列，发现就是一个第二类斯特林数。那么可以用容斥原理，(C_{n-k}^{0}*(n-k)^n-C_{n-k}^{1}*(n-k-1)^n+C_{n-k}^{2}*(n-k-2)^n...)，那么最终答案就是(2*C_{n}^{n-k}*[C_{n-k}^{0}*(n-k)^n-C_{n-k}^{1}*(n-k-1)^n+C_{n-k}^{2}*(n-k-2)^n...])
要注意特判一下当(n=0)时，答案就为(n!)，当(kge n)时，答案为(0)
第二类斯特林数详解传送门
Accept Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int mod = 998244353;
ll fac[maxn];
ll qpow(ll a, ll b){
ll res = 1;
while (b){
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init(){
fac[0] = 1;
for (int i = 1; i < maxn; i++)
fac[i] = fac[i - 1] * i % mod;
}
ll c(int x, int y){
return fac[x] * qpow(fac[y] * fac[x - y] % mod, mod - 2) % mod;
}
int main(){
init();
int n, k;
cin>>n>>k;
if (k == 0){
cout<<fac[n]<<"
";
return 0;
}
if (k >= n){
cout<<"0
";
return 0;
}
ll ans = 0;
for (int i = 0; i <= n - k; i++)
ans += 1ll * qpow(mod - 1, i) * c(n - k, i) % mod * qpow(n - k - i, n) % mod;
ans %= mod;
cout<<2ll * ans % mod * c(n, n - k) % mod<<"
";
return 0;
}