(一场难度稍微低 1丶丶的模拟赛,不过我太弱了,依然没多少分。。。)
给定
想到了几个贪心,如按照节点对其它节点的贡献,或节点本身被贡献的去排序,亦或做差考虑最终的贡献排序,想了好多人类智慧,然后都假掉了。。。
至于为什么假了也能想到,这样的排序实际是一个动态的过程,是不能根据最开始的状态无脑排序的,然而动态的这玩意似乎难以维护,如果每次删除并插入难以实现,每次重排的话大概是
xxxxxxxxxx
861
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17// using namespace __gnu_pbds;
18
19mt19937 rnd(random_device{}());
20int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21bool rnddd(int x){return rndd(1, 100) <= x;}
22
23typedef unsigned int uint;
24typedef unsigned long long unll;
25typedef long long ll;
26typedef long double ld;
27
28
29char buf[MAXSIZE],*p1,*p2;
30
31inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-') f=-1;c=gc();}while(isdigit(c)) x=x*10+(c^48),c=gc();return x*f;}
32
33
34
35// struct cmp{
36// bool operator ()(const int &x, const int &y){return ctr[x] - cost[x] > ctr[y] - cost[y];}
37// };
38
39int N, M;
40int val[1100000];
41int idx[1100000];
42ll ctr[1100000];
43ll cost[1100000];
44ll ans(0);
45vector < int > vt[1100000];
46// vector < int > heap;
47bool used[1100000];
48
49
50int main(){
51 freopen("candy.in", "r", stdin);
52 freopen("candy.out", "w", stdout);
53 // freopen("candy1.in", "r", stdin);
54 N = read(), M = read();
55 for(int i = 1; i <= N; ++i)val[i] = read(), idx[i] = i;
56 for(int i = 1; i <= M; ++i){
57 int s = read(), t = read();
58 ctr[s] += val[s], ctr[t] += val[t];
59 cost[s] += val[t], cost[t] += val[s];
60 vt[s].emplace_back(t), vt[t].emplace_back(s);
61 }
62 for(int i = 1; i <= N; ++i)ctr[i] -= cost[i];
63 // sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return ctr[x] == ctr[y] ? cost[x] < cost[y] : ctr[x] > ctr[y];});
64 // sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return cost[x] == cost[y] ? ctr[x] > ctr[y] : cost[x] < cost[y];});
65 sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return ctr[x] > ctr[y];});
66 // for(int i = 1; i <= N; ++i)
67 // heap.emplace(lower_bound(heap.begin(), heap.end(), i, CMP), i);
68 for(int i = 1; i <= N; ++i){
69 // sort(idx + 1, idx + N + 1, );
70 // int p = heap.front();
71 int p = idx[i];
72 used[p] = true;
73 // heap.erase(heap.begin());
74 ans += cost[p];
75 for(auto j : vt[p])
76 if(!used[j])
77 cost[j] -= val[p];
78 // printf("%lld %lld (%d)\n", cost[j], ctr[j], j),
79 // heap.erase(find(heap.begin(), heap.end(), j)),
80 // heap.emplace(lower_bound(heap.begin(), heap.end(), j, CMP), j);
81 }
82 printf("%lld\n", ans);
83 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
84 return 0;
85}
86
原题是 LG-P7152 [USACO20DEC] Bovine Genetics G。
不会
原题是 P7154 [USACO20DEC] Sleeping Cows P。
不会
给定
最开始想口糊一个在树上的动态建点的 ODT,然后发现建不出来。。然后尝试找了半天性质口糊了一个奇怪的做法:对于本题我的想法就是把子树覆盖转换成序列上的操作问题,然后最后想到了把树按照 bfs 序标号,这样的话每一层都会是一个连续的区间,然后我们记录每一个非叶子节点子树所在的下一层的区间,每次修改的时候这样跑一遍。。理论上在随机数据上都能过,但是一条链的话直接退化成比暴力常数还要大的暴力,而且我不知道咋想的区间操作的时候写了个没有 assign
的 ODT,结果基本全寄了,因为这玩意没有区间推平本身就完全用不了 ODT,一直在 Split,反应过来之后想改线段树没改完。。。在随机数据上基本都卡在了 1000ms 左右,刚好寄了。。链上的测试点直接过不了。最后
xxxxxxxxxx
1571
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17// using namespace __gnu_pbds;
18
19mt19937 rnd(random_device{}());
20int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21bool rnddd(int x){return rndd(1, 100) <= x;}
22
23typedef unsigned int uint;
24typedef unsigned long long unll;
25typedef long long ll;
26typedef long double ld;
27
28
29char buf[MAXSIZE],*p1,*p2;
30
31inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-') f=-1;c=gc();}while(isdigit(c)) x=x*10+(c^48),c=gc();return x*f;}
32
33int N, M;
34int idx[310000]; //real => my
35int ridx[310000]; //my => real
36ll ans[310000];
37
38int dsl[310000], dsr[310000];//i-1-depth-subtree-l / r
39
40struct Node{
41 int l, r;
42 mutable ll val;
43 friend const bool operator < (const Node &x, const Node &y){return x.l < y.l;}
44};
45
46class ODT{
47private:
48 set < Node > tr;
49public:
50 auto Insert(Node p){return tr.insert(p);}
51 auto Split(int p){
52 auto it = tr.lower_bound(Node{p});
53 if(it != tr.end() && it->l == p)return it;
54 --it;
55 if(p > it->r)return tr.end();
56 auto l = it->l, r = it->r;
57 auto val = it->val;
58 tr.erase(it);
59 Insert(Node{l, p - 1, val});
60 return Insert(Node{p, r, val}).first;
61 }
62 void Assign(int l, int r, ll val){
63 // printf("assigning %d-%d : %lld\n", l, r, val);
64 auto itR = Split(r + 1), itL = Split(l);
65 for(auto it = itL; it != itR; ++it)it->val += val;
66 }
67 void SetAns(void){
68 for(auto p : tr)for(int i = p.l; i <= p.r; ++i)ans[ridx[i]] = p.val;
69 }
70}odt;
71
72// class SegT{
73// private:
74// #define LS (p << 1)
75// #define RS ((p << 1) + 1)
76// #define SIZ (gr - gl + 1)
77// #define SIZZ(l, r) (r - l + 1)
78// #define MID ((gl + gr) >> 1)
79// ll tr[310000 << 2];
80// ll lt[310000 << 2];
81// public:
82// void Pushdown(int p, int gl, int gr){
83// tr[LS] += lt[p] * SIZZ(gl, MID);
84// tr[RS] += lt[p] * SIZZ(MID + 1, gr);
85// lt[LS] += lt[p], tr[RS] += lt[p];
86// lt[p] = 0;
87// }
88// void Pushup(int p){
89// tr[p] = tr[LS] + tr[RS];
90// }
91// void Modify(int p, int l, int r, ll val, int gl = 1, int gr = N){
92// if(l <= gl && gr <= r)tr[p] += SIZ * val, lt[p] += SIZ
93// }
94// }
95
96struct Edge{
97 Edge* nxt;
98 int to;
99 OPNEW;
100}ed[610000];
101ROPNEW(ed);
102Edge* head[310000];
103
104void bfs(void){
105 int cnt(0);
106 queue < pair < int, int >/*vertex, father*/ > q;
107 q.push({1, 0});
108 while(!q.empty()){
109 auto p = q.front(); q.pop();
110 idx[p.first] = ++cnt;
111 ridx[cnt] = p.first;
112 vector < pair < int, int > > tmp;
113 for(auto i = head[p.first]; i; i = i->nxt)
114 if(SON != p.second)
115 q.push({SON, p.first});
116 // tmp.push_back({SON, p.first});
117 // for(auto i = tmp.rbegin(); i != tmp.rend(); ++i)q.push(*i);
118 if(!dsl[idx[p.second]])dsl[idx[p.second]] = dsr[idx[p.second]] = idx[p.first];
119 else dsr[idx[p.second]] = idx[p.first];
120 // if(!head[p.first]->nxt)dsl[p.first] = dsr[p.first] = cnt;
121 }
122}
123void modify(int dep, int p, ll val){
124 int l(p), r(p); odt.Assign(l, r, val);
125 while(dep--){
126 while(!dsl[l] && l <= r)++l;
127 while(!dsr[r] && l <= r)--r;
128 if(l > r)return;
129 l = dsl[l], r = dsr[r];
130 // if(l > r)return;
131 odt.Assign(l, r, val);
132 }
133}
134
135int main(){
136 freopen("tree.in", "r", stdin);
137 freopen("tree.out", "w", stdout);
138 N = read();
139 odt.Insert(Node{1, N, 0});
140 for(int i = 1; i <= N - 1; ++i){
141 int s = read(), t = read();
142 head[s] = new Edge{head[s], t};
143 head[t] = new Edge{head[t], s};
144 }bfs();
145 // for(int i = 1; i <= N; ++i)swap(dsl[i], dsr[i]);
146 // for(int i = 1; i <= N; ++i)if(dsl[i] > dsr[i])printf("ERROR! at%d\n", i), exit(0);
147 M = read();
148 for(int i = 1; i <= M; ++i){
149 int p = read(), dep = read(), val = read();
150 modify(dep, idx[p], (ll)val);
151 }
152 odt.SetAns();
153 for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
154 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
155 return 0;
156}
157
考虑把删点变成删边,对于删除每条边,显然其贡献为两个端点中的一个的权值,所以遍历每条边答案加上两个端点中的最小值即可。
xxxxxxxxxx
521
2
3
4
5
6
7
8
9
10
11using namespace std;
12using namespace __gnu_pbds;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23template<typename T = int>
24inline T read(void);
25
26ll ans;
27ll v[1100];
28
29int main(){
30 int N = read(), M = read();
31 for(int i = 1; i <= N; ++i)v[i] = read();
32 for(int i = 1; i <= M; ++i)ans += min(v[read()], v[read()]);
33 printf("%lld\n", ans);
34 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35 return 0;
36}
37
38template<typename T>
39inline T read(void){
40 T ret(0);
41 short flag(1);
42 char c = getchar();
43 while(c != '-' && !isdigit(c))c = getchar();
44 if(c == '-')flag = -1, c = getchar();
45 while(isdigit(c)){
46 ret *= 10;
47 ret += int(c - '0');
48 c = getchar();
49 }
50 ret *= flag;
51 return ret;
52}
咕咕咕。
咕咕咕。
考虑把修改离线,记录每个点上的所有修改,然后做一个奇怪的树上差分,搜索的时候考虑把每一个深度记录在当前搜索的子树内对应的差分值,然后每搜到一个点先加上对应的差分值,把它的修改加到答案里,然后在对应的差分的结束的地方减去这个值,当搜完节点所在子树的时候,要搜其它的子树了,这个节点子树的差分桶就不再有效了,所以此时将之前的修改回退一下即可。
xxxxxxxxxx
851
2
3
4
5
6
7
8
9
10
11using namespace std;
12using namespace __gnu_pbds;
13
14mt19937 rnd(random_device{}());
15int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16bool rnddd(int x){return rndd(1, 100) <= x;}
17
18typedef unsigned int uint;
19typedef unsigned long long unll;
20typedef long long ll;
21typedef long double ld;
22
23
24
25template<typename T = int>
26inline T read(void);
27
28struct Edge{
29 Edge* nxt;
30 int to;
31 OPNEW;
32}ed[610000];
33ROPNEW(ed);
34Edge* head[MAXN << 1];
35
36int N, M;
37ll ans[MAXN];
38ll d[MAXN];
39int dep[MAXN];
40vector < pair < int, int > /*depth, value*/ > mdf[MAXN];
41
42void dfs(int p = 1, int fa = 0, ll cur = 0){
43 dep[p] = dep[fa] + 1;
44 cur += d[dep[p]];
45 for(auto m : mdf[p])
46 cur += m.second,
47 (dep[p] + m.first + 1 < MAXN) ? (void)(d[dep[p] + m.first + 1] -= m.second) : void();
48 ans[p] = cur;
49 for(auto i = head[p]; i; i = i->nxt)
50 SON != fa ? dfs(SON, p, cur) : void();
51 for(auto m : mdf[p])
52 if(dep[p] + m.first + 1 < MAXN)d[dep[p] + m.first + 1] += m.second;
53}
54
55int main(){
56 N = read();
57 for(int i = 1; i <= N - 1; ++i){
58 int s = read(), t = read();
59 head[s] = new Edge{head[s], t};
60 head[t] = new Edge{head[t], s};
61 }M = read();
62 for(int i = 1; i <= M; ++i){
63 int vt = read(), dep = read(), val = read();
64 mdf[vt].push_back({dep, val});
65 }dfs();
66 for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
67 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68 return 0;
69}
70
71template<typename T>
72inline T read(void){
73 T ret(0);
74 short flag(1);
75 char c = getchar();
76 while(c != '-' && !isdigit(c))c = getchar();
77 if(c == '-')flag = -1, c = getchar();
78 while(isdigit(c)){
79 ret *= 10;
80 ret += int(c - '0');
81 c = getchar();
82 }
83 ret *= flag;
84 return ret;
85}
update-2022_10_19 初稿