解题报告-2019国庆清北Day6

https://download.csdn.net/download/qq_45721135/11866514

Day6

T1

二维差分

考场代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define INF 0x7fffffff

using namespace std;

int n,m,k,ux,dx,lx,rx,ans,cnt,sum;
int map[1000005],u[1000005],d[1000005],l[1000005],r[1000005],tj[1000005];
int cx[1000005],f[1000005];

int main()
{
	freopen("paint.in","r",stdin);
	freopen("paint.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= k; i++) u[i] = l[i] = INF,d[i] = r[i] = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			cnt++;
			scanf("%d",&map[cnt]);
			cx[map[cnt]] = 1;
			u[map[cnt]] = min(u[map[cnt]],i);
			d[map[cnt]] = max(d[map[cnt]],i);
			l[map[cnt]] = min(l[map[cnt]],j);
			r[map[cnt]] = max(r[map[cnt]],j);
		}
	for(int i = 1; i <= k; i++)
	{
		if(!cx[i]) continue;
		f[u[i] * m - m + l[i]]++;
		f[u[i] * m - m + r[i] + 1]--;
		f[d[i] * m + l[i]]--;
		f[d[i] * m + r[i] + 1]++;
	}
//	printf("%d %d %d %d\n",u[2],d[2],l[2],r[2]);
//	f[u[2] * m - m + l[2]]++;
//	f[u[2] * m - m + r[2] + 1]--;
//	f[d[2] * m + l[2]]--;
//	f[d[2] * m + r[2] + 1]++;
//	for(int i = 1; i <= n; i++)
//	{
//		for(int j = 1; j <= m; j++) printf("%d ",f[i * m - m + j]);
//		printf("\n");
//	}
	for(int i = 1; i <= n; i++) f[i] = f[i - 1] + f[i];
	for(int i = 2; i <= n; i++)
		for(int j = 1; j <= m; j++)
			f[i*m-m+j] = f[i*m-m-m+j] + f[i*m-m+j-1] - f[i*m-m-m+j-1] + f[i*m-m+j];
//	for(int i = 1; i <= n; i++)
//	{
//		for(int j = 1; j <= m; j++) printf("%d ",f[i * m - m + j]);
//		printf("\n");
//	}
	for(int i = 1; i <= cnt; i++) if(f[i] > 1) tj[map[i]] = 1;
	for(int i = 1; i <= k; i++) if(!tj[i]) ans++;
	for(int i = 1; i <= k; i++) if(cx[i]) sum++;
	if(sum == 1 && k > 1) ans--;
	printf("%d\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}

std

然而std和我的算法貌似不一样……

#include<bits/stdc++.h> 
#define M 100010
#define p(a, b) (a * mm + b - mm) 
using namespace std;
int i, j, Li[M], Ri[M], Lj[M], Rj[M], a[M], use[M], ans, n, m, K, fl, nxt[M], pre[M], vis[M], mm, u;
int find(int x){
	if(!vis[x])return x;
	return nxt[x] = find(nxt[x]);
}
int main(){
	fl = 0;
	scanf("%d%d%d", &n, &m, &K);
	memset(Li, 63, sizeof(Li));
	memset(Lj, 63, sizeof(Lj));
	memset(Ri, 0, sizeof(Ri));
	memset(Rj, 0, sizeof(Rj));
	memset(use, 0, sizeof(use));
	mm = max(n, m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			if(n > m) u = p(j, i);
			else u = p(i, j);
			scanf("%d", &a[u]);
		}
	if(n > m)swap(n, m);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			u = p(i, j);
			nxt[u] = p(i, j + 1);
			pre[u] = p(i, j - 1);
			if(Ri[a[u]] == 0 && a[u])fl++;
			if(i < Li[a[u]])Li[a[u]] = i;
			if(i > Ri[a[u]])Ri[a[u]] = i;
			if(j < Lj[a[u]])Lj[a[u]] = j;
			if(j > Rj[a[u]])Rj[a[u]] = j;
		}
	for(int i = 1; i <= K; i++)
		if(Li[i] <= Ri[i]){
			for(int j = Li[i]; j <= Ri[i]; j++)
				for(int k = Lj[i]; k <= Rj[i]; k = find(nxt[k]))
					if(a[p(j, k)] != i){
						use[a[p(j, k)]] = 1;
						vis[p(j, k)] = 1;
						nxt[pre[p(j, k)]] = nxt[p(j, k)];
						pre[nxt[p(j, k)]] = pre[p(j, k)];
					}
		}
	for(int i = 1; i <= K; i++)
		if(!use[i])ans++;
	if(ans == K && fl == 1 && ans > 1)ans--;
	if(fl)printf("%d\n", ans);
	else puts("0");
}

T2

std

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
map<int, int>dad, h;
int n, m, l, r, X, Y, i, t, k, p;
char s1[110];
int find(int x){
	if(!dad[x])return x;
	int t = find(dad[x]);
	h[x] = (h[x] + h[dad[x]]) % p;
	return dad[x] = t;
}
char ch;
void read(int &x) {
	for(ch = getchar(); ch < '0'; ch = getchar());
	for(x = 0; ch >= '0'; ch = getchar()) x = x * 10 + ch - '0';
}
int main(){
	read(n);
	read(m);
	read(p);
	for(i = 1; i <= m; i++){
		read(l);
		read(r);
		read(k);
		r++;
		X = find(l);
		Y = find(r);
		t = (h[r] - h[l] + p) % p;
		if(X != Y){
			dad[X] = Y;
			h[X] = (t - k + p) % p;
		}else if(t != k)break;
	} 
	printf("%d\n", i - 1);
}

T3

std

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n, a[N], f[N], g[N], F[N], G[N], t, ans;
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1); 
	F[1] = 1, f[0] = 0;
	for(int i = 2; i <= n; i++){
		f[i] = 5e8;
		for(F[i] = F[i - 1]; (a[i] - a[F[i] + 1]) * 2 >= f[F[i] + 1] * 3; F[i]++);
		f[i] = min((f[F[i] + 1] * 3 + 1) / 2, a[i] - a[F[i]]);
	}
	G[n] = n, g[n] = 0;
	for(int i = n - 1; i >= 1; i--){
		g[i] = 5e8;
		for(G[i] = G[i + 1]; (a[G[i] - 1] - a[i]) * 2 >= g[G[i] - 1] * 3; G[i]--);
		g[i] = min((g[G[i] - 1] * 3 + 1) / 2, a[G[i]] - a[i]);
	}
	ans = 2e9;
	for(int i = 1; i <= n; i++){
		if(max(f[i], g[i]) < ans) t = i;
		ans = min(ans, max(f[i], g[i]));
	}
	int tt = t, an = ans;
	for(int j = t; j >= 1; j--){
		if(a[j] < a[tt] - an){
			tt = j + 1;
			an = an * 3 / 2; 
		}
		if(a[j] < a[tt] - an)assert(1);
	}
	tt = t, an = ans;
	for(int j = t; j <= n; j++){
		if(a[j] > a[tt] + an){
			tt = j - 1;
			an = an * 3 / 2; 
		}
		if(a[j] > a[tt] + an)assert(2);
	}
	tt = t, an = ans - 1; int flag = 0;
	for(int j = t; j >= 1; j--){
		if(a[j] < a[tt] - an){
			tt = j + 1;
			an = an * 3 / 2; 
		}
		if(a[j] < a[tt] - an)flag = 1;
	}
	if(!flag)assert(3);
	tt = t, an = ans - 1; flag = 0;
	for(int j = t; j <= n; j++){
		if(a[j] > a[tt] + an){
			tt = j - 1;
			an = an * 3 / 2; 
		}
		if(a[j] > a[tt] + an)flag = 1;
	}
	if(!flag)assert(4);
	printf("%d\n", ans);
}