Loading... ## 徐州网络赛 <!--more--> ### [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 © 允许规范转载 Support 如果觉得我的文章对你有用,请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
3 comments
得第几啊!
我们学校100名左右(╯°A°)╯︵○○○
那也可以了