20230223
A
比较显然的，不考虑每天的需求，单看总量可以确定一个最小需求\(x_1\),再看单日最大需求量\(x_2\)，可以证明两者的最大值一定可以满足条件，故最终答案为\(max(x_1,x_2)\)
code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e5 + 5;
int n, q;
ll a[N], m, sum;
multiset<ll> s;
ll ans;
int main() {
freopen("server.in", "r", stdin);
freopen("server.out", "w", stdout);
scanf("%d%lld%d", &n, &m, &q);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s.insert(a[i]);
sum += a[i];
}
ll mx = *s.rbegin();
ans = max(mx, (sum - 1) / m + 1);
printf("%lld\n", ans);
int p;
ll c;
while (q--) {
scanf("%d%lld", &p, &c);
sum += c - a[p];
s.erase(s.find(a[p]));
s.insert(c);
a[p] = c;
ll mx = *s.rbegin();
ans = max(mx, (sum - 1) / m + 1);
printf("%lld\n", ans);
}
}
B
\(40pts:\)
每次枚举\(l\),\(r\)，直接反转，用哈希处理
\(30pts:\)
若\(c\)不在中间位置上，直接以\(c\)和\(mid\)作为\(l\),\(r\)，不断向两端扩展
r若\(c\)在中间位置上，可以证明直接从两边向中间，和从中间向两边去找第一个不同的位置，在某一侧进行\(rev\)，一定是最终答案（证明了半页）
\(100pts:\)
从特殊性质的结论出发，从两端向中间找第一个不同的位置，则两个位置必有一个是答案的端点，证明过程类比特殊性质
code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int p = 1e9 + 7, bas = 233;
int n;
char s[N];
ll pw[N];
ll hl[N], hr[N];
ll calcl(int l, int r) { return ((hl[r] - hl[l - 1] * pw[r - l + 1] % p) % p + p) % p; }
ll calcr(int l, int r) { return ((hr[l] - hr[r + 1] * pw[r - l + 1] % p) % p + p) % p; }
bool rev_chk(int l, int r) {
return ((((hl[n] - calcl(l, r) * pw[n - r] % p) % p + p) % p + calcr(l, r) * pw[n - r] % p) % p) ==
((((hr[1] - calcr(l, r) * pw[l - 1] % p) % p + p) % p + calcl(l, r) * pw[l - 1] % p) % p);
}
void solve1() {
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
if (rev_chk(i, j)) {
printf("%d %d\n", i, j);
return;
}
printf("-1 -1\n");
return;
}
int vis[27];
int pos, wd;
void solve2() {
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++) ++vis[s[i] - 'a'];
for (int i = 0; i < 26; i++)
if (vis[i] == 1)
wd = i;
for (int i = 1; i <= n; i++)
if (s[i] - 'a' == wd)
pos = i;
if (n % 2 == 0) {
printf("-1 -1\n");
return;
}
int mid = (n + 1) / 2;
if (pos == mid) {
int l = 1, r = n / 2;
while (l <= n / 2 && s[l] == s[n - l + 1]) ++l;
while (r >= 1 && s[r] == s[n - r + 1]) --r;
if (l > r) {
printf("1 1\n");
return;
}
if (rev_chk(l, r))
printf("%d %d\n", l, r);
else
printf("-1 -1\n");
} else {
int l = min(mid, pos), r = max(mid, pos);
for (int i = 0; l - i >= 1 && r + i <= n; i++) {
if (rev_chk(l - i, r + i)) {
printf("%d %d\n", l - i, r + i);
return;
}
}
printf("-1 -1\n");
return;
}
}
void solve() { //solve1、solve2为赛时暴力，对应前40分与特殊性质
scanf("%d %s", &n, s + 1);
hr[n + 1] = 0;
for (int i = 1; i <= n; i++) hl[i] = (hl[i - 1] * bas % p + s[i]) % p;
for (int i = n; i; i--) hr[i] = (hr[i + 1] * bas % p + s[i]) % p;
// if(n<=1000)
// return solve1();
// else
// return solve2();
int sl, sr;
for (int i = 1; i <= (n + 2) / 2; i++)
if (s[i] ^ s[n - i + 1]) {
sl = i, sr = n - i + 1;
break;
}
// printf("%d %d\n",sl,sr);
for (int i = sl; i <= n; i++)
if (rev_chk(sl, i)) {
printf("%d %d\n", sl, i);
return;
}
for (int i = sr; i; i--)
if (rev_chk(i, sr)) {
printf("%d %d\n", i, sr);
return;
}
printf("-1 -1\n");
return;
}
int main() {
freopen("palindrome.in", "r", stdin);
freopen("palindrome.out", "w", stdout);
pw[0] = 1;
for (int i = 1; i <= 100000; i++) pw[i] = pw[i - 1] * bas % p;
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}
/*
2
5
bacba
13
aabcdefebcdaa
*/
C
\(???pts:\)
将可以互相攻击到的点之间连一条边，可以观察出来得到的图是一张二分图，直接暴力建图跑二分图最大匹配，可以获得\(20-35pts\)，实测匈牙利跑得会比网络流快一些
\(100pts:\)
直接贴题解（不会打太多\(\LaTeX\)
简单来说就是预处理出来所有小块的分法，然后把询问的大块拆开输出
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int T;
int n, m;
int calc(int x, int y) { return (x - 1) * m + y; }
vector<int> e[1000005];
int dx[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
int dy[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
int col[N][N];
int match[1000005];
int vis[1000005];
bool dfs(int u, int tim) {
if (vis[u] == tim)
return false;
vis[u] = tim;
for (int v : e[u])
if (!match[v] || dfs(match[v], tim)) {
match[v] = u;
return true;
}
return false;
}
struct node {
int a, b, c, d;
};
vector<node> vec[9][9];
void pre() {
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
col[i][j] = ((i & 1) ^ (j & 1)) ? 1 : 0;
int u = calc(i, j);
vis[u] = 0;
match[u] = 0;
e[u].clear();
if (!col[i][j])
continue;
for (int k = 0; k < 8; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > m)
continue;
int v = calc(x, y);
e[u].push_back(v);
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (col[i][j]) {
int u = calc(i, j);
if (dfs(u, u))
++res;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!col[i][j]) {
int v = calc(i, j);
if (match[v]) {
int u = match[v];
int x = (u - 1) / m + 1, y = u - (x - 1) * m;
vec[n][m].push_back({ i, j, x, y });
}
}
}
void init() {
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++) n = i, m = j, pre();
}
// int n,m;
vector<node> ans;
int cal(int x, int y) { return x - y > 7 ? 4 : x - y + 1; }
void solve() {
// int n,m;
ans.clear();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i += cal(n, i))
for (int j = 1; j <= m; j += cal(m, j))
for (auto x : vec[cal(n, i)][cal(m, j)])
ans.push_back({ x.a + i - 1, x.b + j - 1, x.c + i - 1, x.d + j - 1 });
printf("%d\n", ans.size());
for (auto i : ans) printf("%d %d %d %d\n", i.a, i.b, i.c, i.d);
}
int main() {
freopen("knight.in", "r", stdin);
freopen("knight.out", "w", stdout);
init();
scanf("%d", &T);
while (T--) solve();
return 0;
}
D
\(20pts:\)
直接暴力枚举集合，判断是否为团
\(100pts:\)
然而赛时赛后都没几个人去写正解
随机化（随便艹）
每次shuffle一下点的顺序，然后依次判断每个点能否加入已有集合，去更新答案的最大值
优化思路1：如果当前点度数小于当前答案，那么选择它就一定不更优，故可以将其删除
优化思路2：如果当前剩下的点数已经不比答案多了，答案就不再会被更新了
加上卡时4s稳过，1s也不算困难
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
mt19937 rnd(time(0));
unordered_set<int> e[N];
int n, m, a[N];
int tmp[N], tot;
int ans, tim, res;
int main() {
freopen("zhijiang.in", "r", stdin);
freopen("zhijiang.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) a[i] = i;
int x;
for (int i = 1; i <= m; i++) {
scanf("%d", &x);
e[a[x]].insert(a[x + 1]);
e[a[x + 1]].insert(a[x]);
swap(a[x], a[x + 1]);
}
for (int i = 1; i <= n; i++)
if (e[i].size())
a[++tot] = i;
while ((++tim %= 100) || (double)clock() / CLOCKS_PER_SEC < 0.95) {
shuffle(a + 1, a + tot + 1, rnd);
res = 0;
for (int i = 1; i <= tot; i++)
if (e[a[i]].size() >= res) {
tmp[++res] = a[i];
for (int j = 1; j < res; j++)
if (!e[a[i]].count(tmp[j])) {
--res;
break;
}
}
if (res > ans) {
ans = res, m = 0;
for (int i = 1; i <= tot; i++)
if (e[a[i]].size() >= res)
a[++m] = a[i];
tot = m;
}
}
printf("%d\n", ans);
return 0;
}