比赛链接：传送门
上半场5题，下半场疯狂挂机，然后又是差一题金，万年银首也太难受了。
（每次银首都会想起前队友的灵魂拷问：你们队练习的时候进金区的次数多不多啊？）
Problem J. Justifying the Conjecture 00：09 （+） Solved by Dancepted
签到。好像见过很多次了，经典水题。然后英语太差了，理解题意用了不少时间。
代码：
#include <bits/stdc++.h>
#define endl '\n' using namespace std; int main() {
int T;
cin >> T;
while (T--) {
int x;
scanf("%d", &x);
if (x <= ) {
puts("-1");
continue;
}
else if (x&) {
cout << << ' ' << x - << endl;
}
else {
cout << << ' ' << x - << endl;
}
} return ;
}
Problem K. Keeping Rabbits 00：09 （-1） Solved by Dancepted
签到。稍微想一下发现期望重量跟第一天的重量线性相关，把所有的胡萝卜按重量分配即可。
因为担心不必要的精度问题用了long double结果交上去不知道为啥输出了-0.000000，WA了一发。
代码：
#include <bits/stdc++.h>
#define N 100005 using namespace std;
typedef double db; db w[N]; int main() {
int T;
cin >> T;
while (T--) {
int n, k;
scanf("%d%d", &n, &k);
db sum = ;
for (int i = ; i <= n; i++) {
scanf("%lf", &w[i]);
sum += w[i];
}
for (int i = ; i <= n; i++) {
w[i] += (db)k*w[i]/sum;
printf("%.6f%c", w[i], " \n"[i == n]);
}
}
return ;
}
Problem F. Fixing Banners 00：36 （+） Solved by lh
签到。暴力枚举。
代码：
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define lowbit(x) ((-x) & x)
#define ffor(i, d, u) for (int i = (d); i <= (u); ++i)
#define _ffor(i, u, d) for (int i = (u); i >= (d); --i)
#define mst(array, Num, Kind, Count) memset(array, Num, sizeof(Kind) * (Count))
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
typedef long long ll;
typedef double db;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
const db PI = acos(-);
template <typename T>
inline void read(T &x)
{
x=;char c;T t=;while(((c=getchar())<''||c>'')&&c!='-');
if(c=='-'){t=-;c=getchar();}do(x*=)+=(c-'');while((c=getchar())>=''&&c<='');x*=t;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args)
{
read(x), read(args...);
}
template <typename T>
inline void write(T x)
{
int len=;char c[];if(x<)putchar('-'),x*=(-);
do{++len;c[len]=(x%)+'';}while(x/=);_ffor(i,len,)putchar(c[i]);
}
const ll MO = 1e9 + ;
const ll Inv2 = (MO + ) / ;
#define N 2000005
#define M 3000005
int T, cnt[][];
char a[][N], mu[] = {'h', 'a', 'r', 'b', 'i', 'n'};
bool flag[] = {};
inline int ac()
{
read(T);
while (T--)
{
int b[] = {, , , , , };
ffor(i, , )
{
scanf("%s", a[i]);
ffor(j, , ) cnt[i][j] = ;
}
ffor(i, , )
{
int len = strlen(a[i]) - ;
ffor(j, , len)
{
switch(a[i][j])
{
case 'h':
++cnt[i][];
break;
case 'a':
++cnt[i][];
break;
case 'r':
++cnt[i][];
break;
case 'b':
++cnt[i][];
break;
case 'i':
++cnt[i][];
break;
case 'n':
++cnt[i][];
break;
}
}
}
bool flag = false;
do
{
int tot = ;
ffor(i, , ) if (cnt[b[i]][i] > )++ tot;
else break;
if (tot == )
{
flag = true;
break;
}
} while (next_permutation(b, b + ));
puts(flag ? "Yes" : "No");
}
return ;
}
int main()
{
ac();
return ;
}
Problem I. Interesting Permutation 01：48 （-1） Solved by Dancepted
不考虑a1是什么，而是考虑$a_{i}和a_{i-1}$之间的相对大小关系。
如果h序列是合法的话，最后n个数肯定是占据数轴上的一段长度为n的区间，这时再移动a1使得所有的数都落在[1, n]。
考虑h序列相邻两项
①$h_{i} < h_{i-1}$，不存在这样的序列，答案为0
②$h_{i} > h_{i-1}$，$a_{i}$比之前的最大值大$h_{i} - h_{i-1}$，或比之前的最小值小$h_{i} - h_{i-1}$，仅这两种选择，所以。
③$h_{i} = h_{i-1}$，$a_{i}$落在之前的最大值和最小值之间，选择的方案数为：[最小值，最大值]的区间长度 - $a_{i}$之前的数的个数（i - 1）
（WA了一发是因为脑抽把1e9+7写成了1e9+9，害得队友帮我写了一发暴力对拍了超久）
代码：O（n）
#include <bits/stdc++.h>
#define N 100005
#define md 1000000007 using namespace std;
typedef double db;
typedef long long ll; int h[N]; int main() {
int T;
cin >> T;
while (T--) {
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &h[i]);
}
ll ans = ;
if (h[] != || h[n] != n-)
ans = ;
for (int i = ; i <= n; i++) {
if (h[i] < h[i-]) {
ans = ;
}
else if (h[i] == h[i-]) {
ans = ans * (h[i] + - (i - )) % md;
}
else if (h[i] > h[i-]) {
ans = ans * % md;
} if (h[i]+ <= i-)
ans = ;
if (ans == )
break;
} cout << ans << endl;
} return ;
}
Problem E. Exchanging Gifts 02：19 （-1） Solved by Dancepted
因为礼物可以任意交换，所以如果知道了最后一个序列内各个数字出现的次数总和sum和数量最多的数字的数量$cnt_{max}$，那么答案肯定就是max(sum，2 × （sum - $cnt_{max}$）。
考虑如何统计各个数字的出现次数。
①如果最后一个序列是直接给出的，那么直接统计即可。
②如果最后一个序列是由之前的两个串给出的，那么对那两个串x和y分别统计。
然后是类似dp的做法，$f_{i}$表示第i个序列被统计的次数，那么②操作就相当于$f_{x} += f_{i}, f_{y} += f_{i}$
（WA了一发是因为f数组没有开long long，掌嘴）
代码：O（n + $\sum k$）
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define N 1000005 using namespace std;
typedef double db;
typedef long long ll; vector<int> nums[N];
ll mul[N];
int x[N], y[N];
unordered_map<int, ll> numcnt;
unordered_map<int, ll> :: iterator it;
int main() {
int T;
cin >> T;
while (T--) {
int n;
scanf("%d", &n);
numcnt.clear();
for (int i = ; i <= n; i++) {
nums[i].clear();
mul[i] = ;
x[i] = y[i] = -;
}
mul[n] = ;
for (int i = ; i <= n; i++)
{
int act;
scanf("%d", &act);
if (act == )
{
int k;
scanf("%d", &k);
for (int j = ; j <= k; j++)
{
int q;
scanf("%d", &q);
nums[i].push_back(q);
}
}
else if (act == )
{
scanf("%d%d", &x[i], &y[i]);
}
}
for (int i = n; i >= ; i--) {
if (x[i] != -) {
mul[x[i]] += mul[i];
mul[y[i]] += mul[i];
}
} ll sum = , mx = ;
for (int i = ; i <= n; i++) {
if (x[i] == - && mul[i]) {
for (int &tmp : nums[i]) {
numcnt[tmp] += mul[i];
sum += mul[i];
mx = max(mx, numcnt[tmp]);
}
}
}
ll ans = min(sum, * (sum - mx));
cout << ans << endl;
}
return ;
}
比赛结束前我还在敲B题，奈何思路太乱了，实现起来太复杂，赛后调了半天还是过不去（最后还是惨兮兮去看了题解）。
UPD：B. Binary Numbers（dp+滚动数组优化）
函数$F_{k}(a, b)$相当于求a，b转化成长度为m的二进制串后求最长公共前缀lcp
然后可以发现两个数值相差越大，lcp越小。所以对于$[L_{i}, R_{i}]$这个区间，只要满足：
①：$lcp(A_{j}, L_{i}) <= lcp(A_{i}, L{i})，j < i$
②：$lcp(A_{j}, R_{i}) <= lcp(A_{i}, R{i})， j > i$
用$f_{i, j, k}$表示考虑了前i个区间，$A_{i}$和$L_{i+1}$的lcp为j，和$R_{i}$的lcp为k的价值。
然后暴力枚举$f_{i-1}$中满足条件的j和k进行转移即可。
空间不够，可以滚动数组优化一下。
代码：O（$2^{m}m^{2}$）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 266666
// #define N 555
#define M 18 using namespace std;
typedef long long ll;
const int md = ; inline int add(int a, int b) {
int res = (a + b) % md;
if (res < )
res += md;
return res;
}
inline int mul(int a, int b) {
return (int)((ll)a * b % md);
} inline int lcp(int a, int b, int m) {
int res = ;
for (int i = m-; i >= ; i--) {
if ((a & (<<i)) == (b & (<<i)))
res++;
else
break;
}
return res;
} int l[N], r[N];
int f[][M][M];
int main() {
int T;
cin >> T;
while (T--) {
int m, n;
cin >> m >> n;
for (int i = ; i <= n; i++)
scanf("%d%d", &l[i], &r[i]);
for (int i = ; i < ; i++) {
for (int j = ; j <= m; j++) {
for (int k = ; k <= m; k++) {
f[i][j][k] = ;
}
}
}
for (int i = l[]; i <= r[]; i++) {
int lcpl = lcp(i, l[], m), lcpr = lcp(i, r[], m);
f[][lcpl][lcpr] = add(f[][lcpl][lcpr], i);
}
for (int i = ; i <= n; i++) {
int id = i & ;
memset(f[id], , sizeof f[id]);
for (int j = l[i]; j <= r[i]; j++) {
int lcpl = lcp(j, l[i+], m), lcpr = lcp(j, r[i], m);
int prelcpr = lcp(j, r[i-], m), prelcpl = lcp(j, l[i], m);
for (int l1 = ; l1 <= prelcpl; l1++) {
for (int r1 = prelcpr; r1 <= m; r1++) {
f[id][lcpl][lcpr] = add(f[id][lcpl][lcpr], mul(j, f[id^][l1][r1]));
}
}
}
}
ll ans = ;
for (int l = ; l <= m; l++) {
for (int r = ; r <= m; r++) {
ans = add(ans, f[n&][l][r]);
}
}
cout << ans << endl;
}
return ;
}
总结：
这场的几个罚时都不太应该，没有开long long（差点还踩了1e8+7的坑）、手滑写错了1e9+9、long double 输出-0.000000。。。
主要刚开始上手vscode，心理上有点不适应，所以写代码的时候有点暴躁？而且用的队友的电脑，没有头文件给我复制。。。
B题读题的时候太慢了，也是题目做的太少了，归纳能力太差劲。
然后xk这场状态不是很好的亚子（也可能是都花时间帮我debug了，不过有一说一，xk帮我找bug确实每次都能找出来）。
金区不像银、铜区，卡牌子的都只有一道题，开出来就高一档次，没开出来就没有。
金区那条线的题有很多，多过一道题就能金。然鹅我们队签完到进入银区后，因为没有学得很精的算法，基本没有能开出来的金牌题，还是有点难受的。