专栏文章

20251002国庆模拟2

___H_J_M__
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minq67ao
此快照首次捕获于
2025/12/02 06:32
3 个月前
此快照最后确认于
2025/12/02 06:32
3 个月前
查看原文

Part 1 题目

题目: 点击这里快速下载

Part 2 考试重大时间线

8:00 开题，却发现题做过了（当然不是我做过），延迟十分钟。
8:10 再次开题，立刻开T1，认为就是一个简单的dijkstra，于是直接开写。
8:50 样例随便过，大样例TLE飞了，于是加了一个神秘的估价函数，时间复杂度不详，但大样利秒过，认为包没有问题的，没想到是大样例太水了。
9:20 读完题后，先写了一个Tarjan，又是熟悉的样例随便过，大样例**TLE**飞了，然后想其他解法。
9:50 仔细研究了大样例后，发现整张图只有两个强连通分量，只需要将不是连接同一个强连通分量便可以Accepted\color{green} Accepted 于是又是轻松过大样例，由于这道题用的时间有点长，就先看下一题。
10:30 终于看懂T3题面之后，先写了一个完全不用脑子的暴力，然后发现除了样例，啥都出不来，加了个记忆化，过了 20\color{red} 20 分的点。
11:20 T4写了一个暴力，发现这次连样例都过不了了，于是直接输出大样例，骗了十分。
12:10 后来又转头回去看T2，终于发现了原来的办法除了能过大样例其他什么都过不了，最后关头写了一个跟TJ思路有几分相像的代码，也就比暴力分高几分。

Part 3 题目详解

T1

dijkstra 当然没有错，优化的主要是在一个节点停留时间的选择。
先说结论:
设t为 到这个节点+等待的时间。
设t'为 到下一个节点的时间。
得到：
t=d (d为题面中的参数)t=\sqrt{d}\ (d为题面中的参数)
证明
设
f(t)=t+bt=t2+bt \begin{align} f(t) & = t+\frac{b}{t}\\ & = \frac{t^2+b}{t} \end{align}
则对这个函数求导得：
f′(t)=2t2−t2−bt2=1−bt2\begin{align} f'(t) & = \frac{2t^2-t^2-b}{t^2}\\ & = 1-\frac{b}{t^2} \end{align}
所以当f′(t)=0f'(t)=0。
t=b\begin{align} t & = \sqrt b \end{align}
所以我们只需要每一次转移到:
t′=max(t,b)t'=max(t,\sqrt b)
（因为有可能不能到b\sqrt b）
ACcodeCPP
#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=1e5+5;
int n,m;
int dis[N];
int vis[N];
struct node{int y,c,d;};
vector<node> v[N];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void Dij(){
	priority_queue<PII> Q;
	Q.push({0,1});
	while(!Q.empty()){
		int x=Q.top().second;
		int t=-Q.top().first;
		Q.pop();
		if(x==n){
			cout<<t;
			exit(0);
		}
		if(vis[x]) continue;
		vis[x]=1;
		for(node y: v[x]){
			int num=1e18;
			int nt=max(t,(int)sqrt(y.d));
			Q.push({-nt-y.c-(y.d/(nt+1)),y.y});
		}
	}
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c,d;cin>>a>>b>>c>>d;
		v[a].push_back({b,c,d});
		v[b].push_back({a,c,d});
	}
	Dij();
	cout<<-1;
	return 0;
}

T2

警告
接下来是一大段废话。
这道题目我们可以分两种情况讨论：
  • 这条边在一个强连通分量重
  • 这条边连接着两个强连通分量
【情况一】
我们发现在这里可以简单的画出输出same和diff的情况
same: 对于边 (1,8)
diff: 对于边 (2,3)
我们可以发现：
【出现same】对于边 (a,b) 若除了边 (a,b) 有 路径a-b 联通 则这条边没有影响
【出现diff】对于边 (a,b) 若除了边 (a,b) 所有其他 路径a-b 都不联通 则这条边有影响
【情况二】
same: 对于边 (6,7)
diff: 对于边 (6,2),(5,1)
我们可以发现：
【出现same】对于边 (a,b) 若除了边 (a,b) 有 路径a-b 联通 则这条边有影响
【出现diff】对于边 (a,b) 若除了边 (a,b) 所有其他 路径a-b 都不联通 则这条边没有影响
总结：
由于【情况一】满足一定有 路径b-a,而【情况二】满足一定没有 路径b-a。
因而答案为： 若同时存在 a-b 和 b-a 或同时不存在，则为same。
于是完了吗？\color{white} 吗？
本题重点！！！
因为不太好回避原本的边，因而把有关 路径a-b有 改为 路径a-b数量大于一（且路径不相同）。
因而从一个节点出发时，枚举走的第一个点，一次正序，一次倒叙，如果两次出发的点相同，则只有一条路径。

T3

推的实在是太好看了。
fm(n)为长度为m,值域大小为n的满足题意的序列数量。f_m(n)为长度为m,值域大小为n的满足题意的序列数量。 ∑i=1n∑j=1nfm(⌊ngcd⁡(i,j)⌋)=∑d=1nfm(⌊nd⌋)∑i=1n∑j=1n[gcd⁡(i,j)=d]=∑d=1nfm(⌊nd⌋)∑i=1⌊nd⌋∑j=1⌊nd⌋[gcd⁡(i,j)=1]=∑d=1nfm(⌊nd⌋)(2∑i=1⌊nd⌋φ(i)−1)\begin{aligned} \sum_{i=1}^{n} \sum_{j=1}^{n} f_{m}\left(\left\lfloor\frac{n}{\operatorname{gcd}(i, j)}\right\rfloor\right) & =\sum_{d=1}^{n} f_{m}\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \sum_{i=1}^{n} \sum_{j=1}^{n}[\operatorname{gcd}(i, j)=d] \\ & =\sum_{d=1}^{n} f_{m}\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\operatorname{gcd}(i, j)=1] \\ & =\sum_{d=1}^{n} f_{m}\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\left(2 \sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} \varphi(i)-1\right) \end{aligned}
额······

T4

没啥好说的，但是交大样例竟然有十分。

Part 4 总结

题目预期得分实际得分主要算法失分原因改进方法
不稳定的道路10021dijkstra+数学由于大样例太水，完全没看出代码的问题仔细算好时间复杂度
翻转有向图24+28思维+dfs如果看预期的分的话，实际的分还高几分，但是可惜了，考场上一共写了三种做法，也是只有暴力得了分···
在表格里造序列2020数学+杜教筛没推出式子···
zzzyyds010DP+组合数学额。还多了十分（大样例）···
总分： 79
预期得分：144

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...