1
30
2018
0

Thuwc2018游记

Day0:

呱呱高铁晚点快6个小时,到宾馆已经快累死了。

Day1:

试机真傻逼。

中饭真难吃。

然后下午考试。

T1怎么这么可做?风格不对啊?

那我拿拿暴力分100+50+50岂不是很滋滋,咦T3交上去怎么A了呀?

pretest真水,希望不要GG。

晚上无所事事地漫步在雅礼校园,寝室没网没电没人。

Day2:

上午无所事事。

考试推迟半小时?

然后下午考试。

T1好像不太会啊?T2好难啊?T3大鬼畜啊?

出考场后有人告诉我,T3行和列是反的?那我丢了30分啊?

我要回家种田了,你们再也见不到我了QAQ

Day3:

面试怎么还让读英语啊T_T

我好傻逼啊,d2t1我做法已经和正解没区别了为啥不写正解啊?

我回家种田了,你们再也见不到我了。

 

你们再也见不到我了。

你们再也见不到我了。

你们再也见不到我了。

Category: 垃圾 | Tags:
1
29
2018
0

TC-SRM-545-div1-975

考虑每位独立,容斥即可。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
LL ans,p2[55];
int n,m,tmp[55],fa[55],a[55][55];
bool b[55];
int getf(int x){
	return fa[x]==x?x:fa[x]=getf(fa[x]);
}
void dfs(int x,int s,int blk){
	if (x>m){
		if (s&1) ans-=p2[blk]-2; else ans+=p2[blk]-2;
		return;
	}
	int FA[n+1];
	FOR(i,1,n) FA[i]=fa[i];
	b[x]=0;
	dfs(x+1,s,blk);
	FOR(i,1,n) fa[i]=FA[i];
	b[x]=1;
	FOR(j,2,a[x][0]){
		int y=a[x][j];
		int X=getf(a[x][1]),Y=getf(y);
		if (X!=Y) fa[X]=Y,--blk;
	}
	dfs(x+1,s+1,blk);
}
class SetAndSet{
	public:
	long long countandset(vector<int> A){
		n=A.size();
		p2[0]=1;
		FOR(i,1,n) p2[i]=p2[i-1]*2;
		m=0;
		FOR(i,0,19){
			FOR(j,1,n) tmp[j]=(A[j-1]>>i)&1;
			bool ok=1;
			FOR(j,2,n) if (tmp[j]!=tmp[1]) ok=0;
			if (ok) continue;
			++m;
			FOR(j,1,n) if (!tmp[j]) a[m][++a[m][0]]=j;
		}
		FOR(i,1,n) fa[i]=i;
		dfs(1,0,n);
		return ans;
	}
}cwy;
Category: TC | Tags:
1
28
2018
0

TC-SRM-590-div1-1000

原图相当于一些限制,要最小化代价,最小割模型。

Category: TC | Tags:
1
28
2018
0

TC-SRM-647-div1-950

删掉垃圾点后,对于(u,v,cost)连上(u,v,cost)和(v,u,INF),即可保证存在到达关系的两条边不会同时被割。

Category: TC | Tags:
1
27
2018
0

TC-SRM-491-div1-900

二分答案后跑费用流。

Category: TC | Tags:
1
26
2018
0

TC-SRM-494-div1-1000

知道了两行一列之后剩下的直接表示出来,然后列方程,高斯消元。

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
#define pi acos(-1)
typedef pair<int,int> pa;
typedef long double ld;
const int MO=123456789;
const int dx[]={0,-1,-2,-1,-2,1,1,2,2};
const int dy[]={0,-2,-1,2,1,-2,2,-1,1};
bitset<455> o[155][155];
bitset<455> a[455];
int n,m,N,M;
class KnightsOut{
	public:
	int guass(){
		int now=0;
		FOR(i,1,m){
			int t=0;
			FOR(j,now+1,n)
				if (a[j][i]) t=j;
			if (!t) continue;
			++now;
			swap(a[t],a[now]);
			FOR(j,now+1,n)
				if (a[j][i]) a[j]^=a[now];
		}
		/*
		puts("");
		FOR(i,1,n){
			FOR(j,1,m+1) cout<<a[i][j];
			puts("");
		}
		*/
		FOR(i,now+1,n)
			if (a[i][m+1]) return 0;
		int ans=1;
		FOR(i,1,m-now) ans=ans*2%MO;
		return ans;
	}
	int count(int NN, int MM){
		N=NN,M=MM;
		if (N<2) return 1;
		m=0;
		FOR(i,1,N)
			FOR(j,1,M)
				if (i<=2 || j<=1){
					++m;
					o[i][j][m]=1;
				}
		FOR(i,1,N-2)
			FOR(j,1,M-1){
				FOR(d,0,7){
					if (i+dx[d]<1 || i+dx[d]>N || j+dy[d]<1 || j+dy[d]>M) continue;
					o[i+2][j+1]^=o[i+dx[d]][j+dy[d]];
				}
				o[i+2][j+1][m+1]=o[i+2][j+1][m+1]^1;
			}
		/*
		FOR(i,1,N)
			FOR(j,1,M){
				FOR(k,1,m+1) cout<<o[i][j][k];
				puts("");
			}
		*/
		FOR(i,1,N)
			FOR(j,1,M)
				if (i>N-2 || j>M-1){
					++n;
					FOR(d,0,8){
						int x=i+dx[d],y=j+dy[d];
						if (x<1 || x>N || y<1 || y>M) continue;
						a[n]^=o[x][y];
					}
					a[n][m+1]=a[n][m+1]^1;
				}
		/*
		puts("");
		FOR(i,1,n){
			FOR(j,1,m+1) cout<<a[i][j];
			puts("");
		}
		*/
		return guass();
	}
}cwy;
Category: TC | Tags:
1
25
2018
0

TC-SRM-620-div1-800

高斯消元求自由元

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef pair<int,int> pa;
const int MO=1e9+7;
int a[1111][1111],n,p[1111][1111],m,tot,N,now;
map<int,int> M;
vector<int> v[100010];
class PerfectSquare{
	public:
	int guass(){
		now=0;
		FOR(i,1,N){
			int w=0;
			for (int j=now+1;j<=m;j++)
				if (a[j][i]==1){
					w=j;
					break;
				}
			if (!w) continue;
			++now;
			FOR(j,1,N+1) swap(a[w][j],a[now][j]);
			FOR(j,now+1,m)
				if (a[j][i]){
					FOR(k,1,N+1) a[j][k]^=a[now][k];
				}
		}
		FOR(i,now+1,m)
			if (a[i][N+1]!=0) return 0;
		int t=N-now;
		LL ans=1;
		while (t--) ans=(ans<<1)%MO;
		return (int)ans;
	}
	int ways(vector <int> x){
		n=sqrt(x.size());
		N=n*n;
		int t=0;
		tot=0;
		FOR(i,1,n)
			FOR(j,1,n){
				int A=x[t];
				p[i][j]=++t;
				for (int k=2;k*k<=A;++k){
					int cnt=0;
					while (A%k==0) cnt^=1,A/=k;
					if (cnt){
						if (M.find(k)==M.end()) M[k]=++tot;
						v[M[k]].pb(t);
					}
				}
				if (A>1){
					if (M.find(A)==M.end()) M[A]=++tot;
					v[M[A]].pb(t);
				}
			}
		m=0;
		FOR(i,1,n){
			++m;
			FOR(j,1,n)
				a[m][p[i][j]]=1;
			a[m][N+1]=1;
		}
		FOR(j,1,n){
			++m;
			FOR(i,1,n)
				a[m][p[i][j]]=1;
			a[m][N+1]=1;
		}
		FOR(i,1,tot){
			++m;
			for (int j=0;j<v[i].size();++j){
				int x=v[i][j];
				a[m][x]=1;
			}
		}
		return guass();
	}
}cwy;
Category: TC | Tags:
1
25
2018
0

TC-SRM-580-div1-1000

f[i][j]表示走到(i,j)的....

转移分3种

1.拦的人硬点

2.走的人拐弯一次

3.走的人拐弯两次

奥妙重重得过了。

考虑正确性更显然的做法,容易知道一行里面拦的墙是连续的一段,状态改成3维后容易转移。

Category: TC | Tags:
1
20
2018
0

CF674G

查询区间出现次数>1/k的数,不断消除k个不同的数即可。

http://codeforces.com/contest/674/submission/34350749

Category: CF | Tags:
1
18
2018
0

欧拉回路

http://uoj.ac/submission/219661

http://uoj.ac/submission/219665

 

Category: 板子 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com