C题全员fst，不过幸好过了D、E，上了62分。现在Rating：1815，上紫指日可待。
先贴个代码，心情好的时候回来补题解QwQ。
Codeforces1244A. Pens and Pencils（水题）
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db;
/** fast read **/
template <typename T>
inline void read(T &x) {
x = 0; T fg = 1; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -1;
ch = getchar();
}
while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
int main()
{
int t;
cin >> t;
while (t--){
int a, b, c, d, k;
read(a, b, c, d, k);
int ans1 = a/c + (a%c>0);
int ans2 = b/d + (b%d>0);
if (ans1 + ans2 <= k) {
cout << ans1 << ' ' << ans2 << endl;
}
else {
cout << -1 << endl;
}
}
return 0;
}
Codeforces1244B. Rooms and Staircases（两种情况枚举一下，水题）
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db;
/** fast read **/
template <typename T>
inline void read(T &x) {
x = 0; T fg = 1; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -1;
ch = getchar();
}
while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
int main()
{
int t;
cin >> t;
while (t--) {
int n; read(n);
string s; cin >> s;
int ans = n;
int pre = -1;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
pre = i;
break;
}
}
if (pre != -1) {
ans = max(ans, 2*(n - pre));
}
pre = -1;
for (int i = n-1; i >= 0; i--) {
if (s[i] == '1') {
pre = i;
break;
}
}
if (pre != -1) {
ans = max(ans, 2*(pre+1));
}
cout << ans << endl;
}
return 0;
}
Codeforces1244C. The Football Season（暴力，可以证明循环节长度不超过max(w,d)，全民fst）
UPD：
很多人WA on test 62，是因为算出了负数的答案。TLE on test 66的话可能是忘记break了。
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db;
/** fast read **/
template <typename T>
inline void read(T &x) {
x = 0; T fg = 1; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -1;
ch = getchar();
}
while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
int main()
{
ll n, p, w, d;
read(n, p, w, d);
ll cntw = 0, cntd = 0, cntl = 0;
if (d < w) {
ll sum = 0;
for (; cntd <= w; cntd++) {
if ((p-sum) % w == 0) {
break;
}
sum += d;
}
cntw = (p-sum) / w;
cntl = n-cntw-cntd;
if ((p-sum)%w != 0 || cntw+cntd > n) {
puts("-1");
}
else {
if (cntw < 0 || cntd < 0 || cntl < 0) {
return 0 * puts("-1");
}
printf("%I64d %I64d %I64d
", cntw, cntd, cntl);
}
}
else if (d >= w) {
ll sum = 0;
for (; cntw <= d; cntw++) {
if ((p-sum) % d == 0) {
break;
}
sum += w;
}
cntw = (p-sum) / d;
cntl = n-cntw-cntd;
if ((p-sum)%d != 0 || cntw+cntd > n) {
puts("-1");
}
else {
if (cntw < 0 || cntd < 0 || cntl < 0) {
return 0 * puts("-1");
}
printf("%I64d %I64d %I64d
", cntw, cntd, cntl);
}
}
return 0;
}
Codeforces1244D. Paint the Tree
UPD：
可以发现给出的树不是链的情况都是不可能染色的。对于链的情况，枚举前三个节点的颜色，暴力跑一边取最小值就好了。
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db;
/** fast read **/
template <typename T>
inline void read(T &x) {
x = 0; T fg = 1; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -1;
ch = getchar();
}
while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
/** graph **/
int tot = 0;
int head[N], nxt[M<<1], ver[M<<1];
int deg[N];
void addEdge(int u, int v) {
nxt[++tot] = head[u], ver[tot] = v, head[u] = tot;
deg[u]++;
}
int n;
ll c[N][4];
void input() {
read(n);
memset(head, -1, sizeof head);
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
read(c[j][i]);
}
}
for (int i = 1; i <= n-1; i++) {
int u, v;
read(u, v);
addEdge(u, v);
addEdge(v, u);
}
}
bool vis[N];
vector <int> nodes;
void dfs(int u) {
vis[u] = true;
nodes.push_back(u);
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = ver[i];
if (vis[v])
continue;
dfs(v);
}
}
ll f[N][4][4];//i-th node choose j-th color's and previous node is k-th color tot cost
int pre[N][4][4];
int ans[N];
ll dp() {
ll res = 1e18;
vector <int> vs;
for (int i = 1; i <= 3; i++)
vs.push_back(i);
do {
ll tmpres = 0;
for (int i = 0; i < sz(nodes); i++) {
int u = nodes[i];
tmpres += c[u][vs[i%3]];
}
if (res > tmpres) {
res = tmpres;
for (int i = 0; i < sz(nodes); i++) {
int u = nodes[i];
ans[u] = vs[i%3];
}
}
}while (next_permutation(vs.begin(), vs.end()));
return res;
}
int main()
{
input();
bool ok = true;
int st = 1;
for (int i = 1; i <= n; i++) {
if (deg[i] == 1) {
st = i;
}
if (deg[i] >= 3) {
ok = false;
break;
}
}
if (!ok) {
puts("-1");
}
else {
memset(vis, false, sizeof vis);
dfs(st);
ll res = dp();
cout << res << endl;
for (int i = 1; i <= n; i++) {
printf("%d%c", ans[i], i == n ? '
' : ' ');
}
}
return 0;
}
Codeforces1244E. Minimizing Difference（一个很经典的模拟题）
UPD：
我的做法是把所有数值的数量统计好，并把所有数值放在一个vector里面排序去重。
用l和r指针分别指向最小的数和最大的数。
每次考虑移动数量比较小的一边，并考虑是否能向l+1（或r-1）合并。能合并的话，就把两个数量加起来，并最小值变成l+1（或最大值变成r-1）；不能合并说明k要用完了，看最多能改变多少最小值（或最大值），修改之后就直接出答案了。
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db;
/** fast read **/
template <typename T>
inline void read(T &x) {
x = 0; T fg = 1; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -1;
ch = getchar();
}
while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
ll a[N];
unordered_map <ll, ll> mcnt;
vector <ll> v;
int main()
{
int n; ll k;
read(n, k);
for (int i = 1; i <= n; i++) {
read(a[i]);
v.push_back(a[i]);
mcnt[a[i]]++;
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int pl = 0, pr = sz(v)-1;
ll vall = v[pl], valr = v[pr];
ll cntl = mcnt[vall], cntr = mcnt[valr];
ll _min = vall, _max = valr;
while (pl < pr && k > 0) {
vall = v[pl], valr = v[pr];
if (cntl < cntr) {
// pl+
ll vallr = v[pl+1];
ll cutk = (vallr - vall) * cntl;
if (k >= cutk) {
k -= cutk;
pl++;
cntl += mcnt[vallr];
_min = vallr;
}
else {
ll add = k / cntl;
k = 0;
_min += add;
}
}
else if (cntl >= cntr) {
ll valrl = v[pr-1];
ll cutk = (valr - valrl) * cntr;
if (k >= cutk) {
k -= cutk;
pr--;
cntr += mcnt[valrl];
_max = valrl;
}
else {
ll add = k / cntr;
k = 0;
_max -= add;
}
}
}
ll ans = _max - _min;
cout << ans << endl;
return 0;
}
Codeforces1244F. Chips（模拟）
UPD：
补完这题发现这场真的是手速场，一堆模拟题。错失上分的大好机会QAQ。
用手模拟一下样例，就可以发现两个结论：
1、连续的W或者B不论执行多少次操作，都不会改变。
2、连续的形如WBWB的子串，每次操作会翻转一次。
形如WWBWBWW，中间的BWB在执行一次操作之后就会翻转成WBW，两侧的WBW会合并到两侧的W中。
此时我们就可以模拟了。将所有形如WBWB的子串的两端（l，r）记录下来，每次操作将两段的点修改为和相邻的连续的W或者B相同，再l++，r--就好了。
特别地，如果没有连续的W或者B，每次操作都会使整个字符串翻转，如果翻转偶数次，则不变，奇数次每个W改成B，B改成W输出就好了。
#include <bits/stdc++.h> #define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define N 200005 #define M 100005 #define INF 0x3f3f3f3f #define mk(x) (1<<x) // be conscious if mask x exceeds int #define sz(x) ((int)x.size()) #define upperdiv(a,b) (a/b + (a%b>0)) #define mp(a,b) make_pair(a, b) #define endl ' ' #define lowbit(x) (x&-x) using namespace std; typedef long long ll; typedef double db; /** fast read **/ template <typename T> inline void read(T &x) { x = 0; T fg = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') fg = -1; ch = getchar(); } while (isdigit(ch)) x = x*10+ch-'0', ch = getchar(); x = fg * x; } template <typename T, typename... Args> inline void read(T &x, Args &... args) { read(x), read(args...); } int n, k; bool vis[N]; int posl[N], posr[N]; string s; void input() { read(n, k); cin >> s; for (int i = 0; i < n; i++) { if (i == 0) posl[i] = n-1; else posl[i] = i-1; if (i == n-1) posr[i] = 0; else posr[i] = i+1; vis[i] = false; } } struct SNode{ int p; int type; // l1, r2; bool operator < (const SNode& x) const { return p < x.p; } }; int main() { input(); queue <SNode> ps, tmpps; for (int l = 0; l < n; l++) { int r = l; while (r+1 < n && s[r+1] == s[r]) { ++r; } if (r-l+1 >= 2) { for (int i = l; i <= r; i++) vis[i] = true; ps.push(SNode{l, 1}); ps.push(SNode{r, 2}); l = r; } } if (!vis[0] && !vis[n-1] && s[0] == s[n-1]) { ps.push(SNode{n-1, 1}); ps.push(SNode{0, 2}); vis[0] = vis[n-1] = true; } /** 000000pr0000pl000 **/ bool can_reverse = false; for (int i = 1; i <= k; i++, can_reverse = !can_reverse) { if (ps.empty()) break; while (!ps.empty()) { SNode tmpr = ps.front(); ps.pop(); if (tmpr.type == 1) { ps.push(tmpr); continue; } SNode tmpl = ps.front(); ps.pop(); int pl = tmpl.p, pr = tmpr.p; if (posl[pl] != pr && posl[posl[pl]] != pr) { int prr = posr[pr], pll = posl[pl]; s[prr] = s[pr]; vis[prr] = true; tmpps.push(SNode{prr, 2}); s[pll] = s[pl]; vis[pll] = true; tmpps.push(SNode{pll, 1}); } else if (posl[posl[pl]] == pr) { int p = posl[pl]; vis[p] = true; if (s[pl] == s[pr]) s[p] = s[pl]; else if (can_reverse) { if (s[p] == 'B') s[p] = 'W'; else if (s[p] == 'W') s[p] = 'B'; } } } while (!tmpps.empty()) { ps.push(tmpps.front()); tmpps.pop(); } } if (can_reverse) { for (int i = 0; i < n; i++) { if (!vis[i]) { if (s[i] == 'B') s[i] = 'W'; else if (s[i] == 'W') s[i] = 'B'; } } } cout << s << endl; return 0; } /* 6 1 BWBBWW */
Codeforces1244G. Running in Pairs（构造，大水题！！！！）
UPD:
显然最小的和是$sum_{i=1}^{n}i$= n*（n+1）/2。如果k小于这个最小值，那显然是不行的。
否则必定是可行的。不妨先将p和q都设1，2，……，n。sum = n*（n+1）/2。
从n到1枚举i，考虑是否能把q中的元素i放到q中第一个没被修改的点，从而让sum接近但不超过k。如果超过k就跳过当前的i。最多能接近$sum_{i=1}^{n/2}(n-i+1)-i$，这样的操作最后会把步长收敛到1，所以是最优的。
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 1000005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
typedef double db;
/** fast read **/
template <typename T>
inline void read(T &x) {
x = 0; T fg = 1; char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') fg = -1;
ch = getchar();
}
while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
int ans1[N], ans2[N];
int main()
{
ll n, k;
read(n, k);
ll minres = n*(n+1) / 2;
ll maxres = 0;
for (int i = 1; i <= n; i++) {
ans1[i] = i;
ans2[i] = n-i+1;
maxres += max(ans1[i], ans2[i]);
}
if (k < minres)
return 0 * puts("-1");
else if (k >= maxres) {
k = maxres;
}
else {
int l = 1, r = n;
ll sum = minres;
for (int i = 1; i <= n; i++) {
if (r >= ans1[i] && sum + r - ans1[i] <= k) {
sum += r - ans1[i];
ans2[i] = r--;
}
else {
ans2[i] = l++;
}
}
}
cout << k << endl;
for (int i = 1; i <= n; i++)
printf("%d%c", ans1[i], "
"[i==n]);
for (int i = 1; i <= n; i++)
printf("%d%c", ans2[i], "
"[i==n]);
return 0;
}
/*
5 20
*/