A. Road To Zero
题意：
有(x, y)两个数，你的目的是让(x = 0 and y = 0)，你可以花费(a)元使(x)或(y)加减(1)，也可以花费(b)元使(x)和(y)加减(1)。求最小代价？
题解：
(if x*yleq 0,ans = (abs(x) + abs(y)) * a)
(else,ans = min(abs(x + y) * a, min(abs(x), abs(y)) * b + abs(x - y) * a))
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t; cin >> t;
while(t --){
ll a, b, x, y;
cin >> x >> y >> a >> b;
ll ans;
if((x <= 0 && y >= 0) || (x >= 0 && y <= 0)){ // 异号只有一种做法
ans = (abs(x) + abs(y)) * a;
}
else{ // 同号就两种情况取小值
ll ans1, ans2;
ans1 = (abs(x) + abs(y)) * a;
ans2 = min(abs(x), abs(y)) * b + abs(abs(y) - abs(x)) * a;
ans = min(ans1, ans2);
}
cout << ans << endl;
}
return 0;
}
B. Binary Period
题意
给你一个字符串(t)，构造字符串(s)，使得(t)是(s)个子序列（不连续），并且(s)的循环周期(k)最小。
例：(s = 0010010010)，则(k = 3)。要求(len(s) leq 2 * len(t))
题解
根据他的长度要求，显然(k leq 2)，所以我们只需要判断(t)是否是全(1)或全(0)，如果是，直接输出(t)，否则我们构造一个长度为(2 * len(t))的字符串(s)，就可以符合要求
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while(t --){
string t, s = "";
cin >> t;
int mark = 0;
for(int i = 1; i < t.size(); i ++) // 判断t是否包含0和1
if(t[i] != t[i - 1]){
mark = 1;
break;
}
if(!mark){
cout << t << endl;
}else{
for(int i = 0; i < t.size(); i ++){
s += '0'; s += '1';
}
cout << s << endl;
}
}
return 0;
}
C. Yet Another Counting Problem
题意：
在区间([l, r])中有多少个x满足(((x mod a) mod b)≠((x mod b) mod a))？
题解：
数论上来先打表！打表出奇迹！
多枚举几个(a, b, l, r)，把(x)打出来看，就可以发现其中的规律
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 210;
int f[N * N];
// 打表
// void makeChart(int a, int b, int l, int r){
// for(int i = l; i <= r; i ++){
// if((i % a) % b != (i % b) % a){
// cout << i << endl;
// }
// }
// }
ll cal(ll n, ll x){
return n / x * f[x] + f[n % x];
}
int main(){
// freopen("output.txt", "w", stdout);
// makeChart(4, 6, 1, 100);
int t; cin >> t;
while(t --){
ll a, b, l, r, q;
cin >> a >> b >> q;
memset(f, 0, sizeof f);
for(int i = 1; i <= a * b; i ++){
f[i] = f[i - 1] + (i % a % b != i % b % a);
}
while(q --){
cin >> l >> r;
cout << cal(r, a * b) - cal(l - 1, a * b) << " ";
}
puts("");
}
return 0;
}
D. Multiple Testcases
题意：
给你(n)个数(m[i] leq k(i leq n))，再给你(k)个数(c[i](i leq k))，将这(n)个数分组，要求每组(geq i)的数的个数(leq c[i])，问最少可以分几组？
题解：
先求出最小的分组数，预处理出(geq i)的数的个数(cnt[i])，那么分组数(ans = max(ans, left lceil frac{cnt[i]}{c[i]}
ight
ceil))，然后将(m)排序，依次插入这(ans)个组，则第(i)组里面的数为：({m[i], m[i + ans], m[i + 2 * ans] ...})。
证明：以任意一组举例，其中(geq i)的数的个数(t = left lceil frac{cnt[i]}{ans}
ight
ceil)，又因为(ans geq left lceil frac{cnt[i]}{c[i]}
ight
ceil)，那么显然(t leq c[i])，故符合题意。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k;
int m[N], c[N], cnt[N];
vector<int> vec[N];
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++){
scanf("%d", &m[i]);
cnt[m[i]] ++; // 记每个数出现的次数
}
for(int i = 1; i <= k; i ++){
scanf("%d", &c[i]);
}
for(int i = k; i >= 1; i --){
cnt[i] += cnt[i + 1]; // 算出>=i的个数
}
int ans = 1;
for(int i = 1; i <= k; i ++){ // 计算组数
int tmp = cnt[i] / c[i] + (cnt[i] % c[i] != 0);
ans = max(ans, tmp);
}
sort(m + 1, m + n + 1);
for(int i = 1; i <= n; i ++){ // 轮流插入
vec[i % ans].push_back(m[i]);
}
cout << ans << endl;
for(int i = 0; i < ans; i ++){
cout << vec[i].size();
for(int j = 0; j < vec[i].size(); j ++){
printf(" %d", vec[i][j]);
}
puts("");
}
return 0;
}
E. Placing Rooks
题意：
在(n imes n)的棋盘中，你可以放(n)枚棋子，棋子可以攻击同行和同列距离最近的棋子（参考象棋中的车），在你摆放完所有棋子后，要求有(k)对棋子可以互相攻击，并且对于没有摆放棋子的空格来说，他的同行或同列至少有一枚棋子。求摆放的方案数？
题解：
显然要么每行都有一个棋子，要么每列都有一个棋子。
我们考虑每行都有一个棋子。那么攻击的棋子只能在列中产生了。假设一列中有(x)枚棋子，那么有(x - 1)对棋子可以相互攻击，也就是说(n)枚棋子最多有(n - 1)对棋子可以相互攻击，那么对于(k > n - 1)的，我们可以直接过滤掉。
那么对于每行都有一个棋子的情况下，要符合条件我们应该摆多少列呢（例如我们摆(n)列显然不符合条件）？
假设我们摆(t)列，那么每列摆了(c_1,c_2,c_3......c_t)个，则可以得到两个方程：
相减即可得到：(t = n - k)，即要符合条件我们必须摆(n - k)列。
接下来就是组合数学的问题了，我们将(n)枚棋子放入(t)列，每一枚棋子都有(t)种方法，则共有(t^n)种情况。但是我们发现可能出现了不足(t)列的情况，所以我们需要减去这些情况，即那些只放了(1,2,3,...,t-1)列的情况，但是这样不好计算，所以我们需要换种计算思路。
我们在(t)列中选出一个空列（没有摆放棋子的），然后减去(n)枚棋子在剩余(t - 1)列摆放的情况，但和(t)列一样，也会出现没有摆满的情况，所以我们就减多了（由于(t-1)列中也有空列，就会再次被选出来，所以重复计算了），那么我们就需要加上多减的，再在(t-1)列中选出一个空列，加上(n)枚棋子在剩余(t-2)列中摆放的情况。但显然是存在摆不满的情况的，所以我们又加多了，又需要减，如此重复下去，直到最后只剩(1)列的情况。那么我们可以得到公式：
化简一下即：
由于还要从(n)列里面选出(t)列，所以还要乘以(C_n^t)。最后我们将行列颠倒考虑，即还有相同的方案数，所以(ans = ans imes 2)，但是当(k = 0)的时候，即没有两枚棋子可以相互攻击，即每行每列只有一枚棋子，这种情况下行列的情况都是一样，所有不用( imes 2)。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 200010, mod = 998244353;
typedef long long ll;
int n, k;
ll fact[N]; // 阶乘
ll fastPow(ll a, ll b){ // 快速幂
ll res = 1;
while(b){
if(b & 1) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
ll cal(int a, int b){ // 计算组合数
return fastPow(fact[b] * fact[a - b] % mod, mod - 2) * fact[a] % mod;
}
int main(){
// freopen("input.txt", "r", stdin);
cin >> n >> k;
if(k >= n) { puts("0"); return 0; }
fact[0] = 1;
for(int i = 1; i <= n; i ++){
fact[i] = fact[i - 1] * i % mod;
}
int c = n - k;
ll ans = 0;
for(int i = 0; i <= c; i ++){ // 求和
ans = ((ans + cal(c, i) * fastPow(-1, i) * fastPow(c - i, n)) % mod + mod) % mod;
}
ans = ans * cal(n, c) % mod; // 乘上从n列里选(n - k)列的方案数
if(k){
ans = (ans << 1) % mod;
}
cout << ans << endl;
return 0;
}