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代码点击
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768def mul(a,b,mod): res = 0 while(b>0): if(b%2==1): res = (res + a)%mod a = (a + a)%mod b //=2 return res gcd = 0def exgcd(a, b): global gcd if (b == 0): gcd = a return 1,0 x,y = exgcd(b,a%b) return y,x-a//b * ydef 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 = 1while 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点击
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include using namespace std;int n, q;typedef long long ll;const int ms = 1e6;int a[ms * 3], cnt;pairb[ms];//unordered_mapid;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代码点击
12345678910#includetypedef 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点击
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118#include #include #include #include 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点击
12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include using namespace std;int n, m;typedef long long ll;const int ms = 1e6;paira[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代码点击
12
G Colorful String
题目描述定义一个字符串的价值为其所有回文子串的包含的不同字符数，求$s$的价值。
解题思路状态压缩，建立一个回文树，记录下每一个本质不同的回文串出现的次数计数即可。
AC代码点击
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#includetypedef long long ll;using namespace std;#define N 1200010#define P 26char a[N];ll ans;ll f(int x){return 1LL<=0;i--)cnt[fail[i]]+=cnt[i]; for(i=0;i
H function
题目描述解题思路AC代码点击
12
I query
题目描述给定$1-n$的排列$p$，求一个区间中$min(p_i,p_j)=gcd(p_i,p_j),i
解题思路问题转化为一个区间中某个元素的倍数有多少个，从左到右枚举元素及其倍数，用树状数组计数即可。
AC代码点击
12345678910111213141516171819202122232425262728293031323334353637#includetypedef long long ll;using namespace std;#define N 100010int a[N],bit[N],l[N],r[N],pos[N],res[N];vectorq[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
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点击
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include #include #include #include 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 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
K Center
题目描述求最少要多少个点能够把一堆点变成一个中心对称图形。
解题思路枚举每两个元素的连线中点，求出交点对数以及在交点上点的个数取最大值，剩余元素个数即为答案。
AC代码 - by qxforever点击
123456789101112131415161718192021222324252627282930313233#include 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 m;Point p[maxn];int n;int main(){ cin >> n; for(int i=0;isecond); printf("%d",n-ans);}
L Dice
题目描述解题思路AC代码点击
12
M Longest subsequence
题目描述求出$S$中最长的满足字典序严格$>t$的子序列长度。
解题思路开始看成子串了，求了一手$exkmp$，$WA$了。
维护一个最多匹配到$t$的第几位，如果遇到更大的直接对答案进行更新，特判与$t$串相等的情况即可。
AC代码 - by Mogg点击
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include 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;}