A - Power (abc283 a)
题目大意
给定(A,B)，输出 (A^B)
解题思路
数不大，暴力即可。
数大了可用快速幂。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int a,b;
cin >> a >> b;
int ans = 1;
while(b--){
ans *= a;
}
cout << ans << 'n';
return 0;
}
B - First Query Problem (abc283 b)
题目大意
给定一个数组(A)和 (Q)个操作，分两种
1 k x，令 (A_k = x)2 k，输出 (A_k)
解题思路
暴力模拟即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(auto &i : a)
cin >> i;
int q;
cin >> q;
while(q--){
int op;
cin >> op;
if (op == 1){
int k, x;
cin >> k >> x;
a[k - 1] = x;
}else{
int k;
cin >> k;
cout << a[k - 1] << 'n';
}
}
return 0;
}
C - Cash Register (abc283 c)
题目大意
要在屏幕上输入一个数字(S)，有以下 (11)种操作，其中 (10)种就是输入数字 (0,1,2,3,4,5,6,7,8,9)，跟正常输手机号码一样，还有一种操作是连输入两个 (0)（即(00)，但算一次操作） 。问最小的输入次数。
解题思路
连续的(0)的区间必定是若干次 (00)和一次 (0)（如果需要的话）。因此答案就是每个连续 (0)区间(0)的个数除以 (2)的上取整和其他数的个数。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
int ans = 0;
int cnt = 0;
for(auto &i : s){
if (i == '0'){
++ cnt;
}else{
ans ++;
ans += (cnt + 1) / 2;
cnt = 0;
}
}
ans += (cnt + 1) / 2;
cout << ans << 'n';
return 0;
}
D - Scope (abc283 d)
题目大意
给定一个合法的括号序列，其中夹杂着若干个小写字母。依次扫描这个序列的每个字符。
- 如果是小写字母，则放到对应的盒子里（即
a放到盒子a）里。若对应盒子已经有东西，则扫描失败。 - 如果是
(，则什么都不做。 - 如果是
)，则找到与其匹配的(，将这期间的放入盒子的字母都扔掉。
问扫描是否成功。
解题思路
因为字母只有(26)个，因此当遇到一个 )时，我们不必扫描原序列，而只用看这(26)个盒子是否有要扔掉的即可。
记录每个盒子放入时的下标，即可知道要不要扔掉。
括号匹配，用栈即可求得与)匹配的(的下标。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
auto check = [&](){
int n = s.size();
vector<int> pos(26, -1);
stack<int> left;
for(int i = 0; i < n; ++ i){
if (s[i] == '('){
left.push(i);
}else if (s[i] == ')'){
assert(!left.empty());
int l = left.top();
left.pop();
for(int i = 0; i < 26; ++ i)
if (pos[i] >= l)
pos[i] = -1;
}else{
if (pos[s[i] - 'a'] != -1)
return false;
pos[s[i] - 'a'] = i;
}
}
return true;
};
if (check())
cout << "Yes" << 'n';
else
cout << "No" << 'n';
return 0;
}
E - Don't Isolate Elements (abc283 e)
题目大意
给定一个(01)矩阵。可以进行一种操作，该操作为翻转某行的 (01)值。
问操作次数的最小值，使得不存在一个位置，其上下左右的值都与其不同。
解题思路
因为一个位置合不合法涉及到上下左右四个方向，我们从上往下(dp)时，因为当前行的下的位置还未做决策，因此不能判断当前行是否合法，得留到后面来判断。
除此之外，我们称一个位置为危险位置，当仅当上左右的值与其不同。转移时要判断是否合法，即要判断每一列是不是危险位置，需要知道当前行和上一行的翻转状态才能知道。
即设(dp[i][j])表示前 (i)行，最后两行的翻转状态为 (j)，且前(i-1)行都合法的最小操作次数。转移则枚举前两行和当前行的翻转状态即可。
即当前行为(i)，从 (i-1)行转移过来，(i-1)行状态只保证了前 (i-2)行合法，转移时需要判断第 (i-1)行的合法性，需枚举 (i-2,i-1,i)行的翻转状态 ，对(i-1)行的每个格子判断是否合法，合法的才能转移到第 (i)行。
注意从最后一行得答案时还要判断最后一行的合法性。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int h, w;
cin >> h >> w;
vector<vector<int>> a(h, vector<int>(w, 0));
for(auto &i : a)
for(auto &j : i)
cin >> j;
vector<vector<int>> dp(h, vector<int>(4, inf));
dp[0][0] = 0;
dp[0][1] = 1;
dp[0][2] = 0;
dp[0][3] = 1;
auto danger = [&](int x, int y, int s){ // 判断(x,y)是否危险，其中x-1,x行的翻转状态为s
int s1 = ((s >> 1) & 1);
int s2 = (s & 1);
int cnt = 0;
if (x == 0 || (a[x - 1][y] ^ s1) != (a[x][y] ^ s2))
++ cnt;
if (y == 0 || (a[x][y - 1] ^ s2) != (a[x][y] ^ s2))
++ cnt;
if (y == w - 1 || (a[x][y + 1] ^ s2) != (a[x][y] ^ s2))
++ cnt;
return cnt == 3;
};
auto valid = [&](int x, int s, int ls, int sign){ // 判断第x-1行是否合法，其中第x行翻转状态为s，第x-2,x-1行翻转状态为ls，sign表示是否判断该列下一行的格子数是否相等（仅仅区别于判断最后一行的危险性时）
int s1 = (ls & 1);
int s2 = (s & 1);
for(int i = 0; i < w; ++ i){
if (danger(x - 1, i, ls) && (sign || (a[x - 1][i] ^ s1) != (a[x][i] ^ s2)))
return false;
}
return true;
};
for(int i = 1; i < h; ++ i){
for(int j = 0; j < 2; ++ j) // 第i行翻转状态
for(int k = 0; k < 4; ++ k) // 第i-2,i-1行翻转状态,2即10表示i-2行翻转，i-1行没翻转
if (valid(i, j, k, 0)){ // 判断第i-1行是否合法
int sign = ((k & 1) << 1);
int nxstat = (j | sign);
dp[i][nxstat] = min(dp[i][nxstat], dp[i - 1][k] + (j == 1));
}
}
int ans = inf;
for(int i = 0; i < 4; ++ i)
if (valid(h, 0, i, 1)) // 判断第h-1行（最后一行）是否合法，1表示没有下面的格子了
ans = min(ans, dp[h - 1][i]);
if (ans == inf)
ans = -1;
cout << ans << 'n';
return 0;
}
F - Permutation Distance (abc283 f)
题目大意
给定一个排列(p)，求 (d)数组，其中 (d_i = minlimits_{j neq i} ( |p_i - p_j| + |i - j| ))
解题思路
将绝对值去掉，得
里面四项每一个都是一个二维偏序问题（满足两个不等关系的条件下求最值）。分别解之取最小值即可。
二维偏序的解法，假想在一个二维坐标系内，就是问一个矩形的最值。
可通过循环满足一个不等式关系（即满足一维），再用一个数据结构维护另一个不等式关系（维护另一维）求最值。
以第一个偏序问题为例，即枚举下标(i)，把小于 (i)的加入到数据结构中（满足了 (j < i)），然后在满足小于(p_i)中找到最小的 (p_j + j)，此为一个区间查询操作。故对(p_i)建立一棵线段树， 其位置（为(p_i)，不是 (i)）维护的值是(p_i + i)。然后查询([1,p_i - 1])的最小值。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
const int N = 2e5 + 8;
class segment{
#define lson (root << 1)
#define rson (root << 1 | 1)
public:
int minn[N << 2];
void build(int root, int l, int r){
if (l == r){
minn[root] = inf;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
minn[root] = min(minn[lson], minn[rson]);
}
void update(int root, int l, int r, int pos, int val){
if (l == r){
minn[root] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(lson, l, mid, pos, val);
else
update(rson, mid + 1, r, pos, val);
minn[root] = min(minn[lson], minn[rson]);
}
int query(int root, int l, int r, int ll, int rr){
if (ll > rr)
return inf;
if (ll <= l && r <= rr){
return minn[root];
}
int mid = (l + r) >> 1;
int ans = inf;
if (ll <= mid)
ans = min(ans, query(lson, l, mid, ll, rr));
if (rr > mid)
ans = min(ans, query(rson, mid + 1, r, ll, rr));
return ans;
}
}sg1, sg2, sg3, sg4;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++ i)
cin >> a[i];
vector<int> ans(n + 1, inf);
sg1.build(1, 1, n);
sg2.build(1, 1, n);
for(int i = 1; i <= n; ++ i){
ans[i] = min(ans[i], a[i] + i + sg1.query(1, 1, n, 1, a[i] - 1));
ans[i] = min(ans[i], i - a[i] + sg2.query(1, 1, n, a[i] + 1, n));
sg1.update(1, 1, n, a[i], -(a[i] + i));
sg2.update(1, 1, n, a[i], -(-a[i] + i));
}
sg3.build(1, 1, n);
sg4.build(1, 1, n);
for(int i = n; i >= 1; -- i){
ans[i] = min(ans[i], a[i] - i + sg3.query(1, 1, n, 1, a[i] - 1));
ans[i] = min(ans[i], -i - a[i] + sg4.query(1, 1, n, a[i] + 1, n));
sg3.update(1, 1, n, a[i], -(a[i] - i));
sg4.update(1, 1, n, a[i], -(-a[i] - i));
}
for(int i = 1; i <= n; ++ i)
cout << ans[i] << " n"[i == n];
return 0;
}
貌似还可以看成点((i, p_i))，然后问曼哈顿距离的最小值。对原图求一遍曼哈顿距离最小生成树，与之相连的边距离取个最小值。
G - Partial Xor Enumeration (abc283 g)
题目大意
给定一个(n)个数的数组(A)，任选数进行异或，可得异或集合 (S)，问该集合里第 (l)到第 (r)小的数分别是多少。
解题思路
其实就是异或线性基求第(k)大的裸题。
即对(n)个数求得一组线性基，假设该线性基有(k)个，这意味着这(n)个数在二进制下张成了一个(k)维空间。
然后对这(k)个线性基正交化后（类似于二维空间的两个基((1,0),(0,1))，或三位空间的两个基 ((1,0,0),(0,1,0),(0,0,1))，即正交基组成的矩阵是个对角阵），这个时候各维互不干扰，可以选择也可以不选择。
那么第 (k)小（从(0)开始）的值就是其二进制下为(1)的位数（即维度）的那些线性基的异或值。
即(k=b_4b_3b_2b_1b_0)，那么其值就是 (b_4ji_4 oplus b_3ji_3 oplus b_2ji_2 oplus b_1ji_1 oplus b_0ji_0)
其正确性感觉很显然吧，这些线性基本身有大小关系，而且选择与否不会影响到其他维度的值，然后线性基本身只有选和不选两种，感觉就跟二进制数一样，第(0)小就是什么都不选（(0)），第 (1)小就是选最小的（(1)），第 (2)小就是选择 (ji_1)（(10)），第三小就是选择 (ji_1)和 (ji_0)（(11)）.
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
LL l, r;
cin >> n >> l >> r;
vector<LL> ji(64, 0);
for(int i = 0; i < n; ++ i){
LL a;
cin >> a;
for(int j = 60; j >= 0; -- j){
if (((a >> j) & 1) && ji[j] == 0){
ji[j] = a;
break;
}
else if (((a >> j) & 1)){
a ^= ji[j];
}
}
}
for(int i = 60; i >= 0; -- i)
for(int j = i + 1; j <= 60; ++ j)
if ((ji[j] >> i) & 1)
ji[j] ^= ji[i];
vector<LL> jj;
for(int i = 0; i <= 60; ++ i)
if (ji[i])
jj.push_back(ji[i]);
-- l;
-- r;
for(LL i = l; i <= r; ++ i){
LL ans = 0;
int pos = 0;
LL tmp = i;
while(tmp){
if (tmp & 1)
ans ^= (jj[pos]);
++ pos;
tmp >>= 1;
}
cout << ans << " n"[i == r];
}
return 0;
}
Ex - Popcount Sum (abc283 h)
题目大意
给定(n,m,r)，问 ([1,n])中满足 (x mod m = r)的所有 (x)的二进制下 (1)的个数的和。
多组数据。
解题思路
满足条件的(x)都是形如 (mi + r)的数。将这些数的(popcount)（即二进制下(1)的个数）加起来就是答案。
但这些数的数量高达 (O(10^9))。考虑二进制位下每一位(1)的贡献。即第 (k)位是 (1)的数的个数。
以下三个等价条件：
- (x)二进制下的第(k) 位是(1)
- (2^k leq x mod 2^{k + 1} < 2^{k + 1})
- (lfloor frac{x + 2^k}{2^{k+1}} rfloor - lfloor frac{x}{2^{k+1}} rfloor = 1)
第二个条件就是，取模后最高位就是第(k)位，其为 (1)，因此余数就不小于(2^k)。
第三个条件就是，如果第(k)位是 (1)，那么加了 (2^k)后就会在 (2^{k+1})处进位，其除以(2^{k+1})就会多 (1)，否则不影响。
由于所有(x = mi + r)，我们代入第三个式子后就是 (lfloor frac{mi + r + 2^k}{2^{k+1}} rfloor - lfloor frac{mi + r}{2^{k+1}} rfloor)
如果(x)的二进制在第 (k)位是(1) ，那上述式子的结果就是(1)，否则就是 (0)。因此对其累积求和就是答案。
即
每一项都是形如(sumlimits_{i} lfloor frac{ai+b}{c} rfloor)的形式，可用类欧几里德算法在(O(log))时间内算出。再对(k)累计求和，最终的时间复杂度为 ((log^2 n))
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL floor_sum(LL a, LL b, LL c, LL n){
if (n < 0)
return 0;
LL val = 0;
if (a >= c){
val += n * (n + 1) / 2 * (a / c);
a %= c;
}
if (b >= c){
val += (n + 1) * (b / c);
b %= c;
}
LL m = (a * n + b) / c;
val += n * m - floor_sum(c, c - b - 1, a, m - 1);
return val;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n, m, r;
cin >> n >> m >> r;
LL ans = 0;
for(int i = 0; i < 31; ++ i){
ans += floor_sum(m, r + (1 << i), (1 << (i + 1)), (n - r) / m);
ans -= floor_sum(m, r, (1 << (i + 1)), (n - r) / m);
}
cout << ans << 'n';
}
return 0;
}
有一个有趣的现象是
至于证明，只想到个感性的，我们考虑(x)二进制下的每一位 (1)，假设是 (2^i)，它在第一项的结果，随着(k)变大，依次为(2^{i-1},2^{i-2},2^{i-3},cdots,2, 1)，当(k)是 (i+1)时，因为还加了 (2^i)的缘故，此时还有一个结果是 (1)，因此 (2^i)在第一项的贡献为 (2^{i-1},2^{i-2},2^{i-3}, cdots, 2, 1, 1)，等比求和一下就是(2^i - 1 + 1 = 2^i)。
即(x)的某一位(2^i) 在第一项和式的最终贡献还是(2^i)，因此该和式的结果还是原来的 (x)。
有了后者的式子的话，就可以少做一半的求和了。
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
