2019ICPC徐州网络赛部分题解

其实今天成绩不怎么样,学校排名依然100+。但由于过题数量较多,打完后心里还是比较愉快的。

A.Who is better?

中国剩余定理+斐波那契博弈,首先利用中国剩余定理算出$n$,然后使用斐波那契博弈计算胜负状态。

1
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
def exgcd(a, b):
if b == 0:
return 1, 0, a
x, y, q = exgcd(b, a % b)
x, y = y, (x - a // b * y)
return x, y, q
def put1():
n = int(input())
return n
def put2():
a1, r1 = map(int, input().split())
return a1, r1
def solve(flag):
if flag:
return "Tankernb!"
else:
arr = [1, 2]
cnt = 2
while True:
res = arr[cnt - 1] + arr[cnt - 2]
if ans<res:
break
arr.append(res)
cnt = cnt + 1
flag = False
for num in arr:
if num == ans:
flag = True
break
if flag:
return "Lbnb!"
else:
return "Zgxnb!"
flag = False
n = put1()
a1, r1 = put2()
for i in range(n - 1):
a2, r2 = put2()
r= r2 - r1
x, y, d = exgcd(a1, a2)
tmp = a2 // d
if r% d != 0:
flag = True
r1 = ((x * r// d) % tmp + tmp) % tmp * a1 + r1
a1 = a1 * (a2 // d)
lcm = a1
ans = (r1 % lcm + lcm) % lcm
print(solve(flag))

B.so easy

题目大意为:给你一个长度为$n$的数组,数组内元素按顺序为$1~n$,接下来由$q$个操作,$z=1$时操作为删除$x$,$z=2$时操作为查询当前数组内$x$右边距离最近的一个数(包括其本身)。

由于b范围巨大,不能开数组去计算,因此用$map$来求解。每次删除,就将这个数链接到其下一个数,如果这个数在$map$中没出现过,就直接链接到这个数,并在$map$中加入这个数;如果出现过,就用并查集的方法继续向后找。$mp[i]$表示的是第$i$个数接下来链接到的数字。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1000000+10;
unordered_map<int,int>mp;
int n,q,op,x;
int find(int x){
if(x>n) return mp[x]=-1;
if(mp[x]==0){
mp[x]=x;
return mp[x];
}
return x==mp[x]?mp[x]:mp[x]=find(mp[x]);
}
int main()
{
scanf("%d %d",&n,&q);
while(q--){
scanf("%d %d",&op,&x);
if(op==1) mp[x]=find(x+1);
else printf("%d\n",find(x));
}
return 0;
}

C.Buy Watermelon

签到题,大于2的偶数即可分,否则不可分。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if(n>2 && n%2==0) printf("YES\n");
else printf("NO\n");
return 0;
}

D.Carneginon

题目大意为:你有一个字符串$T$,接下来输入n个字符串$S$,对于每个字符串$S$:

如果$len_T>len_S$ && $S$是$T$的字串,输出my child!
如果$len_T>len_S$ && $S$不是$T$的字串,输出oh, child!
如果$len_T<len_S$ && $T$是$S$的字串,输出my teacher!
如果$len_T<len_S$ && $T$不是$S$的字串,输出senior!
如果$len_T=len_S$ && $T$等于$S$,输出jntm!
如果$len_T=len_S$ && $T$不等于$S$,输出friend!

KMP暴力题,预先处理完$T$ 的$nxt[]$数组,接下来如果$len_S\leq len_T$的话,直接跑KMP,否则对$S$跑一遍KMP。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1000000+10;
char s[maxn],t[maxn];
int nxt[maxn],nxt2[maxn];
int T,n,m;
void get_next(char *B,int m){
int i,j;
j=0;i=1;
nxt[0]=0;
while(i<m){
if(B[i]==B[j]){
nxt[i++]=++j;
}
else{
if(j) j=nxt[j-1];
else i++;
}
}
}
void get_next2(char *B,int m){
int i,j;
j=0;i=1;
nxt2[0]=0;
while(i<m){
if(B[i]==B[j]){
nxt2[i++]=++j;
}
else{
if(j) j=nxt2[j-1];
else i++;
}
}
}
int kmp_search(char* A,char* B,int n,int m){
int i,j;
i=j=0;
while(i<n&&j<m){
if(A[i]==B[j]) i++,j++;
else if(j) j=nxt[j-1];
else i++;
}
if(j==m){
return i-m+1;
}
return -1;
}
int kmp_search2(char* A,char* B,int n,int m){
int i,j;
i=j=0;
while(i<n&&j<m){
if(A[i]==B[j]) i++,j++;
else if(j) j=nxt2[j-1];
else i++;
}
if(j==m){
return i-m+1;
}
return -1;
}
int main()
{
scanf("%s",t);
n=strlen(t);
get_next(t,n);
scanf("%d",&T);
while(T--){
scanf("%s",s);
int m=strlen(s);
if(n>m){
if(kmp_search(t,s,n,m)!=-1) printf("my child!\n");
else printf("oh, child!\n");
}
else if(n==m){
if(kmp_search(t,s,n,m)!=-1) printf("jntm!\n");
else printf("friend!\n");
}
else if(n<m){
get_next2(s,m);
if(kmp_search2(s,t,m,n)!=-1) printf("my teacher!\n");
else printf("senior!\n");
}
}
return 0;
}

E.XKC’s basketball team

题目大意:给你一个长度为$n$的数组以及一个数$m$,对于每个位置$i$,找到右边最远的位置$j$,使得$w_j\geq w_i+m(j\geq i)$ 。

首先我们进行离散化,将每个数所对应的位置储存在离散化后所对应的数组编号中,这样我们就能根据大小对每个数的位置进行统计,在离散化后的数组中,对于一个数$w_i$,假设我们能够找到一个数$w_j$,使得$w_j\geq w_i$,那么$w_{j+1}>w_i$ ,因此我们可以用状态转移方程$pos[i]=min(pos[i],pos[i+1])$去节省查询时间。
接下来对于每个数,我们使用lower_bound()​函数找到第一个大于等于$w_i+m$的数的位置即可。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1000000+10;
int a[maxn],b[maxn],c[maxn];
int pos[maxn];
int ans[maxn];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b,b+n);
int N=unique(b,b+n)-b;
for(int i=0;i<n;i++){
c[i]=lower_bound(b,b+N,a[i])-b;
pos[c[i]]=i;
}
for(int i=N-2;i>=0;i--) pos[i]=max(pos[i],pos[i+1]);
for(int i=0;i<n;i++){
if(i) printf(" ");
int x=lower_bound(b,b+N,a[i]+m)-b;
if(x==N || pos[x]<i) printf("-1");
else printf("%d",pos[x]-i-1);
}
return 0;
}

F.Little M’s attack plan

G.Colorful String

题目大意为:给你一个字符串,求$\sum每个子回文字符串中字母的种类数$ 。

马拉车+序列自动机,使用马拉车找出以这个字符为中心最长的回文串的长度,然后利用序列自动机for一个26的循环找出26个字母中每个字母离中间这个字符最近的位置,然后进行判断统计贡献即可。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1000000+10;
char s[maxn],t[maxn];
ll n;
ll f[maxn][30];
ll vis[maxn];
void Manacher(ll l)
{
for(ll i=l;i>0;i--)
{
t[2*i]=s[i];
t[2*i+1]='#';
}
t[0]='$';
t[1]='#';
ll id,mx,ans;
id=mx=ans=0;
for(ll i=1;i<=2*l+1;i++)
{
if(mx>i) vis[i]=min(vis[2*id-i],mx-i);
else vis[i]=1;
while(t[i+vis[i]]==t[i-vis[i]]) vis[i]++;
if(mx<vis[i]+i)
{
id=i;
mx=vis[i]+i;
}
ans=max(ans,vis[i]);
}
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(ll i=n;i>0;i--){
for(ll j=0;j<26;j++){
f[i-1][j]=f[i][j];
}
f[i-1][s[i]-'a']=i;
}
Manacher(n);
ll res=0;
ll pos,len,cur;
for(ll i=2;i<=n*2;i++){
pos=(i+1)/2;
if(i%2==0) len=(vis[i]+1)/2;
else len=vis[i]/2;

for(ll j=0;j<26;j++){
if(s[pos]=='a'+j){//如果相等,长度等于贡献
res+=len;
continue;
}
cur=f[pos][j];
if(cur && cur<=pos+len-1){
res+=pos+len-cur;
}
}
}
printf("%lld\n",res);
return 0;
}

H.function

I.query

题目大意:给你一个$1~n$的全排列,$m$组查询,每次查询在$[l,r]$中满足$min(pi,pj)=gcd(pi,pj)(l\leq i\leq j\leq r)$的元素的对数。

首先我们可以从这个式子中看出来,满足这个式子的情况一定是一个数是另一个数的倍数。假如我们打表计算,我们可以统计出在$10^5$的范围内,满足这个条件的数对大约有1e6个左右,因此我们可以将这些数对变成二维象限内的坐标,坐标的值为$(min(pi,pj),max(pi,pj))$。
那么这个题就转化成了:找出二维平面以$(l,l)$为左下角坐标,$(r,r)$为右上角坐标的矩阵内的点的个数。这个我们可以用树状数组统计前缀和来求解。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const int maxn=2000000+10;
int a[maxn];
struct node{
int l,r,val;
}p[maxn];
node q[maxn];
map<pii,int>mp;
int tree[maxn];
bool cmp(node i,node j){
if(i.r==j.r){
if(i.l==j.l){
return i.val<j.val;
}
return i.l<j.l;
}
return i.r<j.r;
}
int lowbit(int x){return x&(-x);}
void add(int x){
for(;x<=maxn;x+=lowbit(x)) tree[x]++;
}
int querr(int x){
int res=0;
for(;x;x-=lowbit(x)) res+=tree[x];
return res;
}
int main()
{
int n,m,x;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
a[x]=i;
}
int sum=0;
for(int i=1;i<=n;i++){
for(int j=i*2;j<=n;j+=i){
p[sum].l=min(a[i],a[j]);
p[sum].r=max(a[i],a[j]);
p[sum++].val=0;
// printf("l=%d r=%d\n",min(a[i],a[j]),max(a[i],a[j]));
}
}
for(int i=0;i<m;i++){
scanf("%d %d",&q[i].l,&q[i].r);
int l=q[i].l,r=q[i].r;
p[sum].l=l-1,p[sum].r=l-1,p[sum++].val=1;
p[sum].l=l-1,p[sum].r=r,p[sum++].val=1;
p[sum].l=r,p[sum].r=l-1,p[sum++].val=1;
p[sum].l=r,p[sum].r=r,p[sum++].val=1;
}
sort(p,p+sum,cmp);
for(int i=0;i<sum;i++){
if(p[i].val==0) add(p[i].l);
else mp[pii(p[i].l,p[i].r)]=querr(p[i].l);
}
for(int i=0;i<m;i++){
// printf("%d-%d-%d+%d=",mp[pii(q[i].r,q[i].r)],mp[pii(q[i].l-1,q[i].r)],mp[pii(q[i].r,q[i].l-1)],mp[pii(q[i].l-1,q[i].l-1)]);
printf("%d\n",mp[pii(q[i].r,q[i].r)]-mp[pii(q[i].l-1,q[i].r)]-mp[pii(q[i].r,q[i].l-1)]+mp[pii(q[i].l-1,q[i].l-1)]);
}
return 0;
}

J.Random Access Iteartor

K.Center

题目大意为:给你$n$个二维平面坐标内的点,问最少再需要几个点可以将它们变成一个中心对称图形。

中心对称图形的概念即为关于平面内某一点对称,因此我们可以直接找出以这个点为对城中心或者以两个点连成的线段的中点作为对称中心。总共约有$n^2+n=1e6$个,然后对每个点进行处理计算即可。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const ll maxn=1000000+10;
struct node{
int x,y;
}a[maxn];
map<pii,int>mp,mp2;
vector<pii>vec;
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&a[i].x,&a[i].y);
mp2[pii(a[i].x,a[i].y)]++;
}
int num=0;
for(int i=0;i<n;i++){
mp[pii(a[i].x*2,a[i].y*2)]++;
num=max(num,mp[pii(a[i].x*2,a[i].y*2)]);
vec.push_back(pii(a[i].x*2,a[i].y*2));
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
mp[pii(a[i].x+a[j].x,a[i].y+a[j].y)]++;
if(num<mp[pii(a[i].x+a[j].x,a[i].y+a[j].y)]){
num=mp[pii(a[i].x+a[j].x,a[i].y+a[j].y)];
vec.clear();
vec.push_back(pii(a[i].x+a[j].x,a[i].y+a[j].y));
}
if(num==mp[pii(a[i].x+a[j].x,a[i].y+a[j].y)]){
vec.push_back(pii(a[i].x+a[j].x,a[i].y+a[j].y));
}
}
}
int res=n;
for(int i=0;i<vec.size();i++){
int x=vec[i].first,y=vec[i].second;
int cur=n;
for(int j=0;j<n;j++){
if((a[j].x*2==x && a[j].y*2==y) || (mp2[pii(x-a[j].x,y-a[j].y)])) cur--;
}
res=min(res,cur);
}
printf("%d\n",res);
return 0;
}

L.Dice

M.Longest subsequence

题目大意为:给你两个长分别为$n,m$的两个字符串$S,T$,问从$S$中找到的最长的字典序严格大于$T$的字串的长度最长为多长。

由于一定要严格大于,因此我们只要找到前面$i$相同,第i+1个比$T[i+1]$即可,然后取最优解。找相同前缀可以用序列自动机来处理。

1
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;
char s[maxn],t[maxn];
int nxt[maxn][30];
vector<int> vec;
int ans=0,cnt=0,n,m,flag;
void init(char *s){
int len=strlen(s);
for(int i=0;i<26;i++) nxt[len][i]=INF;
for(int i=len-1;i>=0;i--){
for(int j=0;j<26;j++){
nxt[i][j]=nxt[i+1][j];
}
nxt[i][s[i]-'a']=i;
}
}
int main()
{
scanf("%d %d %s %s",&n,&m,s,t);
init(s);
for(int i=0;i<n;i++){
for(int j=t[cnt]-'a'+1;j<26;j++){
if(nxt[i][j]!=INF){
flag=1;
ans=max(ans,cnt+n-nxt[i][j]);
}
}
if(s[i]==t[cnt]){
cnt++;
vec.push_back(i);
}
if(cnt==m) break;
}
if(!flag){
if(vec.size()>=m){
if(vec[m-1]==n-1) printf("-1\n");
else printf("%d\n",m+(n-vec[m-1]-1));
return 0;
}
printf("-1\n");
return 0;
}
if(vec.size()>=m&&vec[m-1]!=-1){
ans=max(ans,m+(n-vec[m-1]-1));
}
printf("%d\n",ans);
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------