第一次AK CF纪念，虽然只是个div4。以前也有div3差点AK的经历，现在div3难度上来了，这种机会永远不会再有了吧……
为什么E水题写得尤其慢？因为中途洗了个澡。
这套题的概况：应该是最难的一场div4了。A~D不是算法题，E~H是算法题，H的dp有点难，想了我不少时间，差点没过。
作者：hans774882968以及hans774882968
A
签到。
B
设sz是集合大小。n - sz为偶数，则答案恰好为sz，否则需要多删一个元素，答案sz-1。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n, a[N];
void dbg() {
puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
cout << f << " ";
dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
read (x);
read (r...);
}
int main() {
int T;
read (T);
while (T--) {
read (n);
rep (i, 1, n) read (a[i]);
map<int, int> mp;
rep (i, 1, n) mp[a[i]]++;
printf ("%d\n", mp.size() - ( (n - mp.size() ) % 2) );
}
return 0;
}
C
题意：8*8棋盘，给出bishop的攻击范围，找bishop的位置。
水。当前点和对角线4个邻居都是'#'的点就是。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n;
char s[15][15];
void dbg() {
puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
cout << f << " ";
dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
read (x);
read (r...);
}
int main() {
int T;
read (T);
while (T--) {
re_ (i, 0, 8) scanf ("%s", s[i]);
rep (i, 1, 6) rep (j, 1, 6) {
if (s[i][j] == '#' && s[i - 1][j + 1] == s[i + 1][j + 1] && s[i - 1][j + 1] == s[i - 1][j - 1] && s[i - 1][j + 1] == s[i + 1][j - 1] && s[i - 1][j + 1] == '#')
printf ("%d %d\n", i + 1, j + 1);
}
}
return 0;
}
D
题意：给出当前时刻（用%02d:%02d表示，如05:50）和delta，表示从当前时刻开始，每delta分钟看一次闹钟，注意该过程是永久的。问总共能看到几个回文时刻。
虽然过程是永久的，但只需要处理到下一次走到当前时刻，即lcm(1440,delta)分钟。这个过程只需要枚举1440 // gcd(1440,delta)次，很稳。
from collections import defaultdict
from math import gcd
def get_time(v):
return "%02d:%02d" % (v // 60, v % 60)
def lcm(a, b):
return a // gcd(a, b) * b
for _ in range(int(input())):
time_s, d = input().split()
d = int(d)
h, m = map(int, time_s.split(':'))
cur = h * 60 + m
ans = 0
las = cur + lcm(1440, d)
for ti in range(cur, las, d):
time_s = get_time(ti % 1440)
if time_s == time_s[::-1]:
ans += 1
print(ans)
E
题意：给出01数组，每次你可以删除数组首元素和末尾元素，问最少删除几次可以得到一个和为s的子数组。如果无法得到输出-1。
双指针老模板题了。枚举所得子数组的右边界r，然后找到最小的l，使得a[l~r]等于s，则r-l+1为一个候选。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 3e5 + 5;
int n, s, a[N];
void dbg() {
puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
cout << f << " ";
dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
read (x);
read (r...);
}
int main() {
int T;
read (T);
while (T--) {
read (n, s);
rep (i, 1, n) read (a[i]);
int tot = accumulate (a + 1, a + n + 1, 0);
if (tot < s) {
puts ("-1");
continue;
}
int l = 1, cur = 0, ans = 0;
rep (i, 1, n) {
cur += a[i];
if (cur < s) {
continue;
}
while (l < i && cur > s) {
cur -= a[l++];
}
ans = max (ans, i - l + 1);
}
printf ("%d\n", n - ans);
}
return 0;
}
F
题意：给你一个数组，求是否存在3个不同下标，使得a[i]+a[j]+a[k]以3结尾。
以3结尾，即模10余3，故只需要扔到模10的桶里，然后3重循环枚举。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 10 + 5;
int n, a[N];
void dbg() {
puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
cout << f << " ";
dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
read (x);
read (r...);
}
bool jdg() {
rep (i, 0, 9) {
if (!a[i]) continue;
a[i]--;
rep (j, 0, 9) {
if (!a[j]) continue;
a[j]--;
rep (k, 0, 9) {
if (!a[k]) continue;
if ( (i + j + k) % 10 == 3) return true;
}
a[j]++;
}
a[i]++;
}
return false;
}
int main() {
int T;
read (T);
while (T--) {
read (n);
memset (a, 0, sizeof a);
rep (i, 1, n) {
int x;
read (x);
x %= 10;
a[x]++;
}
puts (jdg() ? "YES" : "NO");
}
return 0;
}
G
题意：给你一个长为n的数组和k。问有多少个下标i，1 <= i <= n-k满足：2^0 * a[i] < 2^1 * a[i+1] < ... < 2^k * a[i+k]。a[i] <= 1e9, n <= 2e5。
小于号有传递性，所以只需要满足2^j * a[i+j] < 2^(j+1) * a[i+j+1]，即a[i+j] < 2 * a[i+j+1]。我们先预处理出fl[i] = (a[i-1] < 2 * a[i])，然后快速判定长为k的区间是否不存在0即可。这个判定可以用前缀和数组完成。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 2e5 + 5;
int n, k, fls[N];
LL a[N];
void dbg() {
puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
cout << f << " ";
dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
read (x);
read (r...);
}
int main() {
int T;
read (T);
while (T--) {
read (n, k);
rep (i, 1, n) read (a[i]);
rep (i, 2, n) fls[i] = (2 * a[i] > a[i - 1]) + fls[i - 1];
int ans = 0;
rep (i, 1, n - k) {
if (fls[i + k] - fls[i] == k) {
ans++;
}
}
printf ("%d\n", ans);
}
return 0;
}
H
题意：输出任意一个区间[l,r]及其众数，满足2*区间众数-(r-l+1)最大。
首先可以反证法证明答案所选择的数总可以是区间端点，这种不失一般性为答案添加好性质的套路很常见。目标函数本来是2*区间众数-(r-l+1)，现在就变成2*a[r]的出现次数-(r-l+1)。定义dp[i]为以i为右端点的最优目标函数值，则max(dp[i])为最优目标函数值，其对应下标idx为所选区间右端点，a[idx]为所选值。再定义pt[i]为以i为右端点的条件下的左端点，则pt[idx]为所选区间左端点。
dp转移：模仿最大子段和的dp做法，dp[i] = max (1, dp[pre[i]] + (pre[i] - i + 2) )。
pt更新：pt[i] = dp[i] == 1 ? i : pt[pre[i]]。
pre[i]还是熟悉的配方还是熟悉的味道，表示a[i]上一次出现的下标，不存在则为0（1-indexed）。
更新：再也不敢在cf里用umap了……hack里加了卡umap的数据。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)
const int N = 2e5 + 5;
int n, a[N], pre[N], dp[N], pt[N];
void dbg() {
puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
cout << f << " ";
dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
Type f = 1;
char ch;
xx = 0;
for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
xx *= f;
}
void read() {}
template<typename T, typename ...R>void read (T &x, R &...r) {
read (x);
read (r...);
}
int main() {
int T;
read (T);
while (T--) {
read (n);
rep (i, 1, n) read (a[i]);
map<int, int> tmp;
rep (i, 1, n) {
pre[i] = tmp[a[i]];
tmp[a[i]] = i;
}
rep (i, 1, n) {
dp[i] = max (1, dp[pre[i]] + (pre[i] - i + 2) );
pt[i] = dp[i] > 1 ? pt[pre[i]] : i;
}
int idx = max_element (dp + 1, dp + n + 1) - dp;
printf ("%d %d %d\n", a[idx], pt[idx], idx);
}
return 0;
}