(赛中+补题记录)
不是题解,更多是做题心得与评价。
和同学聊天时口胡的思路,可能有点混乱
所求的y y y ,直接看是若干个数 or and and or 这样从左至右算出来的,当然这些数可能重复。or and 运算满足分配律,所以表达式总是可以化简为若干个东西 or 起来再 and,或者若干个东西 and 起来再 or。选后者,比较符合直觉。
可以先从极端想,若干个东西 and 出来只有一位。枚举每一位,把 and 起来还有这一位的东西都 and 起来,尽量让其它位都变 0。当然如果没办法都变成 0,就形成了要有这一位,另一位就必须存在这种关系(注意这关系没有传递性)。比如原来是 10 和 11(二进制),包含最低位的那只能是 11。这些数有个特点,要么独立要么包含,两两 and 不可能更小,不会有 110 和 011 同时出现。这样处理将得到 64 个大数。
现在的问题就是,64 个数,选择一些数做 or,运算结果比x x x 大且最小。
大概要枚举前缀,每次给x x x 加个 lowbit,能不能用这些数或出一个这样的前缀。而后几位不用考虑,不加那肯定最小。比如当前前缀是 V,or 和是 sum,必须始终 sum&V=sum,逐个遍历那 64 个数加入 sum,看最终 sum 是不是等于 V,等于那就说明这个前缀可以构造出来。所有可能的结果取最小值就是答案。
但是复杂度是 log 方的,枚举前缀一个log,再枚举又一个log,过不去。
道理是对的,但是方案有问题,可能哪里浪费了。
确实浪费了。每次给x x x 加个 lowbit 可以假加,因为这个步骤的本质是把某个 0 变成 1,后面忽略。sum&V=sum 也可以假判断,或者说这个判断完全没必要。x x x 有 1 就必须把这个数加上,没得选,就算加上去更大了也没办法,得加,不加上就没法满足那个条件。所以其实是唯一的,没必要判断。这样省了个 log。
现在的方案是,从高位到地位枚举x x x 的二进制位。如果是 1 就加到 sum 里,否则是 0,可能产生答案,把这一位 0 虚拟地变成 1 并把对应的数虚拟地加到 sum 计算结果。所有可能的结果取最小值就是答案。
时间复杂度O [ ( n + q ) log V ] \operatorname{O}[(n+q)\log V] O [ ( n + q ) log V ] 。
注意:mod 不要写 1e16 + 1029
,这是个 double,精度丢完了。
Bonus: 出题人说优雅集对应拓扑,sol 相当于找一组拓扑基。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int n, q;cin >> n >> q; vector<ull> dp (64 , -1 ) ; while (n--) { ull x; cin >> x; for (int bit = 63 ; bit >= 0 ; bit--) { if (x >> bit & 1 ) { dp[bit] &= x; } } } ull ans = 0 ; while (q--) { ull x; cin >> x; ull sum = 0 , res = -1 ; for (int bit = 63 ; bit >= 0 ; bit--) { if (x >> bit & 1 ) { sum |= dp[bit]; } else { res = min (res, sum | dp[bit]); } } res = min (res, sum); ans ^= res % mod; } cout << ans << endl;
我真的是读入一个字符串后,先分离出天干、地支,然后再用 exCRT 算出年份的。
应该先预处理。
比较考验基本功。
对于每个正整数,贪心找第一次出现的位置,下一个 0,下一个出现的位置,再加上后缀本质不同的数的数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 int n;cin >> n; vector<int > a (n) ;for (int i = 0 ; i < n; i++) { cin >> a[i]; } auto all = a;sort (all.begin (), all.end ());all.erase (unique (all.begin (), all.end ()), all.end ()); for (int i = 0 ; i < n; i++) { a[i] = lower_bound (all.begin (), all.end (), a[i]) - all.begin (); } vector<vector<int >> mp (all.size ()); for (int i = 0 ; i < n; i++) { mp[a[i]].push_back (i); } vector<int > suf (n + 1 ) ; vector<int > cnt (all.size()) ;for (int i = n - 1 ; i >= 0 ; i--) { suf[i] = suf[i + 1 ]; if (a[i] && !cnt[a[i]]) { cnt[a[i]]++; suf[i]++; } } ll res = 0 ; auto & vec0 = mp[0 ];for (int i = 1 ; i < mp.size (); i++) { auto & vec = mp[i]; auto it = vec.begin (); it = lower_bound (vec0. begin (), vec0. end (), *it); if (it == vec0. end ()) continue ; it = lower_bound (vec.begin (), vec.end (), *it); if (it == vec.end ()) continue ; res += suf[*it + 1 ]; } cout << res << endl;
可以优化为线性:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 vector<int > fst (all.size()) ;vector<int > suf (n + 1 ) ;for (int i = n - 1 ; i >= 0 ; i--) { suf[i] = suf[i + 1 ]; if (a[i]) { suf[i] += (fst[a[i]] == 0 ); fst[a[i]] = i; } } ll res = 0 ; int last0 = 0 ;for (int i = 0 ; i < n; i++) { if (a[i] == 0 ) { last0 = i; continue ; } if (fst[a[i]] < last0) { res += suf[i + 1 ]; fst[a[i]] = inf; } } cout << res << endl;
不离散化打 map 会多个 log,TLE。
小 DP,按值按下标皆可。k > 26 k>26 k > 2 6 时相当于 26,但需注意数据范围,k k k 不能用 int 或 ll 存。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 string s, t; cin >> s >> t; int k = (t.size () > 2 ) ? 26 : stoi (t);array<int , 26> dp{}; while (k--) { for (auto c : s) { c -= 'a' ; dp[c] = max (dp[c], 1 ); for (int j = 0 ; j < c; j++) { dp[c] = max (dp[c], dp[j] + 1 ); } } } cout << *max_element (dp.begin (), dp.end ()) << endl;
不喜欢计算,小计算也不喜欢。
操作规则很复杂,而且是可打表(不可能无法结束,按照红蓝盒子的顺序能打表)的博弈题,无脑打表观察。
个人认为题解那种转化可操作性不强。除非一眼,有这时间表已经打出来了。
打表程序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int dp[500 ][500 ][500 ];dp[0 ][0 ][0 ] = 0 ; for (int k = 0 ; k < 150 ; k++) { for (int i = 0 ; i < 150 ; i++) { for (int j = 0 ; j < 150 ; j++) { int ans = 1 ; if (j >= 1 ) chmin (ans, dp[i][j - 1 ][k]); if (j >= 2 ) chmin (ans, dp[i][j - 2 ][k]); if (j >= 3 ) chmin (ans, dp[i][j - 3 ][k]); if (i >= 1 ) chmin (ans, dp[i - 1 ][j][k]); if (i >= 1 && j >= 1 ) chmin (ans, dp[i - 1 ][j - 1 ][k]); if (i >= 1 ) chmin (ans, dp[i - 1 ][j + 1 ][k]); if (i >= 2 ) chmin (ans, dp[i - 2 ][j + 1 ][k]); if (k >= 1 ) chmin (ans, dp[i][j + 1 ][k - 1 ]); if (k >= 1 ) chmin (ans, dp[i + 1 ][j][k - 1 ]); if (k >= 1 ) chmin (ans, dp[i + 1 ][j + 1 ][k - 1 ]); dp[i][j][k] = 1 - ans; } } }
打出来长这样:
1 2 3 4 5 6 7 8 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1
0 的位置也比较显然了。
1 2 3 4 5 6 7 8 9 10 11 int j, i, k;cin >> j >> i >> k; j %= 4 ; i %= 2 ; if (j % 2 == 1 ) { cout << "Alice" << endl; } else if (i == j / 2 ) { cout << "Bob" << endl; } else { cout << "Alice" << endl; }
这题大概是区域赛铜,思路好想但不好写的那种。
拓扑排序删掉完美的某行,能全删掉就 ok。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 int n, q;cin >> n >> q; vector<vector<int >> adj (3 * n); bool ok = true ;while (q--) { int x, y, c; cin >> x >> y >> c; x--, y--, c--; int u[3 ] = { y / 2 , 2 * n - 1 - x, x - (y + 1 ) / 2 + 2 * n }; bool found = false ; for (int o = 0 ; o < 3 ; o++) { if (c == u[o]) { found = true ; adj[u[o]].push_back (u[(o + 1 ) % 3 ]); adj[u[o]].push_back (u[(o + 2 ) % 3 ]); } } if (!found) ok = false ; } vector<int > deg (3 * n) ;for (int u = 0 ; u < (3 * n); u++) { for (auto v : adj[u]) deg[v]++; } vector<int > Q; for (int u = 0 ; u < (3 * n); u++) { if (deg[u] == 0 ) Q.push_back (u); } for (int i = 0 ; i < Q.size (); i++) { auto u = Q[i]; for (auto v : adj[u]) { if (--deg[v] == 0 ) Q.push_back (v); } } if (Q.size () != (3 * n)) ok = false ;cout << (ok ? "Yes" : "No" ) << endl;
非常好的图论建模题,只是题面有点绕,真是学高考第 19 题导致的。
题目的意思是将a a a 重排,新数组与原数组的那个关系≺ \prec ≺ (Latex: \prec)相对不变,原来满足那新数组也要满足,反之亦然。
我的想法是,注意i , j i,j i , j 满足那个关系,那么i i i 与i + 1 , … , j − 1 i+1,\dots, j-1 i + 1 , … , j − 1 都满足,可以找对于每个i i i ,第一个不满足那个关系的j j j ,给i → j i\to j i → j 连边后会形成一棵树。但这样丢信息了,只给i → j i\to j i → j 连边不行,没有保证中间的都串在一起。
题解说找i i i 左边最大的j j j ,使得j , i j,i j , i 满足关系,这就对了。现在也构成一棵树,所有有关系的,在树上都有一条链,所有没关系的,在树上都是兄弟。因此,只能修改子树之间的顺序。
从叶子到根依次排序。排序方案是,如果根不同,小的在前(思考为什么字典序最大还要小的在前),如果根不同,按字典序排序。字典序缺位补+ ∞ +\infty + ∞ 。
用 std::list
实现,代码极短。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 vector<int > a (n + 1 ) ;vector<vector<int >> adj (n + 1 ); a[0 ] = inf; stack<int > stk; stk.push (0 ); for (int i = 1 ; i <= n; i++) { cin >> a[i]; while (a[stk.top ()] <= a[i]) { stk.pop (); } adj[stk.top ()].push_back (i); stk.push (i); } vector<list<int >> list (n + 1 ); for (int i = 0 ; i <= n; i++) { list[i].push_back (a[i]); list[i].push_back (inf); } for (int i = n; i >= 0 ; i--) { sort (adj[i].begin (), adj[i].end (), [&](int x, int y) { return a[x] == a[y] ? list[x] > list[y] : a[x] < a[y]; }); for (auto x : adj[i]) { list[i].pop_back (); list[i].splice (list[i].end (), list[x]); } } list[0 ].pop_front (); list[0 ].pop_back (); for (auto x : list[0 ]) { cout << x << " " ; } cout << endl;