The Preliminary Contest for ICPC Asia Xuzhou 2019

Author： tomaito
发布时间：September 8, 2019
2198views
3 comments
435 words
Categories： ACM

##  徐州网络赛
 
### [B. so easy](https://nanti.jisuanke.com/t/41384)

离散然后并查集，赛后发现暴力也能过。。。

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair < int , int > P;
const int N = 2e6 + 10;
const int inf = 0x3f3f3f3f;
struct node{
	int x,y;
}a[N];
int b[N],c[N],tot,q,n,fa[N];
int get(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=get(fa[x]);
}
int main ()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		c[i]=a[i].y;
	}
	sort(c+1,c+q+1);
	int m=unique(c+1,c+q+1)-c-1;
	b[++tot]=c[1];
	for(int i=2;i<=m;i++)
	{
		if(c[i]-c[i-1]>1){
			b[++tot]=c[i-1]+1;
		}
		b[++tot]=c[i];
	}
	if(c[m]+1<=n) b[++tot]=c[m]+1;
	for(int i=1;i<=tot;i++)
		fa[i]=i;
	for(int i=1;i<=q;i++)
	{
		a[i].y=lower_bound(b+1,b+tot+1,a[i].y)-b;
		if(a[i].x==1){
			int u=get(a[i].y);
			fa[u]=u+1;
		}
		else{
			printf("%d\n",b[get(a[i].y)]);
		}

}
	return 0;
}
```

###[D. Carneginon](https://nanti.jisuanke.com/t/41386)

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > P;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
ull f[N],p[N];
ull f1[N];
char s[N],str[N];
int q;
void Hash()
{
	int len=strlen(s+1);
	p[0]=1;
	for(int i=1;i<=len;i++)
	{
		f[i]=f[i-1]*131+(s[i]-'a'+1);
		p[i]=p[i-1]*131;
	}
}
void hash1()
{
	int len=strlen(str+1);
	for(int i=1;i<=len;i++)
	{
		f1[i]=f1[i-1]*131+(str[i]-'a'+1);
	}
}
ull get(int l,int r)
{
	return f[r]-f[l-1]*p[r-l+1];
}
ull get1(int l,int r)
{
	return f1[r]-f1[l-1]*p[r-l+1];
}
int main ()
{
	int len,len1;
	scanf("%s",s+1);
	len1=strlen(s+1);
	Hash();
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s",str+1);
		len=strlen(str+1);
		if(len==len1){
			bool f=true;
			for(int i=1;i<=len;i++){
				if(s[i]!=str[i]) {
					f=false;
					break;
				}
			}
			puts(f?"jntm!":"friend!");
		}
		else if(len<len1){
			hash1();
			bool f=false;
			for(int i=1;i+len-1<=len1;i++){
				if(get(i,i+len-1)==get1(1,len)){
					f=true;
					break;
				}
			}
			puts(f?"my child!":"oh, child!");
		}
		else{
			hash1();
			bool f=false;
			for(int i=1;i+len1-1<=len;i++){
				if(get(1,len1)==get1(i,i+len1-1)){
					f=true;
					break;
				}
			}
			puts(f?"my teacher!":"senior!");
		}
	}
	return 0;
}
```

### [E. XKC's basketball team](https://nanti.jisuanke.com/t/41387)
倒序遍历，维护一个值递增的数组，同时保存下标，因为如果a[i]比a[i+1]小，这个a[i]是无用的，所以维护一个值递增，下标递减的数组，每次二分即可，这样二分到的值一定是位置最大的

```cpp
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

const int maxn = 1e6 + 5;

int w[maxn];
int st[maxn];
int ed[maxn],ans[maxn];

int main()
{
	int n, m;
	scanf("%d%d",&n, &m);
	for(int i = 1; i <= n; i++)
		scanf("%d",&w[i]);
	st[1] = w[n];
	ed[1] = n;
	int ss= 1;
	ans[n]=-1;
	for(int i = n-1; i >= 1; i--)
	{
		if(w[i] > st[ss])
		{
			st[++ss] = w[i];
			ed[ss] = i;
		}
		int p=lower_bound (st+1,st+ss+1,w[i]+m)-st;
		if(p>ss) ans[i]=-1;
		else ans[i]= ed[p]-i-1;
	}
	for(int i=1;i<=n;i++){
		printf("%d",ans[i]);
		if(i!=n) putchar(' ');
	}
	puts("");
	return 0;
}
```

###[G. Colorful String](https://nanti.jisuanke.com/t/41389)
这题真是气死我了，马拉车板子抄错了，T成sb了，啊啊啊啊。

首先马拉车找到以当前位置为中心的回文串左端点，由于不能暴力算，所以我们可以计算每个字符对答案的贡献，a[i][j]记录距离i最近的j字符的位置，那么这个位置到以当前字符为中心的回文串最左端点贡献都是1，预处理一下即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair < int , int > P;
const int N = 6e5 + 10;
const int inf = 0x3f3f3f3f;
char s[N], tmp[N];
int p[N];
int aa[N], a[N][30];
void manacher() {
	int len = strlen(s + 1);
	int tot = 0;
	tmp[tot++] = '$';
	tmp[tot++] = '#';
	for (int i = 1; i <= len; i++) {
		tmp[tot++] = s[i];
		tmp[tot++] = '#';
	}
	len = tot;
	int mx = 0, id = 0;
	for (int i = 1; i < len; i++)
	{
		p[i] = mx > i ? min(mx - i, p[2 * id - i]) : 1;
		while (tmp[i + p[i]] == tmp[i - p[i]]) p[i] ++;
		if (i + p[i] > mx) {
			mx = p[i]+i;
			id = i;
		}
	}
	int st = 1;
	ll ans = 0;
	for (int i = 2; i < len-1; i++)
	{
		int L = i/2-p[i]/2 + 1;
		for (int j = 0; j < 26; j++)
		{
			if (a[st][j] >= L)
			{
				ans += a[st][j] - L + 1;
			}
		}
		if (tmp[i] == '#') st++;
	}
	printf("%lld\n", ans);
}

int main() {

scanf("%s", s + 1);
	int len = strlen(s + 1);
	for (int i = 0; i < 26; i++)
		aa[i] = -1;
	for (int i = 1; i <= len; i++) {
		aa[s[i] - 'a'] = i;
		for (int j = 0; j < 26; j++)
			a[i][j] = aa[j];
	}
	manacher();
	return 0;
}
```

###[ M. Longest subsequence](https://nanti.jisuanke.com/t/41395)

$a[i][j]$预处理$i$后面大于等于$j$字符最近的位置。
基于这样的一种贪心过程，选取$x$个字符与$t$串的前$x$字符相同，然后再选取一个字符大于$t$串的第$x+1$个字符，所以要贪心寻找的最近位置,还有就是最后要有个地方要注意，如果两个串前几个字符相同，退出时还要计算一次

Last modification：September 10th, 2019 at 05:38 pm

如果觉得我的文章对你有用，请随意赞赏

3 comments

云中君
September 8th, 2019 at 04:47 pm

得第几啊！

Reply
1. tomaito
  September 8th, 2019 at 10:04 pm
  
  @云中君
  
  我们学校100名左右(╯°A°)╯︵○○○
  
  Reply
  1. 云中君
    September 8th, 2019 at 11:00 pm
    
    @tomaito
    
    那也可以了
    
    Reply