小埋的Dancing Line之旅 题解
Forward_Star
2018-10-09 07:14:43
又出锅了，还是得向大家道歉……~~（同时谴责验题人）~~
对数据有疑问的可以私信我。
## 热身题
比较水，一道模拟，一道高精压位（裸高精会T），就不多说了
## T1
题意：给出一个长度为$n$字符环，求回文串长度为$l$的回文中心个数。
注意本题中回文串与传统回文串不同之处在于：本题回文串必须有回文中心。这样只是为了防止背板选手，其实反而简化了问题。
**Solution 0**
我们可以有信仰！输出0，期望得分10；输出$n$，期望得分10。
**Solution 1**
我们可以暴力！枚举所有子串，期望得分30；
**Solution 2**
枚举所有回文中心，根据处理环的方式不同（开环枚举断点或补成字符串），时间复杂度也有不同，期望得分50～80（为了照顾不会Manacher的同学）；
然而实际上似乎数据过水，暴力比标程跑得快……
贴一个选手的暴力代码：（竟然效率是标程的10倍？）
```cpp
#include<cstdio>
using namespace std;
int n,l;
char s[2000001];
int main()
{
int ans=0;
scanf("%d%d",&n,&l);
for (int i=1;i<=n;i++)
{
s[i]=getchar();
while (s[i]<'A'||s[i]>'Z')
s[i]=getchar();
}
for (int i=1;i<=n;i++)
{
bool flag=true;
for (int j=1;j<=l/2;j++)
if (s[(i-j+n-1)%n+1]!=s[(i+j-1)%n+1])
{
flag=false;
break;
}
if (flag)
ans++;
}
printf("%d",ans);
}
```
**Solution 3**
把读入的串复制两次分别粘贴在原串前后，这样便和环等价，直接跑一遍Manacher，时间复杂度为$O(n)$，期望得分100分。
不懂Manacher？[戳这](https://blog.csdn.net/weixin_39872717/article/details/81181410)
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,l,cnt;
int str[10000001];
char t[10000001];
char s[10000001];
int main()
{
scanf("%d%d",&n,&l);
for (int i=1;i<=n;i++)
{
t[i]=getchar();
while (t[i]<'A'||t[i]>'Z')
t[i]=getchar();
}
for (int j=1;j<=3;j++)
for (int i=1;i<=n;i++)
{
s[++cnt]='0';
s[++cnt]=t[i];
}
s[++cnt]='0';
int r=0;
int now=0;
int ans=0;
for (int i=1;i<=cnt;i++)
{
if (i<=r)
str[i]=min(r-i+1,str[now*2-i]);
while (i+str[i]<=cnt&&i-str[i]>0&&s[i+str[i]]==s[i-str[i]]) str[i]++;
if (str[i]+i-1>r)
{
r=str[i]+i-1;
now=i;
}
if (str[i]-1>=l&&i>=2*n+1&&i<=cnt-2*n&&s[i]!='0')
ans++;
}
printf("%d",ans);
return 0;
}
```
($PS$：其实字符串粘贴在一端就行；另外，显然出题人也是背板选手，不然为什么要在字符之间插入'0'呢？）
## T2
题意：给出数列$a_{n+1}=(\sqrt[k]{a_n-n}+2)^k+n+1$，求最小$k$使得$a_n \equiv b(mod$ $m)$。
**Solution 0**
我们可以有信仰！输出0，期望得分10；输出INF，期望得分20.
**Solution 1**
我们可以暴力！直接枚举$k$递推$a_n$，期望得分30；
**Solution 2**
发现通项公式$a_n=(2n-1)^k+n$再枚举$k$，期望得分60；
找出通项公式的方法：
1、打表；
2、移项得：$a_{n+1}-(n+1)=(\sqrt[k]{a_n-n}+2)^k$；
两边开$k$次方：$\sqrt[k]{a_{n+1}-(n+1)}=\sqrt[k]{a_n-n}+2$；
3、我们发现什么？！令$t_n=\sqrt[k]{a_n-n}$，则$\left\{t_n\right\}$是等差数列！
算出$t_1=\sqrt[k]{a_1-1}=1$，那么$t_n=1+2(n-1)=2n-1$，则$a_n-n=(2n-1)^k$，则$a_n=(2n-1)^k+n$。
这样，通项公式就找出来了。
**Solution 3**
把$\left\{a_n \right\}$通项公式代入，原题变成：$(2n-1)^k+n \equiv b(mod$ $m)$的形式，那么移项后得$(2n-1)^k \equiv b-n(mod$ $m)$，就是一个标准的BSGS形式。扩展BSGS+快速乘即可。
```cpp
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
long long n,m,b;
map<long long,long long>mp;
inline long long multi(long long x,long long y,long long mod) //快速乘
{
long long tmp=(x*y-(long long)(((long double)x*y+0.5)/mod)*mod);
if (tmp<0) return tmp+mod; else return tmp;
}
inline long long gcd(long long a,long long b)
{
while (a%b)
{
long long k=a%b;
a=b;
b=k;
}
return b;
}
long long quickpower(long long a,int b)
{
long long t=1;
while (b>0)
{
if ((b&1)==1) t=multi(t,a,m);
if (b>1) a=multi(a,a,m);
b=b>>1;
}
return t;
}
int main()
{
mp.clear();
scanf("%lld%lld%lld",&n,&m,&b);
b=((b-n)%m+m)%m;
long long first=((multi(2,n,m)-1)%m+m)%m;
long long tmp=1;
long long ans=0;
while (true)
{
long long d=gcd(first,m);
if (d==1) break;
if (b%d)
{
printf("INF");
return 0;
}
b/=d;
m/=d;
ans++;
tmp=multi(tmp,first/d,m);
if (tmp==b)
{
printf("%lld",ans);
return 0;
}
}
long long now=b;
mp[now]=0;
int mm=ceil(sqrt(double(m)));
for (int i=1;i<=mm;i++) //预处理哈希表
{
now=multi(now,first,m);
mp[now]=i;
}
now=tmp;
long long q=quickpower(first,mm);
for (int i=1;i<=mm;i++)
{
now=multi(now,q,m);
if (mp[now])
{
printf("%lld",(((long long)(i)*(long long)(mm)-mp[now]+ans)%m+m)%m);
return 0;
}
}
printf("INF");
return 0;
}
```
理论上，本题因为$m$不是质数不能用BSGS，但是由于数据很水，裸BSGS也能拿80。
## T3
题意略。
**Solution 0**
我们可以有信仰！~~输出0，期望得分0。~~
**Solution 1**
我们可以暴力！枚举所有组合状态，期望得分30。
**Solution 2**
建图跑费用流。
将所有0视为源点，所有1视为汇点，当然这样是跑不了网络流的，所以我们设置超级源点与超级汇点分别与所有源点和所有汇点相连，由于每个0和1只能用一次，这些边的费用为0，容量为1。
之后处理二进制数，将每一个0与其后面的1连一条费用为两者位数差的绝对值且容量为1的边。
这样建图就完成了，跑一遍费用流即可。
但这里有个问题：如何保证它们不交叉？
其实显然可以发现，同样的几个数，不管对应关系交叉还是不交叉，总启发系数是相等的，这样我们就无需另外特殊处理了。
时间复杂度在$O(n^3)$~$O(n^4)$之间，期望得分100分。
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,first;
char c[501];
int w[502][502];
bool f[502][502];
int stack[502];
int dist[502];
int pre[502];
bool vis[502];
int check()
{
int top=1;
stack[1]=0;
for (int i=1;i<=n+1;i++)
dist[i]=-2147483647;
dist[0]=0;
memset(vis,false,sizeof(vis));
vis[0]=true;
while (top>0)
{
int now=stack[top];
top--;
vis[now]=false;
for (int i=0;i<=n+1;i++)
if (f[now][i]&&dist[now]+w[now][i]>dist[i])
{
dist[i]=dist[now]+w[now][i];
pre[i]=now;
if (!vis[i])
{
vis[i]=true;
stack[++top]=i;
}
}
}
return dist[n+1];
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
char s;
s=getchar();
while (s!='0'&&s!='1') s=getchar();
c[i]=s;
}
for (int i=1;i<=n;i++)
{
if (c[i]=='0')
{
w[0][i]=0;
w[i][0]=0;
f[0][i]=1;
f[i][0]=0;
}
else
{
w[i][n+1]=0;
w[n+1][i]=0;
f[i][n+1]=1;
f[n+1][i]=0;
}
for (int j=i+1;j<=n;j++)
if (c[i]=='0'&&c[j]=='1')
{
w[i][j]=j-i;
w[j][i]=-(j-i);
f[i][j]=1;
f[j][i]=0;
}
}
int ans=0;
bool find=false;
while (!find)
{
int del=check();
if (del!=-2147483647)
find=true;
else
{
ans+=del;
int t=n+1;
while (t!=0)
{
f[t][pre[t]]=!f[t][pre[t]];
f[pre[t]][t]=!f[pre[t]][t];
t=pre[t];
}
}
}
printf("%d",ans);
return 0;
}
```
**Solution 3**
由上面网络流的建图分析可以看出0和1组成了二分图，跑一遍KM做二分图最优匹配即可，期望得分100分。
**Solution 4**
数据增强版就是启发你们想更优做法的，不要认为标程就一定是最优解。
我为什么膜拜YJQ？[清华集训2016D3T2](http://uoj.ac/problem/273)这题，他可是在考场上怒踩标算几行代码A掉了。（据他说标程是写了几K的）
回到正题，我们其实可以贪心地思考：对应关系中的0肯定越左越好，1肯定越右也好；所以用两个指针分别指向最左端未对应的0与最左端已对应的1，那么每当我们找到一个1，我们先看看有没待对应的0，即查找0的指针，有的话就直接对应并移动指针就好了；如果没有，那么显然把最左端的1替换掉更优，此时启发系数调整为原值+它们两数位数的差。
如果对于思考题那种还有修改的呢？只需要加个堆就好啦！
代码短小精悍，时间复杂度为$O(n)$，完虐标程：
```cpp
#include<cstdio>
using namespace std;
int l,r,n;
int ans;
char s[1000001];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
s[i]=getchar();
while (s[i]!='0'&&s[i]!='1')
s[i]=getchar();
}
for (int i=1;i<=n;i++)
if (s[i]=='0'&&l==0)
l=i;
else if (s[i]=='1')
{
if (l==0&&r==0)
continue;
if (l==0&&r!=0)
{
ans+=i-r;
r++;
while (s[r]!='1'&&r<=i)
r++;
if (r>i)
r=0;
}
else if (l!=0)
{
ans+=i-l;
l++;
while (s[l]!='0'&&l<=i)
l++;
if (l>i)
l=0;
if (r==0)
r=i;
}
}
printf("%d",ans);
}
```
## T4
题意较为复杂，详见题面。
本题操作较多，前面的测试点基本上都分别对应一个操作，因此我们逐个测试点分析。
本题应该没人在线处理吧…下面的方法都是基于对时刻排序过的离线处理。
$1$：没什么好说的……
$2$：最暴力的方法也能过，也没什么好说的。
随手打的暴力：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct forward_star
{
int next,to,w;
};
struct newdata
{
int t,type,u,v,w,del;
};
int n,m,t,cnt,tot;
forward_star edge[1000001];
int head[100001],dist[100001];
int oriedge[1000001][3];
newdata oper[100001];
bool vis[100001];
void add(int u,int v,int w)
{
cnt++;
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt;
}
bool dijkstra(int tm)
{
for (int i=1;i<=tot;i++)
add(oriedge[i][0],oriedge[i][1],oriedge[i][2]);
memset(vis,false,sizeof(vis));
memset(dist,255,sizeof(dist));
dist[1]=0;
for (int i=1;i<=n;i++)
{
int maxdist=-1;
int k;
for (int j=1;j<=n;j++)
if (maxdist<dist[j]&&!vis[j])
{
k=j;
maxdist=dist[j];
}
vis[k]=true;
int j=head[k];
while (j!=0)
{
if (dist[k]+edge[j].w>dist[edge[j].to])
dist[edge[j].to]=dist[k]+edge[j].w;
j=edge[j].next;
}
}
if (dist[n]!=-1)
{
printf("%d\n%d",tm,dist[n]);
return true;
} else return false;
}
bool cmp(newdata i,newdata j)
{
return i.t<j.t;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
oriedge[i][0]=u;
oriedge[i][1]=v;
oriedge[i][2]=w;
++tot;
}
scanf("%d",&t);
if (t==0)
{
if (dijkstra(0)) return 0;
printf("Continue from the last checkpoint");
return 0;
}
for (int i=1;i<=t;i++)
{
int type,tmj;
scanf("%d%d",&tmj,&type);
oper[i].t=tmj;
oper[i].type=type;
if (type==0)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
oper[i].u=u;
oper[i].v=v;
oper[i].w=w;
}
else
{
int k;
scanf("%d",&k);
oper[i].del=k;
}
}
/*if (n>100)
{
printf("Continue from the last checkpoint");
return 0;
}*/
sort(oper+1,oper+t+1,cmp);
for (int i=1;i<=t;i++)
{
if (oper[i].type==0)
{
++tot;
oriedge[tot][0]=oper[i].u;
oriedge[tot][1]=oper[i].v;
oriedge[tot][2]=oper[i].w;
}
else
{
int k=oper[i].del;
for (int j=k;j<tot;j++) swap(oriedge[i],oriedge[i+1]);
tot--;
}
memset(head,0,sizeof(head));
memset(edge,0,sizeof(edge));
if (dijkstra(oper[i].t)) return 0;
}
printf("Continue from the last checkpoint");
}
```
$4$：这个也很简单，直接跑一遍最长路即可，当然裸$dijkstra$是过不了的，需要加堆优化；（其实$dijkstra$不能求最长路，应该要用$spfa$，所以标程你们忽略就好了）
由于出题人的数据生成器比较水，生成个数据都要几分钟，所以很良心地没有卡$spfa$。
$3$：这一测试点边权为0，那就省去了最长路了；
如何判断图的连通性？顺着去枚举并每次判断连通性，显然会超时；
这里标程用了笨办法：分块二分；由于删除的边不超过1000条，最多只会把操作分成1000个部分，每一部分操作都是添加边，显然有单调性！
顺着枚举每一部分的操作，在处理每个部分时二分判断连通性，可以减少判断的次数，优化操作时间。
至于删除操作，我用了树状数组+二分，树状数组存前缀和，即它是第几条边，然后二分它在原数组的标号即可。
$5-6$：经过上面一番分析大家大概也有整体思路了：先分块二分判连通性，再求最长路。
这里无消失的边，那么省去了分块与删除操作，其它与上面方法一样。
$7-8$：这里也是非常简单的，由于删除边对生成连通图没有贡献，所以操作同$4$。
$9-10$：其实就是测试点$3$+测试点$4$，用$3$的方法判断连通性后求个最长路即可。
可见，本题中其实大部分分都可以水的，而要AC，解决测试点$3$是关键。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct newdata
{
int tm,type,u,v,w,k;
};
struct forward_star
{
int next,to,w;
};
int n,m,t,cnt,tot;
forward_star edge[1100001];
newdata work[100001];
int head[100001];
int heap[100001];
int que[100001];
int ref[100001];
int tree[1100001];
int dist[100001];
bool usable[1100001];
bool vis[100001];
void add(int u,int v,int w)
{
cnt++;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
void adjust_up(int now)
{
if (now>1&&dist[heap[now]]>dist[heap[now/2]])
{
ref[heap[now]]=now/2;
ref[heap[now/2]]=now;
swap(heap[now],heap[now/2]);
adjust_up(now/2);
}
}
void adjust_down(int now)
{
if (now*2+1<=tot)
{
int k;
if (dist[heap[now*2+1]]>dist[heap[now*2]]) k=now*2+1; else k=now*2;
if (dist[heap[k]]>dist[heap[now]])
{
ref[heap[k]]=now;
ref[heap[now]]=k;
swap(heap[k],heap[now]);
adjust_down(k);
}
}
else if (now*2<=tot)
{
if (dist[heap[now*2]]>dist[heap[now]])
{
ref[heap[now]]=now*2;
ref[heap[now*2]]=now;
swap(heap[now],heap[now*2]);
adjust_down(now*2);
}
}
}
void addheap(int now)
{
heap[++tot]=now;
ref[now]=tot;
adjust_up(tot);
}
void pushheap()
{
heap[1]=heap[tot];
ref[heap[1]]=1;
tot--;
adjust_down(1);
}
void dijkstra_heap(int u)
{
memset(vis,false,sizeof(vis));
memset(dist,255,sizeof(dist));
dist[u]=0;
vis[u]=true;
addheap(u);
while (tot!=0)
{
int now=heap[1];
pushheap();
int i=head[now];
while (i!=0)
{
if (usable[i]&&i<=cnt)
if (dist[now]+edge[i].w>dist[edge[i].to])
{
dist[edge[i].to]=dist[now]+edge[i].w;
if (!vis[edge[i].to])
{
vis[edge[i].to]=true;
addheap(edge[i].to);
} else adjust_up(ref[edge[i].to]);
}
i=edge[i].next;
}
}
}
bool cmp(newdata i,newdata j)
{
return i.tm<j.tm;
}
bool check(int u,int v)
{
memset(vis,false,sizeof(vis));
int top=1;
que[top]=u;
vis[u]=true;
while (top>0)
{
int now=que[top];
top--;
int i=head[now];
while (i!=0)
{
if (i<=cnt&&usable[i])
if (!vis[edge[i].to])
{
if (edge[i].to==v) return true;
vis[edge[i].to]=true;
que[++top]=edge[i].to;
}
i=edge[i].next;
}
}
return false;
}
void adjust(int now)
{
int i=now;
while (i>0)
{
i-=i&i;
tree[now]+=tree[i];
}
tree[now]++;
}
int sum(int now)
{
int tot=0;
int i=now;
while (i>0)
{
tot+=tree[i];
i-=i&i;
}
return tot;
}
int solve(int now)
{
int l=1;
int r=cnt;
while (l<r)
{
int mid=(l+r)>>1;
if (sum(mid)<now)
l=mid+1;
else r=mid-1;
}
tree[l]--;
return l;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
adjust(i);
}
memset(usable,true,sizeof(usable));
scanf("%d",&t);
if (t==0)
{
dijkstra_heap(1);
if (dist[n]==-1)
printf("Continue from the last checkpoint");
else
{
printf("0\n");
printf("%d",dist[n]);
}
return 0;
}
else
{
bool occur=false;
bool disappear=false;
for (int i=1;i<=t;i++)
{
scanf("%d%d",&work[i].tm,&work[i].type);
if (work[i].type==0)
{
scanf("%d%d%d",&work[i].u,&work[i].v,&work[i].w);
occur=true;
}
else
{
scanf("%d",&work[i].k);
disappear=true;
}
}
if (disappear&&!occur)
{
dijkstra_heap(1);
if (dist[n]==-1)
printf("Continue from the last checkpoint");
else
{
printf("0\n");
printf("%d",dist[n]);
}
return 0;
}
sort(work+1,work+t+1,cmp);
if (check(1,n))
{
printf("0\n");
dijkstra_heap(1);
printf("%d",dist[n]);
return 0;
}
int l=1;
for (int i=1;i<=t;i++)
if (work[i].type==1)
{
int r=i-1;
if (l>=r)
{
usable[solve(work[i].k)]=false;
l=i+1;
continue;
}
int cnt_first=cnt;
int l_first=l;
for (int j=l;j<=r;j++)
{
add(work[j].u,work[j].v,work[j].w);
adjust(cnt);
}
while (l<r-1)
{
int mid=(l+r)>>1;
cnt=cnt_first+mid-l_first+1;
if (check(1,n))
r=mid;
else l=mid;
}
cnt=cnt_first+l-l_first+1;
if (check(1,n))
{
printf("%d\n",work[l].tm);
dijkstra_heap(1);
printf("%d",dist[n]);
return 0;
}
cnt=cnt_first+r-l_first+1;
if (check(1,n))
{
printf("%d\n",work[r].tm);
dijkstra_heap(1);
printf("%d",dist[n]);
return 0;
}
cnt=cnt_first+i-l_first+1;
usable[solve(work[i].k)]=false;
l=i+1;
}
int r=t;
int cnt_first=cnt;
int l_first=l;
for (int j=l;j<=r;j++)
{
add(work[j].u,work[j].v,work[j].w);
adjust(cnt);
}
while (l<r-1)
{
int mid=(l+r)>>1;
cnt=cnt_first+mid-l_first+1;
if (check(1,n))
r=mid;
else l=mid;
}
cnt=cnt_first+l-l_first+1;
if (check(1,n))
{
printf("%d\n",work[l].tm);
dijkstra_heap(1);
printf("%d",dist[n]);
return 0;
}
cnt=cnt_first+r-l_first+1;
if (check(1,n))
{
printf("%d\n",work[r].tm);
dijkstra_heap(1);
printf("%d",dist[n]);
return 0;
}
printf("Continue from the last checkpoint");
return 0;
}
return 0;
}
```