2017-06-07

Educational Codeforces Round 22

昨天早上打的. 做出ABCE四道题. 以前看到过F题, 但是不知道具体做法......原来对时间分治是这样的. D题......看到过的人比较少, 可能就没有认真想吧......其实并不困难. 题解: 5/5 # A. The Contest n个问题, 解决第i个需要花费ai个单位的时间. 有m个可提交问题的互不相交的时间段, 按顺序给出, 提交问题的用时忽略不计, 且同时可以提交多个问题. 当然, 问题必须解决了才能提交. 问提交所有问题的最短用时, 或报告无解. (1≤n,m≤10^3, 1≤时刻, ai≤10^5)

目标是提交所有问题. 由于提交问题的用时忽略不计, 同时可以提交多个问题, 所以我们可以把题目屯起来, 最后一起交.

int main()
{
	int n, m, s = 0;
	scanf("%d", &n);
	rep (i, 0, n)
	{
		int a;
		scanf("%d", &a);
		s += a;
	}
	scanf("%d", &m);
	rep (i, 0, m)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		if (r >= s)
			return printf("%d\n", max(l, s)), 0;
	}
	puts("-1");
	return 0;
}

B. The Golden Age

给定正整数x,y. 一个正整数n是不幸的, 当且仅当存在自然数a,b使得n=x^a+yb. 给定区间[l,r], 求区间内最多有多少个连续的幸运数. (2≤x,y≤10^18, 1≤l≤r≤10^18)

指数函数的增长是爆炸式的. 我们知道2^60>1018. 不幸的数至多有60*60=3600个. 这启发我们枚举出[l,r]内所有不幸的数, 排序后扫一遍求最大间隔.

乘法可能爆unsigned long long. 我们只需要判断出这种情况, 然后跳出循环. 以前碰到过这个问题......设是正整数, 那么

看到yp同学用对数来判断, 也不失为一个好办法.

我以为60*60等于360, RE一发......

typedef long long ll;

int ptr;
ll a[4000];

inline bool overflow(ll x, ll y)
{
	return x > numeric_limits<ll>::max() / y;
}

int main()
{
	ios::sync_with_stdio(false);
	ll x, y, l, r, ans = 0;
	cin >> x >> y >> l >> r;
	ll u = 1;
	rep (i, 0, 61)
	{
		ll v = 1;
		rep (j, 0, 61)
		{
			if (u + v > r) break;
			if (u + v >= l)
				a[ptr++] = u + v;
			if (overflow(v, y)) break;
			v *= y;
		}
		if (overflow(u, x)) break;
		u *= x;
	}
	a[ptr++] = l-1;
	a[ptr++] = r+1;
	sort(a, a+ptr);
	rep (i, 1, ptr)
		ans = max(ans, a[i] - a[i-1] - 1);
	cout << ans << endl;
	return 0;
}

C. The Tag Game

一棵n个节点的树, A在1号点, B在x号点 (x≠1). 两人轮流操作, B先走. 一次操作中, 可以选择移动到一个相邻节点, 也可以选择原地不动. A和B到同一个点后, 游戏结束. B想最大化两人的总操作数, A想最小化两人的总操作数. 问游戏在多少次操作后结束. (2≤n≤2*10^5)

以1号点为根.

看起来像是博弈, 再一想, 发现两者的策略都很简单: - B向上爬几步 (可能是0步), 走到某棵子树的最深节点y上, 在那里待着. 需要保证向上爬的时候不被A抓到. - A追着B跑.

操作数等于1到y的距离的两倍.

那么, 我们到底是要最大化操作数, 还是最小化操作数呢? B是先手. 对于B的每种策略, A的策略是确定的. 我们假设B足够机智, 所以应该取最大值.

const int N = 2e5 + 1;

int fa[N], d[N];
bool ban[N];
vector<int> adj[N];

void dfs(int u)
{
	for (auto v : adj[u])
		if (v != fa[u])
		{
			fa[v] = u;
			d[v] = d[u] + 1;
			dfs(v);
		}
}

int dfs_2(int u)
{
	int r = d[u];
	for (auto v : adj[u])
	{
		if (v != fa[u] && !ban[v])
			r = max(dfs_2(v), r);
	}
	return r;
}

int main()
{
	int n, x, ans = 0;
	scanf("%d%d", &n, &x);
	rep (i, 0, n-1)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	for (int y = x; y; y = fa[y])
		ban[y] = true;
	int y = x;
	rep (i, 0, (d[x]-1)/2+1)
	{
		ans = max(ans, dfs_2(y));
		y = fa[y];
	}
	printf("%d\n", 2*ans);
	return 0;
}

D. Two Melodies

在一个长度为n的正整数序列中找两个非空子序列, 要求相邻两个数相差1或者模7同余. 求两个子序列的长度之和的最大值. (2≤n≤5000, 1≤ai≤10^5)

设为一个子序列以位置结尾, 另一个以位置结尾, 且 $Missing \left or extra \right[1,\max\left\\{i,j\right\\}]$ 已经考虑过, 长度之和的最大值. 不妨只考虑的情形. 当 , ; , .

首先来说明状态这样定义的合理性: 对于任意一种合法方案 $Missing \left or extra \right\left\\{x_1,\ldots,x_p\right\\}$ , $Missing \left or extra \right\left\\{y_1,\ldots,y_q\right\\}$ , 我们总能按以下过程转移

x = [(x[i], 0) for i in range(len(x))]
y = [(y[i], 1) for i in range(len(y))]
z = sorted(x + y)
go(0, 0)
i = 0
j = 0
for a,b in range(z):
    if b:
        j = a
    else:
        i = a
    go(i, j)

可以分析得到, 当, 最后移动的一定是 , 因此 $Missing \left or extra \right f(i,j) = 1 + \max\left\\{f(i,k)|0\le k < j, k=0\text{ 或 }a_k\bmod 7 = a_j\bmod 7\text{ 或 }|a_k-a_j|=1\right\\}$

令 $Missing \left or extra \right maxnum(i,j,a) = \max\left\\{f(i,k)|0<k<j, a_k=a\right\\}\\\\ maxmod(i,j,a) = \max\left\\{f(i,k)|0<k<j, a_k\bmod 7=a\right\\}$

那么 $Missing \left or extra \right f(i,j) = 1 + \max\left\\{maxnum(i,j,a_j-1), maxnum(i,j,a_j+1), maxmod(i,j,a_j\bmod 7), f(i,0)\right\\}$

时间复杂度降至 . 在外层枚举 , 内层枚举 , 和的前两位都可以滚动.

启发: DP的填表法和刷表法各有千秋......本题前者思考起来更方便. 转移方程还是得写出来, 光yy是不行的.

被hack了一发......应该是之前内层的j从0开始循环的锅.

template<typename T>
inline void upmax(T& x, T v)
{
	x = max(x, v);
}

const int N = 5001, A = 1e5 + 2;
int a[N], dp[N][N], num[A], mod[7];

int main()
{
	int n, ans = 0;
	scanf("%d", &n);
	rep (i, 1, n+1) scanf("%d", a+i);
	
	rep (i, 0, n)
	{
		rep (j, 0, 7) mod[j] = 0;
		rep (j, 1, n+1) num[a[j]] = 0;

		dp[i][0] = dp[0][i];
		rep (j, 1, i)
		{
			dp[i][j] = dp[j][i];
			upmax(num[a[j]], dp[i][j]);
			upmax(mod[a[j]%7], dp[i][j]);
		}
		
		rep (j, i+1, n+1)
		{
			int& now = dp[i][j];
			upmax(now, num[a[j]-1]);
			upmax(now, num[a[j]+1]);
			upmax(now, mod[a[j]%7]);
			upmax(now, dp[i][0]);
			upmax(ans, ++now);
			upmax(num[a[j]], now);
			upmax(mod[a[j]%7], now);
		}
	}

	printf("%d\n", ans);
	return 0;
}

E. Army Creation

给定常数 , 一个长度为的整数序列 $Missing \left or extra \right\left\\{a_i\right\\}$ , 个询问 : 求 $Missing \left or extra \right\sum_a \min\left\\{k, \sum_{i=l}^r [a_i=a]\right\\}$ . 强制在线.

我们做过区间数颜色, 即 . 一种做法是找出每个值前一次出现的位置, 问题转化为, 内有多少小于的数. 推广一下, 找出每个值前第次出现的位置, 即可解决本题.

const int N = 1e5 + 1, NLGN = 18*N;

int b[N], rt[N];
vector<int> c[N];

struct Seg
{
	int ptr, lc[NLGN], rc[NLGN], v[NLGN];
	void insert(int x, int p, int& o, int l, int r)
	{
		o = ++ptr;
		v[o] = v[p] + 1;
		if (l == r) return;
		int m = (l+r)/2;
		if (x <= m)
			insert(x, lc[p], lc[o], l, m), rc[o] = rc[p];
		else
			insert(x, rc[p], rc[o], m+1, r), lc[o] = lc[p];
	}
	int query(int R, int o, int l, int r)
	{
		if (!o) return 0;
		if (r <= R) return v[o];
		int m = (l+r)/2;
		return query(R, lc[o], l, m) + (R > m ? query(R, rc[o], m+1, r) : 0);
	}
} T;		

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	rep (i, 1, n+1)
	{
		int a;
		scanf("%d", &a);
		b[i] = (int)c[a].size() >= k ? c[a][c[a].size()-k] : 0;
		c[a].push_back(i);
		T.insert(b[i], rt[i-1], rt[i], 0, n-1);
	}
	int q, last = 0;
	scanf("%d", &q);
	while (q--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x = (x + last) % n + 1;
		y = (y + last) % n + 1;
		if (x > y) swap(x, y);
		printf("%d\n", last = T.query(x-1, rt[y], 0, n-1) - T.query(x-1, rt[x-1], 0, n-1));
	}
	return 0;
}

F. Bipartite Checking

n个点的无向图, q个操作, 每个操作将一条边的存在性取反, 回答每个操作后原图是否是二分图. (2≤n,q≤10^5)

bzoj 4025. 可以用对时间分治+并查集, 或LCT. 另开一篇文章写吧.