当前位置： 首页 > backend >正文

“唐人街大赛第二届”题解

backend 2025/9/7 9:26:51

今天，我和机房的几个红蓝名大佬参加了“唐人街大赛第二届”，不过第一名却是绿名(doge)

唐人街大赛第二届 - 洛谷 | 计算机科学教育新生态

今天我将带来这场比赛的题解。

这场比赛为IOI赛制，最后0.5小时增加4道橙题。每套题目40分。

第一题

​​​​​​P1497 木牛流马 - 洛谷，这道题，怎么说呢……

比较简单，但是题目的意思需要稍加翻译，这道题目它在原本的基础上增加了颜色。

我们不妨考虑容斥原理，首先考虑所有颜色都一样的情况。

首先我们考虑怎么放。

先看摆哪一些行：从 n 行里选 k 行，自然就是 C(k,n) 了

再看列该怎么摆：从 n 列里选 k 列，并与行对应(其实就是排列)，共有 A(k,n) 种方法。

所有我们可以得出

 ans=C\begin{pmatrix} k \\ n \end{pmatrix}*A\begin{pmatrix} k \\ n \end{pmatrix}

接下来，我们考虑每种颜色造成的影响，每次从所有的木牛流马中挑选出 i 种进行染色，不难看出有 C(i,k) 种方案，而且 k 每次还要减去 i ，这样就行了。

代码也是非常简单，不愧是橙题。

如此简单，就不放代码了。

当时我做的第一题就是这道题目，所以我获得了首A。（这道题目在比赛中有100分）

第三题

第二题由于标签里面有平衡树，所有我觉得看起来很难，于是就没有再做了。

P2536 [AHOI2005] 病毒检测 - 洛谷

看完了题目，第一反应就是Trie树，但是，感觉不太方便，后来我灵机一动，想到了可以用DNA序列建立Trie，然后在用病毒模板片段进行Trie树上面的匹配。

但是！我写了Trie+dfs之后，发现不知道为什么，我一直WA。于是我发现数据范围不是很大，于是我选择了O(n^3)的暴力 dp。

设f [ i ][ j ]表示病毒模板匹配到第 i 个字符,DNA串匹配到第 j 个字符时是否可行。

但是星号的部分要特殊处理，我创建了一个place数组，表示 i 位置的星号最早能匹配到的一个字符。

匹配时，如果匹配不上，那么判断一下病毒模板的上一位是不是星号。

而且！！！最好不要使用string，因为这样dp的时候下标不好处理。

Code

#include<bits/stdc++.h>
using namespace std;
char vir[1010],s[1010];
int n,lenn,ans,place[1010],f[1010][1010];
bool check(char x,char y){if(x==y||x=='?')return 1;else return 0;
}
void solve(int len){memset(f,0,sizeof(f));memset(place,0x3f,sizeof(place));f[0][0]=1;for(int i=1;i<=lenn;++i){if(vir[i]=='*'){if(i==1)f[1][0]=1;for(int j=1;j<=len;j++)if(f[i-1][j]||f[i][j-1])f[i][j]=1,place[i]=min(place[i],j);}else{for(int j=1;j<=len;j++){if(!check(vir[i],s[j]))continue;if(f[i-1][j-1])f[i][j]=1;else if(i>1&&vir[i-1]=='*'&&place[i-1]<j)f[i][j]=1;}}}if(f[lenn][len])++ans;
}
int main(){cin>>vir+1;lenn=strlen(vir+1);cin>>n;for(int i=1;i<=n;++i){cin>>s+1;solve(strlen(s+1));}cout<<n-ans;
}

180分到手。

结果发现Wei_ch大佬竟然是首A，后来才发现他是暴力DFS……没有Trie，只是加了一个记忆化。

太唐了

​​​​​​结果，mamingcan大佬直接AC了第四题，200分。

tql，orz。

第二题

P2286 [HNOI2004] 宠物收养场 - 洛谷

后来发现Wei_ch和mamingcam大佬都AC了第二题，所以我开始尝试写第二题。

结果发现就是一个暴力模拟。其实STL中的set就可以AC。

我们定义两个set，一个存领养者的情况，一个存宠物的情况。

这个可以通过lower_bound寻找最接近的元素。

但是要特判越界的情况。

code

#include<bits/stdc++.h>
using namespace std;
set<int>a[2];
int n,ans=0;
int main(){cin>>n;for(int i=1,opt,x;i<=n;i++){cin>>opt>>x;if(a[opt^1].empty()){a[opt].insert(x);continue;}if(x>*(--a[opt^1].end())){ans=(ans+x-*(--a[opt^1].end()))%1000000;a[opt^1].erase(*(--a[opt^1].end()));}else if(x<*(a[opt^1].begin())){ans=(ans+*(a[opt^1].begin())-x)%1000000;a[opt^1].erase(*(a[opt^1].begin()));}else{int nxt=*a[opt^1].lower_bound(x),pre=*(--a[opt^1].lower_bound(x));if(x-pre<=nxt-x)a[opt^1].erase(pre),ans=(ans+x-pre)%1000000;else a[opt^1].erase(nxt),ans=(ans+nxt-x)%1000000;}}cout<<ans;
}

于是我当时AC了3道题目，最后一道题目输出0，骗分骗了18分。（满分200分）

当时mamingcam大佬420pts，rank1

Wei_ch大佬418pts，rank2

我这个蒟蒻区区418，rank3

比赛马上只剩40分钟了，我开始写第4题了。

此时，Wei_ch的玄学暴力算法非常厉害！直接AC了T4，他是这个👍！

为了战胜大佬，我开始写第四题。

第四题

​​​​​​P2761 软件补丁问题 - 洛谷

我们不难发现，n特别的少（或者是发现算法标签中有状态压缩和最短路）

我当时想的是枚举每个补丁是否使用，2^n还是可以接受的，但是！

补丁有可能使用多次！所以不能这样。

所以我想到了，我可以枚举错误，用二进制作为每个节点，边权为时间。

然后跑最短路就可以了。

code

#include<bits/stdc++.h>
using namespace std;
struct pack{int f1,f2,b1,b2,t;}p[505];
int n,m,first,minn[1<<22];
queue<int>q;
bool use[1<<22];
int gtag(){char ch=getchar();while(ch!='+'&&ch!='-'&&ch!='0')ch=getchar();if(ch=='+')return 1;if(ch=='-')return 2;return 0;
}
int main(){cin>>n>>m;for(int i=1;i<=m;++i){cin>>p[i].t;for(int j=1;j<=n;++j){int tag=gtag();if(tag==1)p[i].b1|=(1<<j-1);  if(tag==2)p[i].b2|=(1<<j-1);} for(int j=1;j<=n;++j){int tag=gtag();if(tag==1)p[i].f2|=(1<<j-1);if(tag==2)p[i].f1|=(1<<j-1);}}first=(1<<n)-1;memset(minn,0x7f,sizeof(minn));minn[first]=0;q.push(first);while(!q.empty()){int x=q.front();for(int i=1;i<=m;++i)if((x&p[i].b1)==p[i].b1&&(x&p[i].b2)==0){int y=((x|p[i].f1)|p[i].f2)^p[i].f1;if(minn[x]+p[i].t<minn[y]){minn[y]=minn[x]+p[i].t;if(!use[y]){q.push(y);use[y]=true;}}}use[x]=0;q.pop();}if(minn[0]==minn[(1<<22)-1])cout<<0;else cout<<minn[0];
}

终于，经过了调试，我终于AC了，获得了200分！此时，mamingcam大佬失误了，第三题还是没有AC。Wei_ch大佬等到了最后的半个小时，开始做最后附加的4道橙题。

其中有一道题，名字看上去很高级（可持久化动态仙人掌的直径问题），所以我错过了一道最水的题目。

于是我先做了最后一道题目。

第八题

P13256 [GCJ 2014 #2] Data Packing - 洛谷

这道题目比较简单，主要因为它说了每个不超过2个，排序后在使用双指针就可以，于是我AC了

code

#include<bits/stdc++.h>
using namespace std;
int t,n,x,a[100005],cnt;
int main(){cin>>t;while(t--){cnt++;cin>>n>>x;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int l=1,r=n,ans=0;while(l<=r){if(a[l]+a[r]>x)r--;else l++,r--;ans++;}cout<<"Case #"<<cnt<<": "<<ans<<"\n";}
}

此时Eason_cyx大佬加入了，直接AC了T1，并且获得了T5的首A，于是我开始做T5，也就是那道看起来很高级的题目。

第五题

P6685 可持久化动态仙人掌的直径问题 - 洛谷

这道题目是标准的标题党，与题目的标题没有一点关系。

第一眼好难，第二眼暴力。

code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){cin>>n>>m;for(int i=1;;i++)if(pow(i,m)>n){cout<<i-1;return 0;}
}

虽然，虽然可以AC，但是最后一个点TLE了，虽然不计入分数，但是还是要说一下正确的解法。

有好几种做法，这里介绍两种，一种可以利用初中数学的基础。

我们不难看出答案为\left \lfloor \sqrt[m]{n}\right \rfloor，根据初中数学的基础，我们不难看出\left \lfloor \sqrt[m]{n} \right \rfloor=n^{\frac{1}{m}}

恰好，c++的pow函数支持质数为分数的运算（冷知识），所以我可以通过pow运算获得正确的结果。

假如不知道（不是吧不是吧，刚刚那个方法不会有人不知道吧）刚刚那个方法，也可以使用二分。

我看了一眼第七题发现不会做。于是开始做第六题。

第六题

P6857 梦中梦与不再有梦 - 洛谷

一开始以为很难，后来发完全图后才发现很简单。

如果你不是数竞大佬也不是信奥大佬，你可以枚举前几项，不难看出

  • 当 n 为奇数时，答案为 n(n−1)/2​
  • 当 n 为偶数时，答案为 (n−1)(n−2)/2​+(n−1)​/2+1

如果你是数竞大佬，你可以归纳法或者是什么，乱搞一通，直接证明出来👍

如果你是信奥大佬，你可以观察到欧拉回路：

  1. 如果 n 是奇数，那么每个点都连接了偶数条边，原图没有奇点，存在欧拉路，直接输出 n(n−1)/2​；
  2. 如果 n 是偶数，那么每个点都连接了奇数条边。显然，删去一条边会使两个点的度数各减一，也就是将两个奇点变成了两个偶点。显然，我们最多有 2 个奇点，也就是最少有 n−2 个偶点，需要删去 (n−2)/2​ 条边。

code

#include<bits/stdc++.h>
using namespace std;
long long t,n;
int main(){cin>>t;while(t--){cin>>n;if(n%2)cout<<n*(n-1)/2<<"\n";else cout<<n*(n-1)/2-(n-2)/2<<"\n";}
}

最后，比赛结束了。

Wei_ch大佬 720pts rk1

我这个蒟蒻 720pts rk2

mamingcam大佬 598pts rk3

Vct14大佬 278pts rk4

Eason_syx大佬 220pts rk5

zcs2012大佬 100pts rk6

QWQ_SczyYA大佬 30pts rk7

我侥幸获得第二名，荣幸地获得了Alex_smy大佬的6块钱。

虽然Eason_syx大佬排名不高，但是他获得了3题的首A，非常伟大。

（以下是唐包生成的结尾）

回顾这场 “唐人街大赛第二届”，从最初首 A 第一题的小窃喜，到面对第二题平衡树标签时的暂时退缩，再到最后半小时冲刺附加题的手忙脚乱，每一分每一秒都充满了竞技的紧张与解题的乐趣。

赛场上，既有 mamingcan 大佬开局 AC 第四题的惊艳，也有 Wei_ch 大佬用玄学暴力 DFS 拿下首 A、最后又冲刺附加题的强势；既有我从 “骗分 18 分” 到 AC 第四题的突破，也有 Eason_cyx 大佬虽排名靠后却斩获 3 题首 A 的亮眼表现。每个选手都在以自己的节奏突破难题，每一次代码调试成功的提示音，都是对专注与坚持的最好回馈。

最终 720 分与第二名的成绩，或许有几分侥幸 —— 比如误打误撞识破第五题 “标题党” 的套路，又或是第八题双指针解法的顺利通关，但更多的是这场比赛带给我的成长：它让我明白，面对看似复杂的题目（如第二题的平衡树、第四题的状态压缩），只要拆解问题、找对思路，就能找到突破口；也让我看到，在竞技场上，不仅要比拼技术，更要比拼心态与策略。

特别感谢 Alex_smy 大佬的鼓励，也为所有并肩作战的 “红蓝名大佬” 喝彩。这场比赛的结束，不是终点，而是下一次挑战的起点。未来会带着这份解题的热情与收获的经验，继续在编程的道路上稳步前行，期待下一次赛场再见时，能有更出色的表现！

http://www.xdnf.cn/news/20319.html

相关文章：

  • Spring Boot 3.x 的 @EnableAsync应用实例
  • 基于51单片机的信号发生器函数发生器设计
  • 存储卡备用区用尽，拷贝机设置坏块数量又有何意义？
  • hot100-贪心算法（附图解思路）
  • 项目升级--Nginx
  • 一种基于迁移学习的零样本故障诊断方法
  • WSL2环境下因服务器重装引发的SSH连接问题排查记录
  • fastapi通过sqlmodel连接Mysql实现crud功能
  • 如何进行神经网络的模型训练（视频代码中的知识点记录）
  • 2025最新超详细FreeRTOS入门教程：第一章 FreeRTOS移植到STM32
  • dp算法的种类
  • 制衣跟单高效管理软件推荐
  • linux 安全与防护,全方向讲解
  • 华清远见25072班I/O学习day6
  • Qt绘图功能学习笔记
  • 北斗导航 ｜ 导航定位中的卡尔曼滤波算法：原理、公式及C代码详解
  • XXL-JOB基本使用
  • MyBatis高频问题-动态sql
  • 计算机网络：以太网中的数据传输
  • golang连接influxdb的orm操作
  • halcon-亚像素边缘提取教程
  • PyTorch 模型文件介绍
  • element-plus 表单校验-表单中包含多子组件表单的校验
  • （数据结构）哈希碰撞：线性探测法 vs 拉链法
  • 基于区块链的IoMT跨医院认证系统：Python实践分析
  • Flink中的事件时间、处理时间和摄入时间
  • Joplin-解决 Node.js 中 “digital envelope routines::unsupported“ 错误
  • 自旋锁/互斥锁 设备树 iic驱动总线 day66 67 68
  • 输入2.2V~16V 最高输出20V2.5A DCDC升压芯片MT3608L
  • 计算机网络：网络设备在OSI七层模型中的工作层次和传输协议