【日常小测】仰望星空

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

我们按照极角序来贪心匹配
不难发现这样一定有解

另外Dinic是不能求这种要求字典序最小的解的
似乎只能用最裸的匈牙利

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
	int x, y, ty;
	inline int dis(const Point &P) {
		return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
	}
}p[N];

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
} 

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline bool DFS(int w) {
	vis[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
			mth[to[i]] = w;
			mth[w] = to[i];
			return 1;
		} 
	}
	return 0;
}

inline int solve() {
	int ret = 0;
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (!mth[i]) {
			memset(vis, 0, sizeof(vis));
			ret += DFS(i);
		}
	}
	return ret;
}

inline void print(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] == mth[w]) {
			vis[w] = vis[to[i]] = 1;
			printf("%d %d\n", w, mth[w]);
			return;
		} else if (!vis[to[i]]){
			print(mth[to[i]]);
		}
	}
}

int main() {
	n = read(); 
	R = read(); R *= R;
	D = read(); D *= D;
	S = 0; T = N - 1;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (p[i].ty = p[i].dis(p[1]) > R) {
			in[++cnt_in] = i;
		} else {
			ot[++cnt_ot] = i;
		}
	}
	for (int ii = 1; ii <= cnt_in; ii++) {
		int i = in[ii], cnt_arr = 0;
		double mx = -PI, mn = PI;
		for (int jj = 1; jj <= cnt_ot; jj++) {
			int j = ot[jj];
			if (p[i].dis(p[j]) <= D) {
				double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
				mx = max(mx, agl);
				mn = min(mn, agl);
				arr[++cnt_arr] = make_pair(agl, j);
			}
		}
		if (mx - mn >= PI) {
			for (int j = 1; j <= cnt_arr; j++) {
				arr[j].first += arr[j].first < 0? PI * 2: 0;
			}
		}
		sort(arr + 1, arr + 1 + cnt_arr);
		for (int j = 1; j <= cnt_arr; j++) {
			AddEdge(i, arr[j].second);
		}
	}
	printf("%d\n", solve() << 1);
	memset(vis, 0, sizeof(vis));
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (mth[i] && !vis[i]) {
			print(i);
		}
	}
	return 0;
}

【Codeforces 734F】Anton and School

相关链接

题目传送门:http://codeforces.com/contest/734/problem/F
官方题解:http://codeforces.com/blog/entry/48397

解题报告

画一画维恩图便容易发现:$(a \ and \ b) + (a \ or \ b) = a + b$
所以$b_i + c_i = \sum\limits_{j = 1}^{n}{a_i + a_j} = na_i + \sum\limits_{j = 1}^{n}{a_j}$
于是有$\sum\limits_{i = 1}^{n}{a_i} = \frac{\sum\limits_{i = 1}^{n}{b_i + c_i}}{2n}$
最后加加减减搞一搞就可以求出$a_i$了

然后就是检查${a_i}$是否符合${b_i}$和${c_i}$
这个按二进制位枚举一下就可以了
总的时间复杂度是:$O(n \log \max(a_i))$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;

int n, a[N], b[N], c[N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline bool check() {
	static int cnt[100];
	for (int i = 1; i <= n; i++) {
		for (int t = 0, v = a[i]; v; v >>= 1, ++t) {
			cnt[t] += v & 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		int tb = 0, tc = 0;
		for (int j = 0, cur = 1; j <= 30; j++, cur <<= 1) {
			tb += (a[i] & cur)? cnt[j] * cur: 0;
			tc += (a[i] & cur)? n * cur: cnt[j] * cur;
		}
		if (tb != b[i] || tc != c[i]) {
			return false;
		}
	}
	return true;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = b[i] = read();
	}
	LL sum = 0;
	for (int i = 1; i <= n; i++) {
		a[i] += (c[i] = read());
		sum += a[i];
	}
	if (sum % (n << 1)) {
		puts("-1");
		exit(0);
	}
	sum /= n << 1;
	for (int i = 1; i <= n; i++) {
		if ((a[i] -= sum) % n) {
			puts("-1");
			exit(0);
		} else {
			a[i] /= n;
		}
	}
	if (!check()) {
		puts("-1");
		exit(0);
	} 
	for (int i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}

【POJ 3922】A simple stone game

相关链接

题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html

解题报告

根据$k = 1$的情况,我们发现在二进制下,我们取走最低位的$1$,对手取不走较高位的$1$
所以如果不是二的整次幂,那么先手必胜

再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和,表示成二进制状态
之后跟据$k = 1$时的推论,我们取走最低位的$1$,对手不能直接取走较高位的$1$

先在我们看我们依赖拆分数列的哪些性质:

存在一种拆分使得选中的项的任意相邻两项超过$k$倍

于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$,其中$j$尽可能大,且$a_j k < a_i$

于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题,叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法,对于某些数据会更优

Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int t = 1, T = read(); t <= T; ++t) {
		n = read(); k = read();
		a[0] = b[0] = x = y = 0;
		while (a[x] < n) {
			a[x + 1] = b[x] + 1;
			for (++x; (LL)a[y + 1] * k < a[x]; ++y);
			b[x] = y? b[y] + a[x]: a[x];
		}
		if (a[x] == n) {
			printf("Case %d: lose\n", t);
		} else {
			int ans = 0;
			for (; n && x; --x) {
				if (n >= a[x]) {
					n -= a[x];
					ans = a[x];
				}
			}
			printf("Case %d: %d\n", t, ans);
		}
	}
	return 0;
}

【LA 5524】[EC2015 Final] Suffixes and Palindromes

相关链接

题目传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5524

题目大意

给出一个串的$sa$数组和$manacher$求出的那个数组
请你构造出一个字典序最小的符合条件的串,可能无解

有$T(T \le 100)$组数据
数组长度$\le 10^5$
时间限制:$4s$

背景

Claris给我安利的题,似乎子问题都会的样子
但合起来就不会了

解题报告

考虑$manacher$的那个数组,实际上是给出了$O(n)$条信息
每一条信息形如:第$i$个字符(不)等于第$j$个字符
如果只有这个条件的话,我们可以搞成几个大连通块,然后贪心

考虑$sa$数组,上午才做了这个题
也可以直接贪心

但这两货直接合在一起,似乎是给出一个差分约束系统
然后让你输出一组可行解,还要让你字典序最小
于是就不会了

但我们还是考虑直接在$SA$数组上贪心
考虑回文等价的影响的话,那实际上是填一位就会影响后面的很多位
似乎想一想,直接贪心会不会使一个区间的两头被值域给卡住
但仔细想一想,即使你给那一个等价类一个大一点的字符,区间的差分序列没有变啊
该卡住的还是会卡住,没被卡住的也不会有问题

于是我们任然在SA数组上贪心,考虑能不能与前一个数相等的时候
不仅考虑$rank$数组的影响,我们还需要考虑回文等价的影响
于是这题就这么做完啦,仍然是一个$O(n)$的贪心

【BZOJ 4319】[CERC2008] Suffix Reconstruction

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4319
神犇题解:http://www.cnblogs.com/Skyminer/p/6414088.html

解题报告

之前在做这个题的时候就听说过这题
但当时想了一会儿,感觉不可做,以为是他们记错题目了 QwQ
今天居然看到原题了,但想了很久,还是只会$O(26 \cdot n \log{n})$

先来说说$O(26 \cdot n \log{n})$的做法吧!
我们可以从上到下单个字符填,就是尽量往小的填,填完以后$O(n)$验证一遍

我们考虑分出不同的地方,因为填了都是比他小的,所以如果冲突,那一定是之前的太大了
但之前的部分已经贪心尽量小地填了,所以之前的肯定不能改小了,只能把当前位改大

所以这么做是对的,时间复杂度:$O(26 \cdot n^2)$
不难发现$SA$数组上一定是一段连续的A,之后一段连续的B。后面也是这样
于是我们可以二分每一个字符地分界点,这样复杂度就是$O(26 \cdot n \log{n})$的了

正解的话,是$O(n)$的,仍然是从小到大贪心
我们考虑计算$height$数组时候那个Trick的正确性证明
如果$rank[sa[i]+1] > rank[sa[i+1]+1]$的话,那么$sa[i]$填的字符一定比$sa[i+1]$小
否则他俩相等也没有关系,因为后面还是会把他们区分出来
于是贪心就可以$O(1)$验证了,于是总的时间复杂度就是线性的了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) rak[sa[i]=read()]=i;
	ans[sa[1]] = 'a';
	for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
	if (ans[n] <= 'z') printf("%s",ans+1);
	else puts("-1");
	return 0;
}

【BZOJ 3749】[POI2015] Łasuchy

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3749
神犇题解:http://blog.csdn.net/Kanosword/article/details/52864357

题解

我看到这题第一眼想到的是贪心
后来又想到了先搞一个方案然后进行调整
最后看了题解才知道这货居然是个DP!
之前见过构造题用线性基来搞的,居然还有直接上DP的 QwQ
i4uxe_lmpcmhcqym45

考虑第i个人的决策,显然只与他左右二人的决策相关
于是从左向右考虑每一个人的决策
于是搞一个O(4*n)的DP并记录一下转移就可以辣!

【Codeforces 708B】Recover the String

题目传送门:http://codeforces.com/problemset/problem/708/B

《论何为血wa》

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 1000000+9;

LL a00,a01,a10,a11,tag,n;
char pat[MAXN];

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

inline int solve(LL w) {
	w *= 2; LL tmp = sqrt(w);
	if (tmp*(tmp+1) != w) {tag++;return 0;}
	else return tmp+1;
}

int main(){
	a00 = read(); a01 = read(); a10 = read(); a11 = read();
	if (!a00 && !a11 && !a01 && !a10) cout<<0<<endl, exit(0);
	else if (a11 && !a00 && !a10 && !a01) {
		if(solve(a11)) {
			a11 = solve(a11);
			for (LL i=1;i<=a11;i++) pat[i] = '1'; 
			cout<<pat+1;
		} else cout<<"Impossible";
	} else if (!a11 && a00 && !a10 && !a01) {
		if(solve(a00)){
			a00 = solve(a00);
			for (LL i=1;i<=a00;i++) pat[i] = '0'; 
			cout<<pat+1;
		} else cout<<"Impossible";
	} else {
		a00 = solve(a00); a11 = solve(a11);
		if (tag) cout<<"Impossible";
		else if (a00*a11 != a01 + a10) cout<<"Impossible";
		else {
			n = a00+a11; int l1 = a10/a00, l2 = a01/a00;
			if (l1*a00 < a10) pat[n-l2-(a10-l1*a00)] = '1';
			if (l2*a00 < a01) pat[l1+(a01-l2*a00)+1] = '1'; 
			for (int i=1;i<=l1;i++) pat[i] = '1';
			for (int i=1;i<=l2;i++) pat[n-i+1] = '1';
			for (int i=1;i<=n;i++) if (!pat[i]) pat[i] = '0';
			printf("%s",pat+1);
		}
	}
	return 0;
}