差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22 [2020/05/22 22:16]
jjleo [CF1045G]
+++ 2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22 [2020/06/25 23:06] (当前版本)
jjleo ↷ 页面2020-2021:teams:farmer_john:2020.05.16-2020.05.22被移动至2020-2021:teams:farmer_john:jjleo:2020.05.16-2020.05.22
@@ 行 204: / 行 204: @@
 }</code></hidden>
 =====CF383E=====
-容斥dp+高维前缀和
+容斥dp+高维前缀和。
 <hidden><code cpp>#include <bits/stdc++.h>
@@ 行 338: / 行 338: @@
 }</code></hidden>
 =====CF797D=====
-<hidden><code cpp></code></hidden>
+思维+二叉搜索树。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+using namespace std;
+int n;
+int val[maxn];
+int son[maxn][2];
+bool tag[maxn];
+map<int, bool> mp;
+int ans;
+void dfs(int x, int l, int r){
+	if(val[x] < l && r < val[x]) mp[val[x]] = true;
+	if(son[x][0] != -1) dfs(son[x][0], min(l, val[x]), r);
+	if(son[x][1] != -1) dfs(son[x][1], l, max(r, val[x]));
+}
+int main(){
+	scanf("%d", &n);
+	for(int i = 1;i <= n;i++){
+		scanf("%d%d%d", &val[i], &son[i][0], &son[i][1]);
+		if(son[i][0] != -1) tag[son[i][0]] = true;
+		if(son[i][1] != -1) tag[son[i][1]] = true;
+	}
+	for(int i = 1;i <= n;i++){
+		if(!tag[i]){
+			dfs(i, 1e9 + 1, -1);
+			break;
+		}
+	}
+	for(int i = 1;i <= n;i++) if(!mp[val[i]]) ans++;
+	printf("%d", ans);
+}</code></hidden>
 =====CF979D=====
-<hidden><code cpp></code></hidden>
+Trie+数论。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 100086
+using namespace std;
+int son[maxn << 8][2], val[maxn << 8];
+int cnt = maxn;
+void insert(int x, int y){
+	for(int i = 1 << 20;i;i >>= 1){
+		bool z = (y & i) != 0;
+		if(!son[x][z]) son[x][z] = ++cnt, val[son[x][z]] = maxn;
+		x = son[x][z], val[x] = min(val[x], y);
+		//printf("%d %d %d--\n", x, i, val[x]);
+	}
+}
+int query(int x, int y, int s){
+	int ans = 0;
+	for(int i = 1 << 20;i;i >>= 1){
+		//printf("%d %d %d %d--\n", x, y, s, i);
+		bool z = (y & i) != 0;
+		if(val[son[x][z ^ 1]] <= s) x = son[x][z ^ 1], ans += (z ^ 1) * i;
+		else if(val[son[x][z]] <= s) x = son[x][z], ans += z * i;
+		else return -1;
+	}
+	return ans;
+}
+int n;
+int opt, x, y, z;
+int main(){
+	scanf("%d", &n);
+	val[0] = maxn;
+	while(n--){
+		scanf("%d", &opt);
+		if(opt == 1){
+			scanf("%d", &x);
+			for(int i = 1;i * i <= x;i++){
+				if(x % i) continue;
+				insert(i, x);
+				if(i * i != x) insert(x / i, x);
+			}
+		}else{
+			scanf("%d%d%d", &x, &y, &z);
+			if(x % y){
+				puts("-1");
+				continue;
+			}
+			printf("%d\n", query(y, x, z - x));
+		}
+	}
+}</code></hidden>
 =====CF1093G=====
-<hidden><code cpp></code></hidden>
+高维曼哈顿距离+线段树。
+<hidden><code cpp>#include <bits/stdc++.h>
+#define maxn 200086
+using namespace std;
+struct Node{
+	int sum[32];
+	Node(){
+		memset(sum, -0x3f, sizeof(sum));
+	}
+	inline int & operator [] (int i){
+		return sum[i];
+	}
+}t[maxn << 2];
+#define ls(x) (x << 1)
+#define rs(x) (x << 1 | 1)
+inline void up(int x){
+	for(int i = 0;i < 32;i++) t[x][i] = max(t[ls(x)][i], t[rs(x)][i]);
+}
+void modify(int x, int l, int r, int pos, Node d){
+	if(l == r){
+		t[x] = d;
+		return;
+	}
+	int mid = l + r >> 1;
+	if(mid >= pos) modify(ls(x), l, mid, pos, d);
+	else modify(rs(x), mid + 1, r, pos, d);
+	up(x);
+}
+Node query(int x, int l, int r, int ll, int rr){
+	if(ll <= l && r <= rr) return t[x];
+	int mid = l + r >> 1;
+	Node a, b;
+	if(mid >= ll){
+		b = query(ls(x), l, mid, ll, rr);
+		for(int i = 0;i < 32;i++) a[i] = max(a[i], b[i]);
+	}
+	if(mid < rr){
+		b = query(rs(x), mid + 1, r, ll, rr);
+		for(int i = 0;i < 32;i++) a[i] = max(a[i], b[i]);
+	}
+	return a;
+}
+int n, k, x, y;
+int q, opt;
+Node a;
+int main(){
+	scanf("%d%d", &n, &k);
+	for(int i = 1;i <= n;i++){
+		memset(a.sum, 0, sizeof(a.sum));
+		for(int j = 0;j < k;j++){
+			scanf("%d", &x);
+			for(int l = 0;l < 32;l++){
+				if(l & (1 << j)) a[l] += x;
+				else a[l] -= x;
+			}
+		}
+		modify(1, 1, n, i, a);
+	}
+	scanf("%d", &q);
+	while(q--){
+		scanf("%d", &opt);
+		if(opt == 1){
+			int i;
+			scanf("%d", &i);
+			memset(a.sum, 0, sizeof(a.sum));
+			for(int j = 0;j < k;j++){
+				scanf("%d", &x);
+				for(int l = 0;l < 32;l++){
+					if(l & (1 << j)) a[l] += x;
+					else a[l] -= x;
+				}
+			}
+			modify(1, 1, n, i, a);
+		}else{
+			scanf("%d%d", &x, &y);
+			a = query(1, 1, n, x, y);
+			int ans = -1e9;
+			for(int i = 0;i < (1 << k);i++) ans = max(ans, a[i] + a[(1 << k) - 1 - i]);
+			printf("%d\n", ans);
+		}
+	}
+}</code></hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具