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 ‘\n‘
#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 ‘\n‘
#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）
#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 ‘\n‘
#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\n", 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\n", cntw, cntd, cntl);
}
}
return 0;
}
Codeforces1244D. Paint the Tree（可以证明不是链的情况都是不行的，暴力）
#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 ‘\n‘
#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 ? ‘\n‘ : ‘ ‘);
}
}
return 0;
}
Codeforces1244E. Minimizing Difference（是个很经典的模拟）
#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 ‘\n‘
#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（还没补）
Codeforces1244G. Running in Pairs（构造，大水题！！！！）
#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 ‘\n‘
#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], " \n"[i==n]);
for (int i = 1; i <= n; i++)
printf("%d%c", ans2[i], " \n"[i==n]);
return 0;
}
/*
5 20
*/
Codeforces Round #592 (Div. 2)
原文：https://www.cnblogs.com/Lubixiaosi-Zhaocao/p/11668408.html