USACO 2018 Open Solution更好的阅读体验戳此进入题面 Luogu 链接LG-P4379 [USACO18OPEN]Lemonade Line S题面ExamplesSolutionCodeLG-P4380 [USACO18OPEN]Multiplayer Moo S题面ExamplesSolutionCodeLG-P4376 [USACO18OPEN]Milking Order G题面ExamplesSolutionCodeLG-P4377 [USACO18OPEN] Talent Show G题面ExamplesSolutionCodeLG-P4378 [USACO18OPEN]Out of Sorts S题面ExamplesSolutionCodeLG-P4375 [USACO18OPEN]Out of Sorts G题面ExamplesSolutionCodeLG-P4372 [USACO18OPEN]Out of Sorts P题面ExamplesSolutionCodeLG-P4374 [USACO18OPEN]Disruption P题面ExamplesSolutionCodeLG-P4373 [USACO18OPEN]Train Tracking P题面ExamplesSolutionCodeUPD
娱乐题,读完题你们肯定也都秒了。。
有
Input_1
xxxxxxxxxx
215
27 1 400 2 2
Output_1
xxxxxxxxxx
113
没啥可说的,无脑贪心,排个序即可。。
xxxxxxxxxx
541
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
26int N;
27vector < int > cow;
28int ans(0);
29
30int main(){
31 N = read();
32 for(int i = 1; i <= N; ++i)cow.emplace_back(read());
33 sort(cow.begin(), cow.end(), greater < int >());
34 for(auto it = cow.begin(); it != cow.end(); ++it)if(*it >= ans)++ans; else break;
35 printf("%d\n", ans);
36 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
37 return 0;
38}
39
40template < typename T >
41inline T read(void){
42 T ret(0);
43 short flag(1);
44 char c = getchar();
45 while(c != '-' && !isdigit(c))c = getchar();
46 if(c == '-')flag = -1, c = getchar();
47 while(isdigit(c)){
48 ret *= 10;
49 ret += int(c - '0');
50 c = getchar();
51 }
52 ret *= flag;
53 return ret;
54}
存在一个
Input_1
xxxxxxxxxx
514
22 3 9 3
34 9 9 1
49 9 1 7
52 1 1 9
Output_1
xxxxxxxxxx
215
210
第一眼我就感觉这玩意和一个特别远古的经典题《宽搜 海战》特别像,那道题大概就是描述一个
然后对于第二问,我们可以考虑把每块缩一下,然后相邻的不同块建边,在这里枚举所有块,再枚举其相连的块,然后跑一个类似宽搜的东西,无脑枚举还有哪些块是连通的,每次算完取 set
或 unorderer_set
加手写哈希实现,然后发现这玩意会 rand
取点并判重,可以让出解率极高。
当然上面都是我口糊的,正解似乎可以通过 map
判重之类的实现,反正也算是暴力枚举加剪枝过的。。
xxxxxxxxxx
1561
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
28int N;
29int mp[300][300];
30int belong[300][300];
31// bitset < 90000 > exist[90000];
32
33struct HashPair{
34 size_t operator() (const pair < int, int > &x)const{
35 // auto hash1 = hash < int >{}(x.first);
36 // auto hash2 = hash < int >{}(x.second);
37 // return hash1 ^ hash2;
38 return (ll)x.first * x.second % (1000000007);
39 }
40};
41
42unordered_set < pair < int, int >, HashPair > exist;
43int mx1(-1), mx2(-1);
44int cnt(0);
45pair < int, int > blk[110000];
46bitset < 90000 > vis[1];
47int ver(0);
48
49int dx[10] = {0, -1, 0, 1, 0};
50int dy[10] = {0, 0, 1, 0, -1};
51
52struct Edge{
53 Edge* nxt;
54 int to;
55 OPNEW;
56}ed[910000];
57ROPNEW(ed);
58Edge* head[210000];
59
60void bfs(int idx, int val, int px, int py){
61 queue < pair < int, int > > cur;
62 cur.push({px, py});
63 belong[px][py] = idx;
64 ++blk[idx].second;
65 while(!cur.empty()){
66 auto tp = cur.front(); cur.pop();
67 for(int i = 1; i <= 4; ++i){
68 int tx = tp.first + dx[i], ty = tp.second + dy[i];
69 if(!IN_RANGE(tx, ty))continue;
70 if(mp[tx][ty] == val && !belong[tx][ty])++blk[idx].second, belong[tx][ty] = idx, cur.push({tx, ty});
71 }
72 }
73}
74
75int main(){
76 N = read();
77 for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)mp[i][j] = read();
78 for(int i = 1; i <= N; ++i)
79 for(int j = 1; j <= N; ++j)
80 if(!belong[i][j]){
81 blk[++cnt].first = mp[i][j];
82 bfs(cnt, mp[i][j], i, j);
83 }
84 for(int i = 1; i <= N; ++i)
85 for(int j = 1; j <= N; ++j)
86 for(int k = 1; k <= 4; ++k){
87 int tx = i + dx[k], ty = j + dy[k];
88 if(IN_RANGE(tx, ty) && belong[tx][ty] != belong[i][j]){
89 int t = belong[tx][ty], s = belong[i][j];
90 if(exist.find(make_pair(s, t)) == exist.end()){
91 exist.insert({s, t});
92 head[s] = new Edge{head[s], t};
93 head[t] = new Edge{head[t], s};
94 }
95 }
96 }
97 // for(int i = 1; i <= cnt; ++i)printf("blk[%d] = %d\n", i, blk[i].second);
98 for(int i = 1; i <= cnt; ++i)mx1 = max(mx1, blk[i].second);
99 // printf("Belong:\n");
100 // for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)printf("%d%c", belong[i][j], j == N ? '\n' : ' ');
101 // for(int p = 1; p <= cnt; ++p){
102 // printf("Father: %d: ", p);
103 // for(auto i = head[p]; i; i = i->nxt){
104 // printf("%d ", SON);
105 // }printf("\n");
106 // }
107 queue < int > tmp;
108 queue < int > undel;
109 for(int p = 1; p <= cnt; ++p)
110 for(auto t = head[p]; t; t = t->nxt){
111 if((double)clock() / CLOCKS_PER_SEC > 0.9)printf("%d\n%d\n", mx1, mx2), exit(0);
112 while(!undel.empty()){
113 int tp = undel.front(); undel.pop();
114 vis[ver][tp] = false;
115 }
116 int ans(0);
117 // ++ver;
118 // vis[ver].reset();
119 vis[ver][p] = vis[ver][t->to] = true;
120 undel.push(p), undel.push(t->to);
121 tmp.push(p), tmp.push(t->to);
122 ans += blk[p].second, ans += blk[t->to].second;
123 while(!tmp.empty()){
124 int tp = tmp.front(); tmp.pop();
125 for(auto i = head[tp]; i; i = i->nxt){
126 if(vis[ver][SON])continue;
127 if(blk[SON].first == blk[p].first || blk[SON].first == blk[t->to].first){
128 vis[ver][SON] = true;
129 undel.push(SON);
130 tmp.push(SON);
131 ans += blk[SON].second;
132 }
133 }
134 }
135 mx2 = max(mx2, ans);
136 }
137 printf("%d\n%d\n", mx1, mx2);
138 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
139 return 0;
140}
141
142template < typename T >
143inline T read(void){
144 T ret(0);
145 short flag(1);
146 char c = getchar();
147 while(c != '-' && !isdigit(c))c = getchar();
148 if(c == '-')flag = -1, c = getchar();
149 while(isdigit(c)){
150 ret *= 10;
151 ret += int(c - '0');
152 c = getchar();
153 }
154 ret *= flag;
155 return ret;
156}
存在
Input_1
xxxxxxxxxx
414 3
23 1 2 3
32 4 2
43 3 4 1
Output_1
xxxxxxxxxx
111 4 2 3
首先这个题意二分答案应该很显然吧?二分
xxxxxxxxxx
1001
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
26int N, M;
27
28struct Edge{
29 Edge* nxt;
30 int to;
31 OPNEW;
32}ed[210000];
33static Edge* P = ed;
34Edge* head[110000];
35void* Edge::operator new(size_t){return P++;}
36void Clear(void){
37 P = ed;
38 memset(head, 0, sizeof(Edge*) * (N + 10));
39}
40
41int ind[110000];
42vector < int > rnk[51000];
43vector < int > ans;
44vector < int > tmp;
45
46bool Check(int lim){
47 memset(ind, 0, sizeof(int) * (N + 10));
48 Clear();
49 tmp.clear();
50 for(int i = 1; i <= lim; ++i){
51 auto lst = rnk[i].begin();
52 for(auto it = next(rnk[i].begin()); it != rnk[i].end(); ++it)
53 ++ind[*it], head[*lst] = new Edge{head[*lst], *it}, lst = it;
54 }
55 std::priority_queue < int, vector < int >, greater < int > > cur;
56 for(int i = 1; i <= N; ++i)if(!ind[i])cur.push(i);
57 while(!cur.empty()){
58 int tp = cur.top(); cur.pop();
59 tmp.emplace_back(tp);
60 for(auto i = head[tp]; i; i = i->nxt){
61 --ind[SON];
62 if(!ind[SON])cur.push(SON);
63 }
64 }
65 return (int)tmp.size() == N;
66}
67
68int main(){
69 N = read(), M = read();
70 for(int i = 1; i <= M; ++i){
71 int m = read();
72 while(m--)rnk[i].emplace_back(read());
73 }
74 int l = 1, r = M;
75 while(l <= r){
76 int mid = (l + r) >> 1;
77 if(Check(mid))ans.swap(tmp), l = mid + 1;
78 else r = mid - 1;
79 }
80 for(auto i : ans)printf("%d ", i);
81 printf("\n");
82 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
83 return 0;
84}
85
86template < typename T >
87inline T read(void){
88 T ret(0);
89 short flag(1);
90 char c = getchar();
91 while(c != '-' && !isdigit(c))c = getchar();
92 if(c == '-')flag = -1, c = getchar();
93 while(isdigit(c)){
94 ret *= 10;
95 ret += int(c - '0');
96 c = getchar();
97 }
98 ret *= flag;
99 return ret;
100}
给定
Input_1
xxxxxxxxxx
413 15
220 21
310 11
430 31
Output_1
xxxxxxxxxx
111066
完全可以算是 01分数规划 的板子了,然后再套个 01背包即可。具体地,通过 01分数规划,转化一下有
xxxxxxxxxx
711
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
28int N, W;
29int wei[300], val[300];
30double c[300];
31double dp[1100];
32
33bool Check(double lim){
34 for(int i = 1; i <= 1010; ++i)dp[i] = -114514.0;
35 for(int i = 1; i <= N; ++i)c[i] = (double)val[i] - lim * (double)wei[i];
36 for(int i = 1; i <= N; ++i)for(int j = W; j >= 0; --j)
37 j + wei[i] >= W
38 ? dp[W] = max(dp[W], dp[j] + c[i])
39 : dp[j + wei[i]] = max(dp[j + wei[i]], dp[j] + c[i]);
40 return dp[W] >= 0.0;
41}
42
43int main(){
44 N = read(), W = read();
45 double l(0.0), r(0.0);
46 for(int i = 1; i <= N; ++i)wei[i] = read(), val[i] = read(), r += (double)val[i];
47 int ans;
48 while(l + EPS <= r){
49 double mid = (l + r) / 2.0;
50 if(Check(mid))ans = (int)floor(mid * 1000.0), l = mid;
51 else r = mid;
52 }printf("%d\n", ans);
53 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54 return 0;
55}
56
57template < typename T >
58inline T read(void){
59 T ret(0);
60 int flag(1);
61 char c = getchar();
62 while(c != '-' && !isdigit(c))c = getchar();
63 if(c == '-')flag = -1, c = getchar();
64 while(isdigit(c)){
65 ret *= 10;
66 ret += int(c - '0');
67 c = getchar();
68 }
69 ret *= flag;
70 return ret;
71}
给定你冒泡排序的 “奶牛码” 实现,特别地,定义语句 moo
为输出 moo
,对于给定的序列求该 “奶牛码” 会输出几次 moo
。
xxxxxxxxxx
81sorted = false
2while (not sorted):
3 sorted = true
4 moo
5 for i = 0 to N-2:
6 if A[i+1] < A[i]:
7 swap A[i], A[i+1]
8 sorted = false
Input_1
xxxxxxxxxx
615
21
35
43
58
62
Output_1
xxxxxxxxxx
114
离散化,树状数组求逆序对个数,没了。确实没了,分没了。。。
放学前五分钟糊了一个 BIT + 离散化然后交上去直接 WA,回来扫了一眼题目才发现我是**。
观察发现这玩意不是在每次交换的时候 moo
,而是每一趟尝试交换的时候叫一下。那么这东西就需要考虑一下冒泡排序的本质了,发现冒泡排序每次都是扫一遍给所有数的逆序对减少一个,这个应该比较好理解吧,每扫一遍的过程可以认为是把某些数往后移动一段,每次移动都会把这个数对跨过的这段数的
xxxxxxxxxx
661
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
26int N;
27int a[110000];
28vector < int > data;
29
30class BIT{
31private:
32 int tr[110000];
33public:
34 int lowbit(int x){return x & -x;}
35 void Modify(int x, int v = 1){while(x <= N)tr[x] += v, x += lowbit(x);}
36 int Query(int x){int ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
37}bit;
38
39int main(){
40 N = read();
41 for(int i = 1; i <= N; ++i)a[i] = read(), data.emplace_back(a[i]);
42 sort(data.begin(), data.end());
43 data.erase(unique(data.begin(), data.end()), data.end());
44 for(int i = 1; i <= N; ++i)a[i] = (int)data.size() - distance(data.begin(), lower_bound(data.begin(), data.end(), a[i]) + 1) + 1;
45 int ans(0);
46 for(int i = 1; i <= N; ++i)ans = max(ans, bit.Query(a[i] - 1)), bit.Modify(a[i]);
47 printf("%d\n", ans + 1);
48 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49 return 0;
50}
51
52template < typename T >
53inline T read(void){
54 T ret(0);
55 int flag(1);
56 char c = getchar();
57 while(c != '-' && !isdigit(c))c = getchar();
58 if(c == '-')flag = -1, c = getchar();
59 while(isdigit(c)){
60 ret *= 10;
61 ret += int(c - '0');
62 c = getchar();
63 }
64 ret *= flag;
65 return ret;
66}
与上题题意及范围不变,奶牛码变成如下:
xxxxxxxxxx
131sorted = false
2while (not sorted):
3 sorted = true
4 moo
5 for i = 0 to N-2:
6 if A[i+1] < A[i]:
7 swap A[i], A[i+1]
8 for i = N-2 downto 0:
9 if A[i+1] < A[i]:
10 swap A[i], A[i+1]
11 for i = 0 to N-2:
12 if A[i+1] < A[i]:
13 sorted = false
Input_1
xxxxxxxxxx
615
21
38
45
53
62
Output_1
xxxxxxxxxx
112
可以尝试不用 BIT。。可以用 Treap,可以用 LCT。。
考虑和上一题有何不同,上一题是每个数之前的数对其贡献的逆序对取
xxxxxxxxxx
661
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
26int N;
27pair < int, int > a[110000];
28
29class BIT{
30private:
31 int tr[110000];
32public:
33 int lowbit(int x){return x & -x;}
34 void Modify(int x, int v = 1){while(x <= N)tr[x] += v, x += lowbit(x);}
35 int Query(int x){int ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
36}bit;
37
38int main(){
39 N = read();
40 int ans(1);
41 for(int i = 1; i <= N; ++i)a[i] = {read(), i};
42 sort(a + 1, a + N + 1);
43 for(int i = 1; i <= N; ++i)
44 bit.Modify(a[i].second),
45 ans = max(ans, i - bit.Query(i));
46 printf("%d\n", ans);
47
48 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49 return 0;
50}
51
52template < typename T >
53inline T read(void){
54 T ret(0);
55 int flag(1);
56 char c = getchar();
57 while(c != '-' && !isdigit(c))c = getchar();
58 if(c == '-')flag = -1, c = getchar();
59 while(isdigit(c)){
60 ret *= 10;
61 ret += int(c - '0');
62 c = getchar();
63 }
64 ret *= flag;
65 return ret;
66}
存在一个奇怪的快速排序,大致过程是每次通过冒泡排序找到分割点,定义分割点为其左侧的数均小于它,右侧均大于它。找到分割点之后将原序列分割并递归处理被分出来的序列。求最终 work_counter
的值。
主程序奶牛码为:
xxxxxxxxxx
81quickish_sort (A) {
2 if length(A) = 1, return
3 do { // Main loop
4 work_counter = work_counter + length(A)
5 bubble_sort_pass(A)
6 } while (no partition points exist in A)
7 divide A at all partition points; recursively quickish_sort each piece
8}
对于冒泡排序为:
xxxxxxxxxx
41bubble_sort_pass (A) {
2 for i = 0 to length(A)-2
3 if A[i] > A[i+1], swap A[i] and A[i+1]
4}
Input_1
xxxxxxxxxx
817
220
32
43
54
69
78
87
Output_1
xxxxxxxxxx
1112
不难发现题意就是要我们求每次冒泡排序的长度求和,然后发现这东西也不太好求,于是再次转化为求每个数进行了多少次冒泡排序,次数求和显然也是原来的值。不难想到,对于一个数,其不会再被进行冒泡排序当且仅当其左右两个数均为分割点,所以我们的问题就再次转化为求每个点在几次冒泡排序后才会变成分割点,令其为
考虑维护这玩意,不难想到,每次冒泡排序都会把这个数相对所有其后面的小于它的数的距离减
对于具体的维护方式用单调队列或者双指针之类的东西弄一下即可,注意需要离散化,且这个离散化和掉进兔子洞那题差不多,对于相同的值离散化之后的值应该是不同的,这样我们直接倒序遍历,然后维护一个指针,指向第一个满足
xxxxxxxxxx
621
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
26int N;
27int a[110000];
28vector < int > data;
29int tim[110000];
30int cnt[110000];
31
32int main(){
33 N = read();
34 for(int i = 1; i <= N; ++i)data.emplace_back(a[i] = read());
35 sort(data.begin(), data.end()); //data.erase(unique(data.begin(), data.end()), data.end());
36 for(int i = 1; i <= N; ++i)a[i] = distance(data.begin(), lower_bound(data.begin(), data.end(), a[i]) + 1), a[i] += cnt[a[i]]++;
37 int lst(N);
38 for(int i = N; i >= 1; --i){
39 while(a[lst] > i)--lst;
40 tim[i] = max(lst - i, 1);
41 }ll ans(0);
42 for(int i = 1; i <= N; ++i)ans += max(tim[i - 1], tim[i]);
43 printf("%lld\n", ans);
44 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45 return 0;
46}
47
48template < typename T >
49inline T read(void){
50 T ret(0);
51 int flag(1);
52 char c = getchar();
53 while(c != '-' && !isdigit(c))c = getchar();
54 if(c == '-')flag = -1, c = getchar();
55 while(isdigit(c)){
56 ret *= 10;
57 ret += int(c - '0');
58 c = getchar();
59 }
60 ret *= flag;
61 return ret;
62}
给定一棵
Input_1
xxxxxxxxxx
916 3
21 2
31 3
44 1
54 5
66 5
72 3 7
83 6 8
96 4 5
Output_1
xxxxxxxxxx
517
27
38
45
55
依然在题解里先偷个图。。
显然考虑对于我们每一条连的额外边,如
然后我们发现,如果把额外边降序排序,显然后面的边更优,那么每次操作实际上就是覆盖原来的值,那么这东西很显然就是个 assign
,而且只有 assign
没有任何其它操作,所以可以考虑直接上个 树剖 + ODT 即可,理论上对于只有 assign
的操作 ODT 应该更快,但是可能常数太大了,所以最终表现似乎不如线段树?
然后在此之上,我们又可以想到一个做法,把额外边升序排列,这样前面的一定更优,打个标记,对于已经更新过的不去更新即可,然后用倍增或者 Tarjan 直接的求 LCA 找树上路径之类的,可以省掉一个树剖。
xxxxxxxxxx
1531
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
26struct Edge{
27 Edge* nxt;
28 int to;
29 int idx;
30 OPNEW;
31}ed[110000];
32ROPNEW(ed);
33Edge* head[51000];
34
35int ans[51000], nod_idx[51000];
36
37int N, M;
38int dep[51000], dfn[51000], idx[51000], top[51000], siz[51000], fa[51000], hson[51000];
39
40struct Node{
41 int l, r;
42 mutable int val;
43 friend const bool operator < (const Node &a, const Node &b){
44 return a.l < b.l;
45 }
46};
47
48class ODT{
49private:
50 set < Node > tr;
51public:
52 auto Insert(Node x){return tr.insert(x);}
53 auto Split(int p){
54 auto it = tr.lower_bound(Node{p});
55 if(it != tr.end() && it->l == p)return it;
56 --it;
57 // printf("%d %d %d\n", it->l, it->r, it->val);
58 int l = it->l, r = it->r, v = it->val;
59 tr.erase(it), Insert(Node{l, p - 1, v});
60 return Insert(Node{p, r, v}).first;
61 }
62 void Assign(int l, int r, int v){
63 if(l > r)return;
64 // printf("assigning %d~%d, %d\n", l, r, v);
65 auto itR = Split(r + 1), itL = Split(l);
66 tr.erase(itL, itR);
67 Insert(Node{l, r, v});
68 }
69 void SetAns(void){
70 for(auto nod : tr)
71 for(int i = nod.l; i <= nod.r; ++i)
72 ans[nod_idx[idx[i]]] = nod.val;
73 }
74}odt;
75
76struct Edges{
77 int s, t;
78 int val;
79 friend const bool operator < (const Edges &a, const Edges &b){
80 return a.val > b.val;
81 }
82};
83vector < Edges > es;
84
85void dfs_pre(int p = 1, int ffa = 0){
86 fa[p] = ffa;
87 dep[p] = dep[ffa] + 1;
88 siz[p] = 1;
89 for(auto i = head[p]; i; i = i->nxt){
90 if(SON == ffa)continue;
91 nod_idx[SON] = i->idx;
92 dfs_pre(SON, p);
93 siz[p] += siz[SON];
94 if(siz[SON] > siz[hson[p]])hson[p] = SON;
95 }
96}
97void dfs(int p = 1, int tp = 1){
98 static int cdfn(0);
99 top[p] = tp;
100 dfn[p] = ++cdfn;
101 idx[cdfn] = p;
102 if(hson[p])dfs(hson[p], tp);
103 for(auto i = head[p]; i; i = i->nxt){
104 if(SON == fa[p] || SON == hson[p])continue;
105 dfs(SON, SON);
106 }
107}
108
109void AssignRange(int s, int t, int val){
110 while(top[s] != top[t]){
111 if(dep[top[s]] < dep[top[t]])swap(s, t);
112 odt.Assign(dfn[top[s]], dfn[s], val);
113 s = fa[top[s]];
114 }if(dep[s] < dep[t])swap(s, t);
115 odt.Assign(dfn[t] + 1, dfn[s], val);
116}
117
118int main(){
119 N = read(), M = read();
120 for(int i = 1; i <= N - 1; ++i){
121 int s = read(), t = read();
122 head[s] = new Edge{head[s], t, i};
123 head[t] = new Edge{head[t], s, i};
124 }dfs_pre(), dfs();
125 // for(int i = 1; i <= N; ++i)printf("[%d]: dfn: %d, fa: %d, dep: %d, top: %d, hson: %d\n", i, dfn[i], fa[i], dep[i], top[i], hson[i]);
126 // for(int i = 1; i <= N; ++i)printf("nodidx[%d]: %d\n", i, nod_idx[i]);
127 odt.Insert(Node{1, N, -1});
128 for(int i = 1; i <= M; ++i){
129 int s = read(), t = read(), v = read();
130 es.emplace_back(Edges{s, t, v});
131 }sort(es.begin(), es.end());
132 for(auto e : es)AssignRange(e.s, e.t, e.val);
133 odt.SetAns();
134 for(int i = 1; i <= N - 1; ++i)printf("%d\n", ans[i]);
135 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
136 return 0;
137}
138
139template < typename T >
140inline T read(void){
141 T ret(0);
142 int flag(1);
143 char c = getchar();
144 while(c != '-' && !isdigit(c))c = getchar();
145 if(c == '-')flag = -1, c = getchar();
146 while(isdigit(c)){
147 ret *= 10;
148 ret += int(c - '0');
149 c = getchar();
150 }
151 ret *= flag;
152 return ret;
153}
给定长度为 int
类型静态数组,且存取次数和不能超过 helpBessie()
中对于局部变量无空间限制,且你可以获取
题目通过交互实现,具体地,对于序列中每个值都会调用一次 helpBessie()
,你需要实现该函数,函数中对于局部非静态变量空间无限制(或者说 256MiB
),在函数中你可以通过调用交互库来获取本次的基本信息和存取数,即禁止使用静态变量或全局变量。对于具体的实现方式请参考 原题面。
Input_1
xxxxxxxxxx
2110 3
25 7 9 2 0 1 7 4 3 6
Output_1
xxxxxxxxxx
815
22
30
40
50
61
73
83
Tips:输入输出不代表交互过程。
显然如果没有空间的限制的话我们直接写个滑动窗口,或者说单调队列即可很简单的求解。但是发现这个单调队列的空间是
因为我们一共可以获取两次序列的值,所以可以考虑先将序列分成
然后先跳了,没啥好题解,仅有的两个中文题解没能太明白,代码也没看懂,如果 NOIP 没退役的话就回来补这题。。
Tips:对于交互题的调试,我们实际上可以将交互库中的函数手动模拟实现,然后写个主函数调用对应的函数 “模拟” 一遍交互的过程,然后对比结果。如 void set(int index, int value){a[index] = val;}
。
xxxxxxxxxx
11//TODO
update-2022_11_15 初稿