by AHdoc

A

B[J]

给出n个子串,找出一个最大的位置,使得其之前存在一个串不为它的子串
不存在则输出-1

暴力

直接strstr,注意若存在一个串为当前串的子串
则在以后只需要和当前串比较,而不需要与其子串比较

复杂度$O(n^2)$

C

D[G]

给出 n,a,b
表示 1-n n个位置(a,b已选),每次轮流选择一个,
要求这个位置为之前选择的两个位置i,j的和或者差
不能选的人输

博弈

样例给了16组。。。很明显是让你找规律。。。

n/gcd(a,b) 是奇数则先手必胜,反之后手必胜

证明:
能选的数一定是 gcd(a,b) 的倍数
所有可选位置有 n/gcd(a,b) - 2

复杂度 $O(logn)$

E

F

给出n个$a_i$,以及m
求0-m中被 $ka_i \pmod m$ 到达的数(每个只算一次)的和

容斥
很明显所有被访问的数为 $kgcd(a_i,m)$
而且$gcd(a_i,m) | gcd(d,m)$,d为m的因子
我们对所有可以被$gcd(a_i,m)$标记的d容斥即可

容斥过程类似于筛法,将集合内d的所有倍数都减去d对其的贡献

复杂度 $O(n[d|m] + \sqrt{m} + [d|m]^2)$

G

有一个游戏,在边长为300米的正方形进行
按照顺时针方向,四个点都有一个浮标依次标号为#1 #2 #3 #4
两个选手初始都在1号点,它们需要依此经过#2 #3 #4 #1
最后有人触到1号点后比赛结束

得分

  • 对于任意一个浮标,如果触屏时间比对手早,则得到一分
  • 如果你和对手同时到达一个位置,可以进行一次格斗,胜利者得到一分(格斗只能在有人触碰了2号点后进行)

有两个玩家(S和A)进行这个游戏
A速度为V1,S速度为V2,V1 <= V2
S会严格沿矩形边 1->2->3->4->1 移动
A可以在矩形内任意移动,且A可以发动一次格斗,且一定能战胜对手,并使对手眩晕T秒
若两人在同一个浮标相遇,则得分优先给A
如果A的得分可能比S高,则输出Yes,否则输出No

注意每个人都必须按照 #2 #3 #4 #1 的顺序触碰浮标

模拟

题意杀,现场赛没过多少队…

分别判断在 2-3 和在 3-4 这两条边拦截(发动格斗)
拦截位置显然要靠近 2 和 3,这个过程二分即可
如果在 2-3,则判断A是否能在S之前到达 #4
如果在 3-4,则判断A是否能在S之前到达 #1

注意A也要按 #2 #3 #4 #1 的顺序触碰浮标

H

I

J

K

L

M