答疑帖：

赞助团队： UMR IT Team 和洛谷大佬栖息地

赛后题解:更新了那两道练手题的题解

赛时公告,不过一些通知也可能在团队宣言里发出

如果各位发现重题，请将你认为重复的题目链接连同这次比赛的题号一起发到@洛谷万岁 的私信，可能考虑有检举奖励QAQ

下面让我们请出@Forward_Star大佬！

好吧他可能会不在，有些问题我解决吧QAQ 但他应该马上就能回来。

最后祝大家AK愉快！

---

部分内容出自：https://www.luogu.org/blog/user21760/xiao-man-di-dancing-line-zhi-lv-ti-xie

这次比赛也是说难不难，说简单不简单呢，看看各位大佬的得分都如何呢？

---

热身题：

签个到！

这道题应该算是特别水了吧。其实可以记录下当前的方向，一旦改了方向就加1即可。下面给出std，共36ms,大家应该还能注意到空间上也给的比较小，我们就不能再一味的开1000*1000的数组，可以像std一样把数组压缩为$2\ast 1000$，一维记方向，一维记路线.其他如下（海星？）

#include<cstdio> #include<iostream> using namespace std; int n,m,r,ans; char a[2][1001]; int main() { ios::sync_with_stdio<false> scanf("%d%d",&n,&m); r=2; for (int i=1;i<=n;i++) { int row=i%2; for (int j=1;j<=m;j++) { cin>>a[row][j]; if (a[row][j]=='1'&&a[(row+1)%2][j]=='1'&&r==0) { r=1; ans++; } else if (a[row][j]=='1'&&a[row][j-1]=='1'&&r==1) { r=0; ans++; } else if (r==2) { if (a[row][j]=='1'&&a[(row+1)%2][j]=='1') r=1; else if (a[row][j]=='1'&&a[row][j-1]=='1') r=0; } } } printf("%d",ans); return 0; }

二进制之谜（前体）

那么这道题如果你一看题面一定是水的不能再水的题了，但看到数据后，c++之类的选手就要注意了：高精度来作甚？

#include<cstdio> #include<string> #include<algorithm> #include<iostream> using namespace std; struct forward_star { int next,to; }; long long a[501],c[10001][501]; int head[1000001]; forward_star edge[10000001]; int tot,cnt; string s; void plu(int now) { for (int i=1;i<=max(a[0],c[now][0]);i++) { c[now][i]+=a[i]; c[now][i+1]+=c[now][i]/1000000000; c[now][i]%=1000000000; } c[now][0]=max(a[0],c[now][0]); if (c[now][c[now][0]+1]!=0) c[now][0]++; return; } void multiply() { for (int i=a[0];i>=1;i--) { a[i]*=2; a[i+1]+=a[i]/1000000000; a[i]%=1000000000; } if (a[a[0]+1]!=0) a[0]++; return; } void add(int u,int v) { cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; } int main() { while (cin>>s) { tot++; for (int i=s.size()-1;i>=0;i--) if (s[i]=='1') add(s.size()-i-1,tot); } a[0]=1; a[1]=1; for (int i=0;i<=10000;i++) { int j=head[i]; while (j!=0) { plu(edge[j].to); j=edge[j].next; } multiply(); } for (int i=1;i<=tot;i++) { for (int j=c[i][0];j>=1;j--) { int p=10; while (j<c[i][0]&&c[i][j]<1000000000/p) { printf("0"); p*=10; } printf("%lld",c[i][j]); } printf("\n"); } return 0; }

---

比赛题目：

T1

题意：给出一个长度为$n$字符环，求回文串长度为$l$的回文中心个数。

Solution 0

我们可以有信仰！输出0，期望得分10；输出$n$，期望得分10。

Solution 1

我们可以暴力！枚举所有子串，期望得分30；

Solution 2

枚举所有回文中心，根据处理环的方式不同（开环枚举断点或补成字符串），时间复杂度也有不同，期望得分50～80（为了照顾不会Manacher的同学）；

Solution 3

把读入的串复制两次分别粘贴在原串前后，这样便和环等价，直接跑一遍Manacher，时间复杂度为$O(n)$，期望得分100分。

不懂Manacher？百度有啊

#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; }

T2

题意：给出数列an+1=(an−nk+2)k+n+1a_{n+1}=(\sqrt[k]{a_n-n}+2)^k+n+1an+1​=(kan​−n​+2)k+n+1，求最小$k$使得an≡b(moda_n \equiv b(modan​≡b(mod $m)$。

Solution 0

我们可以有信仰！输出0，期望得分10；输出INF，期望得分20.

Solution 1

我们可以暴力！直接枚举$k$递推ana_nan​，期望得分30；

Solution 2

发现通项公式an=2(n−1)+na_n=2(n-1)+nan​=2(n−1)+n再枚举$k$，期望得分60；

找出通项公式的方法：

1、打表；

2、移项得：an+1−(n+1)=(an−nk+2)ka_{n+1}-(n+1)=(\sqrt[k]{a_n-n}+2)^kan+1​−(n+1)=(kan​−n​+2)k；

两边开$k$次方：an+1−(n+1)k=an−nk+2\sqrt[k]{a_{n+1}-(n+1)}=\sqrt[k]{a_n-n}+2kan+1​−(n+1)​=kan​−n​+2；

3、我们发现什么？！令tn=an−nt_n=a_n-ntn​=an​−n，则{tn}\left\{t_n\right\}{tn​}是等差数列！

算出t1=a1−1=0t_1=a_1-1=0t1​=a1​−1=0，那么tn=2(n−1)t_n=2(n-1)tn​=2(n−1)，则an−n=2(n−1)a_n-n=2(n-1)an​−n=2(n−1)，则an=2(n−1)+na_n=2(n-1)+nan​=2(n−1)+n。

这样，通项公式就找出来了。

Solution 3

扩展BSGS+快速乘即可。

#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(n3)O(n^3)O(n3)~O(n4)O(n^4)O(n4)之间，期望得分100分。

#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; }

T4

题意较为复杂，详见题面。

本题操作较多，前面的测试点基本上都分别对应一个操作，因此我们逐个测试点分析。

$1$：没什么好说的……

$2$：最暴力的方法也能过，也没什么好说的。

$4$：这个也很简单，直接跑一遍最长路即可，当然裸$dijkstra$是过不了的，需要加堆优化；

由于出题人的数据生成器比较水，生成个数据都要几分钟，所以很良心地没有卡$spfa$。

$3$：这一测试点边权为0，那就省去了最长路了；

如何判断图的连通性？顺着去枚举并每次判断连通性，显然会超时；

这里标程用了笨办法：分块二分；由于删除的边不超过1000条，最多只会把操作分成1000个部分，每一部分操作都是添加边，显然有单调性！

顺着枚举每一部分的操作，在处理每个部分时二分判断连通性，可以减少判断的次数，优化操作时间。

至于删除操作，我用了树状数组+二分，树状数组存前缀和，即它是第几条边，然后二分它在原数组的标号即可。

$5-6$：经过上面一番分析大家大概也有整体思路了：先分块二分判连通性，再求最长路。

这里无消失的边，那么省去了分块与删除操作，其它与上面方法一样。

$7-8$：这里也是非常简单的，由于删除边对生成连通图没有贡献，所以操作同$4$。

$9-10$：其实就是测试点$3$+测试点$4$，用$3$的方法判断连通性后求个最长路即可。

可见，本题中其实大部分分都可以水的，而要AC，解决测试点$3$是关键。

#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; }

转载于:https://www.cnblogs.com/vercont/p/10210065.html

相关资源：JAVA上百实例源码以及开源项目