「CSP-S」2019年第一届Day1游记+题解
Day 1
7:30 A.M.
8:10 A.M.
8:30 A.M.
T1 格雷码
题目
考场经历+思考（正解）
8:50 A.M.
T2 括号树
题目
考场经历+思考（伪正解）
正解
10:50 A.M.
T3 树上的数
题目
考场经历+思考
正解
12:00
写了那么多场的模拟赛，这次终于是来真的了…
但是…写这篇博客心情复杂啊…
不说心情了…哎
Day 1
7:30 A.M.
很早就到了，但是到的时候发现其实很多人都到了…
心态感觉良好，感觉应该可以拿 200pts+200pts+200pts+（虽然还没有看到题面）
照了张合影，就进考场了。
8:10 A.M.
马上要开考了，感觉好紧张啊…快把模板打好…
运气还好，机子不算太差，只是键盘的回车和 backspacebackspacebackspace（回格）有点问题。
按下去了就弹不起来了
8:30 A.M.
看不到解压密码，往前走了几步
今年的密码好有喜感啊：
Ren2Zhen0Si1Kao9?
认真思考 +++ 201920192019
然后，看到 T1T1T1
T1 格雷码
题目
点这里
考场经历+思考（正解）
看到题面，心中一喜，考前做过同样背景的题。
但是悲伤的是忘记结论了。
但这只是一道签到题，结论再怎么都可以推出来的吧？
花了大概 10min10min10min ，发现如下规律：
每一位的出现数字依次是 01100110...01100110...01100110...
对于第 iii 位，每一个数字出现的次数是 2i−12^{i-1}2i−1
然后…找循环节就好了.
#include<cstdio>
#include<iostream>
#define ull unsigned long long
#define cg (c=getchar())
template<class T>inline void qread(T& x){
x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
#undef cg
const int MAXN=64;
ull n,k;
bool num[10]={0,0,1,1};
inline void init(){
qread(n),qread(k);
// printf("n == %lld, k == %lld\n",n,k);
}
inline ull qkpow(ull n){
ull ret=1,a=2;
while(n>0){
if(n&1)ret=ret*a;
a=a*a;
n>>=1;
}
return ret;
}
inline void getCode(){
for(ull i=n-1;i>=0;--i){
ull mod=qkpow(i);
ull a=k/mod,b=k%mod;
++b;
if(b==mod)++a,b=0;
a%=4;
if(b==0)printf("%d",num[a]);
else printf("%d",num[a+1]);
if(i==0)break;
}
}
int main(){
//freopen("code.in","r",stdin);
//freopen("code.out","w",stdout);
init();
getCode();
return 0;
}
过完大样例，过了。
预估得分 100pts100pts100pts，开心了一会…
8:50 A.M.
看了看表，发现大概还有 333 小时 151515 分钟。
继续往下，看 T2T2T2。
T2 括号树
题目
点这里
考场经历+思考（伪正解）
感觉自己可以做出来。
分多种情况考虑：
情况 1
最普通的情况：()()()直接 ++ans 即可。
情况 2
比较复杂的情况((()))((()))((()))之类的情况。
这种情况下，我们不需要怎么特别讨论，只需要记录一个 tottottot 表示这之前有 tottottot 的正括号，如果这个左括号是合法的，那么 ++ans。
情况 3
当出现()()()()()()()()()()()()这种情况是比较复杂度。
首先，我们看一下，就这个样例来说，有多少个合法串。
一共有十个。
看一看是怎么来的：10=4+3+2+110=4+3+2+110=4+3+2+1
也就是说，当有多个合法串组合在一起的时候，他们可以相邻地两两组合。
但是如果我们这样算，时间复杂度是 O(n2)O(n^2)O(n2) 的，是要 TLETLETLE 的。
用一种更快的方法：
假设最后一个 ()()() 是一起压进去的。
之前的括号串是 ()()()()()()()()()，一共有 666 个。
当最后一个 ()()() 被放进去的时候，合法串增加了 444。
发现规律了？规律不用我总结了吧。
贴一下考场代码：
#include<cstdio>
#define LL long long
#define cg (c=getchar())
template<class T>inline void qread(T& x){
x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
#undef cg
const LL MAXN=5e5;
LL n,ans;
char s[MAXN+5];
LL fa[MAXN+5],st[MAXN+5],ind;
struct edge{
LL to,nxt;
edge(){}
edge(const LL T,const LL N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
LL tail[MAXN+5],ecnt;
inline void add_edge(const LL u,const LL v){
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
}
inline void init(){
qread(n);
scanf("%s",s+1);
for(LL i=2;i<=n;++i){
qread(fa[i]);
add_edge(fa[i],i);
}
}
void dfs(const LL u,const LL pre,LL tot,LL res){
bool flg=false;LL memo;
if(s[u]==')'&&tot>0){
--tot;
++res;
memo=st[ind];
--ind;
res+=st[ind];
++st[ind];
flg=true;
}
else if(s[u]=='('){
++ind;
++tot;
st[ind]=0;
}
ans^=(u*res);
for(LL i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
dfs(v,u,tot,res);
if(flg){
--st[ind];
++ind;
st[ind]=memo;
}
if(s[u]=='(')--ind;
}
int main(){
freopen("brackets.in","r",stdin);
freopen("brackets.out","w",stdout);
init();
dfs(1,0,0,0);
printf("%lld\n",ans);
return 0;
}
这道题其实花费过久，导致最后一道题没时间去骗分了…
这个代码，能够过完所有大样例。
ps:ps:ps:看到 luoguluoguluogu 上面有很多大佬说最后一个样例测不了，但是其实是可以的。
只需要如下操作：
在 Dev−C++Dev-C++Dev−C++ 的编译命令中添加：-Wl,-stack=67108864
可能还是有点不清楚，贴一张图：
预估 100pts100pts100pts，然后十分开心，感觉 Day1Day1Day1 可以手拿 200pts200pts200pts。
正解
其实我这个代码没有多大问题…
但是我少考虑了一种情况：
情况 4
当出现()))))()))))()))))的情况，即有连续的非法的右括号出现的时候。
这个时候之后的合法串是不能和前面的合法串组合的。
贴代码，就是基于原代码而改正的，可以找一下不同。
#include<cstdio>
#define LL long long
#define cg (c=getchar())
template<class T>inline void qread(T& x){
x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
#undef cg
const LL MAXN=5e5;
LL n,ans;
char s[MAXN+5];
LL fa[MAXN+5],st[MAXN+5],ind;
struct edge{
LL to,nxt;
edge(){}
edge(const LL T,const LL N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
LL tail[MAXN+5],ecnt;
inline void add_edge(const LL u,const LL v){
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
}
inline void init(){
qread(n);
scanf("%s",s+1);
for(LL i=2;i<=n;++i){
qread(fa[i]);
add_edge(fa[i],i);
}
}
void dfs(const LL u,const LL pre,LL tot,LL res,bool f){
int flg=0;LL memo;
if(s[u]==')'&&tot>0){
--tot;
++res;
memo=st[ind];
--ind;
if(f)res+=st[ind];
++st[ind];
flg=1;
}
else if(s[u]==')')f=false,tot=0,++ind,st[ind]=0,flg=2;
else if(s[u]=='('){
f=true;
++ind;
++tot;
st[ind]=0;
}
ans^=(u*res);
// printf("Now u == %lld, res == %lld\n",u,res);
// for(int i=0;i<=ind;++i)printf("%lld ",st[i]);
// puts("");
for(LL i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
dfs(v,u,tot,res,f);
if(flg==1){
--st[ind];
++ind;
st[ind]=memo;
}
if(flg==2)--ind;
if(s[u]=='(')--ind;
// puts("After all :");
// printf("Now u == %lld, res == %lld\n",u,res);
// for(int i=0;i<=ind;++i)printf("%lld ",st[i]);
// puts("");
}
int main(){
// freopen("brackets.in","r",stdin);
// freopen("brackets.out","w",stdout);
init();
dfs(1,0,0,0,0);
printf("%lld\n",ans);
return 0;
}
接着说，做完 T2T2T2，发现还有大概 1h1h1h 左右的时间，开始着手骗 T3T3T3。
不说了，看一看 T3T3T3
10:50 A.M.
T3 树上的数
题目
点这里
考场经历+思考
这道题的输入感觉很恶心。
大概思路就是用 O(n!×n)O(n!\times n)O(n!×n) 的复杂度，全排列删边顺序，再用 nnn 来计算。
处理了输入很久，但是还是没有调出来。
然后，花费了差不多 1h1h1h 但是还是没有什么结果。
但是却把 T2T2T2 的 100pts100pts100pts 全部丢掉了…
代码就不贴了。
正解
PS:PS:PS:老师目前并未讲正解，但是部分分讲完了
updateupdateupdate : 正解已补充，同时同步发表于 luoguluoguluogu 的同名题。
方法 1 : 10pts
这 10pts10pts10pts 是这一次考试 T3T3T3 的满分了…
很少有超过 10pts10pts10pts 的人。
思路很好想，用一个 dfsdfsdfs 枚举删边的顺序，再用 O(N)O(N)O(N) 来检查即可。
代码见下：（个人代码风格严重）
/*
10pts code
*/
#include<cstdio>
#include<utility>
using namespace std;
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
//#define FILEOI
typedef pair<int,int> pii;
#define cg (c=getchar())
template<class T>inline void qread(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
inline int qread(){
int x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=-1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);putchar(x%10^48);
}
const int MAXN=2000;
struct edge{
int to,nxt;
edge(){}
edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
++in[u],++in[v];//更改点的入度
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}
int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案
inline void init(){
qread(N);
//清空图
ecnt=0,tcnt=0,maxin=0;
rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;
//输入
rep(i,1,N)a[qread()]=i;
rep(i,1,N-1)add_edge(qread(),qread());
}
bool vis[MAXN+5];int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
dfs(1);
rep(i,1,N)writc(ans[i],' ');
putchar('\n');
}
inline void chk(){
rep(i,1,N)mir[a[i]]=i;
rep(i,1,N){
if(mir[i]<ans[i]){
rep(j,1,N)ans[j]=mir[j];
break;
}
if(mir[i]>ans[i])break;
}
return;
}
void dfs(const int p){
if(p==N)return chk();
rep(i,1,N-1)if(!vis[i]){
swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
dfs(p+1);
swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
}
}
int T;
signed main(){
#ifdef FILEOI
freopen("file.in","r",stdin);
freopen("file.out","w",stdout);
#endif
qread(T);
while(T--){
init();
if(N<=10) getDfs();//暴力
else puts("gugugu~~~");//减少测试时间
}
return 0;
}
方法 2 : 35pts
在拿到暴力的 10pts10pts10pts 之后，我们应该朝着更高的得分奋斗。
那么接下来，我们看到链和菊花图。
哪个更好想？
各位即将进入省队的大佬们，你们应该思考过吧。
下一个部分分，应该拿下菊花图。
怎么做？ 这是一个好问题
不妨看一看菊花图有什么特性。
假如说我们有这样一个菊花图：
我们考虑随便删一些边。
假如我们删除边 {1,4}\{1,4\}{1,4} ，那么 P4−>Y7P_4->Y_7P4−>Y7 是一定可以保证的，因为除了这一条边 {1,4}\{1,4\}{1,4} 以外，没有边和 444 号点有关。
再随便来，把边 {1,2}\{1,2\}{1,2} 删掉，那么 P2−>Y1P_2->Y_1P2−>Y1 也是一定保证了，理由同上。
再试几次，发现在菊花图上，除了花心以外，其他点一定固定了是删边时花心的值，而它本身的数跑到花心，作为下一次固定的值。
仔细想想，是不是有点像一个环，或者说是一条单链？
为什么这么说？
我们这样看，删 {1,4}\{1,4\}{1,4} ，等于加边 {Y7−>P4}\{Y_7->P_4\}{Y7−>P4} ，此时 P1−>Y1P_1->Y_1P1−>Y1 。
再删边 {1,2}\{1,2\}{1,2} ，等于加边 Y1−>P2{Y_1->P_2}Y1−>P2 ，此时 P1−>Y3P_1->Y_3P1−>Y3 .
再枚举几次，发现每个数字 YiY_iYi 只会最多向外连出一条边。
这相当于是一条单链，但是最后连 YnY_nYn 时，整个图一定会连成一个大环。
但是在连边的时候，我们要注意提前成环的情况——用并查集解决这个问题。
代码见下：
#include<cstdio>
#include<utility>
using namespace std;
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
//#define FILEOI
typedef pair<int,int> pii;
#define cg (c=getchar())
template<class T>inline void qread(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
inline int qread(){
int x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=-1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);putchar(x%10^48);
}
const int MAXN=2000;
struct edge{
int to,nxt;
edge(){}
edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
++in[u],++in[v];//更改点的入度
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}
int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案
inline void init(){
qread(N);
//清空图
ecnt=0,tcnt=0,maxin=0;
rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;
//输入
rep(i,1,N)a[qread()]=i;
rep(i,1,N-1)add_edge(qread(),qread());
/*
rep(i,1,N)writc(a[i],' ');
putchar('\n');
*/
}
int pre[MAXN+5];
inline void buildSet(){rep(i,1,N)pre[i]=i;}
int findSet(const int u){return u==pre[u]?u:pre[u]=findSet(pre[u]);}
inline void unionSet(const int u,const int v){return (void)(pre[findSet(u)]=findSet(v));}
bool vis[MAXN+5];
int tmp[MAXN+5],pt[MAXN+5];
inline void work(){//处理菊花图
buildSet();
rep(i,1,N)tmp[a[i]]=i,vis[i]=0;
rep(i,1,N-1){
rep(j,1,N)if(!vis[j]&&findSet(tmp[i])!=findSet(j)){
vis[j]=true,pt[tmp[i]]=j;
unionSet(tmp[i],j);
break;
}
}
rep(i,1,N-1)writc(pt[tmp[i]],' ');
rep(i,1,N)if(!vis[i]){
writc(i,'\n');
break;
}
}
int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
rep(i,1,N)vis[i]=0;
dfs(1);
rep(i,1,N-1)writc(ans[i],' ');
writc(ans[N],'\n');
}
inline void chk(){
rep(i,1,N)mir[a[i]]=i;
rep(i,1,N){
if(mir[i]<ans[i]){
rep(j,1,N)ans[j]=mir[j];
break;
}
if(mir[i]>ans[i])break;
}
return;
}
void dfs(const int p){
if(p==N)return chk();
rep(i,1,N-1)if(!vis[i]){
swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
dfs(p+1);
swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
}
}
int T;
signed main(){
#ifdef FILEOI
freopen("file.in","r",stdin);
freopen("file.out","w",stdout);
#endif
qread(T);
while(T--){
init();
if(N<=10)getDfs();
else if(maxin==N-1)work();
else puts("gugugu~~~");
}
return 0;
}
方法 3 : 60pts
在得到 45pts45pts45pts 之后，你一定很开心，但是如果这是考试，那是一定不够的。
但是如果这是考试，那是一定不够的。
我们继续朝更高的得分奋斗，那么我们现在开始分析链。
首先，链有什么特性？似乎这是很简单的一个问题。
它的特性显然：
它是一条类似于线的东西；
除了两个端点之外，其他的点度都为 222（分出度和入度）；
…（作者太弱，只想得出这几种情况）
那么，针对这些情况进行分析：
针对特性1，我们为了方便处理，可以把这个单链拍到树上，代码如下：
int lt[MAXN+5],lcnt;//链表和下标
inline void getlist(const int u,const int pre){
lt[pt[u]=++lcnt]=u;//pt[i] : 点 i 在链表数组中的位置
for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
getlist(v,u);
}
这个地方很简单。
那么特性2？
所谓入度、出度为 222 即除端点以外，每个点都有两条边与其相连，而这两条边可以保证的是删除时间一定不同。
那么，我们可以对于这两条边进行标记，分几种情况：
左边的边先删，右边的边后删（左先右后）
左后右先
没有过标记
针对这个，我们用一个数组来存
short int mark[MAXN+5];//标记 : 0-无标记 ; 1-左先右后 ; 2-左后右先
此处选用 short int 为的是节省内存 其实省不了多少
为什么这样标记呢？我们来分析一种情况。
假设数 xxx 要到点 iii 去，如下图：
边上的数字是边的编号。
重复一遍问题：数字 xxx 要去 iii 点
那么首先，edge1edge_1edge1 一定是在 edge2edge_2edge2 之后删，不然数字 xxx 就跑到其他地方去了。
根据 mark[]mark[]mark[] 数组的定义，可得 mark[x]=2mark[x]=2mark[x]=2
同理，edge2、edge3、edge4、edge5edge_2、edge_3、edge_4、edge_5edge2、edge3、edge4、edge5 一定是依次删除的，那么可得 mark[p1]=mark[p2]=mark[p3]=1mark[p1]=mark[p2]=mark[p3]=1mark[p1]=mark[p2]=mark[p3]=1
而点 iii ，要保证的是 edge6edge_6edge6 在 edge5edge_5edge5 之前删除，为什么？
因为当 xxx 到 iii 点之后，如果 edge6edge_6edge6 还存在，那么 xxx 就会跑到 p4p_4p4 那里去。
由此推出，mark[i]=2mark[i]=2mark[i]=2
这是 xxx 往右走的情况，xxx 往左的情况可自行推导 要看代码我也不拦你，推荐自己推一下，很简单
而最后，我们判定一个方法是否可行，只需要判断它和前面的边的标记是否冲突即可。
#include<cstdio>
#include<utility>
using namespace std;
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
// #define FILEOI
typedef pair<int,int> pii;
#define cg (c=getchar())
template<class T>inline void qread(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
inline int qread(){
int x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=-1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);putchar(x%10^48);
}
const int MAXN=2000;
struct edge{
int to,nxt;
edge(){}
edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,in[MAXN+5],maxin,tcnt;
pii t[MAXN+5];
inline void add_edge(const int u,const int v){
++in[u],++in[v];//更改点的入度
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
maxin=Max(maxin,Max(in[u],in[v]));//特判菊花图
t[++tcnt]=mp(u,v);//记录一条边连接的两个点
}
int N,a[MAXN+5],ans[MAXN+5];
//a[i] : 点 i 的数字是多少
//ans[i] : 记录答案
inline void init(){
qread(N);
//清空图
ecnt=0,tcnt=0,maxin=0;
rep(i,1,N)tail[i]=0,in[i]=0,ans[i]=N-i+1;
//输入
rep(i,1,N)a[qread()]=i;
rep(i,1,N-1)add_edge(qread(),qread());
/*
rep(i,1,N)writc(a[i],' ');
putchar('\n');
*/
}
int pre[MAXN+5];
inline void buildSet(){rep(i,1,N)pre[i]=i;}
int findSet(const int u){return u==pre[u]?u:pre[u]=findSet(pre[u]);}
inline void unionSet(const int u,const int v){return (void)(pre[findSet(u)]=findSet(v));}
bool vis[MAXN+5];
int tmp[MAXN+5],pt[MAXN+5];
inline void work(){//处理菊花图
buildSet();
rep(i,1,N)tmp[a[i]]=i,vis[i]=0;
rep(i,1,N-1){
rep(j,1,N)if(!vis[j]&&findSet(tmp[i])!=findSet(j)){
vis[j]=true,pt[tmp[i]]=j;
unionSet(tmp[i],j);
break;
}
}
rep(i,1,N-1)writc(pt[tmp[i]],' ');
rep(i,1,N)if(!vis[i]){
writc(i,'\n');
break;
}
}
int mir[MAXN+5];
void dfs(const int);
inline void getDfs(){
rep(i,1,N)vis[i]=0;
dfs(1);
rep(i,1,N-1)writc(ans[i],' ');
writc(ans[N],'\n');
}
inline void chk(){
rep(i,1,N)mir[a[i]]=i;
rep(i,1,N){
if(mir[i]<ans[i]){
rep(j,1,N)ans[j]=mir[j];
break;
}
if(mir[i]>ans[i])break;
}
return;
}
void dfs(const int p){
if(p==N)return chk();
rep(i,1,N-1)if(!vis[i]){
swap(a[t[i].ft],a[t[i].sd]);vis[i]=true;
dfs(p+1);
swap(a[t[i].ft],a[t[i].sd]);vis[i]=false;
}
}
int lt[MAXN+5],lcnt;
short int mark[MAXN+5];//标记 : 0-无标记 ; 1-左先右后 ; 2-左后右先
inline void getlist(const int u,const int pre){
lt[pt[u]=++lcnt]=u;
for(int i=tail[u],v;i;i=e[i].nxt)if((v=e[i].to)!=pre)
getlist(v,u);
}
inline bool chkl(const int p1,const int p2){
if(mark[pt[p1]]==1)return false;
rep(i,pt[p1]+1,pt[p2]-1)if(mark[i]==2)return false;
if(mark[pt[p2]]==1)return false;
return true;
}
inline void getMarkl(const int p1,const int p2){//当 pt[p1]<=pt[p2] 时
if(pt[p1]!=1&&pt[p1]!=N)mark[pt[p1]]=2;
rep(i,pt[p1]+1,pt[p2]-1)mark[i]=1;
if(pt[p2]!=1&&pt[p2]!=N)mark[pt[p2]]=2;
}
inline bool chkr(const int p1,const int p2){//当 pt[p1]>pt[p2] 时
if(mark[pt[p1]]==2)return false;
fep(i,pt[p1]-1,pt[p2]+1)if(mark[i]==1)return false;
if(mark[pt[p2]]==2)return false;
return true;
}
inline void getMarkr(const int p1,const int p2){
if(pt[p1]!=1&&pt[p1]!=N)mark[pt[p1]]=1;
fep(i,pt[p1]-1,pt[p2]+1)mark[i]=2;
if(pt[p2]!=1&&pt[p2]!=N)mark[pt[p2]]=1;
}
inline void workList(){//解决单链
lcnt=0;
rep(i,1,N)if(in[i]==1){//压到数组上面
getlist(i,0);
break;
}
/*
printf("this is the list:");
rep(i,1,N)writc(lt[i],' ');
putchar('\n');
printf("this is pt arr:");
rep(i,1,N)writc(pt[i],' ');
putchar('\n');
*/
rep(i,1,N)vis[i]=false,mir[a[i]]=i,mark[i]=0;
rep(i,1,N)rep(j,1,N)if(!vis[j]&&pt[j]!=pt[mir[i]]){
//目标位置不能和本来的位置重合并且目标位置还没有被其他优先级更高的数占有
// printf("Now the number is %d, the goal position is %d\n",i,j);
int p1=mir[i],p2=j;bool flg=false;
if(pt[p1]<=pt[p2]){//如果这个数是往左边走
if(chkl(p1,p2))
getMarkl(p1,p2),flg=true;
}
else{//反之
if(chkr(p1,p2))
getMarkr(p1,p2),flg=true;
}
if(flg){//记录答案
ans[i]=j,vis[j]=true;
break;
}
}
rep(i,1,N-1)writc(ans[i],' ');//输出答案
writc(ans[N],'\n');
}
int T;
signed main(){
#ifdef FILEOI
freopen("rdata.out","r",stdin);
freopen("file.out","w",stdout);
#endif
qread(T);
while(T--){
init();
if(N<=10)getDfs();
else if(maxin==N-1)work();
else if(maxin==2)workList();
else puts("gugugu~~~");
}
return 0;
}
方法 4 : 100pts
目前尚待讨论…
ljljlj 大佬憋了两天，终于舍得把正解讲出来了，接下来是正解：
首先，我们的单链是怎么做的？
维护一个点的两个边删除的先后顺序。
并且，我们可以得到这样一个结论： 一个比较容易想到的结论
只有共用同一个顶点的边才有删除的先后关系
而判定一个方法是否可行，只需看这个方案是否和前面的方案冲突即可。
那么，我们能否将这样的维护扩展到多条边的情况？其实是可以的 不然我为什么要问这个问题
只有两条边，我们只需维护 左前右后 或者 左后右前 的情况，但是对于多条边这样显然是不行的。
那么，对于多个删边的先后关系，我们将其排成一排，比如我们删边顺序是：1,3,5,4...1,3,5,4...1,3,5,4...
将它们排成一排之后，发现它有点像链表。
考虑用链表维护删除边的先后关系。
但是这里有个问题：如果一个点删除边的顺序不一定是连续的怎么办？
对于这种情况，我们只需要把它们看成有许多个链表，但是它们没有接在一起即可。
那么，我们怎么寻找一条合法路径？
我们把这个方法的寻径算法分成几个部分：
对于起飞点（即数字一开始所在的点）
对于中转点
对于结束点
部分 1:对于起飞点
对于一个起飞点 uuu，我们考虑寻找一条起飞边，并且这条起飞边是一定存在。
那么，这条起飞边需要满足什么条件？
首先，这条起飞边前面不能有什么其他的东西。
即对于点 uuu 的删边顺序所连成的链表集中，这条边必须是其中某一条链的起点。
而且，我们分析，如果这是一条起飞边，那么它一定是所有 uuu 的边中最先删除的那条边（如果不知道为什么，参考本题链的处理方法）
还有一种特殊情况，留到后面结束点之后分析。
部分 2:对于中转点
如果这是一个中转点，考虑枚举一条边 e′e'e′ 在 eee (我们之前删除的那条边)
而这个中转点必须满足什么条件呢?
毕竟 e′e'e′ 是接在 eee 之后的，那么一定要保证 e′e'e′ 之前没有其他的边。
而且，点 e′e'e′ 与点 eee 还没有连在一起，即它们分别所在不同的链上（因为我们本来就是要将他们连在一起）。
并且，e′e'e′ 是在 eee 之后，但是如果 e′e'e′ 是一条起飞边，即这条边必须是最先删除的，那么 e′e'e′ 就是不符合的。
还有一种特殊情况，留到后面结束点之后分析。
部分 3:对于降落点
如果点 uuu 是一个降落点，那么我们的边 eee 必须是最后删除的（如果不知道为什么，参考本题链的处理方式）
即，对于一个点 uuu ，我们目前还并未指定 uuu 的某一条边必须是结束边。
但是还有一种情况，这种情况与前面的两个部分都有关。
如果这条结束边 eee 是与前面的起飞边在同一条链上，即它们先后顺序已确定，那么我们必须要保证这个删边顺序组成的链中，长度刚好为 uuu 的边数。
为什么？因为我们最后，必须保证每条边都被删去。
而上面这种情况，即是我们将最开头所删除的边，与最末尾所删除的边连接在一起而形成一个完整的、已无法再次修改的长链，而如果有剩余的边没有被删去，它们就没有机会再插入到这个链之中，也就是说找不到任何一个机会去删除这条边，与题意不符。
生动地说，我们不能让这个完整的链出现提前自闭的情况。
知道这个之后，我们再反过来补充 部分 1 与 部分 2 。
部分 1 补充
因为我们已经指定起飞边 eee ，而我们要将边 e′e'e′ 接到 eee 之后。
但是如果 e′e'e′ 已经与降落边，即末删边相连，那么我们也要防止提前自闭的情况。
所以我们也要特判一下，链长度必须与 uuu 的边数一样。
部分 2 补充
如果我们的边 eee 已经连接到起始边，而 e′e'e′ 已经连接到末删边。
那如果我们要将 eee 与 e′e'e′ 连起来删，也就是将两个完整链连接起来，这也是防止提前自闭的情况。
代码如下（自带注释）
#include<cstdio>
#include<vector>
using namespace std;
#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)
#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
// #define FILEOI
#define cg (c=getchar())
template<class T>inline void qread(T& x){
char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
if(f)x=-x;
}
inline int qread(){
int x=0;char c;bool f=0;
while(cg<'0'||'9'<c)if(c=='-')f=-1;
for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
return f?-x:x;
}
#undef cg
template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline void getInv(int inv[],const int lim,const int MOD){
inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
template<class T>void fwrit(const T x){
if(x<0)return (void)(putchar('-'),fwrit(-x));
if(x>9)fwrit(x/10);putchar(x%10^48);
}
const int MAXN=2000;
struct edge{
int to,nxt;
edge(){}
edge(const int T,const int N):to(T),nxt(N){}
}e[(MAXN<<1)+5];
int tail[MAXN+5],ecnt,siz[MAXN+5];
inline void add_edge(const int u,const int v){
++siz[u],++siz[v];
e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;
e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;
}
int N,minp;
int pt[MAXN+5];
int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];
//这条边的 前驱,后继
int rt[MAXN+5][MAXN+5][2];
//点 u 的某一条边的 前根节点、后根节点
int len[MAXN+5][MAXN+5];
//这条边 所在链 的链表长度
inline void init(){
qread(N);
ecnt=0;
rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;
rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;
int u,v;
rep(i,1,N-1){
qread(u,v);
add_edge(u,v);
pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;
rt[u][v][0]=rt[u][v][1]=v;
rt[v][u][0]=rt[v][u][1]=u;
len[u][v]=len[v][u]=1;
}
}
void findPath(const int u,const int p){//当前节点、前一个节点
int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
//a:来的边的前根 ; b:来的边的后根
if(p==N+1){//这是起点
for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(ta!=v || (pre[u][p]==tb && len[u][ta]<siz[u]))
//条件一:如果这条边已经有一个起点且不是自己
//条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来
continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起
findPath(v,u);//否则可行
}
}
else{
if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面
if(pre[u][N+1]==0 && (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:
//如果这个点的末删边还没有被指定(必须满足)
//并且:
//1.如果这条链接上开头，那么如果必须满足所有的边都在这条链上
//2.如果没有接上开头，那么长度随意
minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点
for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边，与其尾相连
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况
//如果这两条边已经在同一条链上
//或者这个边不是一个起始边, 即枚举边的前面还有东西
//或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边
continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上
if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])
//如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头
//那么它们组合起来必须等于所有边的数量之和
//否则, 这就是 提前自闭 的情况
continue;
findPath(v,u);//如果以上都不满足, 那么这条边是合法的
}
}
else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边
}
}
inline void merge(const int u,const int a,const int b){
//函数条件:以 a 所在的链表为前链表
//并且满足 a 是前链表尾, b 是后链表头
int ta=rt[u][a][0],tb=rt[u][b][1];
nxt[u][a]=b;
pre[u][b]=a;
for(int i=ta;i && i!=N+1;i=nxt[u][i]){
//访问链表的基本操作
//更新每个点的前根、后根
rt[u][i][0]=ta;
rt[u][i][1]=tb;
}
len[u][ta]+=len[u][b];
}
bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记
//如果这条路径找到终点, 返回 1, 否则返回 0
if(u==minp){//如果找到了终点
pre[u][N+1]=p;//把这条边设为最后删除的边
nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的
return 1;
}
int a=rt[u][p][0],b=rt[u][p][1],ta,tb;
if(p==N+1){//这是起飞点
for(int i=tail[u],v;i;i=e[i].nxt){
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(ta!=v || (pre[u][N+1]==tb && len[u][ta]<siz[u]))
//如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了
//或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面
continue;//那么这条边肯定不在路径上面, 可直接跳过
if(getMark(v,u)){//如果这就是正确的路径
nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边
pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)
return 1;
}
}
}
else{//如果点 u 是中转点, 那么考虑枚举中转边
if(p==b){//如果这条边在链上后面没有其他边的时候
for(int i=tail[u],v;i;i=e[i].nxt){
v=e[i].to;
ta=rt[u][v][0],tb=rt[u][v][1];
if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释
continue;
if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])//同样参考 findPath() 中同样位置
continue;
if(getMark(v,u)){
merge(u,p,v);//把链表合并为一个
return 1;
}
}
}
else getMark(nxt[u][p],u);
}
return 0;
}
signed main(){
#ifdef FILEOI
freopen("rdata.out","r",stdin);
freopen("file.out","w",stdout);
#endif
int T=qread();
while(T--){
init();
if(N==1){
writc(1,'\n');
continue;
}
rep(i,1,N){
minp=N+1;
findPath(pt[i],N+1);
// printf("%d\n",minp);
getMark(pt[i],N+1);
writc(minp,' ');
}
putchar('\n');
}
return 0;
}
12:00
坐了 3.5h3.5h3.5h 之后，感觉整个人爽炸了，还沉浸在自己 AAA 掉 T2T2T2 的喜悦之中（浑然不知自己 Day1Day1Day1 打炸了）
和同学们讨论了一下，发现 200pts+200pts+200pts+ 的人居多。
可能这一次 Day1Day1Day1 的普遍分数应该就在 200pts200pts200pts 左右（之后才知道结果，大家几乎所有人 T2T2T2 打炸了，还有人 T1T1T1 都有丢分）
随便找了家金拱门吃两个汉堡，Day1Day1Day1 就结束了…
![P1880 [NOI1995] 石子合并 题解](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)
![P5020 [NOIP2018 提高组] 货币系统 题解](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
