Codeforces

Educational Codeforces Round 23

在列车上打的......A题一时不会做. TAT C题卡住了. 感觉是个数位DP, 但是拿什么作状态呢? 虽然数位和的所有可能值很少呢......跳过了这题, 发现后面是三道基本数据结构练习题. F没时间写了. 比赛时完成ABDE. C题最后用数位DP写出来了, 但是有更妙的方法. 题解: 6/6. # A. Treasure Hunt 给定x,y, 起点, 终点. 无限大的网格图上, 每次可以移动(+-x, +-y). 问是否能从起点到终点. 次数不限. (|坐标|,x,y≤10^5, x,y≥1)

也就是问 a(x,y) + b(x,-y) = (x',y') 这个方程是否有整数解. 算出表达式, 验证是否为整数.

typedef long long ll;

int main()
{
	ll x1, y1, x2, y2, x, y;
	cin >> x1 >> y1 >> x2 >> y2 >> x >> y;
	x2 -= x1, y2 -= y1;
	ll a = (x2*y + x*y2) / 2 / x / y, b = (x*y2 - x2*y) / 2 / x / y;
	if (a*2*x*y == x2*y + x*y2 && b*2*x*y == x*y2 - x2*y)
		puts("YES");
	else
		puts("NO");
	return 0;
}

B. Makes And The Product

给出长度为n的正整数数组a. 问存在多少个三元组(i,j,k) (i<j<k) 使得a[i],a[j],a[k]的乘积取到最小值. (3≤n≤10^5, 1≤ai≤10^9)

显然取数组a的前3小. 这乘积都爆unsigned long long了. 仔细一想, 我们并不需要知道乘积具体是多少. 它不能是其他3个数的乘积, 否则能被调整得更小. 排一遍序, 看看第3小的数能被哪些替换, 然后做一做乘法.

Tutorial给出了另一种做法. 处理出每个前/后缀的最小值, 和最小值出现的次数. 枚举j (即中间的下标).

typedef long long ll;

const int N = 1e5 + 5;

int a[N];

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	rep (i, 0, n) cin >> a[i];
	sort(a, a+n);
	int k = 3;
	while (k < n && a[k] == a[2]) ++k;
	if (a[0] == a[1] && a[1] == a[2])
	{
		cout << 1LL * k * (k-1) * (k-2) / 6 << endl;
	}
	else if (a[0] != a[1] && a[1] == a[2])
	{
		--k;
		cout << 1LL * k * (k-1) / 2 << endl;
	}
	else
	{
		cout << k-2 << endl;
	}
	return 0;
}

C. Really Big Numbers

有多少个小于等于n的正整数x, 满足 x - x的十进制数位和 ≥ s? (1≤n,s≤10^18)

想做数位DP, 但这个状态不好定义啊......也许数位和所有取值的数量很少 (162个), 这个性质会有帮助?

后来想到, 枚举数位和sum, 并统计反面, 即&le; s. 问题转化为, 有多少个小于 min(n, sum) 的数, 其十进制数位和等于 sum. 这就是经典问题啦.

但标签怎么是二分, 数学?

呃......其实是否满足条件是具有单调性的......式子列出来了, 但我没有关注这个......所以二分即可.

不用二分也可以. 由于数位和最大为162, 所以 s+162 一定是满足条件的数. 进一步地, [s+162,n] 都是. [1,s] 一定不是. 暴力检验 (s,s+162) 即可.

typedef long long ll;

ll f[19][10][164];

ll cal(ll s, ll X)
{
	int x[19], n = 0, t = 0;
	ll ret = 0;
	
	while (X) x[n++] = X % 10, X /= 10;
	
	per (i, n-1, 0)
	{
		ret += x[i] && s >= t ? f[i][x[i]-1][s-t] : 0;
		t += x[i];
	}

	return ret;
}
	
int main()
{
	ios::sync_with_stdio(false);

	rep (j, 0, 10) rep (k, 0, 10)
		f[0][j][k] = (j == k) + (j ? f[0][j-1][k] : 0);
	
	rep (i, 1, 19) rep (j, 0, 10) rep (k, 0, 164)
		f[i][j][k] = (k >= j ? f[i-1][9][k-j] : 0) + (j ? f[i][j-1][k] : 0);
	
	ll n, s, ans = 0;
	cin >> n >> s;
	rep (i, 1, 164)
		ans += cal(i, min(n+1, s+i));
	cout << n - ans << endl;
	return 0;
}

D. Imbalanced Array

一个长度为n的数组a. 求所有子区间的最大值-最小值之和. (1≤n≤10^6, 1≤ai≤10^6)

把最大值和最小值拆开来求. 考虑每个值的贡献, 即, 求出每个值作为最大值和最小值的区间. 这是单调栈的经典应用.

有一个小问题. a中元素可能重复. 我简单粗暴地把数改成 (数,位置), 这样元素就是唯一的了. 这样等价于求出每个元素作为最左最小值, 最右最大值的区间.

有一个小trick可以简化实现. 先求最小值区间. 每个元素取反, 再求最小值区间, 即原数组的最大值区间.

E. Choosing The Commander

维护一个可重集, 支持: - 插入一个正整数 - 删除一个集合中的数 - 给定y,z, 求集合中有多少个数x满足 x xor y < z.

(1≤操作数q≤10^5, 正整数≤10^8)

用 0-1 Trie 树 维护即可. 询问在树上二分. 是否加上另一棵子树的值, 取决于这一位是否为1. [bzoj 4103] [Thu Summer Camp 2015]异或运算 我的TLE做法就是这个......大概是经典问题.

const int V = 28 * 1e5;

struct Trie
{
	int ptr, root, ch[V][2], v[V];
	void modify(int& o, int s, int k, int a)
	{
		if (!o) o = ++ptr;
		v[o] += a;
		if (k >= 0) modify(ch[o][s>>k & 1], s, k-1, a);
	}
	int query(int o, int p, int l, int k)
	{
		if (!o || k < 0) return 0;
		int a = p>>k & 1, b = l>>k & 1, s = 0;
		if (b)
			s = v[ch[o][a]] + query(ch[o][a^1], p, l, k-1);
		else
			s = query(ch[o][a], p, l, k-1);
		return s;
	}
} T;	

int main()
{
	ios::sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--)
	{
		int o, p, l;
		cin >> o >> p;
		if (o <= 2)
		{
			T.modify(T.root, p, 27, o == 1 ? 1 : -1);
		}
		else
		{
			cin >> l;
			cout << T.query(T.root, p, l, 27) << endl;
		}
	}
	return 0;
}

F. MEX Queries

维护一个初始为空的集合, n个操作: - 添加[l,r]中的所有整数 - 删除[l,r]中的所有整数 (如果存在) - 翻转[l,r]中所有整数的存在性

每个操作结束后, 输出集合中没出现的最小正整数. (1≤n≤10^5, 1≤l≤r≤10^18)

线段树就可以实现? 一看数的范围, 10^18......

不过我们可以直接对值域开线段树, 动态加点. 或者, 因为可以离线, 所以离散化一下. 我选择了后者, 粗暴地把x-1,x,x+1都加了进去. 然后, 两种 lazy tag. 下传是容易的, 我们可以保证每个节点每一时刻只有一种标记. 别忘了加入1.

事实上, 对于[l,r], 只用加入l和r+1. 因为, 对于操作相同的一个区间, 我们关心的最小值.

#define NDEBUG
#include <bits/stdc++.h>
// #define rep per
#define ALL 1, 0, top-1
#define LEFT o*2, l, m
#define RIGHT o*2+1, m+1, r

using namespace std;

typedef long long ll;

const int N = 6 * 1e5 + 1;

struct Seg
{
	int cnt[N*4];
	short cov[N*4];
	bool inv[N*4];

	void up(int o)
	{
		cnt[o] = cnt[o*2] + cnt[o*2 + 1];
	}

	void down_cover(int o, int w, short v)
	{
		inv[o] = 0;
		cov[o] = v;
		cnt[o] = v > 0 ? w : 0;
	}

	void down_inverse(int o, int w)
	{
		if (cov[o])
		{
			cov[o] = cov[o] > 0 ? -1 : 1;
			cnt[o] = cov[o] > 0 ? w : 0;
		}
		else
		{
			inv[o] ^= 1;
			cnt[o] = w - cnt[o];
		}
	}

	void down(int o, int w)
	{
		int r = w/2, l = w-r;
		if (cov[o])
		{
			down_cover(o*2, l, cov[o]);
			down_cover(o*2+1, r, cov[o]);
			cov[o] = 0;
		}
		else if (inv[o])
		{
			down_inverse(o*2, l);
			down_inverse(o*2+1, r);
			inv[o] = 0;
		}
	}

	void set(int L, int R, short v, int o, int l, int r)
	{
		if (L <= l && r <= R) return down_cover(o, r-l+1, v);
		down(o, r-l+1);
		int m = (l+r)/2;
		if (L <= m) set(L, R, v, LEFT);
		if (R > m) set(L, R, v, RIGHT);
		up(o);
	}

	void invert(int L, int R, int o, int l, int r)
	{
		if (L <= l && r <= R) return down_inverse(o, r-l+1);
		down(o, r-l+1);
		int m = (l+r)/2;
		if (L <= m) invert(L, R, LEFT);
		if (R > m) invert(L, R, RIGHT);
		up(o);
	}
	
	int query(int o, int l, int r)
	{
		if (l == r) return assert(!cnt[o]), l;
		down(o, r-l+1);
		int m = (l+r)/2;
		return cnt[o*2] < m-l+1 ? query(LEFT) : query(RIGHT);
	}
} T;

struct Op
{
	int o;
	ll l, r;
} Q[N/6];

int top;
ll h[N];

inline void add(ll x)
{
	h[top++] = x;
	h[top++] = x+1;
	if (x > 1) h[top++] = x-1;
}

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	h[top++] = 1;
	rep (i, 0, n)
	{
		cin >> Q[i].o >> Q[i].l >> Q[i].r;
		add(Q[i].l);
		add(Q[i].r);
	}
	sort(h, h+top);
	top = unique(h, h+top) - h;
	rep (i, 0, n)
	{
		Op& q = Q[i];
		int l = lower_bound(h, h+top, q.l) - h, r = lower_bound(h, h+top, q.r) - h;
		if (q.o <= 2) T.set(l, r, q.o == 1 ? 1 : -1, ALL);
		else T.invert(l, r, ALL);
		cout << h[T.query(ALL)] << endl;
	}
	return 0;
}