Shenyang Online 2014

Traversal

lbn187

记录前\(p-2\)个点已经连了几个(0,1,2)个点,状压DP

#include<bits/stdc++.h>
#define M 10007
#define CL(a) memset(a,0,sizeof a)
int T,ca,n,p,o,x,s,i,j,k,v[102],to[3],pw[14],q[14],f[102][188888];
void up(int&x,int y){
	x+=y;
	if(x>=M)x-=M;
}
int get(){
	int v=0;
	for(int i=0;i<p+2;i++)v=v*3+q[i];
	return v;
}
int main(){
	scanf("%d",&T);
	for(pw[0]=i=1;i<=12;i++)pw[i]=pw[i-1]*3;
	for(ca=1;ca<=T;ca++){
		CL(f);
		scanf("%d%d",&n,&p);
		to[0]=1;to[1]=p;to[2]=p+2;
		for(scanf("%d",&k);k--;v[x]=ca)scanf("%d",&x);
		f[0][pw[p+2]-1]=1;
		for(i=0;i<n;i++){
			for(s=0;s<pw[p+2];s++)if(f[i][s]){
				for(o=s,j=p+1;~j;j--)q[j]=o%3,o/=3;
				for(j=p+2;j;j--)q[j]=q[j-1];
				if(v[i+1]==ca){
					q[0]=2;
					if(q[p+2]==2)up(f[i+1][get()],f[i][s]);
					continue;
				}
				q[0]=0;
				if(q[p+2]==2)up(f[i+1][get()],f[i][s]);
				q[0]=1;
				for(j=0;j<3;j++)if(q[to[j]]<2){
					q[to[j]]++;
					if(q[p+2]==2)up(f[i+1][get()],f[i][s]);
					q[to[j]]--;
				}
				q[0]=2;
				for(j=0;j<3;j++)if(q[to[j]]<2){
					q[to[j]]++;
					for(k=j+1;k<3;k++)if(q[to[k]]<2){
						q[to[k]]++;
						if(q[p+2]==2)up(f[i+1][get()],f[i][s]);
						q[to[k]]--;
					}
					q[to[j]]--;
				}
			}
		}
		printf("Case #%d: %d\n",ca,f[n][pw[p+2]-1]);
	}
}

Aki

状压。

#include <bits/stdc++.h>
using namespace std;
const int N = 105, MOD = 10007;
bool ban[N];
int dp[N][177147], P[15];
void upd(int &x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}
int get(int mask, int x) {
	return mask / P[x] % 3;
}
int main() {
	P[0] = 1;
	for (int i = 1; i < 15; ++ i) P[i] = P[i - 1] * 3;
	int T, zzz = 0;
	scanf("%d", &T);
	while (T --) {
		int n, p;
		scanf("%d%d", &n, &p);
		int k;
		scanf("%d", &k);
		for (int i = 1; i <= n; ++ i) ban[i] = 0;
		for (int i = 0; i < k; ++ i) {
			int x;
			scanf("%d", &x);
			ban[x] = 1;
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 1; i <= n; ++ i) {
			for (int mask = 0; mask < P[p + 2]; ++ mask) {
				if (dp[i - 1][mask] == 0) continue;
				if (ban[i]) {
					int new_mask = mask * 3;
					if (get(new_mask, p + 2) == 0) {
						upd(dp[i][new_mask], dp[i - 1][mask]);
					}
				}
				else {
					vector<int> cho = {1, p, p + 2};
					int new_mask = mask * 3 + 2;
					if (get(new_mask, p + 2) == 0) {
						upd(dp[i][new_mask], dp[i - 1][mask]);
					}
					for (int x : cho) {
						new_mask = mask * 3 + 1;
						if (get(new_mask, x) >= 1) {
							new_mask -= P[x];
							if (get(new_mask, p + 2) == 0) {
								upd(dp[i][new_mask], dp[i - 1][mask]);
							}
						}
					}
					for (int a = 0; a < 3; ++ a) {
						for (int b = a + 1; b < 3; ++ b) {
							int x = cho[a], y = cho[b];
							new_mask = mask * 3;
							if (get(new_mask, x) >= 1 && get(new_mask, y) >= 1) {
								new_mask -= P[x] + P[y];
								if (get(new_mask, p + 2) == 0) {
									upd(dp[i][new_mask], dp[i - 1][mask]);
								}
							}
						}
					}
				}
			}
		}
		printf("Case #%d: %d\n", ++ zzz, dp[n][0]);
	}
}

Dividing This Product

Excited Database

Nisiyama

#include <cstdio>
#include <algorithm>

#define _

long long N, Q;

struct node {
    long long sum;
    long long dsum;
    long long rsum;
    long long tag;
    node (long long sum = 0, long long dsum = 0, long long rsum = 0, long long tag = 0) : sum (sum), dsum (dsum), rsum (rsum), tag (tag) {}
} tr[2][1048577];

_ void push (node *tr, long long x, long long l, long long r, long long t) {
    tr[x].sum += t * (r - l + 1);
    tr[x].dsum += t * (l + r) * (r - l + 1) / 2;
    tr[x].rsum += t * (4 * N - l - r + 2) * (r - l + 1) / 2;
    tr[x].tag += t;
}

_ void push_down (node *tr, long long x, long long l, long long r) {
    if (l == r) {
        tr[x].tag = 0;
        return;
    }
    long long m = (l + r) >> 1;
    push (tr, x << 1, l, m, tr[x].tag);
    push (tr, (x << 1) + 1, m + 1, r, tr[x].tag);
    tr[x].tag = 0;
    return;
}

_ void update (node *tr, long long x, long long l, long long r) {
    if (l == r) return;
    tr[x].sum = tr[x << 1].sum + tr[(x << 1) + 1].sum;
    tr[x].dsum = tr[x << 1].dsum + tr[(x << 1) + 1].dsum;
    tr[x].rsum = tr[x << 1].rsum + tr[(x << 1) + 1].rsum;
}

_ void modify (node *tr, long long x, long long l, long long r, long long pl, long long pr, long long d) {
    if (pl > pr) return;
    if (pl <= l && r <= pr) {
        push (tr, x, l, r, d);
        return;
    }
    push_down (tr, x, l, r);
    long long m = (l + r) >> 1;
    if (pl <= m) modify (tr, x << 1, l, m, pl, pr, d);
    if (m + 1 <= pr) modify (tr, (x << 1) + 1, m + 1, r, pl, pr, d);
    update (tr, x, l, r);
}

_ long long query_s (node *tr, long long x, long long l, long long r, long long pl, long long pr) {
    if (pl > pr) return 0;
    if (pl <= l && r <= pr)
        return tr[x].sum;
    push_down (tr, x, l, r);
    long long m = (l + r) >> 1, ans = 0;
    if (pl <= m) ans += query_s (tr, x << 1, l, m, pl, pr);
    if (m + 1 <= pr) ans += query_s (tr, (x << 1) + 1, m + 1, r, pl, pr);
    return ans;
}

_ long long query_d (node *tr, long long x, long long l, long long r, long long pl, long long pr) {
    if (pl > pr) return 0;
    if (pl <= l && r <= pr)
        return tr[x].dsum;
    push_down (tr, x, l, r);
    long long m = (l + r) >> 1, ans = 0;
    if (pl <= m) ans += query_d (tr, x << 1, l, m, pl, pr);
    if (m + 1 <= pr) ans += query_d (tr, (x << 1) + 1, m + 1, r, pl, pr);
    return ans;
}

_ long long query_r (node *tr, long long x, long long l, long long r, long long pl, long long pr) {
    if (pl > pr) return 0;
    if (pl <= l && r <= pr)
        return tr[x].rsum;
    push_down (tr, x, l, r);
    long long m = (l + r) >> 1, ans = 0;
    if (pl <= m) ans += query_r (tr, x << 1, l, m, pl, pr);
    if (m + 1 <= pr) ans += query_r (tr, (x << 1) + 1, m + 1, r, pl, pr);
    return ans;
}

int main () {
    long long T;
    scanf ("%lld", &T);
    for (long long t = 0; t < T; ++t) {
        printf ("Case #%lld:\n", t + 1);
        scanf ("%lld%lld", &N, &Q);
        std::fill (tr[0], tr[0] + std::min (8 * N + 1, 1048577ll), node ());
        std::fill (tr[1], tr[1] + std::min (8 * N + 1, 1048577ll), node ());
        for (long long q = 0; q < Q; ++q) {
            long long op;
            scanf ("%lld", &op);
            if (op == 1) {
                long long l, r;
                scanf ("%lld%lld", &l, &r);
                modify (tr[0], 1, 1, 2 * N, l, r, 1);
            } else if (op == 2) {
                long long l, r;
                scanf ("%lld%lld", &l, &r);
                modify (tr[1], 1, 1, 2 * N, l + N, r + N, 1);
            } else if (op == 3) {
                long long x1, x2, y1, y2;
                scanf ("%lld%lld%lld%lld", &x1, &x2, &y1, &y2);
                long long ans = 0;
                long long l = x1 + y2, r = x2 + y1;
                if (l > r) std::swap (l, r);
                ans += query_d (tr[0], 1, 1, 2 * N, x1 + y1, l - 1) - query_s (tr[0], 1, 1, 2 * N, x1 + y1, l - 1) * (x1 + y1 - 1);
                ans += query_r (tr[0], 1, 1, 2 * N, r + 1, x2 + y2) - query_s (tr[0], 1, 1, 2 * N, r + 1, x2 + y2) * (2 * N - (x2 + y2));
                ans += query_s (tr[0], 1, 1, 2 * N, l, r) * std::min (x2 - x1 + 1, y2 - y1 + 1);
                l = x1 - y1 + N; r = x2 - y2 + N;
                if (l > r) std::swap (l, r);
                ans += query_d (tr[1], 1, 1, 2 * N, x1 - y2 + N, l - 1) - query_s (tr[1], 1, 1, 2 * N, x1 - y2 + N, l - 1) * (x1 - y2 + N - 1);
                ans += query_r (tr[1], 1, 1, 2 * N, r + 1, x2 - y1 + N) - query_s (tr[1], 1, 1, 2 * N, r + 1, x2 - y1 + N) * (2 * N - (x2 - y1 + N));
                ans += query_s (tr[1], 1, 1, 2 * N, l, r) * std::min (x2 - x1 + 1, y2 - y1 + 1);
                printf ("%lld\n", ans);
            }
        }
    }
}

Hold Your Hand

lbn187

数据超过了10组,ISAP T掉了。。

#include<bits/stdc++.h>
#define _ __attribute__ ((optimize ("-O3")))
#define N 1025
#define M 22222
#define inf 1e9
#define CL(a) memset(a,0,sizeof a)
int ca,n,m,i,x,k,L,TE,V[N],W[N];
char s[9],lx[4];
using namespace std;
_ struct MaxFlow{
	int tot,w,fir[N],cur[N],pre[N],d[N],nb[N],va[M],la[M],ne[M];
	void in(){tot=1;CL(fir);CL(d);CL(nb);CL(pre);}//注意每次求都要调用
	void ins(int x,int y,int z){
		la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=z;
		la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;va[tot]=0;
	}
	int flow(int S,int T,int n){//给定起点、终点和点数,求最大流
		register int i,u,V,fl=0;
		for(i=1;i<=n;i++)cur[i]=fir[i];
		for(u=S,nb[0]=n;d[S]<n;){
			if(u==T){
				for(V=inf,i=S;i!=T;i=la[cur[i]])
					if(va[cur[i]]<V)V=va[cur[u=i]];
				for(fl+=V,i=S;i!=T;i=la[cur[i]])
					va[cur[i]]-=V,va[cur[i]^1]+=V;
			}
			for(i=cur[u];i;i=ne[i])
				if(va[i]&&d[la[i]]+1==d[u])break;
			if(i)cur[u]=i,pre[la[i]]=u,u=la[i];else{
				if(!--nb[d[u]])break;
				for(i=cur[u]=fir[u],w=T;i;i=ne[i])
					if(d[la[i]]<w&&va[i])w=d[la[i]];
				++nb[d[u]=w+1];
				if(u!=S)u=pre[u];
			}
		}
		return fl>=inf?-1:fl;
	}
}G;
_ int get(int x){
	register int v=0,i;
	for(i=0;i<8;i++)v|=(x>>i&1)<<8-i-1;
	return v;
}
_ int main(){
	scanf("%d",&TE);
	for(ca=1;ca<=TE;ca++){
		for(i=0;i<N;i++)V[i]=W[i]=inf;G.in();
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)scanf("%d",&x),G.ins(x+256,get(x)+768,inf);
		for(;m--;){
			scanf("%s%s%d",lx,s,&x);k=1;L=strlen(s);
			if(lx[0]=='P'){
				for(i=0;i<L;i++)k=k*2+s[i]-'0';
				V[k]=min(V[k],x);
			}else{
				for(i=L-1;~i;i--)k=k*2+s[i]-'0';
				W[k]=min(W[k],x);
			}
		}
		for(i=2;i<512;i++)G.ins(i/2,i,V[i]),G.ins(i+512,i/2+512,W[i]);
		printf("Case #%d: %d\n",ca,G.flow(1,513,1024));
	}
}

Aki

换到平面上就gg了,没有用好trie的性质。貌似一般的覆盖平面上一堆点,可以用一些横条,竖条,最小代价不能流流流?

#include <bits/stdc++.h>
using namespace std;
const int N = 511 * 2 + 2, INF = 1e9, B =  256;
int a[N], b[N], S, T;
struct edge { int to, f, r; };
vector<edge> G[N];
int d[N], st[N];
bool BFS() {
	for (int i = 0; i <= T; ++ i) d[i] = -1;
	queue<int> q;
	q.push(S);
	d[S] = 0;
	while (!q.empty()) {
		int p = q.front(); q.pop();
		for (edge e : G[p]) {
			int u = e.to;
			if (d[u] == -1 && e.f) {
				d[u] = d[p] + 1;
				q.push(u);
			}
		}
	}
	return d[T] != -1;
}
int DFS(int x, int arg) {
	if (x == T) return arg;
	int A = arg;
	for (int &i = st[x]; i < (int) G[x].size(); ++ i) {
		edge &e = G[x][i];
		if (e.f && d[e.to] == d[x] + 1) {
			int tmp = DFS(e.to, min(arg, e.f));
			e.f -= tmp;
			G[e.to][e.r].f += tmp;
			arg -= tmp;
			if (!arg) break;
		}
	}
	return A - arg;
}
long long mf() {
	long long ans = 0;
	while (BFS()) {
		for (int i = 0; i <= T; ++ i) st[i] = 0;
		ans += DFS(S, INF);
	}
	return ans;
}
void ae(int u, int v, int f) {
	G[u].push_back((edge) {v, f, (int) G[v].size()});
	G[v].push_back((edge) {u, 0, (int) G[u].size() - 1});
}
int main() {
	int TT, zzz = 0;
	scanf("%d", &TT);
	while (TT --) {
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < N; ++ i) G[i].clear();
		S = 0;
		T = 511 * 2 + 1;
		for (int i = 1; i < 512; ++ i) a[i] = b[i] = INF;
		for (int i = 1; i <= n; ++ i) {
			int x;
			scanf("%d", &x);
			int rx = 0;
			for (int j = 0; j < 8; ++ j) rx = rx * 2 + (x >> j & 1);
			ae(x + 256, 511 + 256 + rx, INF);
		}
		for (int i = 1; i <= m; ++ i) {
			char type[2], str[10];
			int w;
			scanf("%s%s%d", type, str, &w);
			int len = (int) strlen(str);
			if (type[0] == 'P') {
				int x = 1;
				for (int i = 0; i < len; ++ i) {
					x = x + x + (str[i] == '1');
				}
				a[x] = min(a[x], w);
			}
			else {
				reverse(str, str + len);
				int x = 1;
				for (int i = 0; i < len; ++ i) {
					x = x + x + (str[i] == '1');
				}
				b[x] = min(b[x], w);
			}
		}
		ae(S, 1, INF);
		ae(512, T, INF);
		for (int i = 1; i < 256; ++ i) {
			ae(i, i + i, a[i + i]);
			ae(i, i + i + 1, a[i + i + 1]);
			ae(511 + i + i, 511 + i, b[i + i]);
			ae(511 + i + i + 1, 511 + i, b[i + i + 1]);
		}
		long long ans = mf();
		if (ans >= INF) ans = -1;
		printf("Case #%d: %lld\n", ++ zzz, ans);
	}
}

Manors

Aki

半平面交。

#include <bits/stdc++.h>
using namespace std;
typedef double DB;
const DB eps = 1e-8;
int sign(DB x) {return (x > eps) - (x < -eps);}

struct Point {
	DB x, y;
	Point() {}
	Point(DB x, DB y) : x(x), y(y) {}
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0);}
	Point turn90() const {return Point(-y, x);}
	Point norm() const { DB t = sqrt(x * x + y * y); return Point(x / t, y / t);}
	DB length() const {return sqrt(x * x + y * y);}
};
Point operator - (Point a, Point b) {return Point(a.x - b.x, a.y - b.y);}
Point operator + (Point a, Point b) {return Point(a.x + b.x, a.y + b.y);}
Point operator * (Point a, DB b) {return Point(a.x * b, a.y * b);}
DB dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
DB det(Point a, Point b) { return a.x * b.y - a.y * b.x; }
struct Line {
	Point a, b;
	bool include(const Point &p) const { return sign(det(b - a, p - a)) > 0; }
	Line () {}
	Line (Point a, Point b) : a(a), b(b) {}
	Line push(DB d = eps) const{ // 将半平面向外推 eps
		Point delta = (b - a).turn90().norm() * d;
		return Line(a - delta, b - delta);
	}
};
Point intersect(Line a, Line b) {
	DB A = det(a.b - a.a, b.b - a.a);
	DB B = det(a.b - a.a, b.a - a.a);
	return b.b + (b.b - b.a).norm() * (A * (b.b - b.a).length() / (B - A));
}
bool parallel(Line a, Line b) {return !sign(det(a.b - a.a, b.b - b.a));}
bool sameDir(const Line &l0, const Line &l1) { return parallel(l0, l1) && sign(dot(l0.b - l0.a, l1.b - l1.a)) == 1; }
bool operator < (const Point &a, const Point &b) {
	if (a.quad() != b.quad()) {
		return a.quad() < b.quad();
	} else {
		return sign(det(a, b)) > 0;
	}
}
bool operator < (const Line &l0, const Line &l1) {
	if (sameDir(l0, l1)) {
		return l1.include(l0.a);
	} else {
		return (l0.b - l0.a) < (l1.b - l1.a);
	}
}
bool check(const Line &u, const Line &v, const Line &w) { return w.include(intersect(u, v)); }
vector<Point> intersection(vector<Line> &l) {
	sort(l.begin(), l.end());
	deque<Line> q;
	for (int i = 0; i < (int)l.size(); ++i) {
		if (i && sameDir(l[i], l[i - 1])) {
			continue;
		}
		while (q.size() > 1 && !check(q[q.size() - 2], q[q.size() - 1], l[i])) q.pop_back();
		while (q.size() > 1 && !check(q[1], q[0], l[i])) q.pop_front();
		q.push_back(l[i]);
	}
	while (q.size() > 2 && !check(q[q.size() - 2], q[q.size() - 1], q[0])) q.pop_back();
	while (q.size() > 2 && !check(q[1], q[0], q[q.size() - 1])) q.pop_front();
	vector<Point> ret;
	for (int i = 0; i < (int)q.size(); ++i) ret.push_back(intersect(q[i], q[(i + 1) % q.size()]));
	return ret;
}

const int N = 105;
long long xx[N], yy[N], x[N], y[N];
int main() {
	int T, zzz = 0;
	scanf("%d", &T);
	while (T --) {
		int n, m;
		scanf("%d%d", &n, &m);
		vector<vector<Point>> all;
		for (int i = 0; i < n; ++ i) {
			all.push_back({});
			xx[i] = yy[i] = x[i] = y[i] = 0;
			for (int j = 0; j < m; ++ j) {
				int x, y;
				scanf("%d%d", &x, &y);
				all.back().push_back(Point(x, y));
				xx[i] += x * x;
				yy[i] += y * y;
				::x[i] += x;
				::y[i] += y;
			}
		}
		vector<int> ans;
		for (int i = 0; i < n; ++ i) {
			vector<Line> lim;
			lim.push_back(Line(Point(0, 0), Point(4095, 0)));
			lim.push_back(Line(Point(4095, 0), Point(4095, 4095)));
			lim.push_back(Line(Point(4095, 4095), Point(0, 4095)));
			lim.push_back(Line(Point(0, 4095), Point(0, 0)));
			for (int j = 0; j < n; ++ j) if (i != j) {
				DB C = xx[i] + yy[i] - xx[j] - yy[j];
				DB A = 2 * (x[j] - x[i]);
				DB B = 2 * (y[j] - y[i]);
				//printf("%d %d : %.2f %.2f %.2f\n", i, j, A, B, C);
				Point p1, p2;
				if (sign(A) == 0) {
					assert(sign(B));
					p1 = Point(1, -C / B);
					p2 = Point(0, -C / B);
				}
				else {
					p1 = Point(- (C + B) / A, 1);
					p2 = Point(- C / A, 0);
				}
				Line L = Line(p1, p2);
				Line L2 = L.push(10);
				if (A * L2.a.x + B * L2.a.y + C < 0) swap(L.a, L.b);
				lim.push_back(L);
				//printf("add %.2f %.2f -> %.2f %.2f\n", lim.back().a.x, lim.back().a.y, lim.back().b.x, lim.back().b.y);
			}
			auto res = intersection(lim);
			DB area = 0;
			if (!res.empty()) {
				res.push_back(res[0]);
				for (int i = 0; i < (int) res.size() - 1; ++ i ) {
					area += det(res[i], res[i + 1]);
				}
				area = fabs(area) / 2;
			}
			ans.push_back((int) (round(area + eps) + eps));
			//printf("area = %.10f\n", area);
		}
		printf("Case #%d: ", ++ zzz);
		for (int i = 0; i < n; ++ i) printf("%d%c", ans[i], " \n"[i == n - 1]);
	}
}