20160728 训练记录

tonyfang posted @ 2016年7月30日 08:23 in 随笔 with tags c++ OI , 452 阅读

1. 字符串复原

【题目大意】

给出n个长度为3的字符串,它们都是一个字串S的长度为3的连续字串,而且字串不包含除了这n个字符串以外的,长度为3的连续子串。求出字串S。

【题解】
hash+离散+欧拉路

# include <stdio.h>
using namespace std;

int n, T, rn;
char st[3];

int head[666666], next[666666], to[666666], tot=0, in[666666], out[666666], hd1[666666];
int s[666666], sn=0, ls[666666];
bool used[666666];
int fc[666666], top, ans[666666], gg[666666], gn=0;
int fa[666666];

// ============UNIONSET============== //
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
// ============UNIONSET============== //

// ============HASH============= //
inline int hash(char a, char b) {
	return a * 256 + b;
}
char UNHASHa, UNHASHb;
inline void unhash(int s) {
	UNHASHb = s % 256;
	UNHASHa = (s - UNHASHb)/256;
}
// ============HASH============= //

inline void add(int a, int b) {
	++tot;
	next[tot] = head[a];
	head[a] = tot;
	to[tot] = b;
	out[a] ++;
	in[b] ++;
	used[tot] = 0;
}

// ===========FLEURY============= //
inline void dfs(int x) {
	ans[++top] = x;
	for (int i=hd1[x]; i; i=next[i]) {
		if(!used[i]) {
			used[i] = 1;
			out[x] --;
			in[to[i]] --;
			hd1[x] = i;
			dfs(to[i]);
			break;
		}
	}
}

inline void fleury(int s) {
	top = 1;
	ans[top] = s;
	while(top > 0) {
		int can = 0;
		if(out[ans[top]] >= 1) can = 1;
		if(can == 0) {
			gg[++gn] = ans[top];
			--top;
		} else {
			--top;
			dfs(ans[top+1]);
		}
	}
}
// ===========FLEURY============= //

int main() {
	freopen("recover.in", "r", stdin);
	freopen("recover.out", "w", stdout);
	scanf("%d", &T);
	for (int I=1; I<=T; ++I) {
		tot=0; sn=0; gn=0;
		scanf("%d", &n);
		for (int i=1; i<=n+66; ++i) 
			head[i] = in[i] = out[i] = 0, fa[i] = i;
		for (int i=1; i<=n; ++i) {
			scanf("%s", st);
			int front = hash(st[0], st[1]), back = hash(st[1], st[2]);
//			printf("%d %d\n", front, back);	
			if(fc[front] != I) {
				fc[front] = I;
				s[++sn] = front;
				ls[front] = sn;
//				printf("***new front\n");
			}
			if(fc[back] != I) {
				fc[back] = I;
				s[++sn] = back;
				ls[back] = sn;
//				printf("***new back\n");
			}
			front = ls[front]; back = ls[back];
			add(front, back);
			int fu = getf(front), fv = getf(back);
			fa[fu] = fv;
//			printf("edge: %d %d  bh=%d\n", front, back, tot);
		}
//		for (int i=1; i<=sn; ++i) 
//			printf("number = %d, in = %d, out = %d\n", i, in[i], out[i]);
		int start=-1, end=-1;
		bool no=0;
		for (int i=1; i<=sn; ++i) {
			hd1[i] = head[i];
			if(in[i] - out[i] == 1) {
				if(end==-1) end=i;
				else {
					no=1;
					break;
				}
			} else if(in[i] - out[i] == -1) {
				if(start==-1) start=i;
				else {
					no=1;
					break;
				}
			} else if(in[i] != out[i]) {
				no = 1;
				break;
			}
		}
		for (int i=1; i<n; ++i) {
			if(getf(i) != getf(i+1)) {
				no = 1;
				break;
			}
		}
		if(no) {
			puts("NO");
			continue;
		}
//		printf("start = %d, end = %d\n", start, end);
		if(start == -1 && end == -1) 
			start = 1, end = 1;
		puts("YES");
		gg[++gn] = start;
		fleury(start);
		for (int i=gn; i>=3; --i) {
			gg[i] = s[gg[i]];
			unhash(gg[i]);
			printf("%c", UNHASHa);
		}
		gg[2] = s[gg[2]];
		unhash(gg[2]);
		printf("%c%c", UNHASHa, UNHASHb);
		printf("\n");
	}
	return 0;
}

2. 好排列

【题目大意】

给出一个排列的大小关系(大于,小于),求排列方案数量

【题解】

f[i, j] 1...i的排列最后一个是j的满足要求的方案数量

随便转移一下前缀和搞搞

 

# include <stdio.h>
# include <algorithm>
# include <string.h>
using namespace std;
int T, n, m;
long long f[2020][2020];
int s[2020];
bool t[2020];
const int MOD = 1e9+7;
int main() {
	freopen("good.in", "r", stdin);
	freopen("good.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		memset(f, 0, sizeof(f));
		memset(t, 0, sizeof(t));
		scanf("%d %d", &n, &m);
		for (int i=1; i<=m; ++i) {
			scanf("%d", &s[i]);
			t[s[i]+1] = 1;
		}
		f[1][1] = 1;
		for (int i=2; i<=n; ++i) {
			if(t[i] == 1) {
				long long sum = 0;
				for (int j=1; j<=i; ++j) {
					f[i][j] = sum;
					sum = (sum + f[i-1][j]) % MOD;
				}
			} else {
				long long sum = 0;
				for (int j=i; j>=1; --j) {
					sum = (sum + f[i-1][j]) % MOD;
					f[i][j] = sum;
				}
			}
		}
		long long ans = 0;
		for (int i=1; i<=n; ++i) ans = (ans + f[n][i]) % MOD;
		printf("%lld\n", ans);
	}
	return 0;
}
		
	

3. 黑帮

【题目大意】同codeforces 690A1,A2

【题解】

随便考虑一下就行啦,见codeforces 690A 题解

 

# include <stdio.h>
using namespace std;

int T;
int n, S;

int main() {
	freopen("distribute.in", "r", stdin);
	freopen("distribute.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &S);
		if(S==1) {
			printf("%d\n", (n+1)/2);
			continue;
		} else {
			if(n&1) 
				printf("%d\n", (n-1)/2);
			else {
				int s = 1;
				if(n <= 2)
					printf("%d\n", (n-1)/2);
				else {
					for (int i=1; i<=30; ++i) {
						s = s * 2;
						if((long long)s*2 > n) {
							printf("%d\n", (n-s)/2);
							break;
						}
					}
				}
			}
		}
	}
	return 0;
}
			

 

 

li9.in 说:
2023年6月18日 15:56

Our reporting team plans to provide the Education & Recruitment Update for all age groups and to present the actual picture of recent events through inside coverage. Our goal is to meet the needs of people of li9.in all ages by publishing news categorised as General, Political, Crime, Sports, Entertainment, Education, and World News.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter