前言
- 比赛链接。
T1 因为忘记判一个东西挂分，听说还有被卡哈希的，题目若按照难度正序的话应该是 T2、T1、T4、T3，T4 看到图论就比较胆怯没怎么想，T3 当然没想出来。
总而言之 T1 挂分的人挺多的，T2 都能做出来，T1 不挂分的排名都很靠前。
打得……不算很唐吧，除了 T1 挂分。
T1 串串
找回文中心，一个回文中心为合法的需满足一下条件之一：
- 其回文右端点为 \(n\)。
- 其回文左端点为 \(1\)，且其右端点为合法回文中心。
由此从后往前扫一遍就行了，可以直接用哈希判回文，如果说回文中心是马拉车的专利话也可以用马拉车，二者复杂度单组数据均为 \(O(n)\)，仔细想来直接暴力的复杂度似乎也能够过。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int T;
char s[N];
ll h[2][N],b[N];
bool vis[N];
void init(int n)
{
b[1]=1331;
for(int i=2;i<=n;i++)
b[i]=b[i-1]*b[1]%P;
}
void get_hash(char s[])
{
int n=strlen(s);
for(int i=0;i<=n-1;i++)
h[0][i+1]=(h[0][i]*b[1]%P+s[i])%P;
h[1][n+1]=0;
for(int i=n-1;i>=0;i--)
h[1][i+1]=(h[1][i+2]*b[1]%P+s[i])%P;
}
bool check(int l,int mid,int r)
{
ll ans1=(h[0][mid]-h[0][l-1]*b[mid-l+1]%P+P)%P;
ll ans2=(h[1][mid]-h[1][r+1]*b[r-mid+1]%P+P)%P;
return ans1==ans2;
}
void solve(char s[])
{
int n=strlen(s);
vis[n]=1;
for(int i=n-1;i>=2;i--)
{
if(check(i-(n-i),i,n)) vis[i]=1;
else if(i+(i-1)<=n)
{
if(!vis[i+(i-1)]) continue;
if(check(1,i,i+(i-1))) vis[i]=1;
}
}
for(int i=1;i<=n;i++)
if(vis[i])
{
write(i),putchar(' ');
vis[i]=0;
}
}
signed main()
{
init(N-10);
read(T);
while(T--)
{
cin>>s;
get_hash(s);
solve(s);
puts("");
}
}
T2 排排
签到题，但由于放在了 T2 的位置且第一眼没有想到，比较晚才切。
答案只有 \(4\) 中情况：
- \(0\)：\(\forall a_i=i\)
- \(1\)：存在一个点满足 \(a_i=i\) 且满足 \(\forall j<i,a_j<a_i;\forall j>i,a_j>a_i\)，因为其为一个排列，不会出现重复元素，所以直接记录前缀最大值即可，不需要开桶。
- \(2\)：发现若 \(1\) 在位置 \(1\) 上，下一步取 \(k=1\) 即可完成，所以此步在 \(1\) 的右面找一个 \(k\) 使得 \(1\) 回到位置 \(1\)，下一步即可完成。\(n\) 同理。
- \(3\)：基于上面操作，若 \(a_1=n\) 且 \(a_n=1\)，则需要先进行一步打破这个状态。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int T,n,a[N];
signed main()
{
read(T);
while(T--)
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
bool flag=0;
for(int i=1;i<=n;i++)
if(a[i]!=i)
{
flag=1;
break;
}
if(!flag)
{
puts("0");
continue;
}
flag=0;
int maxx=0;
for(int i=1;i<=n;i++)
{
if(a[i]==i&&maxx<i)
{
puts("1");
flag=1;
break;
}
maxx=max(maxx,a[i]);
}
if(flag) continue;
if(a[1]!=n||a[n]!=1)
{
puts("2");
continue;
}
puts("3");
}
}
T3 序序
-
只有一组查询对应原题：P6406 [COCI2014-2015#2] Norma。
-
部分分 \(10pts\)：\(O(n^2m)\) 暴力，这个卡卡常甚至能 \(20pts\)。
-
部分分 \(20pts\)：\(O(n^2)\) 二维前缀和预处理，\(O(1)\) 查询，空间复杂度也是 \(n^2\)。
-
部分分 \(30pts\)：在 \(20pts\) 的基础上序列递增的特殊性质用莫队冲过去。
-
部分分 \(40pts\)：对于单词查询复杂度为 \(O(n\log n)\) 分治，可过小数据点和只有一组查询的数据。
-
部分分 \(50pts\)：在 \(40pts\) 的基础上序列递增的特殊性质用莫队冲过去。
-
正解没打出来。
单独写一下 \(40pts\) 的这个分治，对于 \([l,r]\) 依然是处理经过 \(mid\) 的贡献再递归 \([l,mid],[mid+1,r]\)。
从 \(mid\) 开始向左枚举左端点，此时有 \(min_l=\min\limits_{j=i}^{mid} a_j,max_l=\max\limits_{j=i}^{mid} a_j\)，考虑其对 \([mid+1,r]\) 的贡献。
设 \(x\) 表示 \(min_l\) 在 \([mid+1,r]\) 中最远覆盖距离，\(y\) 表示 \(max_l\) 最远覆盖距离，不妨设 \(x<y\)，有：
- 在 \([mid+1,x]\) 这段区间内最大值为 \(max_l\)，最小值为 \(min_l\)，直接处理即可；
- 在 \([x+1,y]\) 这段区间内最大值为 \(max_l\)，最小值不为 \(min_l\)；
- 在 \([y+1,r]\) 这段区间内最大值不为 \(max_l\)，最小值不为 \(min_l\)。
不放单独处理一个区间 \([mid+1,r]\) 的最大值、最小值、最大值乘最小值前缀和，三种情况分别处理，因为最小值单调不增，最大值单调不减，所以此做法是正确的。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
ll n,m,a[N],s1[N],s2[N],s3[N],ans;
void solve(int l,int r)
{
if(l==r)
{
(ans+=a[l]*a[l]%P)%=P;
return ;
}
ll mid=(l+r)>>1,mi,mx,minn,maxx;
mi=minn=0x3f3f3f3f,mx=maxx=0;
s1[mid]=s2[mid]=s3[mid]=0;
for(int i=mid+1;i<=r;i++)
{
minn=min(minn,a[i]),maxx=max(maxx,a[i]);
s1[i]=(s1[i-1]+minn)%P;
s2[i]=(s2[i-1]+maxx)%P;
s3[i]=(s3[i-1]+minn*maxx%P)%P;
}
for(int i=mid,j=mid,k=mid;i>=l;i--)
{
mi=min(mi,a[i]),mx=max(mx,a[i]);
for(;j<r&&a[j+1]>mi;j++);
for(;k<r&&a[k+1]<mx;k++);
int w1=min(j,k),w2=max(j,k);
if(w1>mid)
(ans+=mi*mx%P*(w1-mid)%P)%=P;
if(k>w1)
(ans+=mx*(s1[k]-s1[w1]+P)%P)%=P;
if(j>w1)
(ans+=mi*(s2[j]-s2[w1]+P)%P)%=P;
(ans+=s3[r]-s3[w2]+P)%=P;
}
solve(l,mid),solve(mid+1,r);
}
signed main()
{
read(n,m);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1,l,r;i<=m;i++)
{
read(l,r);
ans=0;
solve(l,r);
write(ans),puts("");
}
}
T4 桥桥
操作分块，每块单独处理，双指针从边权从大到小处理，加可撤销并查集维护，根据时间戳判定当前边权，全部操作完后暴力改掉所有边即可。
取快长为 \(\sqrt q\)，每个块复杂度为 \(O(m\log m+q\log n)\)，总复杂度约为 \(q\sqrt q\log m\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,Q,t,pos[N],f[N],sz[N],vis[N],ans[N];
struct aa {int x,y,w,id;}e[N];
struct bb {int s,w,id;};
vector<bb>c,q,tmp;
stack<int>s1,s2;
bool cmp1(aa a,aa b) {return a.w>b.w;}
bool cmp2(bb a,bb b) {return a.w>b.w;}
int find(int x) {return f[x]==x?x:find(f[x]);}
void merge(int x,int y,stack<int> &s)
{
x=find(x),y=find(y);
if(x==y) return ;
if(sz[x]<sz[y]) swap(x,y);
s.push(y);
sz[x]+=sz[y];
f[y]=x;
}
void split(stack<int> &s)
{
while(!s.empty())
{
sz[f[s.top()]]-=sz[s.top()];
f[s.top()]=s.top();
s.pop();
}
}
void solve()
{
sort(e+1,e+1+m,cmp1);
sort(q.begin(),q.end(),cmp2);
for(int i=1;i<=m;i++) pos[e[i].id]=i;
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
tmp.clear();
for(auto y:c)
{
vis[y.s]=-1;
tmp.push_back({y.s,e[pos[y.s]].w,0});
}
for(auto y:c)
tmp.push_back({y.s,y.w,y.id});
while(!s1.empty()) s1.pop();
for(int i=0,j=1;i<q.size();i++)
{
for(;e[j].w>=q[i].w&&j<=m;j++)
if(vis[e[j].id]==0) merge(e[j].x,e[j].y,s1);
for(auto y:tmp)
if(y.id<=q[i].id) vis[y.s]=y.w;
for(auto y:c)
if(vis[y.s]>=q[i].w) merge(e[pos[y.s]].x,e[pos[y.s]].y,s2);
ans[q[i].id]=sz[find(q[i].s)];
split(s2);
}
for(auto y:c)
{
e[pos[y.s]].w=y.w;
vis[y.s]=0;
}
c.clear(),q.clear();
}
signed main()
{
read(n,m);
t=1075;
for(int i=1,x,y,z;i<=m;i++)
{
read(x,y,z);
e[i]={x,y,z,i};
}
read(Q);
for(int i=1,op,x,y;i<=Q;i++)
{
read(op,x,y);
if(op==1) c.push_back({x,y,i});
else q.push_back({x,y,i});
if(i%t==0) solve();
}
if(Q%t!=0) solve();
for(int i=1;i<=Q;i++)
if(ans[i]!=0) write(ans[i]),puts("");
}
总结
注意一些细节，避免像 T1 一样挂分。
附录
其实是前天打的，今天才补上。
标签：19,void,mid,Tp,2024,int,read,inline,集训 From： https://www.cnblogs.com/Charlieljk/p/18347923