\(Write\ In\ Front\)
“没啥事就写博客呗”
\(Rank36/43\) 得分\(0 + 15 + 0 + 5 = 20pts\)
我草了
开局直接冲\(T1\)，想了个差不多的贪心就开始莽，莽了一会发现假了，然后又把错误情况给整了一下但是贪心似乎还是假的，不过我并没有意识到，花了两个半小时后成功过了样例\(1、2、3\)，于是收获了\(0pts\)
谢谢\(eafoo\)
\(\mathfrak{T1}\ score\ and\ rank\)
\(eafoo\)造数据把假贪心卡成了\(0pts\)，本来是有挺多分的?
等等，刚才向\(wudi\)询问了一下，我赛时的贪心是正确的，不过代码实现有点【】
我超！！！
这个题挺简单的，可以说是签到题，但前提是你不像我一样代码实现出问题
考虑一个朴素的思路
找到一个正数，然后从他尝试向左向右拓展为更大的值，然后对应地删掉最大值的点
假贪心：从1~n扫一遍，遇到负数就把\(set\)里最大值扔掉，扔到为\(0\)为止，如果扔成\(0\)了就另起继续扫（好像是吧
考虑这样一个序列
\[ 1\ \ 2\ \ 3\ \ -114\ \ 51\ \ 4 \]手模一下显然\(fake\)了\(:51\)和\(4\)没算
真贪心捏？
从\(1\)到\(n\)扫，碰到负数时就尝试抵消掉它，如果能够成功抵消那么就接着搜，如果不能就\(sum\)清零，重新在一个新的不是负数的地方开始搜
也就是处理一下负数就\(\text{ok}\)了
T1
#include <iostream>
#include <set>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 1000005
#define ll __int128
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
看来我赛时想对了一半
也不枉我花两个半小时做这题
总之和题解的差别呢就在于我们有考虑加入负数的情况
哎，真的几乎一样，但只是几乎
*/
inline ll read(){
ll x = 0; char c, fl(false);
while (!isdigit(c = getchar()))
if (c == '-')
{fl = true, c = getchar(); break;}
do{x = (x << 3) + (x << 1) + (c & 15);}while(isdigit(c = getchar()));
return ((fl == true) ? (-x) : (x));
}
void ot(ll x){
if (x < 0) x = -x, putchar('-');
if (x > 9) ot(x/10);
putchar((x%10)+48);
}
ll n, S, final_ans, sum;
ll a[N];
multiset<ll> s;
void work(){
n = read(), S = read();
for (re i = 1 ; i <= n ; ++ i)
a[i] = read();
if (S < 0){
for (re i = 1 ; i <= n ; ++ i)
a[i] -= (S+1);
S = 1;
}
for (re i = 1 ; i <= n ; ++ i){
if (a[i] > 0){
sum += a[i];
s.insert(a[i]);
if (sum >= S){
sum -= *prev(s.end()), s.erase(prev(s.end()));
final_ans ++;
}
}
else {
if (s.empty() == true)
continue;
ll res(0);
while (res < -a[i] and s.empty() == false)
sum -= *s.begin(), res += *s.begin(), s.erase(s.begin());
if (res+a[i] > 0)
s.insert(res+a[i]), sum += res+a[i];
}
}
ot(final_ans), putchar('\n');
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(score);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T2}\ HZOI大作战\)
注意到一个性质
假设当前在节点\(x\)，往上的第一个权值比\(x\)大的点为\(y\)，那么从\(x\)到\(y\)之间不需要更换板子
你这不显然吗...
确实显然，但这是一个很有用的性质。这样想：
如果我们把\(x\)和\(y\)直接用\(fa\)数组存下来，然后把\(y\)和\(z\)(往上比\(y\)大的第一个)也是如此存下来...
那么我们查询的时候就可以直接按照\(fa\)数组跳并且查询答案了，而不是一个一个的慢慢跳和判断
既然都这么存了，何不倍增一下呢？
所以直接倍增一下，注意维护就好了
还有需要注意的事情，注意一下\(u\)可能本来就比较大，要先找到第一个比\(u\)大的，然后再继续跳。这个时候可能\(u\)已经跳得比\(v\)高了，也就是说明u~v的路径上都比\(u\)小，那么答案就是\(0\)。
答案并不是\(0\)时正常跳的时候可能\(u\)想要跳得比\(v\)高，这时候用刚开始遍历的时候的dep[]判断一下即可。
具体实现可以看代码。
T2
#include <iostream>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 500005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
wudi锯
似乎是听明白了
我尝试代码实现
倍增跳，然后连边
然后更新倍增
询问的时候就是u往上跳，final_ans累加
注意因为倍增跳连边，在询问答案的时候可能会跳过了v也就是比v高了，用dep判断一下就行了
*/
int n, Q, star_cnt;
int val[N], head[N], dep[N], fath[N], pa[N];
int fa[N][25];
struct star{int v, nxt;}e[N<<1];
inline void star_add(int u, int v){e[++ star_cnt].v=v, e[star_cnt].nxt=head[u], head[u]=star_cnt;}
void dfs(int x, int faer){
if (val[x] < val[fath[x]])
fa[x][0] = fath[x];
else {
int F = fath[x];
for (re i = pa[F] ; i >= 0 ; -- i)// 漂亮的二进制拆分
if (fa[F][i] != 0 and val[fa[F][i]] <= val[x])// 找大于他的
F = fa[F][i];
fa[x][0] = fa[F][0];
}
int k(0);
for (; fa[x][k] != 0 ; ++ k)
fa[x][k+1] = fa[fa[x][k]][k];
pa[x] = k-1;
for (re i = head[x] ; i ; i = e[i].nxt){
int v = e[i].v;
if (v == faer)
continue;
dep[v] = dep[x]+1; fath[v] = x;
dfs(v, x);
}
}
// windows: fc
// linux: diff
inline int ask(int u, int v, int w){
// cerr << u << _ << v << _ << w << '\n';
if (w >= val[u]){// 先跳
for (re i = pa[u] ; i >= 0 ; -- i)
if (fa[u][i] != 0 and val[fa[u][i]] <= w)// 找大于他的
u = fa[u][i];
u = fa[u][0];
}
// cerr << u << _ << res << '\n';
if (dep[u] < dep[v])// 跳过了，说明u~v之间都比w小
return 0;
int res(1);
for (re i = pa[u] ; i >= 0 ; -- i)
if (fa[u][i] != 0 and dep[fa[u][i]] >= dep[v])
u = fa[u][i], res += (1 << i);
// cerr << u << _ << res << '\n';
return res;
}
void work(){
cin >> n >> Q;
for (re i = 1 ; i <= n ; ++ i)
cin >> val[i];
for (re i = 1, uu, vv ; i <= n-1 ; ++ i)
{cin >> uu >> vv; star_add(uu, vv), star_add(vv, uu);}
dep[0] = -1; fa[1][0] = 1;
dfs(1, 0);
int uu, vv, ww;
/*cout << "dep: ";
for (re i = 1 ; i <= n ; ++ i)
cout << dep[i] << _;
cout << '\n';
for (re i = 1 ; i <= n ; ++ i){
cout << i << ": ";
for (re j = 0 ; j <= pa[i] ; ++ j)
cout << fa[i][j] << _;
cout << '\n';
}*/
while (Q --){
cin >> uu >> vv >> ww;
// cerr << "ans: ";
cout << ask(uu, vv, ww) << '\n';
// cerr << '\n' << '\n';
}
}
#define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(accepted);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T3}\ Delov的旅行\)
不会
\(\mathfrak{T4}\ gtm和joke的星球\)
斯坦纳树板子
嘉晚饭是真的
标签：11,ll,int,res,sum,fa,HZOI,CSP,define From： https://www.cnblogs.com/charphi/p/16700877.html