一场 ACM 模拟赛
(这个链接只是为了自己方便找,页面设置权限了,不要尝试访问)
(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
对于
原题 LG-P3503 [POI2010]KLO-Blocks。
赛时没想出来,最后糊了一个乱搞上去,然后乱搞也寄了,直接
一直在考虑维护把大于
xxxxxxxxxx
1741
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17
18mt19937 rnd(random_device{}());
19int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
20bool rnddd(int x){return rndd(1, 100) <= x;}
21
22typedef unsigned int uint;
23typedef unsigned long long unll;
24typedef long long ll;
25typedef long double ld;
26
27
28
29template<typename T = int>
30inline T read(void);
31
32int N, M;
33int cnt;
34int k;
35int base[1100000], a[1100000];
36int ans(0);
37bool finished(false);
38
39vector < int > high;
40
41struct UnionFind{
42 int fal[1100000], far[1100000];
43 int FindL(int x){return fal[x] == x ? x : fal[x] = FindL(fal[x]);}
44 int FindR(int x){return far[x] == x ? x : far[x] = FindR(far[x]);}
45 void UnionL(int f, int s){fal[s] = FindL(f);}
46 void UnionR(int f, int s){far[s] = FindR(f);}
47 void reset(int N, int k){
48 memset(fal, 0, sizeof(fal));
49 memset(far, 0, sizeof(far));
50 for(int i = 1; i <= N; ++i)
51 if(a[i] < k)fal[i] = i;
52 else if(a[i] > k)high.push_back(i), fal[i] = FindL(i - 1);
53 else fal[i] = FindL(i - 1);
54 for(int i = N; i >= 1; --i){
55 if(a[i] < k)far[i] = i;
56 else far[i] = FindR(i + 1);
57 }
58 }
59}uf;
60
61void dfs(int dep = 1){
62 // printf("in dfs, dep = %d\n", dep);
63 if(finished)return;
64 if(!TIME_LIMIT)return finished = true, void();
65 if(dep > (int)high.size()){
66 int len(0);
67 for(int i = 1; i <= N; ++i){
68 if(a[i] >= k)++len;
69 else len = 0;
70 }
71 ans = max(ans, len);
72 return;
73 }
74 int p = high.at(dep - 1);
75 vector < pair < int, int > > editA, editL, editR;
76 if(rnddd(50)){
77 int val = p - k;
78 int cp = uf.FindR(p);
79 while(cp && val > 0){
80 editA.emplace_back(cp, a[cp]);
81 editR.emplace_back(cp, uf.FindR(cp));
82 val -= k - a[cp];
83 a[cp] = k;
84 int tcp = cp;
85 if(val < 0)a[cp] += val;
86 else cp = uf.FindR(cp + 1), uf.UnionR(cp, tcp);
87 }
88 cp = uf.FindL(p);
89 while(cp && val > 0){
90 editA.emplace_back(cp, a[cp]);
91 editL.emplace_back(cp, uf.FindL(cp));
92 val -= k - a[cp];
93 a[cp] = k;
94 int tcp = cp;
95 if(val < 0)a[cp] += val;
96 else cp = uf.FindL(cp - 1), uf.UnionL(cp, tcp);
97 }
98 if(val > 0){
99 ans = N;
100 finished = true;
101 return;
102 }
103 dfs(dep + 1);
104 for(auto i : editA)a[i.first] = i.second;
105 for(auto i : editL)uf.fal[i.first] = i.second;
106 for(auto i : editR)uf.far[i.first] = i.second;
107 }else{
108 int val = p - k;
109 int cp = uf.FindL(p);
110 while(cp && val > 0){
111 editA.emplace_back(cp, a[cp]);
112 editL.emplace_back(cp, uf.FindL(cp));
113 val -= k - a[cp];
114 a[cp] = k;
115 int tcp = cp;
116 if(val < 0)a[cp] += val;
117 else cp = uf.FindL(cp - 1), uf.UnionL(cp, tcp);
118 }
119 cp = uf.FindR(p);
120 while(cp && val > 0){
121 editA.emplace_back(cp, a[cp]);
122 editR.emplace_back(cp, uf.FindR(cp));
123 val -= k - a[cp];
124 a[cp] = k;
125 int tcp = cp;
126 if(val < 0)a[cp] += val;
127 else cp = uf.FindR(cp + 1), uf.UnionR(cp, tcp);
128 }
129 if(val > 0){
130 ans = N;
131 finished = true;
132 return;
133 }
134 dfs(dep + 1);
135 for(auto i : editA)a[i.first] = i.second;
136 for(auto i : editL)uf.fal[i.first] = i.second;
137 for(auto i : editR)uf.far[i.first] = i.second;
138 }
139
140}
141int main(){
142 freopen("TOMO.in", "r", stdin);
143 freopen("TOMO.out", "w", stdout);
144 N = read(), M = read();
145 for(int i = 1; i <= N; ++i)base[i] = read();
146 while(M--){
147 memcpy(a, base, sizeof(base));
148 cnt = ans = finished = 0;
149 high.clear();
150 k = read();
151 uf.reset(N, k);
152 dfs();
153 printf("%d\n", ans);
154 }
155
156 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
157 return 0;
158}
159
160template<typename T>
161inline T read(void){
162 T ret(0);
163 short flag(1);
164 char c = getchar();
165 while(c != '-' && !isdigit(c))c = getchar();
166 if(c == '-')flag = -1, c = getchar();
167 while(isdigit(c)){
168 ret *= 10;
169 ret += int(c - '0');
170 c = getchar();
171 }
172 ret *= flag;
173 return ret;
174}
写了个 DP,假了,爆零,寄。
原题 CF840E In a Trap。
大概就是写了个暴力,然后数据比较奇怪,还多过了几个点。。最后本场唯一的
xxxxxxxxxx
1121
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17
18mt19937 rnd(random_device{}());
19int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
20bool rnddd(int x){return rndd(1, 100) <= x;}
21
22typedef unsigned int uint;
23typedef unsigned long long unll;
24typedef long long ll;
25typedef long double ld;
26
27
28
29template<typename T = int>
30inline T read(void);
31
32struct Edge{
33 Edge* nxt;
34 int to;
35 OPNEW;
36}ed[310000];
37ROPNEW(ed);
38
39Edge* head[150000];
40int N, Q;
41int val[150000];
42int dep[150000];
43int pre[150000];
44void dfs(int p = 1, int fa = 0){
45 dep[p] = dep[fa] + 1;
46 pre[p] = fa;
47 for(auto i = head[p]; i; i = i->nxt)
48 if(SON != fa)dfs(SON, p);
49}
50int Make(int S, int T){
51 int ret(-1);
52 if(dep[S] >= dep[T]){
53 int SS = S;
54 while(T != SS){
55 ret = max(ret, val[SS] ^ abs(dep[SS] - dep[S]));
56 // printf("val: %d xor %d = %d\n", val[S], abs(dep[T] - dep[S]), val[S] ^ abs(dep[T] - dep[S]));
57 SS = pre[SS];
58 }ret = max(ret, val[SS] ^ abs(dep[SS] - dep[S]));
59 }else{
60 while(S != T){
61 ret = max(ret, val[S] ^ abs(dep[T] - dep[S]));
62 // printf("val: %d xor %d = %d\n", val[S], abs(dep[T] - dep[S]), val[S] ^ abs(dep[T] - dep[S]));
63 T = pre[T];
64 }ret = max(ret, val[S] ^ abs(dep[T] - dep[S]));
65 }
66 // int len = abs(dep[S] - dep[T]);
67 // printf("len s = %d, t = %d, is %d\n", S, T, len);
68 // if(dep[s] < dep[t])swap(s, t);
69 // while(S != T){
70 // ret = max(ret, val[S] ^ abs(dep[T] - dep[S]));
71 // printf("val: %d xor %d = %d\n", val[S], abs(dep[T] - dep[S]), val[S] ^ abs(dep[T] - dep[S]));
72 // S = pre[S];
73 // }ret = max(ret, val[S] ^ 0);
74 return ret;
75}
76
77int main(){
78 freopen("CP0A.in", "r", stdin);
79 freopen("CP0A.out", "w", stdout);
80 N = read(), Q = read();
81 for(int i = 1; i <= N; ++i)val[i] = read();
82 for(int i = 1; i <= N - 1; ++i){
83 int s = read(), t = read();
84 head[s] = new Edge{head[s], t};
85 head[t] = new Edge{head[t], s};
86 }dfs();
87 while(Q--){
88 int s = read(), t = read();
89 printf("%d\n", Make(t, s));
90 }
91
92 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
93 return 0;
94}
95
96
97
98template<typename T>
99inline T read(void){
100 T ret(0);
101 short flag(1);
102 char c = getchar();
103 while(c != '-' && !isdigit(c))c = getchar();
104 if(c == '-')flag = -1, c = getchar();
105 while(isdigit(c)){
106 ret *= 10;
107 ret += int(c - '0');
108 c = getchar();
109 }
110 ret *= flag;
111 return ret;
112}
原题 LG-P8386 [PA 2021] Od deski do deski。
不会,寄。
首先问题显然可以转化为,找一段最长的区间,满足区间的平均数大于等于
xxxxxxxxxx
841
2
3
4
5
6
7
8
9
10
11/******************************
12abbr
13
14******************************/
15
16using namespace std;
17using 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
29
30template<typename T = int>
31inline T read(void);
32
33int N, Q;
34int K;
35int s[1100000];
36stack < int > lft;
37int ans(0);
38void Solve(void){
39 ans = 0;
40
41 for(int i = 1; i <= N; ++i){
42 s[i] -= K * i;
43 if(lft.empty() || s[i] < s[lft.top()])lft.push(i);
44 }
45 // for(int i = 1; i <= N; ++i)printf("%d%c", s[i], i == N ? '\n' : ' ');
46 int tpr(INT_MIN);
47 for(int i = N; i >= 1; --i){
48 if(s[i] >= 0)ans = max(ans, i);
49 if(i == N || s[i] > tpr){
50 while(!lft.empty() && s[i] - s[lft.top()] >= 0)
51 ans = max(ans, i - lft.top()), lft.pop();
52 tpr = s[i];
53 }
54 }
55 for(int i = 1; i <= N; ++i)s[i] += K * i;
56 while(!lft.empty())lft.pop();
57}
58signed main(){
59 N = read(), Q = read();
60 for(int i = 1; i <= N; ++i)s[i] = read() + s[i - 1];
61 while(Q--){
62 K = read();
63 Solve();
64 printf("%lld%c", ans, Q ? ' ' : '\n');
65 }
66 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67 return 0;
68}
69
70template<typename T>
71inline T read(void){
72 T ret(0);
73 short flag(1);
74 char c = getchar();
75 while(c != '-' && !isdigit(c))c = getchar();
76 if(c == '-')flag = -1, c = getchar();
77 while(isdigit(c)){
78 ret *= 10;
79 ret += int(c - '0');
80 c = getchar();
81 }
82 ret *= flag;
83 return ret;
84}
咕咕咕。
咕咕咕。
咕咕咕。
update-2022_10_17 初稿