前言

队名:想想双一流该怎么做

时间:2026.11.1

题目质量:不错(但是难,好吧是我菜)

赛站体验:还行

热身赛

题目就是热身赛的难度,大概是div2的前三题的难度,然后这次又是只有两个人参赛,所以题目又全部是交给我当练习了,但是依旧不会防AK

A

搞了个水题,参赛手册的阅读理解

B

一个小模拟,交互题,提交的程序充当”评测机”,评测机向你猜测一个1-100的数字,每次询问是? x,你回答>,<或=.你要让交互次数大于等于6.其中,判你赢也算一次.达到了次数评测机会自动判你赢,提示! 0

比如

1
2
3
input   output
1 >
? 50

上面为一次交互的示例

思路

很直接,为了卡一下,那么自适应性增强就行了,每次选择较大的区间就行

C

设报名规则是,每天结束时结算,然后优先通过队伍编号小的,若一样优先通过选手编号小的

输入为两个3n长度的序列,第一个由n个不同的数字构成,第二个是一个3n的排列
给定选手的报名成功的序列和所属队伍,请你反推选手的报名顺序,使得存在一种天数划分,使得最终能得到成功序列,并要使得这个顺序的字典序最小

思路

若当前的比上一个大,那么和上一个放同一天,反之新开一段.然后对当天的选手序号排序,加入答案就行

D Kingdamn of construction

题目标题其实是构造王坝,但是我觉得写成他妈的构造更好

给定一个矩阵,长宽均不超过70,初始为1-nm的排列,然后每次可以翻转(reverse)一列或者一行,问能否把矩阵变成按行从上到下,从左往右读取,依次为1234…nm,无解输出-1,有解输出操作,0 h,表示行,1 l,表示列,操作次数小于等于9661

思路

首先可以注意到的点是由于是翻转,所以这个数字能去的位置是固定的,此处就形成了一个四绑定的关系,然后对于操作题,常规的想法就是,能不能我只改变这个位置,而不改变其他的位置(请先自行思考一下,对理解下面的正解有帮助)

这个题目其实对玩过魔方的同学特别友好(比如我),操作就类似于盲拧的转换,然后经过推导能发现,可以使用四步实现三角换!

这里要是玩过魔方的已经猜出结论了,要么直接就对,要么是两组双交换,要么是一组三角换,其他的都是不合理的!

手玩小交换操作方式

三角换可以横竖横竖或者竖横竖横实现

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
2
3
4 5 6 7
竖
4
3
2
1 5 6 7
横
4
3
2
7 6 5 1
竖
7
2
3
4 6 5 1
横
7
2
3
1 5 6 4

然后是横着的或者竖着的双交换,注意到可以算出平均分配给每个四元组的次数是7.8,而又得是偶数,0和2次不够,只能是4或6,这种刚好可以6,因此可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1 2  3  4
5 6
7 8
9 10 11 12
横×2
4 3 2 1
5 6
7 8
12 11 10 9
竖
12 3 2 1
7 6
5 8
4 11 10 9
横×2
1 2 3 12
7 6
5 8
9 10 11 4
竖×1
9 2 3 12
5 6
7 8
1 10 11 4

斜向的不写了,请自行推导,也可以6步完成

但是这么交上去发现会WA,这是为什么呢?而且发现我们会把一些正确的判成错误的?

这里我们需要先证明一下为什么这三种情况是合法的

简单的证明

如果写成排列,0 1 2 3

1
2
0 1
2 3

那么每一次交换,实际上就是排列的交换,单次交换只能创造出奇数个逆序对,而目标状态是0逆序对,所以得偶数次交换,因此可以根据这个定义为偶状态和奇状态,只有偶状态是有解的

真正的结论

如果一列全是奇状态的,一次交换后,所有都变成偶状态了,这个是关键,我们可以通过跨轨道,变换成全是偶状态的情况

这里根据这个,转换成01矩阵e,长宽分别为n/2和m/2,

每次转换实现的是,把0和1相互转换,那么,假设行是否转变为Ai,列是否转变为Bj,满足:

而且,要是一列满足了,那么全部满足,所以解出一个特解看是否全满足就行了,这样就能检验全部变为偶状态这一步是否成立了

剩下的当然还是可以继续套用

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
const ll N=75;
ll a[N][N],n,m,e[N][N];
void solve(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>a[i][j];
    }
  }
  for(int i=1;i<=n/2;i++){
    for(int j=1;j<=m/2;j++){
      vector<ll> now={a[i][j],a[i][m-j+1],a[n-i+1][j],a[n-i+1][m-j+1]};
      vector<ll> tar={(i-1)*m+j,(i-1)*m+m-j+1,m*(n-i)+j,m*(n-i)+m-j+1};
      vector<ll> tmp1=now,tmp2=tar;
      sort(tmp1.begin(),tmp1.end());
      sort(tmp2.begin(),tmp2.end());
      if(tmp1!=tmp2){
        cout<<"NO"<<endl;
        return;
      }
      ll cnt=0;
      e[i][j]=1;
      for(int k=0;k<4;k++) cnt+=(now[k]==tar[k]);
      if(cnt==0&&(now[0]==tar[1]&&now[1]==tar[0]&&now[2]==tar[3]&&now[3]==tar[2]||
          now[0]==tar[2]&&now[2]==tar[0]&&now[1]==tar[3]&&now[3]==tar[1]||
          now[0]==tar[3]&&now[3]==tar[0]&&now[1]==tar[2]&&now[2]==tar[1])){
        e[i][j]=0;
      }
      if(cnt==4||cnt==1) e[i][j]=0;
    }
  }
  vector<ll> H(n+1,0),L(m+1,0);
  for(int i=1;i<=n/2;i++) H[i]=e[i][1];
  for(int i=1;i<=m/2;i++) L[i]=e[1][i]^H[1];
  for(int i=1;i<=n/2;i++){
    for(int j=1;j<=m/2;j++){
      if(e[i][j]!=H[i]^L[j]){
        cout<<"NO"<<endl;
        return;
      }
    }
  }
  vector<pair<ll,ll>> ans;
  for(int i=1;i<=n/2;i++){
    if(H[i]){
      ans.pb({0,i});
      reverse(a[i]+1,a[i]+1+m);
    }
  }
  for(int i=1;i<=m/2;i++){
    if(L[i]){
      ans.pb({1,i});
      vector<ll> tmp;
      for(int j=1;j<=n;j++) tmp.pb(a[j][i]);
      reverse(tmp.begin(),tmp.end());
      for(int j=1;j<=n;j++) a[j][i]=tmp[j-1];
    }
  }
  for(int i=1;i<=n/2;i++){
    for(int j=1;j<=m/2;j++){
      vector<ll> now={a[i][j],a[i][m-j+1],a[n-i+1][j],a[n-i+1][m-j+1]};
      vector<ll> tar={(i-1)*m+j,(i-1)*m+m-j+1,m*(n-i)+j,m*(n-i)+m-j+1};
      vector<ll> tmp1=now,tmp2=tar;
      sort(tmp1.begin(),tmp1.end());
      sort(tmp2.begin(),tmp2.end());
      ll cnt=0;
      for(int k=0;k<4;k++) cnt+=(now[k]==tar[k]);
      if(cnt==0){
        if(now[0]==tar[1]&&now[1]==tar[0]&&now[2]==tar[3]&&now[3]==tar[2]){
          ans.pb({1,j}),ans.pb({1,m-j+1}),ans.pb({0,i});
          ans.pb({1,j}),ans.pb({1,m-j+1}),ans.pb({0,i});
        }
        else if(now[0]==tar[2]&&now[2]==tar[0]&&now[1]==tar[3]&&now[3]==tar[1]){
          ans.pb({0,i}),ans.pb({0,n-i+1}),ans.pb({1,j});
          ans.pb({0,i}),ans.pb({0,n-i+1}),ans.pb({1,j});
        }
        else if(now[0]==tar[3]&&now[3]==tar[0]&&now[1]==tar[2]&&now[2]==tar[1]){
          ans.pb({0,n-i+1}),ans.pb({1,j}),ans.pb({0,i});
          ans.pb({0,n-i+1}),ans.pb({1,j}),ans.pb({0,i});
        }
        else{
          cout<<"NO"<<endl;
          return;
        }
      }
      if(cnt==1){
        ll h=(now[0]==tar[0]||now[1]==tar[1]),l=(now[2]==tar[2]||now[0]==tar[0]);
        if(!h&&!l){
         if(now[0]==tar[1])ans.pb({1,j}),ans.pb({0,i}),ans.pb({1,j}),ans.pb({0,i});
          else ans.pb({0,i}),ans.pb({1,j}),ans.pb({0,i}),ans.pb({1,j});
        }
        else if(!h&&l){
          if(now[1]=tar[0]) ans.pb({1,m-j+1}),ans.pb({0,i}),ans.pb({1,m-j+1}),ans.pb({0,i});
          else ans.pb({0,i}),ans.pb({1,m-j+1}),ans.pb({0,i}),ans.pb({1,m-j+1});
        }
        else if(h&&!l){
          if(now[2]==tar[3]) ans.pb({,j}),ans.pb({0,n-i+1}),ans.pb({1,j}),ans.pb({0,n-i+1});
          else ans.pb({0,n-i+1}),ans.pb({1,j}),ans.pb({0,n-i+1}),ans.pb({1,j});
        }
        else{
          if(now[3]==ta[2]) ans.pb({1,m-j+1}),ans.pb({0,n-i+1}),ans.pb({1,m-j+1}),ans.pb({0,n-i+1});
         else ans.pb({0,n-i+1}),ans.pb({1,m-j+1}),ans.pb({0,n-i+1}),ans.pb({1,m-j+1});
        }
      }
    }
  }
  if(n&1){
    bool f1=1,f2=1;
    for(int i=1;i<=m;i++){
      if(a[(n+1)/2][i]!=n/2*m+i) f1=0;
      if(a[(n+1)/2][i]!=n/2*m+m-i+1) f2=0;
    }
    if(!f1&&!f2){
      cout<<"NO"<<endl;
      return;
    }
    if(f2) ans.pb({0,(n+1)/2});
  }
  if(m&1){
    bool f1=1,f2=1;
    for(int i=1;i<=n;i++){
      if(a[i][(m+1)/2]!=(i-1)*m+(m+1)/2) f1=0;
      if(a[i][(m+1)/2]!=(n-i)*m+(m+1)/2) f2=0;
    }
    if(!f1&&!f2){
      cout<<"NO"<<endl;
      return;
    }
    if(f2) ans.pb({0,(m+1)/2});
  }
  cout<<"YES"<<endl;
  cout<<ans.size()<<endl;
  for(auto[i,j]:ans) cout<<i<<" "<<j<<endl;
}
signed main(){
  fast
  ll T; cin>>T;
  while(T--) solve();
  return 0;
}

比赛场地

这个必须说一下了,虽然把所有的活动放在赛场中,减少选手的移动,但是食堂太远了,给的饭票在近处的食堂不能用,连小卖部我们都没找到

比赛的物资

这个很不错,给了一个学校的专属牌子,给了印有武汉的吉祥物的衣服和毛巾,以及一个蒜鸟毛绒玩具(好像也是他们的吉祥物?)

然后居然刷新笔

选手牌子有对应名字了,总之排面拉满了

正式赛复盘

首先,这一场,依旧没有分配任何适合我的题,给了我一个银牌题,然后我想到了有一点用的点,但是想不到真正的关键点,后面队友写完铜牌题,来WA了10多发也艹不过去

前面找我帮他看铜牌题,我刚看懂题目开始有点头猪了,他说他会了,那算了,既然他会了那显然给他写,反正有人写就行了,我赛后补照样能起到练习的效果(不大好意思就是)

虽然但是,我队友并不介意我只做了0题,毕竟,能做的也就3题,我太菜了,那还能怎么办呢,加训呗

感觉自己还是太菜了,有些就是想不到,感觉和大一的时候一样,当时不会写div2的C,现在不会写div2的EF,其实是一样的,但是有些不会你也没什么办法,只能多加练习

此外,我发现我这个人还是更喜欢实现而不是出思路,div3的1900是会的,div2的1900就不一定了,但是总体而言还行,接下来还是需要多练习一些更难的题目,因为区域赛的银牌题,一般在2300左右,铜牌都有1900,

我队友目前大概能出2200,我只能1800-1900,我在完全不用题解出的最高难度只有2000,练习也偏简单,总是不给自己上强度,我认为这和我这个学期比较懒有关,这长比赛后打算练练2000或者更难,加大训练强度有助于我的提升(之前好像也有这个问题,第一次重视)

我队友的想法是,要是我一直练习,一定能最后做出难的,现在的问题还是我们队没有会做难题的人

接下来还有两个CCPC,明年比赛前,我打算再写个500题,这样才能进步一个大档次

可以尝试的新规划

队友分析了一下我的问题,怎么说呢,有些题目,我没必要一直死钻,有些想不到还是想不到,还不如多看看题解学习,然后最好每次记一下时间,并及时记录做题情况

把我和GPT的对话贴在这里,然后我觉得,我可以记录每题的思维误区,纠正思维我要

和GPT的对话(部分)

判断是否该继续想,看有没有进展,不只看时间

同样卡了一小时,下面两种情况价值完全不同:

  • 不断得到新性质、排除错误猜想、缩小问题,已经接近某种状态或转化:值得继续。
  • 反复检查同一个猜想、不断模拟类似样例、一直围绕同一套表达打转:应该换方向或接受提示。

尤其要警惕“我还在思考”的感觉。思考很费力,不代表信息在增加。

看题解时,尽量只看能让自己重新启动的那一点。

“半小时后看完整题解”和“半小时后拿一条关键提示”,训练效果差别很大。

建议按层获取:

  • 只提示应该关注哪个条件或瓶颈。
  • 再提示一个关键观察。
  • 仍然推不出,再看主要转化或算法。
  • 最后补正确性和细节。

复盘要记录“我为什么没想到”,而不是只记用了什么算法。

“这题用了贪心”,“这题用了前缀和”通常太粗,不能直接改善下次的发现能力。

每道值得复盘的题,写三项就够:

  • 我卡在哪里? 例如一直试图描述所有操作后的完整状态。
  • 关键线索是什么? 例如题目只问总和,所以可以按元素统计贡献。
  • 下次怎样触发这个角度? 例如遇到总量统计且操作相互影响时,尝试交换统计顺序。

然后隔几天,不看笔记重推一次。重点检查自己能否重新得到关键转化;实现已经熟练的部分,不必每次都完整重写。

正式赛题解

补题链接:ICPC武汉站

A

给定若干条消息,消息1只会出现在00:00-00:59,消息2只会出现在7:00-7:59,给定若干条消息,求最少经过了几天

思路

模拟题,注意可以一小时内发多条消息就行,算一个坑,幸好签到不在我手中,不然我指定WA在这个上面

D

思路

这个题目,按照队友的解释方式确实更好理解.

把题目看成是找一颗树,遍历这棵树的结果是输入.

这样就能引出dfs树的关键性质了:

任意一条非树边,一定连接某个点和它的祖先/后代,不存在横叉边

横叉边是指,从某个点到一个既非它子孙节点,也非它祖先节点的边,也就是跑到了别的子树上

分析一下dfs遍历的特点,如果两个点在同一个同一个连通分量内的话,他们都会被遍历到,也就是说,一组连通分量的点是一棵子树

在合法方案中,对任意一条边 (u,v),若 dep[u]<dep[v],那么u一定是v的祖先

假设去掉了根节点,剩下的点组成的多个连通分量,每一个分量就是一棵子树;下面的子树,去掉子树的根节点,也是一样的

换句话说,遍历到当前点时,去掉已经遍历过的点,剩下的点组成的图中,和当前点在同一连通分量内的一定是当前点的子树

接下来,再次分析dfs遍历的特点,这次对当个点分析

要是邻居有深度更小的,显然会在自己前面访问过,不然根据前面的结论,这些点会作为其子树的一部分,从而深度更大,显然是不对的;所以在合法状态中,深度小的点必然已全访问,顺序重要

要是深度更大的点,一定不是马上访问,否则深度就会变小,所以得先访问深度为自己+1的点

这样逻辑就通顺了,一类是随时可以访问,另外两类有严格的顺序要求,可以发现,直接选择深度小的先访问就是一种合理的构造,然后我们检验构造是否正确就行了

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const ll N=2e5+10;
ll dep[N],t[N];
bool vis[N];
vector<ll> g[N];
bool cmp(ll a,ll b){return dep[a]<dep[b];}
void dfs(ll now,ll last){
  vis[now]=1;
  for(int nex:g[now]){
    if(nex==last||vis[nex]) continue;
    t[nex]=t[now]+1;
    dfs(nex,now);
  }
}
void solve(){
  ll n,m; cin>>n>>m;
  vector<ll> root;
  for(int i=1;i<=n;i++){
    cin>>dep[i];
    if(dep[i]==0)
      root.pb(i);
  }
  for(int i=1;i<=n;i++){
    ll k; cin>>k;
    for(int j=1,x;j<=k;j++)
      cin>>x,g[i].pb(x);
    sort(g[i].begin(),g[i].end(),cmp);
  }
  if(root.size()!=1){
    cout<<-1<<endl;
    return;
  }
  dfs(root[0],0);
  for(int i=1;i<=n;i++){
    if(t[i]!=dep[i]){
      cout<<-1<<endl;
      return;
    }
  }
  cout<<root[0]<<endl;
  for(int i=1;i<=n;i++){
    for(int j:g[i]) cout<<j<<" ";
    cout<<endl;
  }
}

K

简要分析,反正要么父子无关,要么父子有依赖,并且对于一个节点,若有部分子节点和他有关,那么所有有关的节点要么全部早于父,要么全部晚于父,(自己证,不写了)

这样就简单了,所以直接根据依赖建立新的图,然后对每一个子图进行计算,最后合并起来

然后关键的一个点是:这个依赖图一定是森林,不存在环,这个可以反证法证明,而且要么全部父指子,要么全部子指父

因为多个子图是孤立的,总方案数可以通过公式计算

单个节点的递推满足

这里还有一个关键观察,正图和反图,逻辑一样,所以可以直接统一化处理

进一步优化

化简这个式子,然后发现甚至可以这么做:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
ll n; cin>>n;
vector<ll> fa(n+1),a(n+1),b(n+1),sz(n+1,1);
for(int i=2;i<=n;i++) cin>>fa[i];
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=n;i>=2;i--){
if(a[i]>b[fa[i]]||a[fa[i]]<b[i])
sz[fa[i]]+=sz[i];
}
ll ans=fact[n];
for(int i=1;i<=n;i++)
ans=ans*inv[sz[i]]%mod;
cout<<ans<<endl;
}

这个真没什么实际意义,单纯的化简,然后根据题目的父的编号小于子的搞出来的,这里的inv是数字的逆元,不是阶乘的逆元

本题的反思

我队友和我的问题其实都是一样的,没有根据样例算出自己的错误点,其实我们两个都在考虑不存在的情况,浪费了时间,还有我队友居然不知道不能不用状压算拓扑序数量

J

比较容易想到的点是长度为n的序列一定能生成n个n,大于n的必须直接就有

关键点是想到,怎么定一个容易生成的标准,因为每个数字都需要生成和占位.

但是很显然的一点是仅靠这两个量,直接排序,不能直接判定,那么该怎么办呢?

但是我们可以发现,把一些数字放在最后出现是很优的决策,这些数字不会被前面的生成卡位,等那些难的生成了以后,再生成就行了,我称这种性质为适应性强

这样,我们只要给难生成的数字x留下x的空间就行了,前面容易生成的数字所需的位置作为公共位置(设这个长度为m),可以用来借用,因为只要留下这些空间,那些数字自己就能生成这部分序列

变形一下

可以看出,后面这个值越小,阈值也就越小,所以直接用后面这个比大小,当优先比较的数字就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
map<ll,ll> cnt,cntA;
bool cmp(ll a,ll b){
return a-cnt[a]<b-cnt[b];
}
void solve(){
ll n; cin>>n;
cnt.clear(),cntA.clear();
vector<ll> b(n+1,0),a(n+1,0);
for(int i=1;i<=n;i++) cin>>a[i],cntA[a[i]]++;
for(int i=1;i<=n;i++) cin>>b[i],cnt[b[i]]++;
sort(a.begin()+1,a.end()),sort(b.begin()+1,b.end());
if(a==b){
cout<<"YES"<<endl;
return;
}
vector<ll> tmp;
for(auto[num,_]:cnt) tmp.pb(num);
sort(tmp.begin(),tmp.end(),cmp);
ll m=0,p=tmp.size();
for(int i=0;i<tmp.size();i++){
if(m+cnt[tmp[i]]>=tmp[i]){
m+=cnt[tmp[i]];
}else{
p=i;
break;
}
}
for(int i=p;i<tmp.size();i++){
if(cntA[tmp[i]]<cnt[tmp[i]]){
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;
}

本题反思

没有想到怎么定义好生成,也没有想到可以搞一个借用位,然后最关键的是,我开头直接从大到小比较,这直接导致了我们的去大于n的位置时错误了,这样就少了几个位置,总之选这个题目是个大错误,另外还有几个银题是我们队主力会的,下次一定注意防止这种事情发生