20221107zzszoi模拟赛记录
作者 zzafanti (FreshOrange) 请勿转载
这次比赛题目较简单但是思维难度高一点
开题顺序
\(A-C-B-D\)
或
\(C-A-D-B\)
等等都可
大概就是\(A,C\)较为容易实现，\(B,D\)是图论题，没有前二者好写。
本文按照\(1324\)的顺序开题
T1 均分辣条
1.0s 128MB
题目描述
飞飞买了 \(N\) 条长度相同的辣条，刚到学校就被其他同学发现了，嘴馋的同学要求飞飞均分辣条。总共要均分成 \(M\) 份。飞飞想知道最少需要切多少刀能将这 \(N\) 条辣条均分。请你帮他计算下。
输入
第一行输入两个正整数 \(N\) 和 \(M\)。
输出
均分辣条的最少刀数。
样例输入 1
2 6
样例输出 1
4
样例输入 2
3 4
样例输出 2
3
样例输入 3
6 2
样例输出 3
0
样例说明
对于样例 1，每条辣条切两刀平均分成 3 份，所以需要 4 刀。
对于样例 2，每条辣条切成 \(\frac{3}{4}\) 和 \(\frac{1}{4}\),需要 3 刀。
对于样例 3，不切。
数据规模
\(1\le N,M\le 100\)。
思路
妥妥的数学题。
对于非负整数\(n,m\)(\(n<m\))
将\(n\)个\(1\)均分为\(m\)份，分成的小份可相加，让分的份数尽可能少。显然最终会分成\(m\)个\(\frac{n}{m}\),
因为最终要拼接成\(\frac{n}{m}\)，所以我们可以先把\(n\)个\(1\)切成尽可能多的\(\frac{n}{m}\)，
每个\(1\)要切\([\frac{m-1}{n}]\)刀（读者可以自己推一下，\(m\)减一是为了处理整除的情况,\([x]\)表示不超过\(x\)的最大整数）,
所以要先切\(n\times[\frac{m-1}{n}]\)刀，
每个\(1\)此时还剩下\(\frac{m \mod n}{m}\),记该长度为\(s\)，
则\(n\)个\(1\)总共剩下\(n\times s\)，
每\(\frac{n}{m}\)就要切一次，但是如果\(k\times \frac{n}{m}\)正好被\((m \mod n)\)整除，即这一刀切得是上述已切过的地方或辣条的右端，那么这一刀可以不计，
想一想，满足上面条件的\(k\)（\(0<k\)）的个数应为\(\frac{ns}{lcm(n,s)}\)个（其中\(lcm(a,b)\)表示\(a,b\)的最小公倍数），
而\(k\)的取值范围是\([1,\frac{ns}{n}]\)即\([1,s]\)，
所以除提前切得刀数外，还要切\(s-\frac{ns}{lcm(n,s)}\)，
因为\(gcd(a,b)\times lcm(a,b)=a\times b\)（\(gcd(a,b)\)表示\(a,b\)的最大公约数），
所以该式等价于\(s-gcd(n,s)\)，
由\(gcd(a,b)=gcd(b,a\mod b)\)知，
上式可进一步写作，
\(
\begin{equation}
m \mod n-gcd(n,m)
\end{equation}
\)
okok，
思路明白了就可以\(Code\)了
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int main(){
cin>>n>>m;
n%=m; //让n<m,显然n大于m时，(n-n%m)条辣条都不用切
if(n==0){ //特别处理一下n==0的情况，避免下面除以0
puts("0");
return 0;
}
int ans=(m-1)/n*n;
int t=m%n;
if(t==0){
printf("%d\n",ans);
return 0;
}
ans+=t-gcd(n,m);
printf("%d\n",ans);
return 0;
}
（放在博客里面代码略压行，可自行添加一些空行便于阅读）
读者也可以看看谢润喆同学的思路：
他的想法要形象简单一些
T3 数字转换
1.0s 128MB
题目描述
给定正整数 \(N\) ，每次可以有两个操作任选其一，乘以2，或者减去1，如果减去1后这个数变成非正数了，则过程终止，上限无穷大。请问：如果想由以上过程得到数字 \(M\)，最少要操作多少次？
输入
第一行输入两个正整数 \(N\) 和 \(M\)。
输出
输出最少操作次数。
样例输入 1
4 6
样例输出 1
2
样例输入 2
10 1
样例输出 2
9
样例说明
样例 1，先减去1，然后乘以2。
样例 2，连续减 9 次。
数据规模
\(1\le N,M \le 1e4\)。
思路
很明显这题可以用广度优先搜索(\(bfs\))来做，数据范围非常小，避免数字重复入队可保证时间复杂度为\(O(max{N,M})\)，足以应付本题.
广度优先搜索是对于一个状态空间的遍历方式，主要实现方式是维护一个具有双段性和单调性的队列，并对队列中的元素不断扩展，直到遍历完整个状态空间，遍历顺序类似于二叉树的层次遍历序。
本题相当于对一个正整数\(x\)进行两种方式的扩展:\(x-1\)或\(x*2\)，找到扩展到\(M\)的最小层数即可。
互联网上有很多\(bfs\)教程，读者不理解的话可以自行查阅_.
当然……这题似乎还有贪心的做法，但我现在还没有想出来如何证明。先咕咕咕了
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=20010,inf=0x3f3f3f3f;
int n,m,dist[N]; //dist[i]表示N扩展到i的最少操作次数
int main(){
memset(dist,0x3f,sizeof dist);
cin>>n>>m;
if(n>=m){
printf("%d\n",n-m);
return 0;
}
dist[n]=0;
queue<int> Q;
Q.push(n);
while(Q.size()){
int t=Q.front();
Q.pop();
if(t==m){
printf("%d\n",dist[t]);
return 0;
}
if(t*2<=m*2&&dist[t*2]==inf){ //m*2+1很明显不能扩展成最优解(除非n>2*m 但是我们已经特判过了
dist[t*2]=dist[t]+1;
Q.push(t*2);
}
if(t-1>0&&dist[t-1]==inf){
dist[t-1]=dist[t]+1;
Q.push(t-1);
}
}
return 0;
}
T2 最少能量
1.0s 128MB
题目描述
飞飞昨晚做了一个很有意思的梦，他和他的好朋友壮壮进入了一个地图游戏。地图中有 \(N\) 个结点，有 \(M\) 条双向道路连接这些结点， 结点按照 1 到 \(N\) 编号。刚开始飞飞在 1 号结点，壮壮在 2 号结点，他们要一起到 \(N\) 号结点去。
飞飞花费 \(B\) 的能量可以从一个结点走到相邻的结点，壮壮花费 E 的能量可以从一个结点走到相邻的结点。如果中途他俩走到同一个结点时，好兄弟一辈子，飞飞可以选择抱起壮壮一起走，这样需要花费 \(P\) 的能量可以从一个结点走到相邻的结点。当然了，如果 \(P < B + E\)，他们一起走可以更省力些，否则，他俩还是决定各走各的。
梦醒十分，飞飞感觉这个梦很好玩，他想让你帮忙计算最后他俩走到 \(N\) 点需要的最少能量。
输入
第一行输入 5 个正整数，分别是 \(B，E，P，N, M\)。
输出
输出他俩到 N 的最少能量。
样例输入
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
样例输出
22
样例说明
飞飞从 1 号结点走到 4 号结点花费能量 4，壮壮从 2 号结点走到 3 号结点再走到 4 号结点，花费 8 的能量，然后他俩一起从 4 到 7 到 8，花费 10 的能量，所以总共需要的最少能量是 4+8+10=22。
数据规模
\(1\le M,B,E,P\le 40000\)。\(3 \le N \le 40000\)。
思路
题目大意是给定一张无向图（应该是联通的），求编号为1的点和编号为2的点到编号为n的点所用的最小花费。花费规则如下：从编号为1的点出发，每次经过一条边产生\(B\)的花费；从编号为2的点出发，每次经过一条边产生\(E\)的花费。若两条路径重合，重合的边可以只产生\(P\)的花费，也可以产生\(B+E\)的花费。求最小花费。
不难发现，若\(B+E\leq P\)，这两条路径各算各的即可，可以bfs求出这两点到编号为n的点的最短路（边权都一样，bfs就可以），然后带权相加即为答案。若\(B+E>P\)，假设两条路径第一个交汇点为\(k\)，那么我们可以证明，当这种情况下花费最小时，两条路径此后必然一直重合直到编号为n的点。用\(dis[i]\)表示编号为\(i\)的点到编号为n的点的最短路径，那么由于\(B+E>P\)，\(dis[k]\times B+dis[k]\times E > dis[k]\times P\)。因此，我们只要枚举编号为\(k\)的点即可\((k\in [1,n])\) 相当于该题中找二人的汇合点。当然，每次枚举还要算上二者各自从起点到该点的花费，所以我们需要预处理出三个数组:
- \(dis[0][i]\) 编号为1的点到编号为\(i\)的点的最短路径长度
- \(dis[1][i]\) 编号为2的点到编号为\(i\)的点的最短路径长度
- \(dis[2][i]\) 编号为n的点到编号为\(i\)的点的最短路径长度
由于该图没有边权，所以预处理直接三遍\(bfs\)即可。
总体时间复杂度为\(O(N+M)\)。
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){ //整数快读
int sgn=0,x=0;
char c=getchar();
while(!isdigit(c)) sgn|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return sgn?-x:x;
}
const int N=40010;
const int inf=0x3f3f3f3f;
struct edge{
int nxt,to;
}e[N*2]; //链式前向星存图，注意是无向边
//所以边数组要开二倍，不然就会像wangaofei一样痛失AC
int idx,h[N],dis[3][N],n,m,B,E,P;
void AddEdge(int u,int v){
e[++idx].nxt=h[u],e[idx].to=v,h[u]=idx;
}
void bfs(int sx,int k){
queue<int> Q;
Q.push(sx);
dis[k][sx]=0;
while(Q.size()){
int u=Q.front();
Q.pop();
for(int i=h[u]; ~i; i=e[i].nxt){ //遍历编号为u的点的出边
int j=e[i].to;
if(dis[k][j]!=inf) continue;
dis[k][j]=dis[k][u]+1;
Q.push(j);
}
}
}
int main(){
memset(h,-1,sizeof h); //初始化链表头和dis数组
memset(dis,0x3f,sizeof dis);
B=read(),E=read(),P=read(),n=read(),m=read();
while(m--){
int x=read(),y=read();
AddEdge(x,y);
AddEdge(y,x);
}
bfs(1,0);
bfs(2,1);
ll ans=0; //注意结果可能爆int
if(P>=B+E){
ans=ans+B*dis[0][n];
ans=ans+E*dis[1][n];
printf("%lld\n",ans);
return 0;
}
bfs(n,2);
ans=1<<30; //2^30
for(int i=1; i<=n; i++){
ll t=0;
t=B*dis[0][i]+E*dis[1][i];
ans=min(ans,t+P*dis[2][i]);
}
printf("%lld\n",ans);
return 0;
}
T4 最早时间
1.0s 128MB
题目描述
飞飞和壮壮在同一时刻从1号结点出发。整个路线图里面有\(N\)个结点，结点的编号是 1 到 \(N\)。规定他俩只能从编号小的结点走到编号大的结点。这些结点之间有 \(M\) 条边，每两个结点之间最多只有一条路。
他们经过同一条路所需要花费的时间可能是不一样的，例如，飞飞花费 10 个单位的时间从 1 号结点走到 2 号结点，而壮壮可能要花费 20 个单位的时间从 1 号结点走到 2 号结点。在他俩没有走到终点 \(N\) 号结点以前，中间的过程中都不能有丝毫的停留。
请他们计算他们能够同时到达终点 \(N\) 号结点的最早时间。
输入
第一行输入两个正整数 \(N\) 和 \(M\)。
接下来 M 行，每行 4 个正整数 \(X，Y，Z_1，Z_2\)。\(X\) 和 \(Y\) 表示结点 \(X\) 到结点 \(Y\) 之间有一条路，保证 \(X < Y\)，\(Z_1\) 表示飞飞通过这条路所需要花费的时间，\(Z_2\) 表示壮壮通过这条路所需要花费的时间。
输出
输出他们能够同时到达 N 号结点的最早时间，如果不能同时到达，输出“IMPOSSIBLE”不包括引号。
样例输入
3 3
1 3 1 2
1 2 1 2
2 3 1 2
样例输出
2
样例说明
飞飞走 \(1->2->3\) 花费 2 个单位的时间，壮壮走 \(1->3\) 花费2个单位的时间，他们能够同时到达终点。
数据规模
\(1\leq N \leq 100,1\leq Z_1,Z_2\leq100\)。
思路
题目大意：
给定两张有向无环（只能从编号小的点走向编号大的点）图，这两张图除每条边的权值外完全相同，找出最小的\(ans\)，使得两张图从节点1出发都可以经过权值和为\(ans\)的边且只能从小编号节点走向大编号节点到达编号为\(n\)的节点。不存在\(ans\)输出"IMPOSSIBLE"。
数据范围不是很大，
但是暴力枚举两个图的每一条路径恐怕要\(TLE\)，
但是每条边权值最大不超过100，又由于每个点显然只能经过一次，整个从点1到点n的路径长度就不可能超过\(100\times 100=1e4\)，所以我们可以枚举每种路径长度，看一看是否在两个图上都存在该长度的路径，取最短的即是答案，若不存在输出IMPOSSIBLE。
具体如何求？
我考虑的是记忆化搜索。
用数组 \(f[0~OR~1][i][j]\) 表示在第0或第1张图上，是否可以用长度为\(j\)的路径从节点1到达节点\(i\)。是则取1，否则取0。
数组大小为\(2\times 100\times 100\times 100=2e6\) 空间完全可以接受。
每种状态若此前已搜索过，直接返回。
所以每种状态只会被搜索一次。
总共搜索量为\(O(n^3)\)，本题没有问题。事实上，由于本题里的诸多限制，大部分数据远远跑不满这个搜索量，所以我们可以接受这种解法。
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int read(){
int x=0,sgn=0;
char c=getchar();
while(!isdigit(c)) sgn|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return sgn?-x:x;
}
int g[N][N][2],f[N][N*N][2]; //点数很少，邻接矩阵存即可
int n,m,maxn; //f数组为了提高高维寻址效率，把2开到第三维了
void dfs(int u,int sum,int k){
if(f[u][sum][k]) return; //保证每个状态只被搜索一次
if(u==n){
maxn=max(maxn,sum); //找两张图中到n点的最大路径长度
}
f[u][sum][k]=1;
for(int i=u+1; i<=n; i++){ //从u+1枚举，因为题目要求从编号小的点走向编号大的点
if(g[u][i][k]!=-1){
dfs(i,sum+g[u][i][k],k);
}
}
}
int main(){
memset(g,-1,sizeof g); //初始化一个取不到的值，亦可为inf
n=read(),m=read();
while(m--){
int x=read(),y=read();
if(x>y) swap(x,y);
g[x][y][0]=read();
g[x][y][1]=read();
}
dfs(1,0,0); //搜索第0张图
dfs(1,0,1); //搜索第1张图
for(int i=0; i<=maxn; i++){
if(f[n][i][0]&&f[n][i][1]){ //找最短的路径
cout<<i<<'\n';
return 0;
}
}
puts("IMPOSSIBLE"); //无解
return 0;
}