AtCoder Beginner Contest 404 C-G（无F）题解

干千翻 發表於 2025-5-4 15:20:00

AtCoder Beginner Contest 404 C-G（无F）题解

<h2 id="c-cycle-graph">C. Cycle Graph?</h2>
<h3 id="题意">题意</h3>
给你一个 $N$ 个顶点 $M$ 条边的简单（无重边、自环）无向图，第 $i$ 条边连接节点 $A_i$ 和 $B_i$，判断这个图是不是一个环。
<h3 id="思路">思路</h3>
首先一个图是环，要满足点数等于边数，即 $N=M$；
其次，这个图必须连通，可以通过 $\text{DFS}$ 或 $\text{BFS}$ 搜索判断是否连通（从任意一点开始搜，结束后检查是否每个点都已到达过）；
最后，每个点的度数（所连接的顶点数）必须为 $2$。
可以证明，只要满足上述三个条件，这个图一定是一个环。
<h3 id="c-代码">C++ 代码</h3>
<pre><code class="language-cpp">#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,m;
int deg;
vector<int> g;
bool used;
void dfs(int v){
used=true;
for(int x:g){
if(!used){
dfs(x);
}
}
}
int main(){
cin>>n>>m;
if(n!=m){
cout<<"No\n";
return 0;
}
for(int i=1;i<=m;i++){
int u,v; cin>>u>>v;
g.push_back(v);
g.push_back(u);
}
dfs(1);
for(int i=1;i<=n;i++){
if(!used||g.size()!=2){
cout<<"No\n";
return 0;
}
}
cout<<"Yes\n";
return 0;
}
</code></pre>
<h2 id="d-goin-to-the-zoo">D. Goin' to the Zoo</h2>
<h3 id="题意-1">题意</h3>
$N$ 个动物园，动物园 $i$ 入场费为 $C_i$。$M$ 种动物，第 $j$ 种动物可以在共 $K_j$ 个动物园看到，分别为动物园 $A_{j,1},A_{j,2},\ ...,A_{j,K_j}$。
要看每种动物至少两次，至少花多少钱。
注：只要花一次 $C_i$，就可以进入动物园 $i$ 一次，就可以看里面的每个动物一次；若花两次，则可进入两次，看里面的动物两次
<h3 id="思路-1">思路</h3>
由于 $N \le 10,M\le 100$，可以想到用状态压缩（不是dp）枚举。
状态压缩，就是把状态压缩到一个数字里
大致思路如下：
以 $140$ 为例，三进制数为 $12012$：
<img src="https://cdn.luogu.com.cn/upload/image_hosting/o79vgk67.png">
这样，$1\sim 3^N$ 的每个数字都有了实际含义
只要枚举 $1\sim3^N$ 的每个数，判断这样参观动物园能否达成“每种动物至少看两次”的目标，若可以，则记录答案，取最小值。
时间复杂度 $O(NM·3^N )$
<h3 id="c-代码-1">C++ 代码</h3>
<pre><code class="language-cpp">#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=3e18;
const int maxn=1000005;
int c;
int k;
int v;
int mask;
int n,m;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c;
}
for(int i=1;i<=m;i++){
cin>>k;
for(int j=0;j<k;j++){
cin>>v;
}
}
int ans=inf;
for(int msk=0;msk<pow(3ll,n);msk++){
memset(mask,0,sizeof(mask));//mask为当前数字所对应的三进制数
int num=0;//num为花费
int p=msk;
for(int i=1;i<=n;i++){
num+=(p%3)*c;
for(int j=1;j<=m;j++){
for(int a=0;a<k;a++){
if(v==i) mask+=p%3;
}
}
p/=3;
}
bool flag=true;
for(int j=1;j<=m;j++){
 if(mask<2) flag=false;
 }
if(flag) ans=min(ans,num);
}
cout<<ans<<endl;
return 0;
}
</code></pre>
<h2 id="e-bowls-and-beans">E. Bowls and Beans</h2>
<h3 id="题意-2">题意</h3>
$N$ 个碗排成一排，编号为 $0\sim N-1$，碗 $i$ 中有 $A_i$ 个豆子，上面写着一个数字 $C_i$。
每次操作可以将碗 $i$ 里的豆子可以放到之前 $i-C_i \sim i-1$ 中的任意碗里，并且可以任意分配每个碗里放几颗。
最初碗 $0$ 中没有豆子，问：将所有豆子都移到碗 $0$ 中，最少需要多少步。
<h3 id="思路-2">思路</h3>
<s>贪心好像也可以，但是我不会！！</s>
$N \le 2000$，考虑 $O(n^2)$ 动态规划。
动态规划基本三步：
<ol>
<li>设计 $\text{DP}$ 状态：</li>
</ol>
 定义 $f_i$ 表示将编号 $\ge i$ 的所有碗中的豆子全部移到碗 $i$ 中的最小步骤；
<ol start="2">
<li>初始化：</li>
</ol>
 设最后一个有豆子的碗为 $p$，则对于 $i=p\sim n-1$，$f_i=0$（不需要操作），其余初始 $f_i=\infty$；
<ol start="3">
<li>
转移顺序及转移方程：
顺序：由于每个碗里的豆子只能往前移，为避免转移产生影响后续计算，应从后往前转移；
满足以下条件时，$f_i=\min(f_i,f_j+1)$：
<ul>
<li>
条件1：$j>i$；
</li>
<li>
条件2：碗 $j$ 的豆子可以移到碗 $i$ 中，即$j-i \le C_j$；
</li>
<li>
条件3：若 $i-j\ge2$，$i+1$ 到 $j-1$ 之间的任何一个碗都没有豆子（否则不可能一步就完成 $j \rightarrow i$ 的操作）。
</li>
</ul>
</li>
</ol>
<pre><code class="language-cpp">#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=3e18;
const int maxn=2005;
int n;
int c,f;
bool a;
signed main(){
cin>>n;
for(int i=1;i<n;i++) cin>>c;
for(int i=1;i<n;i++) cin>>a;

//初始化
for(int i=0;i<n;i++) f=inf;
int pos;
for(int i=n-1;i>=0;i--){
 f=0;
 if(a){
 pos=i-1;
 break;
 }
}

//转移
for(int i=pos;i>=0;i--){//为了避免产生后效性，从后往前遍历
for(int j=i+1;j<n;j++){//为了满足条件1，j=i+1开始
if(j-i<=c) f=min(f,f+1);//为了满足条件2
if(a) break;//为了满足条件3，只要遇到了有豆子的碗就退出
}
}
cout<<f<<endl;
return 0;
}
</code></pre>
<h2 id="g-specified-range-sums">G. Specified Range Sums</h2>
<h3 id="题意-3">题意</h3>
有三个长度为 $M$ 的序列 $L,R,S$，你要判断是否存在一个长度为 $N$ 的 正整数 序列 $A$，满足以 $\sum_{j=L_i}^{R_i} A_j=S_i$。
若存在，找到最小的 $\sum_{j=1}^N A_j $；否则，输出 <code>-1</code>。
<h3 id="思路-3">思路</h3>
首先，我们考虑将求和转换为前缀和，即定义 $C_i=\sum_{j=1}^iA_j$，则$C_{R_i}-C_{L_i-1}=S_i$。
建立有向图，顶点编号为 $0 \sim n$，这样连边：$(L_i-1,R_i)=S_i$，$(R_i,L_i-1)=-S_i$。另外，由于是正整数序列，所以 $(i+1,i)=-1$。
我们需要计算 $n \rightarrow 0$ 的最短路，答案即为这个值的相反数。
注意：无解时图中有负环，所以 $\text{Dijkstra}$ 不可以。考虑可以处理负环的 $\text{Bellman-Ford}$ 算法（不会没关系，下面讲）：
与图上动态规划相似，定义 $dis_i$ 表示从 $n$ 到 $i$ 的最短路，$dis_n=0$，其余为 $\infty$。
共进行 $N$ 次操作，每次操作如下：
<ul>
<li>对于每一条有向边 $(u,v)=w$，$dis_v=\min(dis_v,dis_u+w)$，共 $M$ 条边。</li>
</ul>
复杂度为 $O(NM)$，通常把上述操作称作 松弛(relax)。
在这 $N$ 次松弛之后，再执行第 $N+1$ 次操作，若还可以继续执行松弛操作，就说明图中存在负环，无解，输出 $-1$。
最终答案即为 $-dis_0$。
<h3 id="c-代码-2">C++ 代码</h3>
<pre><code class="language-cpp">#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=3e18;
const int maxn=4005;
int n,m;
struct Node{
int u,v,w;
};
vector<Node> v;
int dis;
signed main(){
cin>>n>>m;

//建图连边
for(int i=1;i<=m;i++){
int l,r,s;
cin>>l>>r>>s;
v.push_back({l-1,r,s});
v.push_back({r,l-1,-s});
}
for(int i=0;i<n;i++) v.push_back({i+1,i,-1});

//初始化
for(int i=1;i<=n;i++) dis=inf;
dis=0;

//Bellman-Ford计算最短路直接将第N+1次操作放入循环中
for(int i=1;i<=n+1;i++){
for(Node e:v){
if(dis>dis+e.w){
if(i==n+1){//若已经执行完n+1次松弛还可以继续执行，则无解
cout<<-1<<endl;
return 0;
}
dis=dis+e.w;
}
}
}
cout<<-dis<<endl;
return 0;
}
</code></pre> 
来源：https://www.cnblogs.com/AKDreamer-HeXY/p/18859257

頁: [1]

琼殿技术论坛's Archiver

AtCoder Beginner Contest 404 C-G（无F）题解