【Codeforces 802L】Send the Fool Further! (hard)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf

解题报告

这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$

Code

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

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[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;
}

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

inline int REV(int x) {
	int ret = 1, t = MOD - 2;
	for (; t; x = (LL)x * x % MOD, t >>= 1) {
		if (t & 1) {
			ret = (LL)ret * x % MOD;
		}
	}
	return ret;
}

void solve(int w, int f) {
	if (d[w] > 1) {
		a[w] = -1;
		for (int i = head[w]; i; i = nxt[i]) {
			b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
			if (to[i] != f) {
				solve(to[i], w);
			}
		}
		if (w != f) {
			b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
			a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
		}
	}
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		AddEdge(u + 1, v + 1, read());
	}
	solve(1, 1);
	int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
	ans = (ans + MOD) % MOD;
	cout<<ans<<endl;
	return 0;
}

【BZOJ 3517】翻硬币

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3517
神犇题解Ⅰ:http://blog.csdn.net/lych_cys/article/details/50363106
神犇题解Ⅱ:http://foreseeable97.logdown.com/posts/193171-bzoj3517-coins

解题报告

一道非常妙妙的题目啊!虽然没做出来 QwQ

我们先来明确两个结论:
1. 首先一个格子要么被翻一次,要么不被翻
2. 其次全部变白和全部变黑是互逆的,所以求出一个可以推出另一个。所以我们只考虑求全部变白的情况

我们考虑设$b_{i,j}$表示最终对没对$(i,j)$这个格子进行操作
于是我们可以得到$n^2$个方程,因为只有$n^2$个变量
所以我们可以用高斯消元在$O(n^3)$的时间复杂度内求解

但我我们发现题目中提到的$n$为偶数这个条件并没有用到
现在考虑优化高斯消元:

设$a_{i,j}$为这个格子的原始状态
设$xb_i$表示第$i$行所有$b_{i,j}$异或起来,$xa_i$表示第$i$行所有$a_{i,j}$异或起来
设$yb_i$表示第$i$列所有$b_{i,j}$异或起来,$ya_i$表示第$i$列所有$a_{i,j}$异或起来
于是我们可以得到$b_{i,j} \oplus xb_j \oplus yb_i = a_{i,j}$,设为一号方程
考虑我们求$b_{i,j}$,那么我们把所有第$j$行和第$i$列的方格对应的一号方程异或起来
之后我们发现因为$n$为偶数,所以等式变为$b_{i,j}=ya_i \oplus xa_j \oplus a_{i,j}$

然后我们惊讶地发现问题已经解决了?
第一次手动解异或方程组,感觉非常玄妙啊!

Code

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

const int N = 1009;

int n,ans,x[N],y[N],a[N][N];
char pat[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 j=1;j<=n;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) {
			a[i][j] = pat[i] - '0';
			x[i] ^= a[i][j];
			y[j] ^= a[i][j];
		}
	}
	for (int j=1;j<=n;j++) {
		for (int i=1;i<=n;i++) {
			ans += x[i] ^ y[j] ^ a[i][j];	
		}
	} 
	printf("%d\n",min(ans, n * n - ans));
	return 0;
}

【BZOJ 3569】DZY Loves Chinese II

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3569
数据生成器:http://paste.ubuntu.com/23227745/

这个题,是我到目前为止,做过的最妙的一道题
没有之一

给每一个非树边搞一个权值
然后亦或到它所覆盖的每一条树边上去
考虑不联通的情况:删掉了一条树边和所有覆盖他的非树边
及一个子集的亦或和为0
于是像求线性基一样,判一下是否线性无关即可

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

const int N = 100000+9;
const int M = 1000000+9;
const int MOD = 9999971; 
const int SGZ = 40;

int head[N],nxt[M],to[M],n,m,q,val[M];
int vis[N],c[SGZ],cnt,bas[SGZ],sym[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;
}

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

void DFS1(int w, int f) {
	vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (vis[to[i]]) {
			int W = rand()*(rand()%MOD); val[i] ^= W; val[i^1] ^= W;
			sym[w] ^= W; sym[to[i]] ^= W;	
		} else DFS1(to[i],w);
	}
}

void DFS2(int w, int f) {
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && !val[i]) 
		DFS2(to[i], w), val[i] ^= sym[to[i]], 
		val[i^1] ^= sym[to[i]], sym[w] ^= sym[to[i]];
}

inline bool update(int w) {
	for (int i=0,tmp=val[w];i<=30;i++) if (tmp&(1<<i)) {
		if (!bas[i]) {bas[i] = tmp; return false;}
		else {tmp ^= bas[i]; if (!tmp) return true;}
	} return val[w]?false:true;
}

int main(){
	srand(9999971); n = read(); m = read(); 
	for (int i=1;i<=m;i++) Add_Edge(read(),read());
	DFS1(1,1); DFS2(1,1);
	for (int q=read(),k,tag;q;q--) {
		k = read(); tag = 1; memset(bas,0,sizeof(bas));
		for (int i=1;i<=k;i++) c[i] = read()^cnt;
		for (int i=1;i<=k && tag;i++) if (update(c[i]*2)) puts("Disconnected"), tag = 0;
		if (tag) puts("Connected"), cnt++;
	}
	return 0;
}

【SOJ 1718】特工

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/08/216378216437812.png
题解传送门:http://oi.cyo.ng/wp-content/uploads/2016/08/123478756.png
OJ传送门:http://oi.cdshishi.net:8080/Problem/1718

考试的时候,看一眼数据范围
马上反应过来开是FFT,而且坚信是FFT
结果后来没想出来,考完试还被lcr给D了………
结果最后一看,真™是FFT!

这个题,看一眼马上想到高斯消元
于是考试的时候就写了O(n^3)的高斯消元

后来讲题的时候,说到其实就是一个矩阵求逆,我很赞同
于是就来补O(n^3)的矩阵求逆啦!

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

const int MAXN = 3000;
const double EPS = 1e-8;

int n;
double mat[MAXN*2][MAXN],vout[MAXN],arr[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;
}

#define lowbit(x) ((x)&-(x))
inline int bitcount(int w){
	int ret = 0;
	while (w) ret++, w -= lowbit(w);
	return ret;
}

int LCA(int a, int b){
	if (!b) return a;
	else return LCA(b,a%b);
}

inline void Get_Reverse_Matrix(){
	for (int i=1,w;i<=n;i++) {
		for (w=i;w<=n;w++) if (mat[i+n][w]) break;
		for (int j=1;j<=n*2;j++) swap(mat[j][w], mat[j][i]);
		if (abs(mat[i+n][i]) < EPS) continue;
		else for (int j=1;j<=n;j++) if (abs(mat[i+n][j]) > EPS && j != i) {
			double tmp = mat[i+n][j]/mat[i+n][i];
			for (int k=1;k<=n*2;k++) mat[k][j] -= mat[k][i]*tmp;
		}
		double tmp = mat[i+n][i];
		for (int j=1;j<=n*2;j++) mat[j][i] /= tmp;
	}
}

int main(){
	n = read(); 
	for (int i=1;i<=n;i++) arr[i] = read();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) 
		mat[i+n][j] = (bitcount((i-1|j-1)^i-1)+1) % 2;
	for (int i=1;i<=n;i++) mat[i][i] = 1;
	Get_Reverse_Matrix();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) 
		vout[i] += mat[i][j]*arr[j];
	for (int i=1;i<=n;i++) printf("%d ",(int)(vout[i]+EPS));
	return 0;
}

std是应用数据特点,把矩阵求逆给搞到了O(n^logn)
我就不写程序啦,反正SOJ代码可以看

—————————— UPD 2017.7.3 ——————————
仔细想一想,似乎按二进制分治也可以做?

【BZOJ 1923】[Sdoi2010] 外星千足虫

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1923
数据生成器:http://paste.ubuntu.com/18996088/

今天在做高斯消元的专题。一看这题,欸,这不高斯消元求解异或方程组的板题吗? (~ ̄▽ ̄)→))* ̄▽ ̄*)o
于是写了一写,果然是板题。然而我想只有我这种纸张才会因为把结果输反了而wa了半天吧?QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

const int MAXN = 1000+9;

int n,m,mat[MAXN][MAXN],tmp[MAXN],cnt;
char pat[MAXN],tag[MAXN];

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

inline bool update(){
	for (int i=1;i<=n;i++) if (tmp[i]){
		if (!tag[i]) {
			tag[i] = 1; cnt++;
			for (int j=1;j<=n+1;j++) 
				mat[j][i] = tmp[j];
			return cnt == n;
		} else for (int j=1;j<=n+1;j++) tmp[j] ^= mat[j][i];
	}
	return cnt == n;
}

inline void output(int k){
	printf("%d\n",k);
	for (int i=n;i;i--){
		int ans = mat[n+1][i];
		for (int j=i+1;j<=n;j++)
			ans ^= mat[j][i];
		if (ans) tag[i] = 1;
		else tag[i] = 0;
		for (int j=i-1;j;j--)
			mat[i][j] *= ans;	
	}
	for (int i=1;i<=n;i++) 
		if (tag[i]) puts("?y7M#");
		else puts("Earth");
}

int main(){
	scanf("%d%d",&n,&m);
	for (int k=1;k<=m;k++){
		scanf("%s",pat+1); tmp[n+1]=read();
		for (int i=1;i<=n;i++)
			tmp[i] = pat[i]-'0';
		if (update()) output(k), exit(0);
	}
	puts("Cannot Determine\n");
	return 0;
} 

PS:这份代码是在线的做法,看题解,貌似离线也是可以做的。

【BZOJ 4269】再见Xor

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4269
离线版题目:http://paste.ubuntu.com/18971803/

这个题目,拿到以后,一脸懵逼啊QAQ,想拿BFS乱搞一搞,估计会T,结果还是可耻地看了题解
高斯消元求线性基QAQ,又没有学过QAQ,I well vegtable are (T_T)
其实也不难,每一个数的二进制看成方程组,然后上高斯消元。
求出线性基之后,全部^起来就是最大值,找一个最小的^一下就是次小值

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000+9;

int n,arr[MAXN],cnt;

inline void Gauss(){
	for (int k=31;k;k--){
		int w = 1<<(k-1), pos;
		for (pos=cnt+1;pos<=n;pos++) 
			if (arr[pos]&w) break;
		if (pos==n+1) continue;
		else {
			swap(arr[++cnt], arr[pos]);
			for (int i=1;i<=n;i++)
				if (i!=cnt && (arr[i]&w))
					arr[i] ^= arr[cnt];
		}
	}	
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&arr[i]);
	Gauss(); int vout = 0;
	for (int i=1;i<=cnt;i++) vout ^= arr[i];
	printf("%d ",vout);
	printf("%d\n",vout ^= arr[cnt]);
	return 0;
}

好像还有一种方法,写法跟在线求解亦或方程组很像。
但感觉不如直接高斯消元优雅,且时间复杂度相同,所以就不贴代码啦!

【BZOJ 1770】[Usaco2009 Nov] lights 燈

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1770
离线版题目:http://paste.ubuntu.com/18956597/
数据生成器:http://paste.ubuntu.com/18956646/

首先,这道题状态压缩的方法很显然,但是状态太多了,会T(然而黄学长说:折半搜索也可过QAQ)
然后开始想高斯消元。一开始不知道高斯消元能解异或方程组,于是想了两个多小时QAQ
然后去补了解异或方程组,一开始对自由元的理解有问题,正确的应该是:
自由元可以随便定,每一组不同的自由元可以导出一组方程的解
换一句话说,消完元之后,非自由元的未知数的解,并非最终解

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 50;
const int INF = 50;

int n,m,vout=INF;
int mat[MAXN][MAXN],tag[MAXN];

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

inline void Gauss(){
	for (int k=1,w=k;k<n;w=++k){
		for (int i=k+1;i<=n&&!mat[k][w];i++) if (mat[k][i]) w = i;
		for (int i=1;i<=n+1;i++) swap(mat[i][w],mat[i][k]);
		for (int i=k+1;i<=n;i++) if (mat[k][i]) 
			for (int j=1;j<=n+1;j++) mat[j][i] ^= mat[j][k];
	}
}

void DFS(int w, int cost){
	if (cost >= vout) return;
	else if (!w) vout = min(vout, cost);
	else {
		if (mat[w][w]) {
			int t = mat[n+1][w];
			for (int i=w+1;i<=n;i++)
				if (mat[i][w]) t ^= tag[i];
			tag[w] = t;
			DFS(w-1, cost+(t?1:0));
		} else {
			tag[w] = 1;
			DFS(w-1, cost+1);
			tag[w] = 0;
			DFS(w-1, cost);
		}
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) 
		mat[i][i] = 1, mat[n+1][i] = 1;
	for (int i=1,a,b;i<=m;i++){
		a = read(); b = read();
		mat[a][b] = mat[b][a] = 1;
	}
	Gauss(); 
	DFS(n,0);
	printf("%d\n",vout);
	return 0;
} 

【BZOJ 1013】[JSOI2008] 球形空间产生器sphere

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1013
离线版题目:http://paste.ubuntu.com/18938759/

高斯消元第一题! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
1A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
设n维坐标,然后加上一个半径,刚好n+1个未知数
然后一个坐标一个方程,刚好n+1个方程
然后就是高斯消元啦!

#include<iostream>
#include<cstdio>
#define fabs(x) ((x)<0?-(x):(x))
using namespace std;

const int MAXN = 20;

double mat[MAXN][MAXN];
int n;

inline void Gauss(){
	for (int k=1;k<=n;k++){
		int w = k;
		for (int i=k+1;i<=n+1;i++) if (fabs(mat[k][w]) < fabs(mat[k][i])) w = i;
		for (int i=1;i<=n+2;i++) swap(mat[i][k],mat[i][w]);
		for (int i=k+1;i<=n+1;i++){
			double t = mat[k][i]/mat[k][k];
			for (int j=1;j<=n+2;j++)
				mat[j][i] -= mat[j][k]*t;
		}
	}
	for (int k=n+1;k;k--){
		for (int i=n+1;i>k;i--) mat[n+2][k] -= mat[i][k]*mat[n+2][i];
		mat[n+2][k] /= mat[k][k]; 
	}
}

int main(){
	scanf("%d",&n);
	for (int j=1;j<=n+1;j++){
		for (int i=1;i<=n;i++)
			scanf("%lf",&mat[i][j]),
			mat[n+2][j] -= mat[i][j]*mat[i][j],
			mat[i][j] *= -2.0;
		mat[n+1][j] = 1;
	}
	Gauss();
	for (int i=1;i<n;i++) printf("%.3lf ",mat[n+2][i]);
	printf("%.3lf",mat[n+2][n]);
	return 0;
}