20160814 训练记录
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;
}
2023年6月17日 13:51
TeachersBadi is a website dedicated to education, students, and teachers.The name 'TeachersBadi' reveals the nature of the site. A dedicated Team for teachers, students, and educators is launching and running the site. teachersbadi.in We enjoy sharing primarily educational material and employee and teacher-related content in the educational area.