\(\text{Preface}\)
排名 \(\text{Rank 27/44}\)
得分 \(\text{100pts + 0pts + 4pts + 0pts = 104pts}\)
总结：
\(\text{T1}\) 场切题我写了个shab贪心搞了 \(\text{2h}\)
\(\text{T2}\) 本来想小 \(\text{dp}\) 一把，然后发现 \(\text{dp}\) 假了
\(\text{T3}\) 考场思路是对的，但是不知道脑子哪里抽了就给否了。然后想到 \(\text{smtwy}\) 在超大定义域里随机撒点撒到 \(\text{50pts}\) 就来气，所以直接开始大力撒点。因为有 \(\text{subtask}\) 所以最后只有 \(\text{4pts}\)。
\(\text{T4}\) 刚开始看到 \(\text{40pts}\) 的部分分挺开心，后来意识到这玩意的求方案数没那么简单。
\(\mathfrak{T1}\ 木棍\)
思路跟别人不大一样。但是感觉是个假做法。
赛时的思路是 \(10\) 一共有五种分法，2+2+2+2+2、2+2+2+4、2+4+4、3+3+2+2、3+3+4，仔细思考了一下发现两个三个 \(2\) 能合成一个 \(6\)，两个 \(3\) 也能合成一个 \(6\)，\(2\) 和 \(4\) 也能合成一个 \(6\)，于是就把 \(10\) 拆成了 \(6+4\)。发现似乎是个方程，所以设了一下完全由 \(2\) 变成 \(6\) 的个数为 \(x\) 和由 \(2\) 与 \(4\) 变成 \(6\) 的个数为 \(y\)。
设 \(n_6\) 为 \(6\) 的个数，那么首先就是让 \(n_3\) 全部转化为 \(6\) (你留着他也没啥别的用啊)。
因为要尽量让 \(6\) 和 \(4\) 相等，那么有：
\[n_6 + x + y = n_4 - y + \frac { n_2 - 3x - y } { 2 } \]移项整理得：
\[\begin{aligned} 5(x+y) &= 2n_4 - 2n_6 + n_2\\ x + y &= \frac { 2n_4 - 2n_6 + n_2 }{ 5 } \end{aligned} \]发现 \(x+y\) 即为新增的 \(6\) 的个数，正好是我们想要的，所以直接解出来赋值给 \(n_6\)。因为方程满足了 \(n_6 = n_4\) (\(6\) 或者 \(4\) 多一个少一个可以忽略，因为你多一个 \(6\) 或者多一个 \(4\) 你又不能自己凑出来答案)，所以此时 \(n_6\) 就是能凑出来的 \(10\) 的个数。
发现这样做第三个样例是过不去的，于是怀着爆零的心态加了个nb特判，结果就 \(\text{A}\) 了。。。
具体加的特判就是如果 \(n_4\) 极大的话就直接让 \(2\) 和 \(4\) 去全部合成 \(6\)，统计答案输出。\(n_4\) 极大指的就是 \(n_2\) 全部和 \(n_4\) 去转换为 \(n_6\) 后，\(n_4\) 还是比 \(n_6\) 大，即 \(n_4 - n_2 >= n_6 + n_2\)。
T1
/*
做总结
T1 贪心+分类讨论？
T2 找简单环。我 超
T3 没想出来啥 有点像树的重心
T4 魔鬼时空限制 还有看不出来是啥题 应该是个dp+组合数 以及样例似乎走丢了(
开题顺序：T1 -> T2 -> T3 -> T4
还有 T2 T4 要开文件
*/
#include <cstdio>
#include <cctype>
#include <iostream>
#define GMY (520&1314)
#define char_phi int
#define re register int
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout)
#define Endl cout << '\n'
#define _ ' '
#define Dl cerr << '\n'
#define DMARK cerr << "###"
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define ll __int128
using namespace std;
// inline void Fastio_setup(){ ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); }
/*
考虑10的分法
10 = 2+2+2+2+2
= 2+2+2+4
= 2+4+4
= 3+3+4
= 3+3+2+2
于是就大力分类讨论？
数据组数只有100是什么鬼啊(
之前似乎在哪做过类似的题
发现了神奇的东西
可以把4给全部转成2
哦吼
但是会炸long long
所以开 __int128 反正noip也让用
于是便只剩两种情况了
wow！！！
然后再把n3给全部整成6
那么剩下的就比较显然了，首先满足n3，再满足五个n2就行了
c，假了
我说出题人怎么会闲的没事考__int128
但是经过一番思考我决定特判
又想到了神奇的玩应。。。
把2和3都转成6
首先当然是把3全部转成6
由于2+2 -> 4，2+4 -> 6
所以考虑让6和4尽可能地等同需要分讨一下
又假，wc
我囸，两个小时了，我赶紧开别的题去
唉希望别爆零
*/
inline ll read(){
ll x = 0; char c;
while (!isdigit(c = getchar()));
do { x = (x << 3) + (x << 1) + (c & 15); } while (isdigit(c = getchar()));
return x;
}
void ot(ll x){
if (x > 9) ot(x/10);
putchar((x%10)+48);
}
ll T, n2, n3, n4, final_ans, n6;
inline void work(){
final_ans = 0;
n2 = read(), n3 = read(), n4 = read();
n6 = n3/2;
if (n6 >= n4+n2/2){// n6已经够多了
final_ans = (n4+n2/2);
}
else {// n6还少，需要转化
// 然后考虑用2+4去转化还是用2+2+2去转化
// 小解一把方程
// 发现不用exgcd都
if (n4-n2 > n6+n2)// 如果n4极大
{ n6 = n6 + n2; final_ans = n6; goto OUT; }
// cout << "res: "; ot((2*n4 - 2*n6 + n2) / 5), putchar('\n');
ll res = (2*n4 - 2*n6 + n2) / 5;// x+y
n6 = n6 + res;
// res < 0 说明n6多，不可能，因为确定了 n6*2 < n4*2 + n2 了
// 那么6的个数就是n6个啦。
final_ans = n6;
}
OUT:{}
ot(final_ans); putchar('\n');
}
#undef int
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
// Fastio_setup();
T = read();
while (T --)
work();
return GMY;
}
\(\mathfrak{T2}\ 环\)
贺的陈嘉然先生的。
T2
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define char_phi signed
#define re register int
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define Endl cout << '\n'
#define _ ' '
#define Dl cerr << '\n'
#define DMARK cerr << "###"
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 5005
#define P 998244353
#define mod %
using namespace std;
inline void Fastio_setup(){ ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); }
/*
*/
long long n, final_ans;
long long a[N], f[N];
inline long long ksm(long long A, long long B){
long long res(1);
while (B != 0){
if ((B & 1) == 1) res = res * A mod P;
A = A * A mod P;
B >>= 1;
}
return res;
}
inline void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
cin >> a[i];
sort(a+1, a+n+1);
f[0] = 1;
for (re i = 1 ; i <= n ; ++ i){
for (re j = a[i-1]+1 ; j <= a[i] ; ++ j)
for (re k = j ; k >= 1 ; -- k)
f[k] = (f[k] + f[k-1]) mod P;
final_ans = (final_ans + (f[1]-a[i]+P) mod P) mod P;
for (long long j = 0 ; j <= a[i] ; ++ j)
f[j] = (f[j] + f[j+1] * (j+1) mod P * j mod P) mod P;
}
cout << final_ans * ksm(2, P-2) mod P << '\n';;
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T3}\ 传令\)
这回不是贺的了。从下午的两点多开始改(自己的nt思路)，一直到晚上的七点，我tm改了一个下午。。。
先说思路。首先你二分答案一个时间。递归到叶子后往根回溯，然后贪心地选择当前点是否要作为国王选择的城市。
思路十分明确且简单，然后就是代码实现了。
然后代码实现我走了错路。(或者说我太弱了根本没调出来)
被覆盖指的是在某一作为国王选择的城市的点的影响范围内(就是你二分的时间内，距离就是影响范围)
我用结构体形式返回两个变量，分别是从当前点往下第一个没能被覆盖的点的深度(当然有可能因为贪心跑到他的上边，不过没关系)，第二个是当前点往下第一个作为国王选择的城市的深度。然后就大力分类讨论，调了无数个数据点，最后忍痛放弃换了 \(\text{SMTwy}\) 的代码实现方式。
\(\text{SMTwy}\) 的实现方式特别简洁。当然我猜他的习惯会让他的代码变得不是很简洁，不过我没看他代码。
设当前二分的值为 tmpans。
整一个 a[] 数组，先考虑链上的情况。具体地：
-
叶子节点的
a[]为0。 -
一个父亲的
a[]值为其儿子a[]值 \(+1\)(如果其儿子a[]值 \(+1\) 后 \(< \text{tmpans}\))。 -
当一个点的
a[]值 \(\ge \text{tmpans}\) 时，将他的a[]值变为 \(\text{tmpans-1}\)。
这么做的原因显然，是为了贪心嘛。当前点除了能往上覆盖 \(\text{tmpans}\) 长度之外，贪心地在他上面的 \(2 \times \text{tmpans}\) 处建立新的点。这样直接覆盖了更多的距离。自己画一条链就理解了。
但是毕竟链是链，不是树。考虑树的情况下应该咋合并。
假设一个节点 \(x\)，他的儿子传过来的 a[] 值中，最大值和最小值分别为 \(\text{mx}\) 和 \(\text{mn}\)。首先a[x]肯定是要儿子于是做以下分类讨论：
-
如果 \(mx < 0\) 并且 \(mn < 0\)，也就是说 \(x\) 的儿子把 \(x\) 给覆盖过了，那么根据贪心原则显然不会再选 \(x\)。
-
如果 \(mx + mn > 0\)，也就是说 \(x\) 的儿子中覆盖了 \(x\) 的儿子不仅能把 \(x\) 给覆盖，还能覆盖掉 \(x\) 其他的儿子。那么此时就算 \(\text{mx} \ge \text{tmpans}\) 也不会将 \(x\) 选上。
-
其他情况下 \(x\) 的
a[]值应为 \(\text{mx+1}\)。原因也显然，为了让 \(x\) 的父亲知道最深的在哪。
还有最后根节点需要特判一下。因为你是是贪心地选 \(2 \times \text{tmpans}\) 的，有可能根节点正好处于\(\text{tmpans} \sim 2 \times \text{tmpans}\) 之间，你贪心的时候不会把根节点选上，但是你不选根节点你那一块就直接没被覆盖了。所以特判一下是否要选根节点。
代码实现较为简单。按照我那一版写的话代码实现较为恶心。
T2
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define char_phi signed
#define re register int
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define Endl cout << '\n'
#define _ ' '
#define Dl cerr << '\n'
#define DMARK cerr << "###"
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 5005
#define P 998244353
#define mod %
using namespace std;
inline void Fastio_setup(){ ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); }
/*
*/
long long n, final_ans;
long long a[N], f[N];
inline long long ksm(long long A, long long B){
long long res(1);
while (B != 0){
if ((B & 1) == 1) res = res * A mod P;
A = A * A mod P;
B >>= 1;
}
return res;
}
inline void work(){
cin >> n;
for (re i = 1 ; i <= n ; ++ i)
cin >> a[i];
sort(a+1, a+n+1);
f[0] = 1;
for (re i = 1 ; i <= n ; ++ i){
for (re j = a[i-1]+1 ; j <= a[i] ; ++ j)
for (re k = j ; k >= 1 ; -- k)
f[k] = (f[k] + f[k-1]) mod P;
final_ans = (final_ans + (f[1]-a[i]+P) mod P) mod P;
for (long long j = 0 ; j <= a[i] ; ++ j)
f[j] = (f[j] + f[j+1] * (j+1) mod P * j mod P) mod P;
}
cout << final_ans * ksm(2, P-2) mod P << '\n';;
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
作为纪念我还是挂一下我写的屎山代码。
屎山代码 $\text{(74pts)}$
#include <iostream>
#include <cstring>
#define GMY (520&1314)
#define char_phi signed
#define re register int
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define Endl cout << '\n'
#define _ ' '
#define Dl cerr << '\n'
#define DMARK cerr << "###"
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 200005
using namespace std;
inline void Fastio_setup(){ ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); }
// #define Debug
/*
T3好简单好像
我赛时想麻烦了
我刚发现
我赛时的想法似乎是正确的
二分一个答案
然后直接跑树形dp
是O(nlogn)？
*/
/*
17 2
17 7
10 14
6 5
16 17
17 4
11 9
4 10
10 11
16 8
1 2
14 6
4 13
17 12
5 3
3 1
17 15
*/
/*
9 3
8 3
6 4
5 7
5 9
5 8
6 1
7 6
9 2
*/
/*
22 2
9 16
12 19
5 2
7 14
14 18
8 3
17 22
5 13
19 20
9 6
19 15
22 7
13 9
4 1
4 5
22 10
15 11
20 21
21 4
16 8
17 12
*/
/*
18 3
12 18
11 13
12 17
5 9
10 5
4 8
17 14
3 11
17 15
10 4
8 3
7 1
18 2
5 16
12 10
8 7
11 6
*/
/*
17 3
7 2
8 16
11 5
14 9
8 12
4 17
15 11
10 8
2 3
11 7
4 10
1 14
7 1
10 15
12 13
11 6
*/
int n, K, star_cnt, final_ans, chscnt, tmpans;
char chs[N];
int head[N], dep[N];
struct star {int v, nxt;};
struct RTN {int mxdep, mnchs;};
struct star e[N<<1];
struct RTN U_L_S;
inline void star_add(int u, int v){ e[++ star_cnt].v=v, e[star_cnt].nxt=head[u], head[u]=star_cnt; }
inline int Max(int x, int y){ return MAX(x, y); }
inline int Min(int x, int y){ return MIN(x, y); }
void getdep(int x, int faer){
for (re i = head[x] ; i ; i = e[i].nxt){
int v = e[i].v;
if (v == faer)
continue;
dep[v] = dep[x]+1;
getdep(v, x);
}
}
RTN dfs(int x, int faer){
int mxdep(-1145141919), mnchs(1145141919);
for (re i = head[x] ; i ; i = e[i].nxt){
int v = e[i].v;
if (v == faer)
continue;
/*long long deper;
deper = dfs(v, x);
#ifdef Debug
cerr << "感谢来自 " << v << " 老板的 " << deper << '\n';
#endif*/
RTN tmp = dfs(v, x);
mxdep = Max(mxdep, tmp.mxdep);
mnchs = Min(mnchs, tmp.mnchs);
}
#ifdef Debug
cerr << "dfs: " << x << _ << dep[x] << _ << mxdep << _ << mnchs << '\n';
Dl;
#endif
if (x == 1 and (mnchs-tmpans-1 >= dep[x] or mxdep-tmpans-1 >= dep[x]))
{ chs[x] = true; return (RTN){1, 1}; }
if (mxdep == -1145141919 and mnchs == 1145141919)// 啥都没干，是个叶子
{ /*cerr << x << "[1]" << '\n'; Dl; Dl;*/ return (RTN){dep[x], mnchs}; }
else if (mxdep-dep[x] >= tmpans and mnchs-dep[x]+mxdep-dep[x] > tmpans)// 该选
{ /*cerr << x << "[2]" << '\n'; Dl; Dl;*/ chs[x] = true; return (RTN){dep[x]-tmpans-1, dep[x]}; }
else if (mnchs-dep[x]+mxdep-dep[x] <= tmpans)// 当前点的mxdep被其他子树控制了，不用选，直接返回
{ /*cerr << x << "[3]" << '\n'; Dl; Dl;*/ return (RTN){mnchs-tmpans-1, mnchs}; }
else // 最最最普通的链
{ /*cerr << x << "[4]" << '\n'; Dl; Dl;*/ return (RTN){mxdep, mnchs}; }
/*if (mxdep == -1145141919)// 啥都没干，是个叶子
{ cerr << x << "返回了[1]" << dep[x] << '\n'; return dep[x]; }
if (mxdep-dep[x] >= tmpans)// 此处应当有chs
{ cerr << x << "返回了[2]" << dep[x]-tmpans-1 << '\n'; chs[x] = true; return dep[x]-tmpans-1; }
else // 不够格(
{ cerr << x << "返回了[3] " << mxdep << '\n'; return mxdep; }*/
}
inline char check(int mid){// 那应当是check写挂了
memset(chs, false, sizeof(chs)); chscnt = 0;
#ifdef Debug
cerr << "~~~~~~~~~~~~~mid: " << mid << '\n';
#endif
tmpans = mid;
U_L_S = dfs(1, 0);
for (re i = 1 ; i <= n ; ++ i)
if (chs[i] == true)
chscnt ++;
#ifdef Debug
cerr << "chscnt: " << chscnt << '\n';
cerr << "选了：";
for (re i = 1 ; i <= n ; ++ i)
if (chs[i] == true)
cerr << i << _;
Dl;
#endif
if (chscnt <= K)
return true;
else
return false;
}
inline void work(){
cin >> n >> K;
for (re i = 1, uu, vv ; i <= n-1 ; ++ i)
{ cin >> uu >> vv; star_add(uu, vv), star_add(vv, uu); }
dep[1] = 1;
getdep(1, 0);
/*for (re i = 1 ; i <= n ; ++ i)
if (check(i) == true)
{final_ans = i; break;}*/
#ifdef Debug
Dl; Dl; Dl;
#endif
int l, r, mid;
l = 1, r = n;
while (l <= r){
mid = (l+r) >> 1;
if (check(mid) == true)// 时限可以更小
final_ans = mid, r = mid-1;
else
l = mid+1;
#ifdef Debug
Dl; Dl; Dl;
#endif
}
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T4}\ 序列\)
没改(
标签：10,17,16,19,text,long,HZOI,tmpans,define From： https://www.cnblogs.com/charphi/p/16796932.html