2020.3.15
D. Unusual Sequences
题目链接：https://codeforces.com/contest/900/problem/D
题意：
给你 X 、Y，让你构造一个序列a满足 gcd(a1, a2, ..., an) = x 并且 $sum ^{n}_{i=1}a_{i}=y$
求满足条件的序列个数
分析：
容斥 + 隔板法
很显然当 Y % X != 0 时是无法构造出系列满足条件的
当 Y % X == 0 时，我们可以将条件建转换一下
即构造序列a满足gcd(a1, a2, ..., an) = 1 并且 $sum ^{n}_{i=1}a_{i}=y/x$
那么如果只看条件②，我们用隔板法可以得到的构造方案为 $sum ^{n}_{i=1}a_{i}=y/x$ 参见这里
然后我们再看条件①，因为构造出来的部分答案可能会改变gcd，所以我们只要再把改变gcd的情况减掉就可以了
举个栗子： X = 3 , Y = 12 , 那么改变条件之后 X = 1 , Y = 4。假设 solve(y / x) 得到的是当 gcd = x , sum = y 的构造方案
那么这个栗子的答案就为 solve(4 / 1) - solve(4 / 2)
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long #define ll long long #define MOD 1000000007 using namespace std; ll pow_mod(ll x , ll n , ll mod) { ll res = 1; while(n) { if(n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } const int N = 2e5 + 10; unordered_map<int , int>vis; int dfs(int n) { if(n == 1) return 1; if(vis[n]) return vis[n]; vis[n] = pow_mod(2 , n - 1 , MOD) - 1; for(int i = 2 ; i * i <= n ; i ++) { if(n % i == 0) { vis[n] = (vis[n] - dfs(n / i) + MOD) % MOD; if(i * i != n) vis[n] = (vis[n] - dfs(i) + MOD) % MOD; } } return vis[n]; } signed main() { int x , y; cin >> x >> y; if(y % x) return cout << 0 << ' ' , 0; int ans = dfs(y / x); cout << ans << ' '; return 0; }
2020.3.16
E. XOR and Favorite Number
题目链接：https://codeforces.com/contest/617/problem/E
题意：
给你一个长度为 N 的序列和 M 个查询，每个查询问你区间 [L , R] 中有多少子区间异或和为 K
分析：
莫队 + 前缀异或和
设 sum[i] 为序列的前 i 个数的异或和，那么根据异或性质可知一段区间 X , Y的异或和就为 sum[y] ^ sum[x - 1]
于是可以将询问转换为区间 [L , R] 中有多少对 X , Y 使得 sum[y] ^ sum[x - 1] = k
设 cnt[i] 表示异或和 i 出现的次数，那么常规的做法就是对于每次询问从 L 遍历到 R 一边更新答案一遍记录前缀异或和
map<int , int>cnt; for(int i = 1 ; i <= m ; i ++) { int ans = 0 ; cnt.clear(); cnt[0] = 1; for(int j = q[i].l; j <= q[i].r ; j ++) { int now = sum[q[i].l - 1]; //把 [1 - (L - 1)] 的异或和去掉 ans += cnt[sum[j] ^ k ^ now]; cnt[sum[j] ^ now] ++ ; } cout << ans << ' '; }
显然这么做复杂度是肯定不行的，而题目又不涉及修改区间等操作，所以很显然可以套个莫队离线操作
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long using namespace std; const int N = 2e5 + 10; struct Q{ int l , r , id; }q[N]; int a[N] , pos[N] , sum[N] , ans[N] ; unordered_map<int , int>cnt; int n , m , k , sz , l = 1 , r , res; bool cmp(Q a , Q b) { if(pos[a.l] == pos[b.l]) return a.r < b.r; return pos[a.l] < pos[b.l]; } void Add(int x) { res += cnt[sum[x] ^ k]; cnt[sum[x]] ++ ; } void Sub(int x) { cnt[sum[x]] -- ; res -= cnt[sum[x] ^ k]; } signed main() { ios; cin >> n >> m >> k; sz = sqrt(n); rep(i , 1 , n) cin >> a[i] , sum[i] = sum[i - 1] ^ a[i] , pos[i] = i / sz; rep(i , 1 , m) { cin >> q[i].l >> q[i].r; q[i].id = i; } cnt[0] = 1; sort(q + 1 , q + 1 + m , cmp); rep(i , 1 , m) { while(q[i].l < l) -- l , Add(l - 1); while(q[i].l > l) Sub(l - 1) , l ++; while(q[i].r > r) Add(++ r); while(q[i].r < r) Sub(r --); ans[q[i].id] = res; } rep(i , 1 , m) cout << ans[i] << ' '; return 0; }
2020.3.16
D. Police Stations
题目链接：https://codeforces.com/contest/796/problem/D
题意：
给你一颗包含 N 节点的树，其中有 K 个节点为关键点。
问在满足所有点和关键点的距离 <= d 的前提下最多可以删除多少条路径
分析：
思维 + BFS
相对简单的一道题吧？
将每个关键点加入队列，一边进行BFS一边记录路径
直到所有点都被访问过再把没记录过的路径输出即可
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define pb push_back #define fi first #define se second #define int long long using namespace std; const int N = 3e5 + 10; vector<pair<int , int>>mat[N]; int a[N]; queue<int>que; int vis1[N] , vis2[N] , cnt , n , k , d , ans; void bfs() { while(!que.empty()) { int now = que.front(); que.pop(); if(cnt == n) break ; for(auto i : mat[now]) { if(vis1[i.fi] || vis2[i.se]) continue ; vis1[i.fi] = 1 , vis2[i.se] = 1; que.push(i.fi); cnt ++ , ans ++ ; } } } signed main() { cin >> n >> k >> d; rep(i , 1 , k) { cin >> a[i]; if(vis1[a[i]]) continue ; cnt ++ , que.push(a[i]) , vis1[a[i]] = 1; } rep(i , 1 , n - 1) { int u , v; cin >> u >> v; mat[u].pb(make_pair(v , i)) , mat[v].pb(make_pair(u , i)); } bfs(); cout << n - 1 - ans << ' '; rep(i , 1 , n - 1) if(!vis2[i]) cout << i << " "; return 0; }
2020.3.17
D2. Too Many Segments (hard version)
题目链接：https://codeforces.com/contest/1249/problem/D2
题意：
给你 N 条线段，每条线段覆盖的点为 [Li , Ri] ，如果某个点被超过 k 条线段覆盖，那么这个点为坏点，
问最少可以去掉哪些线段可以使得没有坏点
分析：
线段树 + multiset
挺水的一题。
很显然在满足 L <= 当前坏点位置时 ，删除 R 最大的线段是最优的
对于每个线段它覆盖的点为 [Li , Ri] , 那么就用线段树对应维护这个区间内的所有点
在所有线段都操作完毕后再将坏点取出，以及对线段排序
然后遍历所有坏点，将左端点 L 小于当前坏点的线段存入 multiset 中，存完后再删除其中 R 最大的几项即可
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long #define ll long long #define il inline #define fi first #define se second #define pb push_back using namespace std; struct Tree { ll l,r,sum,lazy,maxn,minn; } tree[1000000]; il void push_up(ll rt) { tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; tree[rt].maxn=max(tree[rt<<1].maxn,tree[rt<<1|1].maxn); tree[rt].minn=min(tree[rt<<1].minn,tree[rt<<1|1].minn); } il void push_down(ll rt , ll length) { if(tree[rt].lazy) { tree[rt<<1].lazy+=tree[rt].lazy; tree[rt<<1|1].lazy+=tree[rt].lazy; tree[rt<<1].sum+=(length-(length>>1))*tree[rt].lazy; tree[rt<<1|1].sum+=(length>>1)*tree[rt].lazy; tree[rt<<1].minn+=tree[rt].lazy; tree[rt<<1|1].minn+=tree[rt].lazy; tree[rt<<1].maxn+=tree[rt].lazy; tree[rt<<1|1].maxn+=tree[rt].lazy; tree[rt].lazy=0; } } il void build(ll l , ll r , ll rt , ll *aa) { tree[rt].lazy=0; tree[rt].l=l; tree[rt].r=r; if(l==r) { tree[rt].sum=aa[l]; tree[rt].minn=tree[rt].sum; tree[rt].maxn=tree[rt].sum; return; } ll mid=(l+r)>>1; build(l,mid,rt<<1,aa); build(mid+1,r,rt<<1|1,aa); push_up(rt); } il void update_range(ll L , ll R , ll key , ll rt) { if(tree[rt].r<L||tree[rt].l>R)return; if(L<=tree[rt].l&&R>=tree[rt].r) { tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*key; tree[rt].minn+=key; tree[rt].maxn+=key; tree[rt].lazy+=key; return; } push_down(rt,tree[rt].r-tree[rt].l+1); ll mid=(tree[rt].r+tree[rt].l)>>1; if(L<=mid)update_range(L,R,key,rt << 1); if(R>mid)update_range(L,R,key,rt << 1 | 1); push_up(rt); } il ll query_range(ll L, ll R, ll rt) { if(L<=tree[rt].l&&R>=tree[rt].r) { return tree[rt].sum; } push_down(rt,tree[rt].r-tree[rt].l+1); ll mid=(tree[rt].r+tree[rt].l)>>1; ll ans=0; if(L<=mid)ans+=query_range(L,R,rt << 1); if(R>mid)ans+=query_range(L,R,rt << 1 | 1); return ans; } const int N = 2e5 + 10; struct node { int l , r , id; bool operator < (node const & a) const { if(l == a.l) return r < a.r; return l < a.l; } } x[N]; int n , k , a[N] , b[N] , cnt; multiset<pair<int , int>>s; vector<int>ans; signed main() { cin >> n >> k; build(1 , N - 10 , 1 , a); rep(i , 1 , n) { cin >> x[i].l >> x[i].r; update_range(x[i].l , x[i].r , 1 , 1); x[i].id = i; } rep(i , 1 , N - 10) if(query_range(i , i , 1) >= k) b[++ cnt] = i; sort(x + 1 , x + 1 + n); int now = 1; rep(i , 1 , cnt) { while(x[now].l <= b[i] && now <= n) s.insert(make_pair(-x[now].r , x[now].id)) , now ++ ; int tot = query_range(b[i] , b[i] , 1) - k; while(tot > 0) { auto it = *s.begin(); update_range(b[i] , -it.fi , -1 , 1); s.erase(it); tot -- ; ans.pb(it.se); } } cout << ans.size() << " "; for(auto i : ans) cout << i << " "; cout << ' '; return 0; }
2020.3.17
D. Two Sets
题目链接：https://codeforces.com/contest/469/problem/D
题意：
给你一个长度为 N 的序列 p 和两个数 a , b
现有两个集合 A , B , 要求你将这个序列放入集合A 、B（每个数只能放入一个集合）使得
如果 pi 存在于 A ， 则 a - pi 也存在于 A ， 如果 pi 存在于 B ，则 b - pi也存在于 B
分析：
思维 + 并查集
我们定义 rootA 代表集合 A , rootB 代表集合 B
对于 pi ，我们分四种情况讨论
①、如果 a - pi 存在 ，则 pi 和 a - pi 必将存在于相同集合
②、如果 a - pi 不存在，则 pi 必将存在于集合 B , 即 pi 与 rootB 存在于相同集合
③、如果 b - pi 存在 ，则 pi 和 b - pi必将存在于相同集合
④、如果 b - pi 不存在，则 pi 必将存在于集合 A , 即 pi 与 rootA 存在于相同集合
以上情况我们用并查集维护 pi 下标来操作，其中 rootA 我们定义为 n + 1 , rootB定义为 n + 2
那么最后如果 find（rootA）== find（rootB）则答案不存在 , 因为当两者相等时必然存在以下其中一种情况
①、对于某个数 pk , 既不存在 a - pk , 也不存在 b - pk
②、对于某个数 pk , 它既需要存在于集合 A ，也需要存在于集合 B
如果 find（rootA）!= find（rootB），则对应输出就可以了
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long using namespace std; const int N = 2e5 + 10; int far[N] , p[N] , n , a , b; map<int , int>vis; int find(int x) { if(x == far[x]) return x; return far[x] = find(far[x]); } void Union(int x , int y) { int tx = find(x) , ty = find(y); if(tx != ty) far[tx] = ty; } signed main() { cin >> n >> a >> b; rep(i , 1 , n) cin >> p[i] , vis[p[i]] = i , far[i] = i; int rootA = n + 1 , rootB = n + 2; far[rootA] = n + 1 , far[rootB] = n + 2; rep(i , 1 , n) { if(vis[a - p[i]]) Union(i , vis[a - p[i]]); else Union(i , rootB); if(vis[b - p[i]]) Union(i , vis[b - p[i]]); else Union(i , rootA); } if(find(rootA) == find(rootB)) return cout << "NO " , 0; cout << "YES "; rep(i , 1 , n) { if(find(rootA) == find(i)) cout << 0 << " "; else cout << 1 << " "; } cout << ' '; return 0; }
2020.3.18
D. Jerry's Protest
题目链接：https://codeforces.com/problemset/problem/626/D
题意：
给你 N 个球，每个球都有自己的分数 ai
现在有两个人 A , B 进行游戏 , 一共三轮 , 每轮每个人从中抽取一个球 , 谁球的分数大谁胜
胜者可以获得abs(两球分值差)的积分
已知 A 赢了两轮 , B 赢了 一轮 ，问 B 获得的积分比 A 大的概率是多少
分析：
概率 + 思维
对于一场比赛可能出现的情况有 C(n , 2)种 ， 那么三场一共就有 C(n , 2) ^ 3种
我们设 one[i] 表示赢一场获得 i 积分情况数 ， two[i] 表示赢两场获得 i 积分的情况数
那么它们的求法如下:
sort(a + 1 , a + 1 + n); for(int i = 1 ; i <= n ; i ++) for(int j = i + 1 ; j <= n ; j ++) one[a[j] - a[i]] ++ ; for(int i = 1 ; i <= 5000 ; i ++) for(int j = 1 ; j <= 5000) two[i + j] += one[i] * one[j];
于是易得 B 获得积分比 A 多的情况数计算方式为:
int sum = 0; for(int i = 1 ; i <= 10000 ; i ++) for(int j = i + 1 ; j <= 5000 ; j ++) sum += two[i] * one[j];
那么这题就这样轻松解决了
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long using namespace std; const int N = 2e5 + 10; int a[N] , one[N] , two[N]; signed main() { int n; cin >> n; int tot = n * (n - 1) >> 1; rep(i , 1 , n) cin >> a[i]; sort(a + 1 , a + 1 + n); rep(i , 1 , n) rep(j , i + 1 , n) one[a[j] - a[i]] ++ ; rep(i , 1 , 5000) rep(j , 1 , 5000) two[i + j] += one[i] * one[j]; int sum = 0; rep(i , 1 , 10000) rep(j , i + 1 , 5000) sum += two[i] * one[j]; double ans = (1.0) * sum / tot / tot / tot; cout << setprecision(10) << fixed << ans << ' '; return 0; }
2020.3.18
G. New Roads
题目链接：https://codeforces.com/contest/746/problem/G
题意：
告诉你一棵树有 N 个节点 , 其中 1 为树根 , 树有T 层，第 i 层节点个数为 a(i-1) , 叶子节点的个数为 K
问你能否构造出树边使得这棵树满足以上条件
分析：
思维 + 构造
很显然当本层的节点全都指向一个父节点时，叶子节点个数最多
当本层节点分散指向不同父节点时，叶子节点个数最少
那么叶子节点最多为 ma = a[t] + (a[t - 1] - 1) + (a[t - 2] - 1) + ... + (a[1] - 1)
最少为 mi = a[t] + max(0 , a[t - 1] - a[t]) + ... + max(0 , a[1] - a[2])
所以当 K 不在 mi ~ ma 这个范围之内就一定无法构造，反之必然可以构造
当叶子节点个数等于 ma 时，代表每层的节点都指向上一层的同一父节点
那么当第 i 层其中一个节点指向另一个父节点节点后, ma的数量就会减少min(1,a[i-1]-1)
其中两个节点指向另外两个父节点后，ma的数量就会减 min(2 , a[i - 1] - 1)
于是当 ma > k 时，我们就可以按照上述操作不断减少 ma，直到 ma = k 时，再按照所有节点指向同一个父节点的方法构造即可
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define fi first #define se second #define int long long using namespace std; const int N = 2e5 + 10; int a[N] , ma , mi; vector<int>num[N]; vector<pair<int , int>>ans; signed main() { int n , t , k , cnt = 1; cin >> n >> t >> k; rep(i , 1 , t) cin >> a[i]; ma = a[t] , mi = a[t]; per(i , t - 1 , 1) ma += a[i] - 1 , mi += max(0LL , a[i] - a[i + 1]); if(k > ma || k < mi) return cout << -1 << ' ' , 0; num[0].pb(1); rep(i , 1 , t) { int j = 0 ; num[i].pb(++ cnt); ans.pb(make_pair(num[i - 1][0] , cnt)); a[i] -- ; while(a[i] && j < num[i - 1].size()) { if(k < ma && j + 1 < num[i - 1].size()) j ++ , ma -- ; ans.pb(make_pair(num[i - 1][j] , ++ cnt)) , num[i].pb(cnt); a[i] -- ; } } cout << n << ' '; for(auto i : ans) cout << i.fi << " " << i.se << ' '; return 0; }
2020.3.18
I. Olympiad in Programming and Sports
题目链接：https://codeforces.com/contest/730/problem/I
题意：
有 N 个人，每个人编程能力为 xi ，运动能力为 yi
现要求你选 p 个人参加编程比赛 , s 个人参加运动比赛（每个人只能参加一项比赛）
使得这 p 个人编程能力和 + 这 s 个人运动能力和最大，问怎么选择
分析：
dp
我们可以先以一种能力降序排序（假设以 yi）
那么排完序后，因为是降序的，所以参加运动的人选择的范围肯定是 [1 , p + s]
而参加编程队的我们就无法确定
依此我们可以建立dp方程 dp[i][j] 表示前 i 个人有 j 个选择参加编程比赛
那么转移方程也很显然：
dp[i][j] = max(①dp[i - 1][j] , ②dp[i - 1][j - 1] + a[i].x , ③dp[i - 1][j] + a[i].y)
答案为dp[n][p]
其中当 i - j > s 时不再进行③的转移，因为此时 [1 , i - i] 已经有大于等于S个人没参加编程比赛 , 也就是这些人是可以参加运动比赛的，而数组是以运动能力降序排序所以前面的人参加运动比赛的收益一定比[i , n]的人高，所以参加运动比赛的人肯定不会从后面选择
这也是能保证 dp[n][p] 的选择方案里一定有 S 个参加运动比赛的原因（因为是降序的所以当运动人数没满时不参加编程比赛的一定去了运动比赛而不是哪都没去）
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long using namespace std; const int N = 3e3 + 10; struct node{ int x , y , id; bool operator < (node const & a) const { return y > a.y; } }a[N]; int dp[N][N] , vis[N]; pair<int , int>pre[N][N]; void dfs(int i , int j) { if(i == 0) return ; if(pre[i][j].second == 1) vis[i] = 1 ; dfs(i - 1 , pre[i][j].first) ; } signed main() { int n , p , s; cin >> n >> p >> s; rep(i , 1 , n) cin >> a[i].x , a[i].id = i; rep(i , 1 , n) cin >> a[i].y; sort(a + 1 , a + 1 + n); memset(dp , -0x3f3f3f , sizeof(dp)); dp[0][0] = 0; rep(i , 1 , n) { rep(j , 0 , min(i , p)) { if(i - j <= s && dp[i - 1][j] + a[i].y > dp[i][j]) dp[i][j] = dp[i - 1][j] + a[i].y , pre[i][j] = make_pair(j , 2); if(i - j > s && dp[i - 1][j] > dp[i][j]) dp[i][j] = dp[i - 1][j] , pre[i][j] = make_pair(j , 0); if(j - 1 >= 0 && dp[i - 1][j - 1] + a[i].x > dp[i][j]) dp[i][j] = dp[i - 1][j - 1] + a[i].x , pre[i][j] = make_pair(j - 1 , 1); } } cout << dp[n][p] << ' '; dfs(n , p) ; int cnt = 0 ; rep(i , 1 , n) if(vis[i]) cout << a[i].id << " "; cout << ' '; rep(i , 1 , n) if(!vis[i] && cnt < s) cout << a[i].id << " " , cnt ++ ; cout << ' '; return 0; }
2020.3.18
D. Bear and Blocks
题目链接：https://codeforces.com/contest/574/problem/D
题意：
给你一个长度为 N 的序列，其中 ai 表示 i 这个位置有 ai 的木块
现在进行游戏，每轮可消除木块（若某木块的上或左或右没有木块则可以消除）
问要消除所有木块最多要几轮
分析：
思维
首先转换题意 , 把消除所有木块转换成要将所有列的木块个数变为 0
这样就可以按列考虑考虑
那么要消除一列，我们需要的最少步骤会是多少呢?
很显然要消除的条件有三种：
①、前一列为空，那么下一轮这列必然可以被消灭
②、后一列为空，那么下一轮这列必然可以被消灭
③、每轮该列至少消灭最上方的木块，那么经过 ai 轮后该列就能被删除
我们记录 L[i] 为从左往右逐列消灭的最优解，R[i] 为从右往左逐列消灭的最优解
于是 L[i] = min(L[i - 1] + 1 , a[i]) , R[i] = min(R[i + 1] + 1 , a[i])
ans = max(ans , min(L[i] , R[i]))
#include<bits/stdc++.h> #define rep(i , a , n) for(int i = a ; i <= n ; i ++) #define per(i , n , a) for(int i = n ; i >= a ; i --) using namespace std; const int N = 2e5 + 10; int a[N] , l[N] , r[N] , n , ans; signed main() { cin >> n; rep(i , 1 , n) cin >> a[i] , l[i] = min(l[i - 1] + 1 , a[i]); per(i , n , 1) r[i] = min(a[i] , r[i + 1] + 1) , ans = max(ans , min(l[i] , r[i])); cout << ans << ' '; return 0; }
2020.3.20
P2757 [国家集训队]等差子序列
题目链接：https://www.luogu.com.cn/problem/P2757
题意：
给你一个 1 ~ N 的排列，问是否存在等差子序列
分析：
权值线段树 + hash
首先要满足等差序列的条件为 a[ i ] + a[ k ] = 2 * a[ j ] ，其中 i < j < k
那么根据这个条件我们就可以枚举等差序列中心，判断两端是否有满足条件的 a[i] , a[k]
我们可以知道若一个排列长度为 3 , 并且我们要以 2 为等差序列中心 , 那么 1 3 就必须在 2 的两端
理解以上后，我们可以选择枚举等差序列的中心 j ，来找它的两端是否有满足条件的 i , k
假设现在有个数组 vis , 其中 vis[i] 表示 i 这个数是否已经出现
举个栗子 , 假设现在序列为 1 2 3 , 那么我们枚举到 a[1] 时vis[1] = 1 , vis[2] = 0 , vis[3] = 0
当我们枚举到 a[2] 时 , vis[2] = 1 , vis[1] = 1 , vis[3] = 0，枚举到 a[3] 的时全都等于1
其中，枚举到 a[2] 即枚举到 2 这个数的时候 , vis[1] = 1 , vis[3] = 0 , 数组呈现为 110
也就是说 1 这个数是在 2 之前出现的 , 3这个数是在 2 之后出现的，那么我们就可以以
a[2] 为中心构造等差子序列；而如果枚举到2时 1、3 都在2的同一端即 111 或者 010
那么就无法以a[2]为中心构造等差子序列
根据以上我们会发现当以 X 这个数为中心时，如果两端对称位置数的数组值相同
则说明这对称位置的数同时存在于 X 的同一侧，也就是它们和 X 无法构成等差子序列
那如果对称位置数组值不相同,则它们存在 X 的不同侧,也就是它们可以和 X 构成等差子序列
那么倘若 X 两端对称位置数的数组值全相同，则以 X 为中心的数组呈现会是一个回文串(左右两端相同)
所以我们只要枚举每个数，每次枚举判断这个数作为中心是否会产生回文串 , 待找到不回文或者枚举结束即可
至于回文我们可以用线段树来维护正反hash值来操作
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define int long long #define ll long long #define ull unsigned long long using namespace std; const int P = 13331 , mod = 999998639; const int N = 2e5 + 10; ull power[N]; int a[N]; struct Seg_ment{ int l , r ; ull pre , suf; }tree[N << 2]; void push_up(int id , int len1 , int len2) { tree[id].pre = tree[id << 1].pre * power[len2] + tree[id << 1 | 1].pre; tree[id].pre %= mod; tree[id].suf = tree[id << 1 | 1].suf * power[len1] + tree[id << 1].suf; tree[id].suf %= mod; } void build(int id , int l , int r) { tree[id].pre = tree[id].suf = 0; tree[id].l = l , tree[id].r = r; if(l == r) return ; int mid = l + r >> 1; build(id << 1 , l , mid); build(id << 1 | 1 , mid + 1 , r); push_up(id , mid - tree[id].l + 1 , tree[id].r - mid); } void update(int id , int pos , int val) { if(tree[id].l == tree[id].r) { tree[id].pre = tree[id].suf = val; return ; } int mid = tree[id].l + tree[id].r >> 1; if(pos <= mid) update(id << 1 , pos , val); else update(id << 1 | 1 , pos , val); push_up(id , mid - tree[id].l + 1 , tree[id].r - mid); } ull query_range(int id , int l , int r , int ch) { if(tree[id].l >= l && tree[id].r <= r) { if(ch == 1) return tree[id].pre ; return tree[id].suf; } int mid = tree[id].l + tree[id].r >> 1; if(r <= mid) return query_range(id << 1 , l , r , ch); if(l > mid) return query_range(id << 1 | 1 , l , r , ch); ull lson = query_range(id << 1 , l , r , ch); ull rson = query_range(id << 1 | 1 , l , r , ch); ull ans ; if(ch == 1) ans = lson * power[min(r , tree[id].r) - mid] + rson; else ans = rson * power[mid - max(tree[id].l , l) + 1] + lson; return ans % mod; } void init() { power[0] = 1; rep(i , 1 , 100000) power[i] = power[i - 1] * P % mod; } signed main() { init(); int t; cin >> t; while(t --) { int n , flag = 0 , x; cin >> n; build(1 , 1 , n); rep(i , 1 , n) { cin >> x; update(1 , x , 1); if(i == 1 || i == n) continue ; int len = min(x , n - x + 1); int y = query_range(1 , x - len + 1 , x , 1); int z = query_range(1 , x , x + len - 1 , 2); if(y != z) flag = 1 ; } if(flag) cout << "Y "; else cout << "N "; } return 0; }
2020.3.22
Game
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6312
题意：
你有 N 个数，分别是 1 , 2 , 3 ... N。
有两个人玩游戏，每轮一个人可以从中取一个数，并删除它即它的因子
当其中一人无法再取数时 , 游戏结束 , 无法取数的人输。问先手赢还是后手赢
分析：
博弈
休闲水题
首先考虑当序列为 [2 , N] 时，先手取这个序列要么胜，要么败（废话）
也就是说这个序列要么是必胜状态，要么是必败状态（还是废话）
那么当 [2 , N] 为必胜状态的时候 , 先手就可以选择这个序列（此时[1]会被[2,N]覆盖）
当[2 , N]为必败状态的时候，先手就可以选择[1]并将这个序列丢给后手
#include<bits/stdc++.h> using namespace std; int main() { int n ; while(cin >> n) cout << "Yes "; return 0; }
2020.3.22
E. Two Permutations
题目链接：https://codeforces.com/contest/213/problem/E
题意：
给你一个 1 ~ N的排列 A 和一个 1 ~ M 的排列 B ( N <= M )
问有多少个 d 可以使得排列 A 的每个数 + d 后为排列 B 的子序列
分析：
权值线段树 + hash
只要满足每个 a[i] + d 在 A 中的相对位置和在 B 中的相对位置相同即可
也就是判断 B 中[1~N]、[2~N+1] ... [M - N + 1~ M]与A中[1, N] 的相对位置是否相同
于是我们先可以定义 pos[i] 表示 i 这个数在 B 中的位置（pos[ b[ i ] ] = i）
要判断相对位置是否相同，我们可以通过 hash 来操作
具体是用线段树维护 1 ~ M 的区间, 第i个区间表示 B 数组第i个位置的数是多少
然后简单来说就是再把这些位置的值提取出来计算hash值是否会和A的hash值相同
(细节看代码)
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define int long long #define ull unsigned long long using namespace std; const int N = 2e5 + 10; const int P = 13331; const int mod = 999998639; ull power[N]; int a[N] , b[N] , pos[N]; struct Seg_ment{ ull pre , tot; int l , r; }tree[N << 2]; void push_up(int id) { tree[id].tot = tree[id << 1].tot + tree[id << 1 | 1].tot; tree[id].pre = (tree[id << 1].pre * power[tree[id << 1 | 1].tot] + tree[id << 1 | 1].pre) % mod; } void build(int l , int r , int id) { tree[id].l = l , tree[id].r = r; tree[id].pre = 0; if(l == r) return ; int mid = l + r >> 1; build(l , mid , id << 1); build(mid + 1 , r , id << 1 | 1); push_up(id); } void update(int id , int pos , int val) { if(tree[id].l == tree[id].r) { if(!val) tree[id].tot -= 1; else tree[id].tot += 1; tree[id].pre = val; return ; } int mid = tree[id].l + tree[id].r >> 1; if(pos <= mid) update(id << 1 , pos , val); if(pos > mid) update(id << 1 | 1 , pos , val); push_up(id); } void init() { power[0] = 1; rep(i , 1 , 200000) power[i] = power[i - 1] * P % mod; } signed main() { init(); int n , m , ans = 0; cin >> n >> m; build(1 , m , 1); ull sum = 0 , add = 0; rep(i , 1 , n) cin >> a[i] , sum = (sum * P + a[i]) % mod , add += power[i - 1] , add %= mod; rep(i , 1 , m) cin >> b[i] , pos[b[i]] = i; rep(i , 1 , m) { if(i > n) update(1 , pos[i - n] , 0); update(1 , pos[i] , i); int cha = i - n; if(cha >= 0 && tree[1].pre % mod == (sum + cha * add) % mod) ans ++ ; } cout << ans << ' '; return 0; }
2020.3.23
D. Imbalanced Array
题目链接：https://codeforces.com/contest/817/problem/D
题意：
给你一个序列，让你求出这个序列的每个区间最大值的和 - 最小值的和
分析：
单调栈
单调栈经典题。
我们先求出以 a[ i ] 为最小值的左右最长拓展 L1[i] , R1[i]
那么以 a[ i ] 为最小值的区间个数就为 (L1[ i ] + 1) * (R1[ i ] + 1)
再求出以 a[ i ] 为最大值的左右最长拓展 L2[ i ] , R2[ i ]
那么以 a[ i ] 为最大值的区间个数就为 (L2[ i ] + 1) * (R2[ i ] + 1)
最后线性扫一遍即可
(为了避免相同值区间长度被重复计算，需采用左开右闭的维护方式)
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define int long long using namespace std; const int N = 1e6 + 10; int a[N] , sta[N] , l[N] , r[N] , ans; signed main() { int n ; cin >> n; rep(i , 1 , n) cin >> a[i]; int top = 0; rep(i , 1 , n) { while(top && a[sta[top]] >= a[i]) top -- ; if(!top) l[i] = i - 1; else l[i] = i - sta[top] - 1; sta[++ top] = i; } top = 0; per(i , n , 1) { while(top && a[sta[top]] > a[i]) top --; if(!top) r[i] = n - i; else r[i] = sta[top] - i - 1; sta[++ top] = i; } rep(i , 1 , n) ans -= a[i] * (l[i] + 1) * (r[i] + 1); top = 0; rep(i , 1 , n) { while(top && a[sta[top]] <= a[i]) top -- ; if(!top) l[i] = i - 1; else l[i] = i - sta[top] - 1; sta[++ top] = i; } top = 0; per(i , n , 1) { while(top && a[sta[top]] < a[i]) top --; if(!top) r[i] = n - i; else r[i] = sta[top] - i - 1; sta[++ top] = i; } rep(i , 1 , n) ans += a[i] * (l[i] + 1) * (r[i] + 1); cout << ans << ' '; return 0; }
写博客太耗时间了 , 认真思考了一下还是决定先不写好了