今天，我和机房的几个红蓝名大佬参加了“唐人街大赛第二届”，不过第一名却是绿名(doge)
今天我将带来这场比赛的题解。
这场比赛为IOI赛制，最后0.5小时增加4道橙题。每套题目40分。
第一题
P1497 木牛流马 - 洛谷，这道题，怎么说呢……
比较简单，但是题目的意思需要稍加翻译，这道题目它在原本的基础上增加了颜色。
我们不妨考虑容斥原理，首先考虑所有颜色都一样的情况。
首先我们考虑怎么放。
先看摆哪一些行：从 n 行里选 k 行，自然就是 C(k,n) 了
再看列该怎么摆：从 n 列里选 k 列，并与行对应(其实就是排列)，共有 A(k,n) 种方法。
所有我们可以得出
接下来，我们考虑每种颜色造成的影响，每次从所有的木牛流马中挑选出 i 种进行染色，不难看出有 C(i,k) 种方案，而且 k 每次还要减去 i ，这样就行了。
代码也是非常简单，不愧是橙题。
如此简单，就不放代码了。
当时我做的第一题就是这道题目，所以我获得了首A。（这道题目在比赛中有100分）
第三题
第二题由于标签里面有平衡树，所有我觉得看起来很难，于是就没有再做了。
看完了题目，第一反应就是Trie树，但是，感觉不太方便，后来我灵机一动，想到了可以用DNA序列建立Trie，然后在用病毒模板片段进行Trie树上面的匹配。
但是！我写了Trie+dfs之后，发现不知道为什么，我一直WA。于是我发现数据范围不是很大，于是我选择了的暴力 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。
第二题
后来发现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，他是这个👍！
为了战胜大佬，我开始写第四题。
第四题
我们不难发现，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，也就是那道看起来很高级的题目。
第五题
这道题目是标准的标题党，与题目的标题没有一点关系。
第一眼好难，第二眼暴力。
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了，虽然不计入分数，但是还是要说一下正确的解法。
有好几种做法，这里介绍两种，一种可以利用初中数学的基础。
我们不难看出答案为，根据初中数学的基础，我们不难看出
恰好，c++的pow函数支持质数为分数的运算（冷知识），所以我可以通过pow运算获得正确的结果。
假如不知道（不是吧不是吧，刚刚那个方法不会有人不知道吧）刚刚那个方法，也可以使用二分。
我看了一眼第七题发现不会做。于是开始做第六题。
第六题
一开始以为很难，后来发完全图后才发现很简单。
如果你不是数竞大佬也不是信奥大佬，你可以枚举前几项，不难看出
- 当 n 为奇数时，答案为 n(n−1)/2
- 当 n 为偶数时，答案为 (n−1)(n−2)/2+(n−1)/2+1
如果你是数竞大佬，你可以归纳法或者是什么，乱搞一通，直接证明出来👍
如果你是信奥大佬，你可以观察到欧拉回路：
- 如果 n 是奇数，那么每个点都连接了偶数条边，原图没有奇点，存在欧拉路，直接输出 n(n−1)/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 大佬的鼓励，也为所有并肩作战的 “红蓝名大佬” 喝彩。这场比赛的结束，不是终点，而是下一次挑战的起点。未来会带着这份解题的热情与收获的经验，继续在编程的道路上稳步前行，期待下一次赛场再见时，能有更出色的表现！