20160814 训练记录

tonyfang posted @ 2016年8月14日 22:30 in 随笔 with tags c++ OI , 310 阅读

1. tri

给出$n$个点,求有多少个三元点对能组成三角形。

$n \leq 100$

【题解】枚举即可。

如果$n \leq 1000$,减法原理,对于三点共线,枚举中间点,极角排序即可。复杂度$O(n^2logn)$

 

# include <stdio.h>
using namespace std;

int n;
struct point {
	int x, y;
}p[110];
int ans = 0;

int main() {
	freopen("tri.in", "r", stdin);
	freopen("tri.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) 
		scanf("%d%d", &p[i].x, &p[i].y);
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			for (int k=1; k<=n; ++k) {
				if(i==j || i==k || j==k) continue;
				if(p[i].x - p[j].x == 0 || p[j].x - p[k].x == 0) {
					if(p[i].x - p[j].x == 0 && p[j].x - p[k].x != 0) ++ans;
					else if(p[i].x - p[j].x != 0 && p[j].x - p[k].x == 0) ++ans;
					continue;
				}
				int dy1=p[i].y-p[j].y, dy2=p[j].y-p[k].y;
				int dx1=p[i].x-p[j].x, dx2=p[j].x-p[k].x;
				if((long double)dy1/dx1 != (long double)dy2/dx2) ++ans;
			}
	ans /= 6;
	printf("%d\n", ans);
	return 0;
}

2. letter

给出n个长度小于100的模式串,给出m个长度小于1350000的字符串,问这个字符串中是否出现了所有的n个模式串。

$n \leq 100, m \leq 10$

【题解】kmp即可。当然正确做法是AC自动机。

 

# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;

int n;
char str[110][110];
int len[110];
int next[110][110];
char p[1360001];

inline void getnext(int pos) {
	next[pos][1] = 0; len[pos] = strlen(str[pos]+1);
	int j = 0;
	for (int i=2; i<=len[pos]; ++i) {
		while(j>0 && str[pos][j+1] != str[pos][i]) j=next[pos][j];
		if(str[pos][j+1] == str[pos][i]) ++j;
		next[pos][i] = j;
	}
}

inline bool kmp(int pos) {
	int j=0; int leng = strlen(p+1);
//	printf("%s", p+1);
	for (int i=1; i<=leng; ++i) {
		while(j>0 && str[pos][j+1] != p[i]) j=next[pos][j];
		if(str[pos][j+1] == p[i]) ++j;
		if(j == len[pos]) return 1;
	}
	return 0;
}

int main() {
	freopen("letter.in", "r", stdin);
	freopen("letter.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%s", str[i]+1);
	random_shuffle(str+1, str+n+1);
	for (int i=1; i<=n; ++i) getnext(i);
	while(~scanf("%s", p+1)) {
		p[strlen(p+1)] = '\0';
//		printf("checking %s\n", p);
		bool flag = 0;
		for (int i=1; i<=n; ++i) {
//			printf("===nowchecking %s\n", str[i]+1);
			bool gg = kmp(i);
			if(gg == 0) {
				flag = 1;
				break;
			}
		}	
		if(flag) puts("No");
		else puts("Yes");
	}
	return 0;
}
 

AC自动机有点问题……我去调一下

具体就是这个数据会有问题:

2

ay

gay

gay$

答案应该是Yes,但是有些会输出No

啊更新完成 (upd 20160818)

# include <stdio.h>
# include <string.h>
# include <queue>
# include <algorithm>
using namespace std;

int n;
int len[110], x;
char ps[1360001];
char str[510];
int ch[2000010][27], fail[2000010], last[2000010], cnt[2000010], siz;
bool val[2000010];

inline void ACinsert() {
	int len = strlen(str), p=0;
	for (int i=0; i<len; ++i) {
		int c = str[i] - 'a';
		if(!ch[p][c]) ch[p][c] = ++siz;
		p = ch[p][c];
	}
	val[p] = 1;
}

queue<int> q;
inline void ACgetfail() {
	fail[0] = 0;
	for (int c=0; c<26; ++c) {
		int p = ch[0][c];
		if(p) {
			fail[p] = last[p] = 0;
			q.push(p);
		}
	}
	while(!q.empty()) {
		int top=q.front();
		q.pop();
		for (int c=0; c<26; ++c) {
			int p = ch[top][c];
			if(!p) continue;
			q.push(p);
			int v = fail[top];
			while(v && !ch[v][c]) v = fail[v];
			fail[p] = ch[v][c];
			last[p] = val[fail[p]] ? fail[p] : last[fail[p]];
		}
	}
}

inline void ACadd(int x) {
	for (; x; x=last[x]) 
		cnt[x] = 1;
}

inline void ACfind() {
	int p=0, len = strlen(ps);
	memset(cnt, 0, sizeof(cnt));
	for (int i=0; i<len-1; ++i) {
		int c = ps[i] - 'a';
		while(p && !ch[p][c]) p = fail[p];
		p = ch[p][c];
		if(val[p]) ACadd(p);
		else if(last[p]) ACadd(last[p]);
	}
}


int main() {
	freopen("letter.in", "r", stdin);
	freopen("letter.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) scanf("%s", str), ACinsert();
	ACgetfail();
	while(~scanf("%s", ps)) {
		ACfind();
		bool gg=0;
		for (int i=1; i<=siz; ++i) 
			if(val[i] != 0)
				if(cnt[i] == 0) {
				gg=1;
				break;
			}
		if(gg) puts("No");
		else puts("Yes");
	}
	return 0;
}
 

3. mir

给出n个反射镜,问一束光从原点沿x轴正方向射出,T时刻后到哪里。假设光一时刻走一个单位。反射镜均成45度或135度角,且两面都可以反射。

$n \leq 100000, T \leq 10^{18}$

【题解】

最普通的想法:按时间暴力

我们可以优化点,就是预处理出来,每次走一大段,这样就有85分啦

那么我们发现如果有环就会爆炸啦!

那么我们判环即可,如果有就把T拿去对于环长度取余。

判断环的时候注意一个反射镜拆成4个点

 

# include <stdio.h>
# include <algorithm>
# include <iostream>

using namespace std;

int n; long long T;
struct mirror {
	int x, y, id;
	bool f;
}p[666666];
char str[5];
int s[666666][5];
bool vis[2666666];
long long sx[2666666];

//  right:1, up:2, left:3, down:4
inline void turn(int &FACE, bool g) {
	if(g == 1) {
		if(FACE == 1) FACE=2;
		else if(FACE == 2) FACE=1;
		else if(FACE == 3) FACE=4;
		else if(FACE == 4) FACE=3;
	} else {
		if(FACE == 1) FACE=4;
		else if(FACE == 2) FACE=3;
		else if(FACE == 3) FACE=2;
		else if(FACE == 4) FACE=1;
	}
}

inline int get(int id, int fx) {
	bool gg = p[id].f;
	/*
	if(gg == 1) {//"/"
		if(fx == 1 || fx == 2) return id;
		else return id+n;
	} else {
		if(fx == 1 || fx == 4) return id;
		else return id+n;
	}*/
	if(fx == 1) return id;
	if(fx == 2) return id+n;
	if(fx == 3) return id+n+n;
	if(fx == 4) return id+n+n+n;
}

inline void go(long long &x, long long &y, long long T, int face) {
	if(face == 1) x=x+T;
	if(face == 2) y=y+T;
	if(face == 3) x=x-T;
	if(face == 4) y=y-T;
}


inline int cmp1(mirror a, mirror b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}

inline int cmp2(mirror a, mirror b) {
	return a.y < b.y || (a.y == b.y && a.x < b.x);
}

inline int cmp3(mirror a, mirror b) {
	return a.id < b.id;
}

int main() {
	freopen("mir.in", "r", stdin);
	freopen("mir.out", "w", stdout);
	scanf("%d%*d", &n); cin >> T;
	for (int i=1; i<=n; ++i) {
		scanf("%d%d%s", &p[i].x, &p[i].y, str);
		if(str[0] == '/') p[i].f=1;
		else p[i].f=0;
		p[i].id=i;
		s[i][1] = s[i][2] = s[i][3] = s[i][4] = -1;
	}
	sort(p+1, p+n+1, cmp1);
	for (int i=1; i<=n; ++i) {
		int begin = i, end = i;
	//	printf("BEGIN=%d x=%d\n", begin, p[begin].x);
		while(p[begin].x == p[end+1].x) ++end;
		for (int j=begin; j<end; ++j) s[p[j].id][2] = p[j+1].id;
		for (int j=begin+1; j<=end; ++j) s[p[j].id][4] = p[j-1].id;
	//	printf("END=%d x=%d\n", end, p[begin].x);
		i = end;
	}	
	sort(p+1, p+n+1, cmp2);
	for (int i=1; i<=n; ++i) {
		int begin = i, end = i;
		while(p[begin].y == p[end+1].y) ++end;
		for (int j=begin; j<end; ++j) s[p[j].id][1] = p[j+1].id;
		for (int j=begin+1; j<=end; ++j) s[p[j].id][3] = p[j-1].id;
		i = end;
	}
	long long x=0, y=0; int face = 1;
	int id=-1, tem;
	for (int i=1; i<=n; ++i) {
		if(p[i].y == 0 && p[i].x > 0) {
			id=i;
			break;
		}
	}
	tem = p[id].id;
	if(id == -1 || T <= p[id].x) {
		cout << T << " 0\n";
		return 0;
	}
	T = T-p[id].x;
	x = p[id].x;
	//cout << "face bef = " << face << ' ' << p[id].f << endl;
	turn(face, p[id].f);
	//cout << "face aft = " << face << endl;
	id = tem;
	//cout << x << ' ' << y << ' ' << T << ' ' << face << endl;
	
	sort(p+1, p+n+1, cmp3);
	/*
	for (int i=1; i<=n; ++i) {
		printf("right=%d, up=%d, left=%d, down=%d\n", s[i][1], s[i][2], s[i][3], s[i][4]);
	}
	*/
	bool incircle=0;
	long long TT = T;
	while(T>0) {
		if(id>n) id=id%n;
//		cout << x << ' ' << y << ' ' << T << ' ' << face << ' ' << id << endl;
		int next = s[id][face];
//		printf("%d\n", next);
		if(next == -1) {
			go(x, y, T, face);
			T=0;
			continue;
		}
		long long dis;
		if(face == 1) dis = p[next].x - p[id].x;
		if(face == 2) dis = p[next].y - p[id].y;
		if(face == 3) dis = p[id].x - p[next].x;
		if(face == 4) dis = p[id].y - p[next].y;
		if(T <= dis) {
			go(x, y, T, face);
			T=0;
			continue;
		}
		go(x, y, dis, face);
//		cout << x << ' ' << y << endl;
		T-=dis;
		int ID=get(next, face);
//		printf("%d\n", ID);
		turn(face, p[ID>n?(ID%n):ID].f);
		
		if(vis[ID] && !incircle) {
			long long TIME = TT-T-sx[ID];
//			printf("TIME=%d\n", TIME);
			T=T%TIME;
			incircle=1;
		}
		vis[ID] = 1;
		sx[ID] = TT - T;
//		printf("sx = %d\n", sx[ID]);
		id=ID;
	}
	cout << x << ' ' << y << endl;

	return 0;
}

 

 


登录 *


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