Codeforces Round 1340 简要题解_综合

第一次听说因为有假题unrated了。。。

A. Nastya and Strange Generator

略

B. Nastya and Scoreboard

略

C. Nastya and Unexpected Guest

考虑一个分层图最短路的算法。
先给 $d_i$ 排序去重。令 $F [i] [j]$ 表示走到 $d_i$ ，时间 $mod(g+r)=j\bmod \ (g+r)=j$ 的最短时间（实际上第二维只用记 $0?g0\sim g$ ），转移的时候考虑向左右最近的 $d$ 走过去即可。
如果直接使用dijkstra算法，时间复杂度为 $O(mglog?m)\mathcal O(mg\log m)$ ，不能接受。不过注意到按 $?F[i][j]g+r?\lfloor \frac{F[i][j]}{g+r}\rfloor$ 来看这是个 $O(m)\mathcal O(m)$ 层的分层图，且每层的距离上界是 $g$ ，直接对每个距离开个队列类似bfs实现即可。
时间复杂度为 $O(mg)\mathcal O(mg)$ 。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3fusing namespace std;bool f[10005][1005];
queue <int> q1[1005],q2[10005];int num[10005];int main() {
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%d",&num[i]);int G,B;scanf("%d%d",&G,&B);sort(num+1,num+m+1);m=unique(num+1,num+m+1)-num-1;int ans=inf,s=0;q2[0].push(1);while (ans==inf) {
    if (q2[s].empty()) {
    puts("-1");return 0;} while (!q2[s].empty()) {
    int x=q2[s].front();q2[s].pop();q1[0].push(x);f[x][0]=1;if (num[m]-num[x]<=G) ans=min(ans,(G+B)*s+(num[m]-num[x]));}if (ans<inf) break;for(int i=0;i<G;i++)while (!q1[i].empty()) {
    int x=q1[i].front();q1[i].pop();if (x>1) {
    int t=i+num[x]-num[x-1];if (t<=G&&!f[x-1][t]) {
    f[x-1][t]=1;q1[t].push(x-1);}}if (x<m-1) {
    int t=i+num[x+1]-num[x];if (t<=G&&!f[x+1][t]) {
    f[x+1][t]=1;q1[t].push(x+1);}}}s++;while (!q1[G].empty()) {
    int x=q1[G].front();q1[G].pop();if (x>1) q2[s].push(x); }}printf("%d\n",(ans<inf)?ans:-1);return 0;
}

D. Nastya and Time Machine

令 $i$ 号点的度数为 $deg_i$ ，注意到对于点 $i$ 至少会进入 $deg_i$ 次，且每次进入时的 $t > 0$ ，因此答案下界为 $D=\max_{i=1}^{n}deg_i$ 。
考虑构造达到这个下界。我们用dfs的方式来构造一个算法，发现有算法能使若进入点 $x$ 子树时的时间为 $0<t≤D0<t\leq D$ ，则离开时的时间为 $t ? 1$ （也即父亲走过来前的时间为 $t ? 1$ ，而回到父亲的时间为 $t$ ）。
这个算法可以递归构造，考虑依次遍历 $x$ 的每个儿子子树，若 $x$ 出发前时间不超过 $D ? 1$ 直接递归调用算法，时间 $+ 1$ ，否则先改变时间为 $D-deg_x$ ，再调用即可。如果最后都没有改变过时间，那么遍历完后直接强行改成出发前时间 $? 1$ 。注意到由于 $degx≤Ddeg_x\leq D$ ，因此至多改变时间一次，于是确实合法。
时间复杂度为 $O(n)\mathcal O(n)$ 。

#include <bits/stdc++.h>
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;vector <int> e[100005];
int deg[100005],maxd;vector <pr> vt;void dfs(int x,int fa,int s) {
    bool v=0;int fir=s;vt.push_back(pr(x,s));for(int i=0;i<e[x].size();i++)if (e[x][i]!=fa) {
    int u=e[x][i];if (s==maxd) {
    v=1;s=maxd-deg[x];vt.push_back(pr(x,s));}s++;dfs(u,x,s);vt.push_back(pr(x,s));}if (!v&&x>1) vt.push_back(pr(x,fir-1));
}int main() {
    int n;scanf("%d",&n);for(int i=1;i<n;i++) {
    int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);e[y].push_back(x);deg[x]++;deg[y]++;}for(int i=1;i<=n;i++) maxd=max(maxd,deg[i]);dfs(1,0,0);printf("%d\n",(int)vt.size());for(int i=0;i<vt.size();i++) printf("%d %d\n",vt[i].FR,vt[i].SE);return 0;
}

E. Nastya and Bees

导致unrated的假题。。。

F. Nastya and CBS

容易证明对于一个序列，我们每次可以随便消除一对相邻的 $(k, ? k)$ （因为如果合法它们一定会被配对），它是合法的括号序列当且仅当最后能被消空。那么给定序列有一个线性的判定方案是用栈，从左往右扫，每次遇到 $k$ 压入栈，遇到 $? k$ ，若栈空或栈首不为 $k$ 必定非法，否则弹出栈首的 $k$ ，最后合法当且仅当栈空。
注意到我们消除的顺序无关，于是可以先选择一段区间内部尽可能配对后再跑这个算法。考虑对序列分块，对每个块维护块内部用栈尽可能消除后的序列，要求这个序列必定是前缀一段负数，后缀一段正数（否则直接记录包含若这个整块，序列一定非法的信息即可）。
那么对于修改重构整块，而对于查询考虑用栈从左到右扫描整个区间（假设中间没有非法的整块），对散块还是直接处理，对于整块，我们显然必须能够从栈中弹出该段对应的前缀的配对部分（这样相当于要求栈中最后一段能够恰好与这个前缀匹配），然后再压入后缀。那么可以考虑栈中压入的不是单个数字而是一段区间，且记录区间正反的哈希值，这样就可以 $O(1)\mathcal O(1)$ 比较两段是否匹配了，由于弹出的次数是跟块数同阶，因此总复杂度仍与块数同阶。
若取块大小为 $n\sqrt n$ ，时间复杂度为 $O((n+q)n)\mathcal O((n+q)\sqrt n)$ 。也可以用线段树套支持可持久化分裂合并的平衡树，类似维护哈希值做到 $O((n+q)log?2n)\mathcal O((n+q)\log^2n)$ 的复杂度。

#include <bits/stdc++.h>
#define MOD1 1004535809
#define MOD2 1061109567 
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;const ll base1=12391,base2=15111; ll powd1[100005],powd2[100005];void pre(int n) {
    powd1[0]=powd2[0]=1;for(int i=1;i<=n;i++) {
    powd1[i]=powd1[i-1]*base1%MOD1;powd2[i]=powd2[i-1]*base2%MOD2;}
}int S;
int num[100005],n;ll suml1[405][405],suml2[405][405];
ll sumr1[405][405],sumr2[405][405];
int val1[405][405],val2[405][405];
int len1[405],len2[405];
bool can[405];void rebuild(int bl) {
    int l=(bl-1)*S+1,r=min(bl*S,n);int top1=0,top2=0,*p=val1[bl],*q=val2[bl];for(int i=l;i<=r;i++)if (num[i]>0) q[++top2]=num[i];else if (!top2) p[++top1]=-num[i];else if (q[top2]!=-num[i]) {
    can[bl]=0;return;}else top2--;can[bl]=1;len1[bl]=top1;len2[bl]=top2;suml1[bl][0]=suml2[bl][0]=0;for(int i=1;i<=top1;i++) {
    suml1[bl][i]=(suml1[bl][i-1]*base1+p[i])%MOD1;suml2[bl][i]=(suml2[bl][i-1]*base2+p[i])%MOD2;}sumr1[bl][top2+1]=sumr2[bl][top2+1]=0;for(int i=top2;i>0;i--) {
    sumr1[bl][i]=(sumr1[bl][i+1]*base1+q[i])%MOD1;sumr2[bl][i]=(sumr2[bl][i+1]*base2+q[i])%MOD2;}
}inline bool equal(int bl1,int bl2,int x,int y,int len) {
    if ((suml1[bl1][x]-suml1[bl1][x-len]*powd1[len]%MOD1+MOD1)%MOD1!=(sumr1[bl2][y]-sumr1[bl2][y+len]*powd1[len]%MOD1+MOD1)%MOD1) return 0;if ((suml2[bl1][x]-suml2[bl1][x-len]*powd2[len]%MOD2+MOD2)%MOD2!=(sumr2[bl2][y]-sumr2[bl2][y+len]*powd2[len]%MOD2+MOD2)%MOD2) return 0;return 1;
}pr st[100005];bool query(int l,int r) {
    if (!((r-l)&1)) return 0;int lb=(l-1)/S+1,rb=(r-1)/S+1;if (lb==rb) {
    int top=0;for(int i=l;i<=r;i++)if (num[i]>0) st[++top]=pr(0,i);else if (!top||num[st[top].SE]!=-num[i]) return 0;else top--;return top==0;}else {
    int nl=l,nr=min(lb*S,n);int top=0;for(int i=nl;i<=nr;i++)if (num[i]>0) st[++top]=pr(0,i);else {
    if (!top||num[st[top].SE]!=-num[i]) return 0;top--;}for(int i=lb+1;i<rb;i++) {
    if (!can[i]) return 0; int cur=1;while (cur<=len1[i]) {
    if (!top) return 0;if (!st[top].FR) {
    if (num[st[top].SE]!=val1[i][cur]) return 0;top--;cur++;}else {
    int t=min(st[top].SE,len1[i]-cur+1);if (!equal(i,st[top].FR,cur+t-1,st[top].SE-t+1,t)) return 0;st[top].SE-=t;if (!st[top].SE) top--; cur+=t;}}if (len2[i]) st[++top]=pr(i,len2[i]);} nl=(rb-1)*S+1;nr=r;for(int i=nl;i<=nr;i++)if (num[i]>0) st[++top]=pr(0,i);else {
    if (!top) return 0;if (!st[top].FR) {
    if (num[st[top].SE]!=-num[i]) return 0;top--;}else {
    if (val2[st[top].FR][st[top].SE]!=-num[i]) return 0;st[top].SE--;if (!st[top].SE) top--;}}return top==0;}
}int main() {
    int k;scanf("%d%d",&n,&k);pre(n);S=(int)(sqrt(n)+0.5);for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i*S<=n;i++)rebuild(i);int m;scanf("%d",&m);for(int i=1;i<=m;i++) {
    int kind,x,y;scanf("%d%d%d",&kind,&x,&y);if (kind==1) {
    num[x]=y;rebuild((x-1)/S+1);}else {
    bool v=query(x,y);puts((v)?"Yes":"No");}}return 0;
}
/* 8 4 1 -1 2 3 -4 -2 4 -4 1 2 1 8 */