A. Road To Zero
贪心。
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/26 22:36:10
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int x, y, a, b;
void run() {
cin >> x >> y >> a >> b;
if(x > y) swap(x, y);
ll ans = 0;
if(1ll * x * y < 0) {
ans += 1ll * (-x) * a + 1ll * y * a;
} else if(1ll * x * y == 0) {
ans += 1ll * y * a;
} else {
int d = abs(x - y);
ans += 1ll * d * a;
if (x < 0) x += d;
else y -= d;
x = abs(x);
ll res = min(1ll * x * b, 2ll * x * a);
ans += res;
}
cout << ans << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
B. Binary Period
像构造(010101...)这样构造即可。
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/26 22:45:50
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
string s; cin >> s;
int len = s.length();
int cnt = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '0') ++cnt;
}
if (cnt == 0 || cnt == len) {
cout << s << '
';
return;
}
int cnt0 = cnt, cnt1 = len - cnt;
string res = "";
for (int i = 0; i < len; i++) {
res += "01";
}
cout << res << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
C. Yet Another Counting Problem
题意：
给出(a,bleq 200)，然后给出(q,qleq 500)个询问，每组询问给出区间([l,r],l,rleq 10^{18})，求出满足(lleq xleq r)且(((x mod a) mod b)
e ((x mod b) mod a))。
思路：
显然询问我们可以拆分为两个前缀的询问。
对于题目中给出的式子，现在(x)以(acdot b)为一个周期，我们用数组(sum)记录一个周期中的前缀信息：(sum_i)表示(0)~(i)中有多少个数不满足上述条件。
对于一次询问(x)，我们将([0,x])拆分为若干个([0,acdot b-1])这样的区间和剩下的区间，直接利用预处理信息计算即可。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/27 16:18:53
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
int a, b, q;
int sum[N];
void run() {
cin >> a >> b >> q;
int n = a * b;
for (int i = 0; i < n; i++) {
if (i) sum[i] = sum[i - 1];
if ((i % a) % b != (i % b) % a) ++sum[i];
}
auto calc = [&](ll r) {
return r / n * sum[n - 1] + sum[r % n];
};
while (q--) {
ll l, r; cin >> l >> r;
ll ans = calc(r) - calc(l - 1);
cout << ans << ' ';
}
cout << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
Bonus: (a,b)限制改为(a,bleq 10^9)。
做法如下：
我们考虑将式子变形(不妨(a<b))：
[egin{aligned}
((xmod a)mod b)&=((xmod b)mod a)\
(xmod a)&=((xmod b)mod a)\
x-x\%b&equiv 0(mod a)\
bcdot lfloorfrac{x}{b}
floor&equiv 0(mod a)
end{aligned}
]
此时(0leq xleq r)，我们处理一个询问的答案。
观察上面的式子，只有左边为(lcm(a,b))的倍数时才为合法答案，那么假设左边为(t)倍(lcm)，就有(displaystyle bcdot lfloorfrac{x}{b}
floor=tcdot frac{ab}{g})，化简为(displaystyle lfloorfrac{x}{b}
floor=tcdot frac{a}{g}=tcdot a')。
显然(t)的个数容易求，即为(displaystyle frac{lfloorfrac{x}{b}
floor}{a'}+1)，当然对于每个(t)，(x)有(b)种取值情况。
同时要注意一些边界情况，(x)不一定刚好取满(b)。
细节见代码：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/27 17:26:05
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int a, b, q;
cin >> a >> b >> q;
if (a > b) swap(a, b);
int g = __gcd(a, b);
a /= g;
auto calc = [&] (ll x) {
ll now = x / b;
ll res = (now / a + 1) * b;
if (now % a == 0) {
(res -= b) += x % b + 1;
}
return res;
};
while (q--) {
ll l, r; cin >> l >> r;
ll ans = r - l + 1;
ans -= calc(r) - calc(l - 1);
cout << ans << ' ';
}
cout << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
D. Multiple Testcases
题意：
给出(n)个数，每个数权值不超过(k)，现在要从这些数中选出一些组成若干个序列，要求每个数恰好被选入一个序列之中。
并且满足限制：(c_i)表示不小于(i)的数的个数，对于(1leq ileq k)都要满足。
现在问最少构成多少个序列。
保证(c_1geq c_2geq cdots geq c_k)。
思路：
最简单的想法，我们从后往前贪心来选，每次找到一个合适的位置然后将其删除添加入序列中，反复执行这个过程即可。
因为我们需要查找对应位置，并且要删除操作，所以用个(set)维护原序列剩下的数。
时间复杂度(O(nlog^2n))。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/26 23:46:45
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
int n, k;
int m[N], c[N];
void run() {
cin >> n >> k;
multiset <int> s;
for (int i = 1; i <= n; i++) {
cin >> m[i];
s.insert(m[i]);
}
for (int i = 1; i <= k; i++) {
cin >> c[i];
}
vector <vector<int>> ans;
while(sz(s)) {
vector <int> res;
while(1) {
int l = 1, r = k + 1, mid;
auto chk = [&] (int x) {
auto it = s.lower_bound(x);
if(it != s.end() && c[*it] >= sz(res) + 1) {
return true;
}
return false;
};
while(l < r) {
mid = (l + r) >> 1;
if(chk(mid)) l = mid + 1;
else r = mid;
}
auto it = s.lower_bound(l - 1);
if(it == s.end() || *it != l - 1) break;
s.erase(it);
res.push_back(l - 1);
}
ans.push_back(res);
}
cout << sz(ans) << '
';
for (int i = 0; i < sz(ans); i++) {
cout << sz(ans[i]);
for (auto it : ans[i]) {
cout << ' ' << it;
}
cout << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
这个题的时间复杂度还可以进一步优化。
我们注意到假设最后的答案为(k)，那么将原数组像(1,2,cdots,k,1,2cdots,k,1,cdots)这样进行分组肯定符合条件。
所以我们二分答案，直接将原序列像上面进行分组然后check即可，时间复杂度为(O(nlogn))。
这个题还可以做到(O(n))。我们现在只需要快速求出最小的(k)即可。
那么遍历一遍，对每个位置求出按照当前位置作为开头最小的分段数，这里面取最大值即是答案。
假设(i)得到(x)，(j,i<j)得到(y)，若(yleq x)，那么分为(x)组也可以满足条件；否则分(y)组才行，分(y)组也满足(i)位置的限制。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/27 16:10:31
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;
int n, k;
int m[N], c[N], cnt[N], suf[N];
void run() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> m[i];
++cnt[m[i]];
}
sort(m + 1, m + n + 1);
for (int i = k; i >= 1; i--) {
suf[i] = suf[i + 1] + cnt[i];
}
for (int i = 1; i <= k; i++) {
cin >> c[i];
}
int res = 0;
for (int i = 1; i <= k; i++) {
res = max(res, (suf[i] - 1) / c[i] + 1);
}
cout << res << '
';
vector <vector <int>> ans(res);
for (int i = 1; i <= n; i++) {
ans[(i - 1) % res].push_back(m[i]);
}
for (int i = 0; i < res; i++) {
cout << sz(ans[i]);
for (auto it : ans[i]) cout << ' ' << it;
cout << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
感觉(O(nlogn))的做法是最自然的，“性价比”也比较高。
E. Placing Rooks
题意：
给出一个(ncdot n)的棋盘，现在要在棋盘上放置(n)个棋子，每个棋盘能够攻击到在同一行、同一列的格子。
现在问满足如下条件的棋子放置总情况个数：
- 棋盘每个格子都能被攻击到；
- 恰好有(k)对棋子能互相攻击，一对棋子能互相攻击的条件是这对棋子位于同一行或者同一列，并且中间没有其它棋子。
比如下图为(n=3,k=2)的一种合法情况：
思路：
因为保证每个格子都处于攻击之下，所以每一行/每一列都必须有一个棋子，我们接下来考虑行的情况，列的情况同理。
注意到有这样一个事实：
- 在每一行放置一个棋子的情况下，互相攻击的棋子必须在同一列，并且将(n)个棋子放入(t)列中，每一列至少有一个，总的攻击的对数为(n-t)。
挺容易证明的，假设现在(t)列共有(k)对棋子互相攻击，那么有(x_1+x_2+cdots+x_t=k)，令(y_i=x_i+1)，那么(y_i)即是第(i)列的棋子个数，所以就有(y_1+y_2+cdots+y_t=n)。现在已知(y_1+y_2+cdots+y_t)，那么很容易推出(x_1+x_2+cdots+x_t)。
那么此时我们所求的方案数为(displaystyle {nchoose n-k}cdot egin{Bmatrix}
n \ n-k
end{Bmatrix}cdot(n-k)!)。
后者为第二类斯特林数，因为我们这里不同的顺序会算上所有情况，那么最后还要乘以一个阶乘。
第二类斯特林数可以直接通过容斥来求，可以参见我之前写的博客。
代码如下：
Code
/*
* Author: heyuhhh
* Created Time: 2020/4/27 0:38:49
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5, MOD = 998244353;
int 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;
}
ll n, k;
int fac[N], inv[N];
int C(int n, int m) {
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
void run() {
cin >> n >> k;
if (k >= n) {
cout << 0 << '
';
return;
}
fac[0] = 1;
for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[N - 1] = qpow(fac[N - 1], MOD - 2);
for (int i = N - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
int ans = 0;
for (int i = 0; i <= n - k; i++) {
int res = 1ll * C(n - k, i) * qpow(n - k - i, n) % MOD;
if(i & 1) res = MOD - res;
ans = (ans + res) % MOD;
}
ans = 1ll * ans * C(n, n - k) % MOD;
if(k) (ans <<= 1) %= MOD;
cout << ans << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}