[CSP 2025]游记
<h2 id="csp-j">CSP-J</h2><hr>
<h3 id="_"><span class="math inline">\(T1\)</span></h3>
<hr>
<p>循环结构 <span class="math inline">\(+\)</span> 字符串，橙题，不说了肯定做出来了。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005
int top,a;
string s;
signed main(){
cin>>s,s=" "+s;
for(int i=1;i<s.length();i++) if(s>='0'&&s<='9') a[++top]=s-'0';
sort(a+1,a+top+1);
for(int i=top;i;i--) cout<<a;
return 0;
}
</code></pre>
<h3 id="_-1"><span class="math inline">\(T2\)</span></h3>
<hr>
<p>循环结构 <span class="math inline">\(+\)</span> 小学数学，橙题，不说了肯定做出来了。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005
int n,m,x,y,cnt,a;
signed main(){
cin>>n>>m;
for(int i=1;i<=n*m;i++){cin>>a;if(a>=a) cnt++;}
x=cnt/n+(cnt%n!=0);
if(x%2==1) y=cnt-n*(x-1);
else y=n-(cnt-n*(x-1))+1;
cout<<x<<" "<<y<<endl;
return 0;
}
</code></pre>
<h3 id="_-2"><span class="math inline">\(T3\)</span></h3>
<hr>
<p>贪心 <span class="math inline">\(+\)</span> 红黑树（<span class="math inline">\(map\)</span>），黄题，不说了肯定做出来了。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005
int n,k,a,pre,cnt;
map<int,int>mp;
signed main(){
cin>>n>>k;
mp=-1;
for(int i=1,r=-1;i<=n;i++){
cin>>a;
pre=pre^a;
if(mp^k]!=0&&mp^k]>=r) r=i,cnt++;
mp]=i;
}
cout<<cnt<<endl;
return 0;
}
</code></pre>
<h3 id="_-3"><span class="math inline">\(T4\)</span></h3>
<hr>
<p>普通背包 <span class="math inline">\(+\)</span> 出题人好心的帮忙解决了的数学部分，绿题，不说了肯定做出来了。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 5005
#define mx 5000
#define md 998244353
int n,a,dp,ans;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a;
sort(a+1,a+n+1);
dp=1;
for(int i=1;i<=n;i++){
for(int j=a+1;j<=mx+1;j++) ans=(ans+dp)%md;
for(int j=mx+1;j>=mx+1-a;j--) dp=(dp+dp)%md;
for(int j=mx;j>=a;j--) dp=(dp+dp])%md;
}
cout<<ans<<endl;
return 0;
}
</code></pre>
<h3 id="_-4"><span class="math inline">\(对拍\)</span></h3>
<hr>
<ul>
<li><span class="math inline">\(T1\)</span> 打了暴搜。</li>
<li><span class="math inline">\(T2\)</span> 打了模拟。</li>
<li><span class="math inline">\(T3\)</span> 打了暴搜。</li>
<li><span class="math inline">\(T4\)</span> 打了状压。<br>
最后四个对拍一起跑了 <span class="math inline">\(1\)</span> 个小时。</li>
</ul>
<hr>
<p>遗憾监考老师强调不能玩 <span class="math inline">\(dino\)</span>。</p>
<hr>
<h2 id="csp-s">CSP-S</h2>
<hr>
<h3 id="_-5"><span class="math inline">\(T1\)</span></h3>
<hr>
<ol>
<li>先不管集合的数要 <span class="math inline">\(\le \frac{n}{2}\)</span> 的条件，贪心直接放。</li>
<li>如果数最多的集合的数 <span class="math inline">\(> \frac{n}{2}\)</span>，取出放入其他集合后对答案影响最小的几个数，放入其他集合。可以证明，此时其他集合数的个数都会 <span class="math inline">\(\le \frac{n}{2}\)</span>。</li>
<li>此时答案最优。</li>
</ol>
<p>挺简单，不到半小时就调完了。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
#define mx 5000
#define md 998244353
int t,n,a,ans;
struct PT{int p,top;}q;
bool cmp(PT a,PT b){return a.top>b.top;}
signed main(){
cin>>t;
while(t--){
cin>>n;
ans=q.top=q.top=q.top=0;
for(int i=1,a,b,c;i<=n;i++){
cin>>a>>b>>c;
if(a>=b&&a>=c) q.p[++q.top]=min(a-b,a-c),ans+=a;
else if(b>=c&&b>=a) q.p[++q.top]=min(b-a,b-c),ans+=b;
else if(c>=b&&c>=a) q.p[++q.top]=min(c-b,c-a),ans+=c;
}
sort(q+1,q+3+1,cmp);
for(int i=1;i<=q.top;i++) a=q.p;
sort(a+1,a+q.top+1);
for(int i=1;i<=q.top-n/2;i++) ans-=a;
cout<<ans<<endl;
}
return 0;
}
</code></pre>
<h3 id="_-6"><span class="math inline">\(T2\)</span></h3>
<hr>
<ol>
<li>先求出 <span class="math inline">\(n\)</span> 个点 <span class="math inline">\(m\)</span> 条边的最小生成树。</li>
<li>状压 <span class="math inline">\(k\)</span> 个乡镇，与原先最小生成树的边一起再求最小生成树，更新答案。</li>
</ol>
<p>时间复杂度 <span class="math inline">\(O(m\log_{2}{m}+2^knk\log_{2}{k})\)</span>？不太对劲。造了个大数据，跑了 <span class="math inline">\(3\)</span> 秒，又调了一个小时，还是 <span class="math inline">\(3\)</span> 秒，最后相信评测机，不调了。</p>
<p>赛后在 <span class="math inline">\(luogu\)</span> 跑得飞快。</p>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005
int n,m,k,f,top,c,ans;
struct EDGE{int u,v,fr;}edge,p;
struct VL{int fr,pt;}pp;
bool cmp(EDGE a,EDGE b){return a.fr<b.fr;}
bool cmpp(VL a,VL b){return a.fr<b.fr;}
int find(int w){return w==f?w:f=find(f);}
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&edge.u,&edge.v,&edge.fr);
sort(edge+1,edge+m+1,cmp);
for(int i=1;i<=m;i++) f=i;
for(int i=1;i<=m;i++){
if(find(edge.u)==find(edge.v))continue;
p[++top]=edge,ans+=edge.fr;
f.u)]=find(edge.v),find(edge.u);
}
for(int i=1;i<=k;i++){
scanf("%lld",&c);
for(int j=1;j<=n;j++) scanf("%lld",&pp.fr),pp.pt=j;
sort(pp+1,pp+n+1,cmpp);
for(int j=1;j<=n;j++) p.u=n+i,p.v=pp.pt,p.fr=pp.fr;
}
for(int i=1;i<(1<<k);i++){
while(!q.empty())q.pop();
int anss=0,up=n-1,top=0;
q.push({p.fr,{0,1}});
for(int j=1;j<=k;j++) if((i>>(j-1))&1) q.push({p.fr,{j,1}}),up++,anss+=c;
for(int i=1;i<=n+k;i++) f=i;
while(top!=up){
int x=q.top().second.first,y=q.top().second.second;
q.pop();
if(p.u!=0) q.push({p.fr,{x,y+1}});
if(find(p.u)==find(p.v))continue;
++top;f.u)]=find(p.v),find(p.u);anss+=p.fr;
}
ans=min(anss,ans);
}
printf("%lld\n",ans);
return 0;
}
</code></pre>
<h3 id="_-7"><span class="math inline">\(T3\)</span></h3>
<hr>
<p>写了个接近 <span class="math inline">\(100\)</span> 行的 <span class="math inline">\(trie+hash\)</span>, 在比赛还剩 <span class="math inline">\(5\)</span> 分钟才能运行，最后小样例过了，大样例没过，绝对 <span class="math inline">\(TLE\)</span>。</p>
<p>无代码。</p>
<h3 id="_-8"><span class="math inline">\(T4\)</span></h3>
<hr>
<p>只看了题。</p>
<hr>
<h2 id="预估">预估</h2>
<table>
<thead>
<tr>
<th style="text-align: center"></th>
<th style="text-align: center"><span class="math inline">\(T1\)</span></th>
<th style="text-align: center"><span class="math inline">\(T2\)</span></th>
<th style="text-align: center"><span class="math inline">\(T3\)</span></th>
<th style="text-align: center"><span class="math inline">\(T4\)</span></th>
<th style="text-align: center"><span class="math inline">\(sum\)</span></th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center">J</td>
<td style="text-align: center">100</td>
<td style="text-align: center">100</td>
<td style="text-align: center">100</td>
<td style="text-align: center">100</td>
<td style="text-align: center"><span class="math inline">\(\le 400\)</span></td>
</tr>
<tr>
<td style="text-align: center">S</td>
<td style="text-align: center">100</td>
<td style="text-align: center">100</td>
<td style="text-align: center">0</td>
<td style="text-align: center">0</td>
<td style="text-align: center">200</td>
</tr>
</tbody>
</table>
<p>希望吧。</p><br><br>
来源：https://www.cnblogs.com/liuruian/p/19188423
頁:
[1]