比赛链接
https://codeforces.com/contest/1023
ABCDEF题解
A. Single Wildcard Pattern Matching
题目大意
给两个串S,TS,T，TT只有小写字母，SS除了小写字母还有最多一个*字符，*字符能够匹配最多一个字符和空串。求SS能否匹配TT，|S|,|T|≤2×105|S|,|T|≤2×105。
题解
由于最多只有一个*，因此可以记录*左边的串和右边的串能不能与TT匹配。
B. Pair of Toys
题目大意
一共有nn个玩具标号为11到nn，要选出一对玩具(a,b)(a,b)，使得a+b=ka+b=k，求满足条件的对数，注意玩具是无序的，n,k≤1014n,k≤1014
题解
就是解一个方程组
解得
这题数据比较水，我用一个错误（有可能是正确）的方法也水过去了
C. Bracket Subsequence
题目大意
给一个括号序列SS，求SS的一个长度为kk并且合法的子序列（显然这个子序列也是括号序列）。|S|,k≤2×105|S|,k≤2×105
题解
用一个栈维护括号，左括号入栈，右括号将栈顶弹出，如果弹出的左括号数量=k=k那么就可以输出了。
D. Array Restoration
题目大意
长度为nn的序列，一共有kk个操作，每次操作将区间[li,ri][li,ri]修改为ii，每个位置至少被修改一次，操作的顺序是不可调换的。n,k≤2×105n,k≤2×105
现在知道操作完成后的序列，但是有一部分是丢失的。求能否通过上述操作得到这个序列，如果不能输出NO，能输出YES，然后输出一组可能的完整序列。
题解
输出NO的条件就是在两个bb值之间有aa值，其中b>ab>a。这个很容易用栈来维护。
否则，由于li≤rili≤ri，序列中必须至少存在一个位置为kk，其他0的位置就用这连续的一片0两侧的任何一个值来代替。
E. Down or Right
题目大意
交互题。
有一个n×nn×n的矩阵，一些位置能走，一些位置不能走。在这个矩阵中你只能向下或向右走。你不知道矩阵的具体情况，但是你可以询问，最多4×n4×n次，每次询问(a,b)(a,b)到(c,d)(c,d)能不能走通，(a,b)(a,b)到(c,d)(c,d)的曼哈顿距离必须≤n≤n。求(1,1)(1,1)走到(n,n)(n,n)的一种可行方案。n≤500n≤500
题解
从(1,1)(1,1)出发尽量往下走，如果往下走不到(n,n)(n,n)再向右走。从(n,n)(n,n)倒着走，尽量往左走，如果往左走不通在往上走。可以证明最终两条路一定会相交。
F. Mobile Phone Network
题目大意
nn个点要构成一棵树，你可以提供kk条边，你的竞争对手能以每条边vivi的价格提供mm条边，你现在的定价是不固定的。客户在价格相同的情况下会尽量多选择你提供的边，要求最小生成树中，你提供的所有边都能选上。在上述前提下，还要求你的获利尽量大。如果你的获利可以无限大那么输出-1，否则输出你最大可能的获利。n,m≤5×105,k<nn,m≤5×105,k<n
题解
首先假设你的每条边价格都是0，求出最小生成树。对于每条非树边，假设权值为vv，它放在生成树上产生的环中，每条边的价格都必须≤v≤v。可以通过这个O(n)O(n)的解决这个问题。
代码
A. Single Wildcard Pattern Matching
#include <cstdio>const int maxn=200000;int n,m,l,r;
char s[maxn+10],t[maxn+10];int main()
{scanf("%d%d%s%s",&n,&m,s+1,t+1);for(int i=1; i<=n; ++i){if(s[i]=='*'){l=i;break;}if(s[i]!=t[i]){puts("NO");return 0;}}if(l==0){puts((n==m)?"YES":"NO");return 0;}for(int i=n; i; --i){if(s[i]=='*'){r=m-n+i+1;break;}if(s[i]!=t[m-n+i]){puts("NO");return 0;}}if(l>r){puts("NO");}else{puts("YES");}return 0;
}
B. Pair of Toys
#include <cstdio>
#include <algorithm>long long n,k,mn,mx;int main()
{scanf("%I64d%I64d",&n,&k);mn=std::max(1ll,k-n);mx=std::min(n,(k-1)/2);printf("%I64d\n",std::max(mx-mn+1,0ll));return 0;
}
C. Bracket Subsequence
#include <cstdio>const int maxn=200000;int n,k,head,stack[maxn+10],instack[maxn+10],cnt;
char s[maxn+10],t[maxn+10];int main()
{scanf("%d%d%s",&n,&k,s+1);for(int i=1; i<=n; ++i){if(s[i]=='('){stack[++head]=i;instack[i]=1;}else{instack[stack[head--]]=0;++cnt;if(cnt*2==k){break;}}}cnt=0;for(int i=1; i<=n; ++i){if(instack[i]){continue;}if(s[i]==')'){++cnt;}putchar(s[i]);if(cnt*2==k){break;}}puts("");return 0;
}
D. Array Restoration
#include <cstdio>int read()
{int x=0,f=1;char ch=getchar();while((ch<'0')||(ch>'9')){if(ch=='-'){f=-f;}ch=getchar();}while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}return x*f;
}const int maxn=200000;int n,q,v[maxn+10],bin[maxn+10];
int stack[maxn+10],head;int main()
{n=read();q=read();for(int i=1; i<=n; ++i){v[i]=read();if(v[i]==0){continue;}if(bin[v[i]]==0){bin[v[i]]=1;}else if(bin[v[i]]==-1){puts("NO");return 0;}while((head>0)&&(stack[head]>v[i])){bin[stack[head--]]=-1;}if(stack[head]==v[i]){--head;}stack[++head]=v[i];}int fk=bin[q]?0:q;for(int i=1; i<=n; ++i){if(v[i]==0){if(fk!=0){v[i]=fk;fk=0;}else if(v[i-1]){v[i]=v[i-1];}else{v[i]=1;}}}if(fk){puts("NO");return 0;}puts("YES");for(int i=1; i<=n; ++i){printf("%d ",v[i]);}puts("");return 0;
}
E. Down or Right
#include <cstdio>const int maxn=500;int get(int ax,int ay,int bx,int by)
{printf("? %d %d %d %d\n",ax,ay,bx,by);fflush(stdout);char s[5];scanf("%s",s);if(s[0]=='Y'){return 1;}return 0;
}int n;
char s[maxn+10],t[maxn+10];int main()
{scanf("%d",&n);int x=1,y=1;while(x+y<=n){if((x+1<=n)&&(get(x+1,y,n,n))){s[x+y]='D';++x;}else{s[x+y]='R';++y;}}x=y=n;while(x+y>n+1){if((y>0)&&(get(1,1,x,y-1))){t[x+y-n]='R';--y;}else{t[x+y-n]='D';--x;}}putchar('!');putchar(' ');for(int i=2; i<=n; ++i){putchar(s[i]);}for(int i=2; i<=n; ++i){putchar(t[i]);}puts("");return 0;
}
F. Mobile Phone Network
#include <cstdio>
#include <cstring>
#include <algorithm>int read()
{int x=0,f=1;char ch=getchar();while((ch<'0')||(ch>'9')){if(ch=='-'){f=-f;}ch=getchar();}while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}return x*f;
}const int maxn=500000;
const int inf=0x3f3f3f3f;struct data
{int u,v,w;data(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};data d[maxn*2+10];
int n,k,m,pre[maxn*2+10],now[maxn+10],son[maxn*2+10],fa[maxn+10];
int tot,val[maxn*2+10],deep[maxn+10],fv[maxn+10],tag[maxn+10];namespace dsu
{int fa[maxn+10];int clear(){for(int i=1; i<=n; ++i){fa[i]=i;}return 0;}int find(int x){return (x^fa[x])?(x=fa[x]=find(fa[x])):x;}
}int ins(int a,int b,int c)
{pre[++tot]=now[a];now[a]=tot;son[tot]=b;val[tot]=c;return 0;
}int dfs(int u)
{int j=now[u];while(j){int v=son[j];if(v!=fa[u]){fv[v]=val[j];deep[v]=deep[u]+1;fa[v]=u;dfs(v);}j=pre[j];}return 0;
}int main()
{n=read();k=read();m=read();for(int i=1; i<=k; ++i){int u=read(),v=read();d[i]=data(u,v,0);}for(int i=1; i<=m; ++i){int u=read(),v=read(),w=read();d[i+k]=data(u,v,w);}dsu::clear();int need=n-1;for(int i=1; i<=k+m; ++i){int x=dsu::find(d[i].u),y=dsu::find(d[i].v);if(x!=y){--need;dsu::fa[x]=y;ins(d[i].u,d[i].v,d[i].w);ins(d[i].v,d[i].u,d[i].w);if(!need){break;}}}dfs(1);dsu::clear();memset(tag,-1,sizeof tag);for(int i=k+1; i<=k+m; ++i){int x=dsu::find(d[i].u),y=dsu::find(d[i].v);while(x!=y){if(deep[y]>deep[x]){std::swap(x,y);}tag[x]=d[i].w;dsu::fa[x]=dsu::find(fa[x]);x=dsu::fa[x];}}long long ans=0;for(int i=2; i<=n; ++i){if(!fv[i]){if(tag[i]==-1){ans=-1;break;}ans+=tag[i];}}printf("%I64d\n",ans);return 0;
}