acwing周赛部分题解(36-54)

大家好，欢迎来到IT知识分享网。

1、54场周赛-括号序列
题意概括：反转一个括号类型，使得其中括号序列变得平衡
解题思路：
（1）统计左括号和右括号的数量，如果差值不为2，那么一定不可能变得平衡
（2）如果是l == r+2，就反转字符串+镜像一下，让r == l+2
（3）编写work函数，从前往后扫描一遍，cnt表示当前左括号数量-右括号数量，r表示右括号的数量和，当发现cnt < 0 的时候，说明要做出改变，将前r个右括号任选一个变成左括号，检验改变之后是否可行，首先cnt += 2，因为改变了一个右括号之后，前i个字符的差值为+2，然后从i+1开始扫描，出现左括号cnt++,右括号cnt–,如果存在cnt < 0，说明改了一个括号之后仍然不满足要求，答案为0，反之，答案为r。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e6+10; int n; char s[N]; int work() { 
    int cnt = 0,r = 0; // 记录左括号-右括号的差值 和到第i个位置时，右括号的数量 for(int i = 0; i < n; i ++) { 
    if(s[i] == '(') cnt ++; else { 
    cnt --; r ++; if(cnt < 0) { 
    cnt += 2; // 判断将从这个位置开始一个右括号变成左括号是否满足要求 for(int j = i + 1; j < n; j ++) { 
    if(s[j] == '(') cnt++; else { 
    cnt --; if(cnt < 0) return 0; } } return r; } } } return 0; } int main() { 
    cin >> n; cin >> s; int l = 0, r = 0; // 表示左右括号的数量 for (int i = 0; i < n; i ++ ) { 
    if(s[i] == '(') l ++; else r ++; } if(r == l + 2) cout << work(); else if(l == r + 2) { 
    // 反转+镜像变成右括号比左括号多 reverse(s,s+n); for (int i = 0; i < n; i ++ ) { 
    if(s[i] == '(') s[i] = ')'; else s[i] = '('; } cout << work() << "\n"; } else puts("0"); return 0; } 

2、53场周赛-树中节点和
题意概括：给定一棵树，告诉深度为奇数的节点到根节点的路径权值和，求所有节点权值和的最小值
解题思路：贪心，对于每个深度为偶数的节点，以它的儿子和它围城的集合是互相独立的，如果每一个集合的权值都取的最小值，那么整体就会小，对于偶节点p，它满足如图所示的关系，a1+a2+a3+ap = 常数-2ap，求ap的最大值，也就是求它的儿子的权值和-它父节点的权值和的最小值。然后根据p来更新它的儿子的权值大小。无解的情况就是p的权值小于0.

#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 2e5+10,INF = 2e9+10; int h[N],e[N],ne[N],idx; int n; int s[N]; //奇数节点的权值路径和 LL ans; void add(int a,int b) { 
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++; } void dfs(int u,int depth,int last_s) { 
    if(depth % 2) { 
    for(int i = h[u];~i;i = ne[i]) { 
    int j = e[i]; dfs(j,depth+1,s[u]); } } else { 
    int p = INF; for(int i = h[u];~i;i = ne[i]) { 
    int j = e[i]; dfs(j,depth+1,0); p = min(p,s[j]-last_s); } if(p < 0) ans = -1e18; for(int i = h[u];~i;i = ne[i]) { 
    int j = e[i]; ans += s[j]-last_s-p; } if(p != INF) ans += p; } } int main() { 
    memset(h, -1, sizeof h); cin >> n; for(int i = 2; i <= n; i ++) { 
    int p; cin >> p; add(p,i); } for (int i = 1; i <= n; i ++ ) cin >> s[i]; ans = s[1]; dfs(1,1,0); // 从1号节点开始搜，节点的深度，奇数节点的权值 if(ans < 0) ans = -1; cout << ans << "\n"; return 0; } 

3、52周赛-信号
题意概括：1-n号方子内有些房子有发射器，发射器有一个半径r，问最少开启多少个发射器能够使得所有点被信号覆盖
解题思路：贪心。假设当前需要覆盖的区间最左端点是st，选择能够覆盖st点的区间中右端点最大的那个

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int n,r; int q[N],cnt; // 存储哪些点有发射器 int main() { 
    cin >> n >> r; for (int i = 1; i <= n; i ++ ) { 
    int x; cin >> x; if(x) q[cnt++] = i; } int res = 0,last = 0; // last表示上一个被覆盖的点 for(int i = 0; i < cnt; i ++) { 
    if(last >= n) break; if(q[i]-r > last) { 
    res = -1; break; } int j = i; while(j+1<cnt&&q[j+1]-r <= last) j++; last = q[j]+r-1; res++; i = j; } if(last < n) res = -1; cout << res << "\n"; return 0; } 

4、50周赛-选元素
题意概括：从前n个元素中选择x个元素，使得连续的k个序列至少有一个元素被选择
解题思路：
dp，主要是连续的k个序列中至少有一个被选择如何处理：
理解为连续两个被选的元素间隔不能超过k
（1）集合表示 f[i][j]表示从前i个元素中选择恰好j个元素，a[i]必须选择，同时连续的两个被选的值间隔不能超过k的所有情况的和。 MAX
（2）状态计算：f[i][j] = max(f[i-k~i-1]+a[i])
（3）结果表示为，枚举从n-k+1~n取最大的f[i][x]
注意：因为是恰好，因此初始化的时候把所有值初始化为负无穷表示不可达，f[0][0] = 0;

#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 210; LL f[N][N]; int n,k,x; int main() { 
    cin >> n >> k >> x; memset(f,-0x3f,sizeof f); f[0][0] = 0; for (int i = 1; i <= n; i ++ ) { 
    int v; cin >> v; for(int j = 1; j <= x; j ++) { 
    for(int s = max(0,i-k); s < i; s ++) { 
    f[i][j] = max(f[i][j],f[s][j-1]+v); } } } LL ans = -1; for (int i = n-k+1; i <= n; i ++ ) { 
    ans = max(ans,f[i][x]); } cout << ans << "\n"; return 0; } 

5、49-点的赋值
题意概括：看题
解题思路：染色法判断二分图、组合数、快速幂
（1）对每一个color[i] == -1的点进行dfs染色，统计白色和黑色点的数量
（2）如果黑色点的数量为0，那么白色点可以有三种选择方式，否则，黑色点有两种选择，白色点有两种选择。ans*这两者之后。可以理解为每一个连通块有多少中染色方式，有多少个连通块，这之间是用乘积进行计算！
（3）注意有多组测试数据，因此初始化的时候在每组测试数据完之后进行初始化。不能用memset，会超时。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 3e5+10, M = 6e5+10, p = ; int T; int n,m; int h[N], e[M], ne[M], idx; int num1,num2; int color[N]; void add(int a,int b) { 
    e[idx] = b,ne[idx] = h[a],h[a] = idx++; } bool dfs(int u,int c) { 
    color[u] = c; if(c == 0) num1 ++; else num2 ++; for(int i = h[u];~i;i=ne[i]) { 
    int j = e[i]; if(color[j] == -1) { 
    if(!dfs(j,1-c)) return false; } else { 
    if(color[j] == c) return false; } } return true; } LL qmi(int a, int k, int p) // 求a^k mod p { 
    LL res = 1 % p; while (k) { 
    if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } int main() { 
    ios::sync_with_stdio(false); cin.tie(0); cin >> T; memset(color,-1,sizeof color); memset(h, -1, sizeof h); while(T --) { 
    idx = 0; cin >> n >> m; for (int i = 1; i <= m; i ++ ) { 
    int a,b; cin >> a >> b; add(a,b); add(b,a); } LL ans = 1; for(int i = 1; i <= n; i ++) { 
    if(color[i] == -1) { 
    num1 = num2 = 0; if(!dfs(i,0)) { 
    ans = 0; break; } if(num2 == 0) ans = (ans * qmi(3,num1,p))%p; else ans = (ans*(qmi(2,num1,p)+qmi(2,num2,p))%p)%p; } } for (int i = 1; i <= n; i ++ ) { 
    color[i] = -1; h[i] = -1; } cout << ans << "\n"; } return 0; } 

6、48-构造数组
题意概括：构造一个数组b，a数组相同的位置b数组也要相同，b[0] = 0，问有多少种构造方法
解题思路：区间合并，发现这样一个性质：假设b[i]与b[j]要相同，又因为b[i+1] >= b[i]，所有这个数组是一个递增数组，这i < j同时b[i] = b[j]，因此i-j的每个数都相同。统计这样的区间有多少个，除了第一组外的区间，每组区间有两种选择。
（1）用哈希表L,R维护每个相同的值的最左端和最右边
（2）合并存在交集的区间
（3）从第二个区间开始乘以2

#include <iostream> #include <cstring> #include <algorithm> #include <unordered_map> using namespace std; const int N = 2e5+10, p = ; typedef pair<int, int> PII; int n; unordered_map<int,int> L(),R(); PII alls[N]; int m; int main() { 
    cin >> n; for (int i = 1; i <= n; i ++ ) { 
    int x; cin >> x; if(!L.count(x)) L[x] = i; R[x] = i; } for(auto &[k,v] : L) { 
    alls[m++] = { 
   L[k],R[k]}; } sort(alls,alls+m); int cnt = 0; int st = -1, ed = -1; for(int i = 0; i < m; i++) { 
    if(alls[i].first <= ed) ed = max(ed,alls[i].second); else { 
    cnt++; st = alls[i].first,ed = alls[i].second; } } int ans = 1; for(int i = 1; i < cnt; i ++) { 
    ans = ans*2%p; } cout << ans << "\n"; return 0; } 

7、47-找回数组
题意概括：
解题思路：x_0%k = a[1]-a[0], x_1%k = a[2]-a[1], x_3%k = a[3]-a[2] ，可以考虑枚举k的长度，check一下这个长度的时候是否合法。例如 1 2 2 1 2 长度为3或者5都可以满足要求

#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 1010; int n; int a[N]; vector<int> ans,q; bool check(int len) { 
    vector<int> tmp; int num = 0; for(int i = 0; i < q.size(); i ++) { 
    if(i < len) tmp.push_back(q[i]); else { 
    if(q[i] != tmp[num]) return false; num++; if(num == len) num = 0; } } return true; } int main() { 
    cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int i = 1; i <= n; i ++ ) { 
    q.push_back(a[i] - a[i-1]); } for(int len = 1; len <= (int)q.size(); len ++) { 
    if(check(len)) ans.push_back(len); } cout << ans.size() << "\n"; for(auto x : ans) cout << x << " "; return 0; } 

8、43-合适数对
题意概括：找到一个[l,r]的区间，使得其中的和 < t，问有多少个这样的区间
解题思路：
暴力解法是求前缀和然后枚举
树状数组、离散化
（1）用s[i]表示前i个数的和，那么枚举右端点r，要求s[r] – s[l-1] < t ，即s[l-1] > s[r]-t;
对于每一个右端点，求解这样的l有多少个
（2）这样问题就转化为了动态的求前缀和，这个数字出现就+1，查询的时候是想知道大于s[r]- t的数有多少个，用i-query(get(s[r]-t))查询
（3）需要注意的是要用到s[0]和s[0]-t，需要事先就加入alls，同时在get的时候，因为我们下标是从0开始，需要再+1.

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 4e5+10; typedef long long LL; LL s[N],tr[N]; LL n,t; vector<LL> alls; int get(LL x) { 
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1; } int lowbit(int x) { 
    return x &-x; } void add(int x,int v) { 
    for(int i = x;i < N; i += lowbit(i)) tr[i] += v; } int query(int x) { 
    int res = 0; for(int i = x;i; i -= lowbit(i)) res += tr[i]; return res; } int main() { 
    cin >> n >> t; // 要用到s0和s[0]-t，先存进去 alls.push_back(0),alls.push_back(-t); for (int i = 1; i <= n; i ++ ) { 
    int x; cin >> x; s[i] = s[i-1]+x; alls.push_back(s[i]); alls.push_back(s[i]-t); } // 离散化 sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end()); // 求值 // 先把0加进去 add(get(0),1); LL ans = 0; for (int i = 1; i <= n; i ++ ) { 
    ans += i-query(get(s[i]-t)); add(get(s[i]),1); } cout << ans << "\n"; return 0; } 

9、42-满二叉树等长路径
解题思路：递归、贪心。ans + abs(sum(left)-sum(right))

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2050; int a[N]; int n,ans; int dfs(int u) { 
    if(u*2 > n) return 0; int l = dfs(u*2) + a[u*2]; int r = dfs(u*2+1) + a[u*2+1]; ans += abs(l-r); return max(l,r); } int main() { 
    cin >> n; n = (1 << (n+1))-1; for (int i = 2; i <= n; i ++ ) cin >> a[i]; dfs(1); cout << ans << "\n"; return 0; } 

10、机器人移动
题意概括：机器人从原点出发，能否通过改变一段指令来使得其可以到达终点
解题思路：二分、前缀和。二分这个代价，判断用这个代价能否从某个点到终点。如何求某个点，对于某个指令，可以看成是对x和y的一个操作，+1或者-1，看成向量，枚举的一个长度，相当于把这个指令分成了三段，然后，可以用前缀和预处理之后在O(1)的时间内求出剩余两段到达的是哪个点。最后判断两个点的曼哈顿距离是否<=len，同时(len-dist)%2==0，因为如果是奇数的话是不可达的。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 2e5+10; typedef pair<int, int> PII; int cntx[N],cnty[N]; int n; char a[N]; int ex,ey; bool check(int len) { 
    for(int i = 1;i + len - 1 <= n; i ++) { 
    int r = i+len-1; int tx = cntx[i-1] + cntx[n] - cntx[r]; int ty = cnty[i-1] + cnty[n] - cnty[r]; //cout << tx <<" " << ty << endl; int tmp = abs(tx-ex)+abs(ty-ey); if(len >= tmp && (len-tmp)%2 == 0) return true; } return false; } int main() { 
    cin >> n; cin >> a+1; int sx = 0,sy = 0; for(int i = 1; i <= n; i ++) { 
    if(a[i] == 'U') cnty[i] = 1; else if(a[i] == 'D') cnty[i] = -1; else if(a[i] == 'L') cntx[i] = -1; else cntx[i] = 1; } cin >> ex >> ey; for(int i = 1; i <= n; i++) { 
    cntx[i] += cntx[i-1]; cnty[i] += cnty[i-1]; } int l = 0, r = n+1; while(l < r) { 
    int mid = l + r >> 1; if(check(mid)) r = mid; else l = mid + 1; } if(l > n) cout << -1 << "\n"; else cout << l << "\n"; return 0; }