【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;
} 

【NOI六连测】[D3T1] 炉石

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版数据:http://paste.ubuntu.com/18386939/
数据传送门:http://pan.baidu.com/s/1i5fN2IT

首先,没玩过炉石的同学表示很受伤:考试的时候一直以为95颗星就算赢
其次,不会概率DP or 高斯消元的同学表示很受伤:因为要爆零啊!QAQ
好吧,高斯消元不会,所以来说一说lcr用的模拟吧:
设arr[i][j]表示走了k步后,位于当前有i颗星,已经连胜j场这个状态的概率
于是转移一下,再加上P>0.48保证了最多的步数就是1000多的样子
所以我们暴力转移1e5次的样子,基本上其他地方的DP值就为0了。
然后就是NOIP的模拟题水平的代码就可以了! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
哎,概率太弱不对,是完全不会
迟早是要找个时间好好学一学啊!

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

const int MAXN = 100;
const int T = 100000;

double win,lose,arr[MAXN][4],tmp[MAXN][4],ans;
int n;

int main(){
	freopen("hearthstone.in","r",stdin);
	freopen("hearthstone.out","w",stdout);
	scanf("%d%lf",&n,&win);
	lose = 1 - win;
	arr[96-n][0] = 1;
	for (int k=1;k<=T;k++){
		for (int i=0;i<=10;i++){
			tmp[i][0] += arr[i][0]*lose;
			tmp[i][0] += arr[i][1]*lose;
			tmp[i][0] += arr[i][2]*lose;
			tmp[i][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=11;i<=70;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=71;i<=95;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+1][3] += arr[i][2]*win;
			tmp[i+1][3] += arr[i][3]*win;
		}
		ans += (tmp[96][0]+tmp[96][1]+tmp[96][2]+tmp[96][3])*k; 
		memcpy(arr,tmp,sizeof(tmp));
		memset(tmp,0,sizeof(tmp));
	}
	printf("%.2lf\n",ans);
	return 0;
} 

【NOI六连测】[D1T2] 过河

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18247944/
数据传送门:http://pan.baidu.com/s/1nvGnd8H

这个题目,第一眼看到的时候,一脸懵逼
后来仔细想了一想,成了二脸懵逼QAQ
于是写了30分的暴力,还好没写挂……

后来听题解,感觉很神
首先是结论:最优解时,所有的F(Xy)的斜率相等
这个按照原教的说法:
如果斜率不等,那么将斜率较低的河流的时间分一点给斜率较高的河流
我们就可以走得更远!
还是比较显然的吧!但是像我这种沙茶在考试的时候肯定想不出来QAQ
接下来就是怎么让斜率一样了。
原教又给了一个非常神的办法:
根据F’(Xy)的表达式可以得到,t随F’(Xy)的增加而减少,所以我们可以二分统一的斜率,然后判一判时间知否足够。
详细的推导如下:
\(
\begin{array}{l}
\partial (({V_i} + \sqrt {{u^2} – \frac{{W_i^2}}{{{t^2}}})} \cdot t) = \partial ({V_i} \cdot t) + \partial (\sqrt {{u^2} \cdot {t^2} – W_i^2} )\\
= {V_i} + \partial ({u^2} \cdot {t^2}) \cdot \frac{{0.5}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }} = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}
\end{array}
\)
不妨设\(k = {V_i} + \frac{{{u^2} \cdot t}}{{\sqrt {{u^2} \cdot {t^2} – W_i^2} }}\)
则有\(\begin{array}{l}
{u^4} \cdot {t^2} = {(k – {V_i})^2} \cdot ({u^2} \cdot {t^2} – W_i^2)\\
{t^2} \cdot ({u^4} – {(k – {V_i})^2} \cdot {u^2}) = – {(k – {V_i})^2} \cdot W_i^2\\
t = \sqrt {\frac{{{{(k – {V_i})}^2} \cdot W_i^2}}{{{{(k – {V_i})}^2} \cdot {u^2} – {u^4}}}}
\end{array}\)
所以t随k的增大而减小,且\(k \in (\max ({V_i}) + u, + \infty ]\)
之后代码就没有什么难度啦!

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define LD long double
using namespace std;

const int MAXN = 50+9;
const LD EPS = 1e-15;

int n;
LD v[MAXN],w[MAXN],ans[MAXN];
LD disx,MXv,u,t;

inline LD cal(LD k){
	LD ret = 0; 
	for (int i=1;i<=n;i++){
		LD r = (k-v[i])*(k-v[i]);
		LD t = sqrt(r*w[i]*w[i]/(r*u*u-u*u*u*u));
		ans[i] = t; ret += t;
	}
	return ret;
}

inline double GetAns(){
	LD ret = 0;
	for (int i=1;i<=n;i++){
		LD tmp = sqrt(u*u*ans[i]*ans[i]-w[i]*w[i]);
		ret += tmp+v[i]*ans[i];
	}
	return (double)sqrt(ret*ret+disx*disx);
}

int main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	scanf("%d",&n); cin>>u>>t;
	for (int i=1;i<=n;i++) cin>>w[i]>>v[i],
		disx+=w[i], MXv=max(MXv,v[i]);
	if (disx/u > t) {printf("-1\n");exit(0);}
	
	LD l=u+MXv,r=1e12,mid;
	while (r-l > EPS){
		mid = (l+r)/2.0;
		if (cal(mid) < t) r = mid;
		else l = mid;
	} 
	
	printf("%.3lf\n",GetAns());
	for (int i=1;i<=n;i++) printf("%.3lf ",(double)ans[i]);
	return 0;
} 

另外,此题卡精度QAQ,long double的EPS都得开到1e-15

【SOJ 256】[NOIP2012] 同余方程

题目传送门:http://oi.cdshishi.net:8080/Problem/256
离线版题目:http://paste.ubuntu.com/17895904/

求逆元的板题,顺便补了exGCD,么么哒!

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

inline void exGCD(int a, int b, int &x, int &y){
	if (b==0) {x=1;y=0;}
	else {exGCD(b,a%b,y,x);y-=(a/b)*x;}
}

int main(){
	int a,b,x,y;
	scanf("%d%d",&a,&b);
	exGCD(a,b,x,y);
	printf("%d\n",((x%b)+b)%b);
	return 0;
}