考试过程：先读题，然后觉得开题顺序1324。首先是T1，我觉得应该比较简单，但是自己做了差不多两个小时，换了一种做法终于过了大样例，追回了心态。但是实际上我的做法是不对的。然后是T3，50分做法基本上很快就能想到，然后就开始想正解，但是实在不会了，想了一个小时左右就打上暴力走了。然后是T2，我刚开始想跑最短路之类的东西，但是复杂度太高了。然后我就想乱搞一下利用并查集直接缩点，其实这就是正解，但是我看错了数据范围，\(n\times m<=5e4\),我以为是\(n,m<=5e4\),然后数组就开小了，并且因为存在有向边，不能直接用并查集缩点，但是当时我没想到，就挂了。
总结：考试分配时间尽量均匀，T1不要花费那么长的时间了，要保证后面的题也能拿到相应的分数。
T1 构造字符串
思路：分析可知有一些位置填的数字相同，其他位置填的数字不同，那么我们可以利用并查集将填数字相同的位置缩起来。注意，因为存在缩点操作，我刚开始利用\(bitset\)存储与当前数字不同的并查集，调了半天，应该是这里会出现问题。后来我把代码重构，利用\(vector\)存储就对了。
代码如下：
AC_code
#include<bits/stdc++.h>
#define re int
#define ii inline int
#define iv inline void
#define F first
#define S second
using namespace std;
const int N=1010;
bitset<N> col[N];
struct node
{
int y,len;
friend bool operator < (node a,node b) {return a.y!=b.y?a.y>b.y:a.len<b.len;}
};
int n,m;
int ans[N],be[N];
vector<int> lt[N],ban[N];
vector<pair<int,int> >cun;
vector<node> v[N];
priority_queue<int,vector<int>,greater<int> > Q;
bool vis[N];
ii read()
{
int x=0; char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii gett(int x) {return x==be[x]?x:be[x]=gett(be[x]);}
int main()
{
freopen("str.in","r",stdin);
freopen("str.out","w",stdout);
n=read(),m=read();
int x,y,z;
for(re i=1;i<=m;i++)
{
x=read(),y=read(),z=read();
if(x>y) swap(x,y);
v[x].push_back((node){y,z});
}
memset(ans,-1,sizeof(ans));
for(re i=1;i<=n;i++) be[i]=i,lt[i].push_back(i);
for(re i=1;i<=n;i++)
{
if(!v[i].size()) continue;
for(re j=0;j<v[i].size();j++)
{
node p=v[i][j];
if(p.len==0) continue;
for(re k=0;k<p.len;k++)
{
int fx=gett(i+k),fy=gett(p.y+k);
if(fx==fy) continue;
if(fx>fy) swap(fx,fy);
be[fy]=fx;
while(lt[fy].size()) lt[fx].push_back(lt[fy].back()),lt[fy].pop_back();
}
}
}
for(re i=1;i<=n;i++)
{
if(!v[i].size()) continue;
for(re j=0;j<v[i].size();j++)
{
node p=v[i][j];
int fx=gett(i+p.len),fy=gett(p.y+p.len);
if(fx==fy) {printf("-1\n");return 0;}
ban[fx].push_back(fy);
ban[fy].push_back(fx);
}
}
for(re i=1;i<=n;i++)
{
int fx=gett(i);
if(vis[fx]) continue;
vis[fx]=1;
int now=0;
for(re j=0;j<ban[fx].size();j++) if(ans[ban[fx][j]]!=-1) Q.push(ans[ban[fx][j]]);
while(!Q.empty())
{
if(now==Q.top()) ++now;
Q.pop();
}
ans[fx]=now;
}
for(re i=1;i<=n;i++) printf("%d ",ans[gett(i)]);
return 0;
}
/*
6 6
4 1 2
4 2 2
4 2 2
5 2 1
6 2 0
2 4 2
*/
T2 寻宝
思路：因为没有修改，只需要判定，所以我们可以利用并查集将所有联通块缩起来。注意，此时不能走传送门，因为传送门是单向的。我们可以缩点后利用\(floyd\)和\(bitset\)判断联通块之间的联通关系。
代码如下：
AC_code
#include<bits/stdc++.h>
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"AC"<<endl
using namespace std;
const int N=5e4+5;
int dx[5]={-1,0,0,1};
int dy[5]={0,1,-1,0};
int n,m,k,q,timi;
vector<int> v[N],pos[N],cun;
char c[N];
int be[N];
bool vis[N],hav[N];
bitset<N> BS[N];
ii read()
{
int x=0; char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii gett(int x) {return x==be[x]?x:be[x]=gett(be[x]);}
iv dfs(int zu,int x,int y,int lx,int ly)
{
be[pos[x][y]]=zu;
vis[pos[x][y]]=1;
for(re i=0;i<4;i++)
{
if(x+dx[i]<=0 or x+dx[i]>n or y+dy[i]<=0 or y+dy[i]>m) continue;
if(x+dx[i]==lx and y+dy[i]==ly) continue;
if(v[x+dx[i]][y+dy[i]]==1) continue;
if(vis[pos[x+dx[i]][y+dy[i]]])
{
int fx=gett(pos[x+dx[i]][y+dy[i]]);
if(fx!=zu) be[fx]=zu;
continue;
}
dfs(zu,x+dx[i],y+dy[i],x,y);
}
}
int main()
{
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
n=read(),m=read(),k=read(),q=read();
for(re i=1;i<=n;i++)
{
scanf("%s",c+1);
v[i].push_back(0);
pos[i].push_back(0);
for(re j=1;j<=m;j++)
{
if(c[j]=='.') v[i].push_back(0);
else v[i].push_back(1);
pos[i].push_back(++timi);
be[timi]=timi;
}
}
for(re i=1;i<=n;i++)
{
for(re j=1;j<=m;j++)
{
if(vis[pos[i][j]] or v[i][j]==1) continue;
dfs(pos[i][j],i,j,0,0);
}
}
int x,y,x2,y2;
for(re i=1;i<=k;i++)
{
x=read(),y=read(),x2=read(),y2=read();
int fx=gett(pos[x][y]),fy=gett(pos[x2][y2]);
if(!hav[fx]) cun.push_back(fx),hav[fx]=1;
if(!hav[fy]) cun.push_back(fy),hav[fy]=1;
BS[fx][fy]=1;
}
sort(cun.begin(),cun.end());
for(re k=0;k<cun.size();k++)
{
for(re i=0;i<cun.size();i++)
{
for(re j=0;j<cun.size();j++)
{
if(k==i or k==j or i==j) continue;
if(BS[cun[i]][cun[k]] and BS[cun[k]][cun[j]]) BS[cun[i]][cun[j]]=1,BS[cun[i]]|=BS[cun[j]];
}
}
}
while(q--)
{
x=read(),y=read(),x2=read(),y2=read();
int fx=gett(pos[x][y]),fy=gett(pos[x2][y2]);
if(fx==fy or BS[fx][fy]) printf("1\n");
else printf("0\n");
}
return 0;
}
T3 序列
容易发现这是一个与斜率有关的题目，这种题目通常通过维护凸包，或者李超树维护
跨过\(p_i\)的区间容易转化为：以\(p\)点单独的贡献+\(p_{i-1}\)为右端点的最优+以\(p_{i}+1\)为左端点的最优
两个问题同理，以\(p{i+1}\)为左端点为例
设\(sa_i=\sum_{j=1}^{i} a_j\) ,\(sb_i=\sum_{j=1}^{i} b_j\)
最优就是\(i+1\)到\(n\)中最大的原式值减去前缀\(p\)的原式值。
离线之后李超树维护直线即可
注意一个细节，负数减去负数可能会得到正数，所以线段树的返回值可以是负数，所以要有建树打标记之类的操作。
时间复杂度为\(O(n\log n)\)，常数略大，需要大力卡常。
AC_code
#include<bits/stdc++.h>
#define int long long
#define re int
#define ii inline int
#define iv inline void
#define D double
#define F first
#define S second
using namespace std;
const int N=1e6+10;
const int INF=1e18;
struct node
{
int p,k,id;
}cun[N];
struct SEG
{
int k,b;
}s[N];
int n,m,mx,tot;
int ans[N];
int a[N],b[N],pa[N],pb[N],sa[N],sb[N];
ii read()
{
int x=0; char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
struct LCT
{
#define lc (rt<<1)
#define rc (rt<<1|1)
int id[N<<3];
bool no[N<<3];
ii calc(int id,int x) {return s[id].k*x+s[id].b;}
iv build(int rt,int l,int r)
{
id[rt]=0,no[rt]=1;
int mid=floor((l+r)/2.0L);
if(l==r) return;
build(lc,l,mid),build(rc,mid+1,r);
}
iv insert(int rt,int l,int r,int L,int R,int p)
{
int mid=floor((l+r)/2.0L);
int u=id[rt],tmp1=calc(u,mid),tmp2=calc(p,mid);
if(l>R or r<L) return;
if(L<=l and r<=R)
{
if(no[rt]) {no[rt]=0,id[rt]=p;return;}
if(l==r)
{
if(tmp2>tmp1) id[rt]=p;
return;
}
if(s[u].k<s[p].k)
{
if(tmp2>tmp1)
{
id[rt]=p;
insert(lc,l,mid,L,R,u);
}
else insert(rc,mid+1,r,L,R,p);
}
else if(s[u].k>s[p].k)
{
if(tmp2>tmp1)
{
id[rt]=p;
insert(rc,mid+1,r,L,R,u);
}
else insert(lc,l,mid,L,R,p);
}
else
{
if(s[p].b>s[u].b) id[rt]=p;
}
return;
}
if(L<=mid) insert(lc,l,mid,L,R,p);
if(mid<R) insert(rc,mid+1,r,L,R,p);
}
ii query(int rt,int l,int r,int x)
{
if(l>x or r<x) return -INF;
int res=(no[rt])?-INF:calc(id[rt],x);
int mid=floor((l+r)/2.0L);
if(l==r) return res;
return max(res,max(query(lc,l,mid,x),query(rc,mid+1,r,x)));
}
#undef lc
#undef rc
}T;
inline bool com(node a,node b) {return a.p<b.p;}
signed main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
n=read(),m=read();
for(re i=1;i<=n;i++) a[i]=read(),b[i]=read();
for(re i=1;i<=m;i++)
{
cun[i]=(node){read(),read(),i};
mx=max(mx,abs(cun[i].k));
}
sort(cun+1,cun+m+1,com);
int cnt=mx;
for(re i=1;i<=n;i++)
{
pa[i]=pa[i-1]+a[i];
pb[i]=pb[i-1]+b[i];
}
T.build(1,-cnt,cnt);
for(re i=m,j=n;i;i--)
{
while(j>cun[i].p and j>0)
{
s[++tot]=(SEG){pb[j],pa[j]};
T.insert(1,-cnt,cnt,-cnt,cnt,tot);
--j;
}
int nx=cun[i].k;
int tmp=T.query(1,-cnt,cnt,-nx)-(pa[cun[i].p]-nx*pb[cun[i].p]);
if(tmp>0) ans[cun[i].id]+=tmp;
ans[cun[i].id]+=a[cun[i].p]-cun[i].k*b[cun[i].p];
}
tot=0;
T.build(1,-cnt,cnt);
for(re i=n;i;i--)
{
sa[i]=sa[i+1]+a[i];
sb[i]=sb[i+1]+b[i];
}
for(re i=1,j=1;i<=m;i++)
{
while(j<cun[i].p and j<=n)
{
s[++tot]=(SEG){sb[j],sa[j]};
T.insert(1,-cnt,cnt,-cnt,cnt,tot);
++j;
}
int nx=cun[i].k;
int tmp=T.query(1,-cnt,cnt,-nx)-(sa[cun[i].p]-nx*sb[cun[i].p]);
if(tmp>0) ans[cun[i].id]+=tmp;
}
for(re i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}