| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/13 | O | O | O | O | O | . | O | . | O | O | O | . | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A Who is better?
题目描述
两个人玩游戏，一共有$n$个石子，第一个人不能全拿走，后面每个人拿走的石子数不能超过上一个人拿走个数的两倍，问最终谁能获胜。$n$通过解一个同余方程组解出。
解题思路
很僵硬的斐波那契博弈和中国剩余定理的结合。很容易发现这个博弈是一个斐波那契博弈，套上$EXCRT$板子即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
res = 0
while(b>0):
if(b%2==1):
res = (res + a)%mod
a = (a + a)%mod
b //=2
return res
gcd = 0
def exgcd(a, b):
global gcd
if (b == 0):
gcd = a
return 1,0
x,y = exgcd(b,a%b)
return y,x-a//b * y
def excrt(a,b,n):
global gcd
M = b[0]
a[0]=a[0]%b[0]
ans = a[0]
x = 0
for i in range(1,n):
x,y=exgcd(M, b[i])
B = b[i]
a[i]=a[i]%b[i]
c = (a[i] - ans % B + B) % B
g = B // gcd
x = mul(x, c // gcd, g)
ans += x * M
M *= g
ans = (ans%M + M) % M
return ans%M
def check(x,n,a,b):
for i in range(n):
if (x%b[i] != a[i]):
return False
return True
s = input()
n = int(s)
a = []
b = []
for i in range(n):
s = input().split()
a.append(int(s[1]))
b.append(int(s[0]))
now = excrt(a,b,n)
fib = [1,1]
l = 0
r = 1
while fib[l] + fib[r] <= 1000000000000001:
fib.append( fib[l] + fib[r])
l+=1
r+=1
#print(now)
if (check(now,n,a,b)):
if (now in fib):
print("Lbnb!")
else:
print("Zgxnb!")
else:
print("Tankernb!")
B so easy
题目描述
初始有一个$1-n$的数列，有$q$次操作，操作有两种
- 删掉某个位置$pos$处的元素
- 问位置不在$pos$之前的没被删掉的最靠前的元素位置
解题思路
并查集，每个被删掉区域并到区间末端即可。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
using namespace std;
int n, q;
typedef long long ll;
const int ms = 1e6;
int a[ms * 3], cnt;
pair<int, int>b[ms];
//unordered_map<int, int>id;
void init()
{
sort(a, a + cnt);
cnt = unique(a, a + cnt) - a;
/*for (int i = 0; i < cnt; ++i)
{
id[a[i]] = i + 1;
}*/
}
int pre[ms * 3];
int find(int x)
{
return x == pre[x] ? pre[x] : pre[x] = find(pre[x]);
}
void join(int x, int y)
{
pre[find(x)] = pre[find(y)];
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 0; i < q; ++i)
{
scanf("%d%d", &b[i].first, &b[i].second);
a[cnt++] = b[i].second;
a[cnt++] = b[i].second + 1;
}
a[cnt++] = n + 1;
init();
int id = 0;
for (int i = 0; i < cnt; ++i)
{
id = (lower_bound(a, a + cnt, a[i]) - a) + 1;
pre[id] = id;
}
for (int i = 0; i < q; ++i)
{
id = (lower_bound(a, a + cnt, b[i].second) - a) + 1;
if (b[i].first == 1)
{
join(id, id + 1);
}
else
{
int res = find(id);
res = a[res - 1];
if (res == n + 1) res = -1;
printf("%d\n", res);
}
}
return 0;
}
C Buy Watermelon
题目描述
$SB$题没有题目描述。
解题思路
$SB$题没有解题思路。
AC代码
2
3
4
5
6
7
8
9
10
typedef long long ll;
using namespace std;
int main(){
int n;
scanf("%d",&n);
if(n>=4&&n%2==0)printf("YES");
else printf("NO");
return 0;
}
D Carneginon
题目描述
给定两个字符串$S,T$，当$S$比$T$长或短时，分别求出是否互为串与子串关系。
解题思路
分情况$kmp$求解即可。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
using namespace std;
int n, m;
typedef long long ll;
const int ms = 1e5 + 10;
char a[ms], b[ms];
int nxa[ms], nxb[ms];
int main()
{
scanf("%s", a);
int lena = strlen(a);
int i = 0, j = -1;
nxa[0] = -1;
while (i < lena)
{
if (j == -1 || a[i] == a[j])
{
i++, j++;
nxa[i] = j;
}
else
j = nxa[j];
}
int t;
scanf("%d", &t);
while (t--)
{
scanf("%s", b);
int lenb = strlen(b);
if (lena < lenb)
{
i = 0, j = 0;
bool flag = false;
while (i < lenb)
{
if (j == -1 || b[i] == a[j])
{
++i; ++j;
}
else
{
j = nxa[j];
}
if (j == lena)
{
flag = true;
break;
j = nxa[j];
}
}
if(flag)
{
printf("my teacher!\n");
}
else
{
printf("senior!\n");
}
}else if(lena == lenb)
{
if (strcmp(a,b)==0)
{
printf("jntm!\n");
}
else
{
printf("friend!\n");
}
}
else
{
i = 0, j = -1;
nxb[0] = -1;
while (i < lenb)
{
if (j == -1 || b[i] == b[j])
{
i++, j++;
nxb[i] = j;
}
else
j = nxb[j];
}
i = 0, j = 0; bool flag = false;
while (i < lena)
{
if (j == -1 || a[i] == b[j])
{
++i; ++j;
}
else
{
j = nxb[j];
}
if (j == lenb)
{
flag = true;
}
}
if (flag)
{
printf("my child!\n");
}
else
{
printf("oh, child!\n");
}
}
}
return 0;
}
E XKC’s basketball team
题目描述
给定一个$1-n$的排列$w$，定义一个人$i$右边的目标人为$w_j\geq w_i+m$的最大$j$，对于每一个$i$求出他与其目标人之间的总人数。
解题思路
根据$w$排序，从右向左双指针更新符合要求的最靠右的位置即可。
AC代码 - by Mogg & Potassium
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
int n, m;
typedef long long ll;
const int ms = 1e6;
pair<int, int>a[ms];
int res[ms];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i].first);
a[i].second = i;
}
sort(a, a + n);
res[a[n - 1].second] = -1;
int r = n - 1, mi = 0;
for (int i = n - 2; i >= 0; --i)
{
while (a[r].first >= a[i].first + m)
{
mi = max(mi, a[r].second);
r--;
}
res[a[i].second] = max(-1, mi - a[i].second - 1);
}
for (int i = 0; i < n - 1; ++i)
{
printf("%d ", res[i]);
}
printf("%d", res[n - 1]);
return 0;
}
F Little M’s attack plan
题目描述
解题思路
AC代码
2
G Colorful String
题目描述
定义一个字符串的价值为其所有回文子串的包含的不同字符数，求$s$的价值。
解题思路
状态压缩，建立一个回文树，记录下每一个本质不同的回文串出现的次数计数即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
typedef long long ll;
using namespace std;
char a[N];
ll ans;
ll f(int x){return 1LL<<x;}
struct PT{
int tr[N][P],fail[N],len[N];
int cnt[N],num[N];
ll state[N];
int tot,s[N],n,last,i;
int newnode(int l){
for(i=0;i<P;i++)tr[tot][i]=0;
len[tot]=l;
cnt[tot]=0;
state[tot]=0;
num[tot]=1;
return tot++;
}
void init(){
n=last=tot=0;
newnode(0);newnode(-1);
s[0]=-1;
fail[0]=1;
}
int getfail(int p){
while(s[n-len[p]-1]!=s[n])p=fail[p];
return p;
}
void add(int p){
s[++n]=p;
int cur=getfail(last);
if(!tr[cur][p]){
int now=newnode(len[cur]+2);
int getf=getfail(fail[cur]);
fail[now]=tr[getf][p];
tr[cur][p]=now;
state[now]=state[cur]|f(p);
num[now]=num[fail[now]]+1;
}
last=tr[cur][p];
cnt[last]++;
}
void insert(char a[]){
int i;
for(i=0;a[i];i++)add(a[i]-'a');
}
void count(){
for(i=tot-1;i>=0;i--)cnt[fail[i]]+=cnt[i];
for(i=0;i<tot;i++)ans+=1LL*cnt[i]*__builtin_popcount(state[i]);
}
}pam;
int main(){
scanf("%s",a);
pam.init();
pam.insert(a);
pam.count();
printf("%lld",ans);
return 0;
}
H function
题目描述
解题思路
AC代码
2
I query
题目描述
给定$1-n$的排列$p$，求一个区间中$min(p_i,p_j)=gcd(p_i,p_j),i<j$的$(i,j)$对数。
解题思路
问题转化为一个区间中某个元素的倍数有多少个，从左到右枚举元素及其倍数，用树状数组计数即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef long long ll;
using namespace std;
int a[N],bit[N],l[N],r[N],pos[N],res[N];
vector<int>q[N],temp[N];
int query(int p){
if(!p)return 0;
int i,ans=0;
for(i=p;i;i-=i&(-i))ans+=bit[i];
return ans;
}
void add(int p){
int i;
for(i=p;i<N;i+=i&(-i))bit[i]++;
}
int main(){
int i,j,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
for(i=1;i<=m;i++){
scanf("%d%d",&l[i],&r[i]);
q[r[i]].push_back(i);
}
for(i=1;i<=n;i++){
for(auto j:temp[i])add(j);
for(j=2*a[i];j<=n;j+=a[i]){
int id=pos[j];
if(id<=i)add(id);
else temp[id].push_back(i);
}
for(auto j:q[i])
res[j]=query(r[j])-query(l[j]-1);
}
for(i=1;i<=m;i++)printf("%d\n",res[i]);
return 0;
}
J Random Access Iterator
题目描述
求树的深度，到点$p$的时候，设$p$的儿子个数为$k$，每次随机$k$次$p$的子树$dfs$，问最后得出正确结果的概率。
解题思路
从叶子向根枚举，设某个节点$q$的失败概率$p_q$，则$p_q=(\frac{\sum_{x是q的儿子}p_x}k)^k$，即选$k$次，每次失败的概率为孩子的失败平均值，只有$k$次全部失败才会失败。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxn = 1e6+23;
int M;
int qpow(int a,int b)
{
a%=mod;
int ans=1,base=a;
while(b){
if(b&1) ans=(1ll*ans*base)%mod;
b>>=1;
base=(1ll*base*base)%mod;
}
return ans;
}
int u,v,n;
int d[maxn],p[maxn];
int vis[maxn],sz[maxn];
vector<int> g[maxn];
inline int inv(int x)
{
return qpow(x,mod-2);
}
void dfs1(int x,int dep)
{
vis[x]=1;
M=max(M,dep);
d[x]=dep;
for(auto i:g[x]) if(!vis[i]) dfs1(i,dep+1),sz[x]++;
}
void dfs(int x,int dep)
{
vis[x]=1;
if(sz[x]==0){
if(d[x]==M){
p[x]=0;return;
}
else{
p[x]=1;return;
}
}
int num=sz[x];
ll sum=0;
for(auto i:g[x]){
if(!vis[i]) dfs(i,dep+1),sum=(sum+p[i])%mod;
}
sum=sum*inv(num)%mod;
sum=qpow(sum,num);
p[x]=sum;
}
int main()
{
//printf("%d",1ll*19*inv(27)%mod);
scanf("%d",&n);
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,1);
memset(vis,0,sizeof(vis));
dfs(1,1);
//for(int i=1;i<=n;i++) printf("%d: %d\n",i,d[i]);
printf("%d",(1-p[1]+mod)%mod);//769958502
}
K Center
题目描述
求最少要多少个点能够把一堆点变成一个中心对称图形。
解题思路
枚举每两个元素的连线中点，求出交点对数以及在交点上点的个数取最大值，剩余元素个数即为答案。
AC代码 - by qxforever
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
using namespace std;
const int maxn = 1e3+23;
struct Point
{
int x,y;
Point (int x=0,int y=0) :x(x),y(y) {}
bool operator <(const Point &a) const
{
if(a.x!=x) return x<a.x;
return y<a.y;
}
};
Point operator + (Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
map<Point,int> m;
Point p[maxn];
int n;
int main()
{
cin >> n;
for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
m[p[i]+p[j]]+=2;
}
m[p[i]+p[i]]++;
}
int ans=0;
for(auto it=m.begin();it!=m.end();it++) ans=max(ans,it->second);
printf("%d",n-ans);
}
L Dice
题目描述
解题思路
AC代码
2
M Longest subsequence
题目描述
求出$S$中最长的满足字典序严格$>t$的子序列长度。
解题思路
开始看成子串了，求了一手$exkmp$，$WA$了。
维护一个最多匹配到$t$的第几位，如果遇到更大的直接对答案进行更新，特判与$t$串相等的情况即可。
AC代码 - by Mogg
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
int n, m;
typedef long long ll;
const int ms = 1e6 + 10;
char a[ms], b[ms], c[ms];
int fx[ms][26], cnt;
int main()
{
scanf("%d%d", &n, &m);
scanf("%s", a);
scanf("%s", b);
memset(fx, -1, sizeof(fx));
for (int i = 0; i < m; ++i)
{
if (i > 0)
for (int j = 0; j < 26; ++j)
{
fx[i][j] = fx[i - 1][j];
}
fx[i][b[i] - 'a'] = i;
}
int res = -1;
for (int i = 0; i < n; ++i)
{
if (a[i] > b[cnt])
{
res = max(cnt + n - i, res);
}
else
{
int idx = -1;
for (int j = 'a'; j < a[i]; ++j)
{
idx = max(idx, fx[cnt][j - 'a']);
}
if (idx > -1)
{
res = max(idx + n - i, res);
}
if (a[i] == b[cnt])
cnt++;
}
}
printf("%d", res);
return 0;
}