8.14 CSP 模拟 21
Talking to the Moon - Bruno Mars
I know you're somewhere out there
Somewhere far away
I want you back
I want you back
My neighbours think I'm crazy
But they don't understand
You're all I have
You're all I have
At night when the stars light on my room
I sit by myself
Talking to the Moon
Try to get to You
In hopes your on the other side talking to me too
Oh Am I a fool, Who sits alone
Talking to the moon
I'm feeling like I'm famous
The talk of the town
They say I've gone mad
Yeah I've gone mad
But they don't know what I know
Cause when the sun goes down
Someone's talking back
Yeah they're talking back
At night when the stars light on my room
I sit by myself
Talking to the Moon
Try to get to You
In hopes your on the other side talking to me too
Oh Am I a fool, Who sits alone
Talking to the moon
(Ahh...Ahh...Ahh..)
Do you ever hear me calling
Ho Hou Ho ho Hou
'Cause every nightI'm Talking to the Moon
Still try to get to You
In hopes your on the other side talking to me too
Oh Am I a fool, Who sits alone talking to the moon
Ohoooo...
I know you're somewhere out there
Somewhere far away
\(\text{Yubai round}\)
T1 Get
原题：Luogu-P5999 CEOI2016 kangaroo
考虑连续段 DP，从小到大加入数字，设 \(f_{i,j}\) 为前 \(i\) 个数字形成 \(j\) 个连续段的方案数。
如果 \(i\neq s\) 且 \(i\neq t\)，有如下几种情况：
- \(i\) 新建一个连续段，此时有 \(j\) 种方案，但如果 \(i>s\) 或 \(i>t\)，会使得边界不能再增加连续段：
-
\(i\) 加入一个连续段，这种情况一定不合法，因为此时该连续段上升，之后无法下降来合并，边界情况如果小于不能下降，如果大于不能扩充边界。
-
\(i\) 合并两个连续段，此时有 \(j\) 种方案：
如果 \(i=s\) 或 \(i=t\)，那么可以新建边界连续段或是添加到边界连续段：
点击查看代码
int n,s,t;
int f[maxn][maxn];
int main(){
n=read(),s=read(),t=read();
f[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
if(i!=s&&i!=t){
f[i][j]=(1ll*(j-(i>s)-(i>t))*f[i-1][j-1]+1ll*j*f[i-1][j+1])%mod;
}
else{
f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
}
}
}
printf("%d\n",f[n][1]);
return 0;
}
T2 On
考虑 \(|X_i-X_j|\le E_i-E_j\) 等价于 \(\max(X_i-X_j,X_j-X_i)\le E_i-E_j\)，移项得到 \(X_i+E_i\ge X_j+E_j\) 且 \(X_i-E_i\le X_j-E_j\)。
不妨设 \(x_i=X_i+E_i,y_i=X_i-E_i\)，那么要求 \(x_i\ge x_j\) 且 \(y_i\le y_j\)，容易发现按 \(x_i\) 排序后就是一个 \(y\) 的单调增加序列，可以单调栈处理，注意 \(x\) 相等的情况。
点击查看代码
int n;
pii a[maxn];
int st[maxn],top;
int main(){
n=read();
for(int i=1;i<=n;++i) a[i].fir=read(),a[i].sec=read();
sort(a+1,a+n+1,[&](pii A,pii B){
if(A.fir+A.sec==B.fir+B.sec) return A.fir-A.sec>B.fir-B.sec;
return A.fir+A.sec<B.fir+B.sec;
});
for(int i=1;i<=n;++i){
while(top&&a[st[top]].fir-a[st[top]].sec>=a[i].fir-a[i].sec) --top;
st[++top]=i;
}
printf("%d\n",top);
return 0;
}
这里有一个赛时写的做法，不知道正确性能否保证，但是通过了包括官方数据在内的所有测试点。
没有把绝对值拆开，讨论 \(X_i\) 与 \(X_j\) 的大小，得到：
-
若 \(X_i\le X_j\)，要求 \(X_i+E_i\ge X_j+E_j\)。
-
若 \(X_i\ge X_j\) 要求 \(X_i-E_i\le X_j-E_j\)。
这样得到两个单调栈，前者“支配”右侧位置，后者“支配”左侧位置，定义一个支配区间为右侧第一个大于 \(X_i+E_i\) 的位置以左，左侧第一个小于 \(X_i-E-i\) 的位置以右。
那么变成若干支配区间覆盖所有位置，按照右端点排序贪心即可求答案。
不清楚是否有正确性的地方在“一个位置可以支配右侧若干位置但只考虑了连续的部分”。
点击查看代码
int n,tot;
pii a[maxn],b[maxn];
int pre[maxn],suf[maxn];
int lpos[maxn],rpos[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int mx[maxn<<2],mn[maxn<<2];
inline void push_up(int rt){
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void build(int rt,int l,int r){
if(l==r){
mx[rt]=-inf,mn[rt]=inf;
return;
}
build(lson),build(rson);
push_up(rt);
}
void update_max(int rt,int l,int r,int p,int k){
if(l==r) return mx[rt]=k,void();
if(p<=mid) update_max(lson,p,k);
else update_max(rson,p,k);
push_up(rt);
}
void update_min(int rt,int l,int r,int p,int k){
if(l==r) return mn[rt]=k,void();
if(p<=mid) update_min(lson,p,k);
else update_min(rson,p,k);
push_up(rt);
}
int query_max(int rt,int l,int r,int k){
if(l==r) return l;
if(mx[rt<<1]>k) return query_max(lson,k);
else return query_max(rson,k);
}
int query_min(int rt,int l,int r,int k){
if(l==r) return l;
if(mn[rt<<1|1]<k) return query_min(rson,k);
else return query_min(lson,k);
}
int query(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return mn[rt];
int res=inf;
if(pl<=mid) res=min(res,query(lson,pl,pr));
if(pr>mid) res=min(res,query(rson,pl,pr));
return res;
}
#undef mid
#undef lson
#undef rson
}S;
vector<pii> V;
int f[maxn];
int main(){
n=read();
for(int i=1;i<=n;++i) a[i].fir=read(),a[i].sec=read();
sort(a+1,a+n+1,[&](pii A,pii B){
if(A.fir==B.fir) return A.sec>B.sec;
else return A.fir<B.fir;
});
for(int i=1;i<=n;++i){
if(a[i].fir!=a[i-1].fir) b[++tot]=a[i];
}
n=tot;
for(int i=1;i<=n;++i) a[i]=b[i];
pre[0]=-inf,suf[n+1]=inf;
for(int i=1;i<=n;++i) pre[i]=max(pre[i-1],a[i].fir+a[i].sec);
for(int i=n;i>=1;--i) suf[i]=min(suf[i+1],a[i].fir-a[i].sec);
S.build(1,0,n+1);
S.update_max(1,0,n+1,n+1,inf);
for(int i=n;i>=1;--i){
S.update_max(1,0,n+1,i,a[i].fir+a[i].sec);
if(pre[i]>a[i].fir+a[i].sec) rpos[i]=i;
else rpos[i]=S.query_max(1,0,n+1,a[i].fir+a[i].sec)-1;
}
S.update_min(1,0,n+1,0,-inf);
for(int i=1;i<=n;++i){
S.update_min(1,0,n+1,i,a[i].fir-a[i].sec);
if(suf[i]<a[i].fir-a[i].sec) lpos[i]=i;
else lpos[i]=S.query_min(1,0,n+1,a[i].fir-a[i].sec)+1;
}
for(int i=1;i<=n;++i) V.push_back(make_pair(lpos[i],rpos[i]));
sort(V.begin(),V.end(),[&](pii A,pii B){
return A.sec<B.sec;
});
S.build(1,0,n+1);
S.update_min(1,0,n+1,0,0);
for(int i=1,j=0;i<=n;++i){
f[i]=inf;
while(V[j].sec==i){
f[i]=min(f[i],S.query(1,0,n+1,V[j].fir-1,V[j].sec-1)+1);
++j;
}
S.update_min(1,0,n+1,i,f[i]);
}
printf("%d\n",f[n]);
return 0;
}
T3 Your
考虑如何求交点个数，容易发现增加一个节点时，这个节点与已经在多边形的节点连线会与其他线段产生交，具体可以枚举一条跨过新加入节点的线段以及分割开的节点个数，形如：
之后对其求和，得到：
这本质是 \(\dbinom{i-1}{3}\) 上指标求和得到 \(\dbinom{n}{4}\)，也可以暴力展开自然数幂和。
总点数加上 \(n\) 即可。
考虑边数，注意到在原来的线段基础上，一个交点会多产生两条边，那么上面的式子乘 \(2\) 就是答案。应用欧拉公式即可求解。
点击查看代码
int n;
ll V,E,F;
int main(){
n=read();
ll S0=n,S1=1ll*n*(n+1)%mod*inv2%mod,S2=1ll*n*(n+1)%mod*(2*n+1)%mod*inv6%mod,S3=S1*S1%mod;
V=((S3-6*S2+11*S1-6*S0)%mod+mod)*inv6%mod;
printf("%lld\n",V);
V=(V+n)%mod;
E=((S3-6*S2+14*S1-9*S0)%mod+mod)*inv3%mod;
E=(E+n)%mod;
F=(E-V+1+mod)%mod;
printf("%lld\n",F);
return 0;
}
T4 Way
原题：AtCoder-ARC141F Well-defined Abbreviation
首先删去一些字符串 \(s_i\)，满足 \(s_i\) 可以被其他字符串经过删除操作得到（即题目中所描述的）。
删除操作可以建 AC 自动机，栈维护未删除部分对应的节点，每次贪心删除即可。
之后一个结论：对于没有删去的任意两个字符串 \(s_i,s_j\)（不要求 \(i\neq j\)），若 \(s_i\) 的后缀与 \(s_j\) 的前缀有公共部分 \(B\)，设 \(s_i\) 的其他部分为 \(A\)，\(s_j\) 的其他部分为 \(C\)，那么当且仅当 \(A=C\) 时集合合法。
必要性显然，否则 \(A+B+C\) 即为可以构造的字符串。
充分性考虑对于一个 \(T\) 删去不同的字符串，若删去部分不重叠则无影响，反之重叠部分剩余即为 \(A=C\)，那么两操作等价。
注意到如果存在对于同一后缀，有两个不同字符串的前缀与其相同，那么至少有一个字符串的 \(C\neq A\)，同一前缀有两个后缀相同也同理。对于判断后缀，注意到这就是对于 \(s_i\) 状态 \(\mathrm{fail}\) 树上所有祖先，判断其 Trie 树子树内是否多于一个未删去的字符串结尾状态；对于判断前缀，即为对于 \(s_i\) 前缀所有状态，判断其 \(\mathrm{fail}\) 树子树内是否多于一个未删除的字符串结尾状态。
最后有效情况对于每个前缀唯一，那么可以 \(O(\sum |s_i|)\) 枚举哈希判断。时间复杂度 \(O(|\Sigma|\sum|s_i|)\)
点击查看代码
int t;
int n;
char str[maxn];
int pw[maxn];
struct String{
int len,end;
vector<char> s;
vector<int> h;
bool mark;
inline void input(){
scanf("%s",str+1);
len=strlen(str+1);
s.resize(len+1);
h.resize(len+1);
h[0]=0;
for(int i=1;i<=len;++i){
s[i]=str[i];
h[i]=(1ll*h[i-1]*base%mod+s[i])%mod;
}
}
inline int get_hash(int l,int r){
return (h[r]-1ll*h[l-1]*pw[r-l+1]%mod+mod)%mod;
}
}S[maxn];
struct ACAutomaton{
int tr[maxn][4],tot;
int fail[maxn];
int mark[maxn];
int submark[maxn][2],triemark[maxn][2],failmark[maxn][2];
vector<int> E[maxn];
inline void clear(){
for(int u=0;u<=tot;++u){
for(int i=0;i<4;++i) tr[u][i]=0;
fail[u]=0;
mark[u]=0,triemark[u][0]=triemark[u][1]=0,failmark[u][0]=failmark[u][1]=0;
E[u].clear();
}
tot=0;
}
inline void insert(int id){
int u=0;
for(int i=1;i<=S[id].len;++i){
int c=S[id].s[i]-'A';
if(!tr[u][c]) tr[u][c]=++tot;
u=tr[u][c];
}
S[id].end=u;
if(!mark[u]) mark[u]=id;
else S[id].mark=1;
}
queue<int> q;
inline void build(){
for(int i=0;i<4;++i){
if(tr[0][i]) q.push(tr[0][i]);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<4;++i){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}
else tr[u][i]=tr[fail[u]][i];
}
}
for(int i=1;i<=tot;++i) E[fail[i]].push_back(i);
}
void dfs1(int u,int m1,int m2){
if(!m1) m1=mark[u];
else if(!m2) m2=mark[u];
for(int v:E[u]){
submark[v][0]=mark[v];
if(!submark[v][0]) submark[v][0]=m1;
if(!submark[v][1]) submark[v][1]=m2;
dfs1(v,m1,m2);
}
}
int st[maxn],top;
inline bool check1(){
vector<int> V;
bool chk=true;
for(int i=1;i<=n;++i){
if(S[i].mark) continue;
top=0;
int u=0;
for(int j=1;j<=S[i].len;++j){
int c=S[i].s[j]-'A';
u=tr[u][c];
st[++top]=u;
if(submark[u][0]&&submark[u][0]!=i){
top-=S[submark[u][0]].len;
u=st[top];
}
else if(submark[u][1]&&submark[u][1]!=i){
top-=S[submark[u][1]].len;
u=st[top];
}
}
if(top&&top<S[i].len) chk=false;
else if(!top){
S[i].mark=true;
V.push_back(S[i].end);
}
}
return chk;
}
void dfs2(){
for(int i=1;i<=n;++i){
if(S[i].mark) continue;
int u=0;
for(int j=1;j<=S[i].len;++j){
int c=S[i].s[j]-'A';
u=tr[u][c];
++triemark[u][0],triemark[u][1]=i;
}
while(u){
++failmark[u][0],failmark[u][1]=i;
u=fail[u];
}
}
}
inline bool check2(){
bool chk=true;
for(int i=1;i<=n;++i){
if(S[i].mark) continue;
int u=0;
for(int j=1;j<=S[i].len;++j){
int c=S[i].s[j]-'A';
u=tr[u][c];
if(failmark[u][0]>1) chk=false;
}
while(u){
if(triemark[u][0]>1) chk=false;
u=fail[u];
}
}
return chk;
}
inline void solve(){
bool chk=true;
for(int i=1;i<=n;++i){
if(S[i].mark) continue;
int u=0;
for(int j=1;j<=S[i].len;++j){
int c=S[i].s[j]-'A';
u=tr[u][c];
if(!failmark[u][0]) continue;
if(S[i].get_hash(j+1,S[i].len)!=S[failmark[u][1]].get_hash(1,S[failmark[u][1]].len-j)) chk=false;
}
}
if(chk) printf("No\n");
else printf("Yes\n");
}
}ACAM;
int main(){
t=read();
pw[0]=1;
for(int i=1;i<=lim;++i) pw[i]=1ll*pw[i-1]*base%mod;
while(t--){
ACAM.clear();
n=read();
for(int i=1;i<=n;++i){
S[i].input();
ACAM.insert(i);
}
ACAM.build();
ACAM.dfs1(0,0,0);
if(!ACAM.check1()){
printf("Yes\n");
continue;
}
ACAM.dfs2();
if(!ACAM.check2()){
printf("Yes\n");
continue;
}
ACAM.solve();
}
return 0;
}
反思
T2 挂分，T3 挂分，T4 挂分。