当前位置：首页 > news >正文

10.2 考试总结

news 2025/10/3 20:40:12

$ \Huge 10.2 考试总结$

得分情况

预计得分：20+20+0+0
实际得分：0+4+0+0

时间分配（大概）

8:20 - 9:10 把所有题都看了一遍，决定先做T1
9:10 - 9:50 打出T1第一版过小样例，去做T2（T1最接近正解的一次）
9:50 - 10:30 打出T2暴力,检查正确性 ~~虽然是tarjan~~
10:30 - 11:00 两道题暴力正确，开始看T3,T4
11:00 - 11:30 T3没思路，T4不会打，回头看T1
11:40 - 12:10 感觉T1好像打错了，第二版是纯暴力并且数组开大了

错点

数组开大了MLE，所以T1没得分
没想太深，直接想的暴力拿分？(T2)
思路不清晰，有些模棱两可，所以代码很难去实现

题目分析

$\textup{\textbf{{\color{black}不稳定的道路(road)}}}$

考场思路

第一版是Dijkstra直接去跑，每次枚举要等的时间，一直到$\sqrt{d_i}+1$为止，还是没法过，但至少有30分
第二版直接暴力搜，每种情况都做，直接爆炸，如果不MLE，应该是21分

正解思路

因为$c_i$是不变的，所以只考虑$d_i$即可。很容易发现当$t>\sqrt{d_i}+1$时，是不需要等的(因为再等一定更劣)，而对于$t<\sqrt{d_i}-1$，则是可能会等的。所以按照这个思路直接跑Dijkstra就可以了。

code:

#include<bits/stdc++.h>
#define int long long
#define mk make_pair
#define PII pair<int,int> 
#define inf 0x3f3f3f3f
using namespace std;
inline int read() {int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return s*f;
}
const int N=3e5+5;
int n,m;
int ver[N],head[N],ne[N],tot;
PII w[N];
int vis[N];
void add(int x,int y,PII z){tot++;ver[tot]=y,ne[tot]=head[x],head[x]=tot,w[tot]=z;
}
struct node{int d,x;
};
bool operator<(node A,node B){return A.d<B.d;
}
void dj(){priority_queue<node> q;q.push({0,1});while(!q.empty()){auto tmp=q.top();q.pop();int x=tmp.x;int t=-tmp.d;if(x==n){cout<<t;return ;}if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=ne[i]){int y=ver[i],z1=w[i].first,z2=w[i].second;int num=1e18;for(int j=max(t,(int)sqrt(z2)-2);j<=max(t,(int)sqrt(z2)+2);j++)num=min(num,j-t+z2/(j+1));q.push({-num-z1-t,y});}}cout<<-1;
}signed main(){freopen("road.in","r",stdin);freopen("road.out","w",stdout);n=read(),m=read();for(int i=1;i<=m;i++){int x=read(),y=read(),z1=read(),z2=read();add(x,y,mk(z1,z2));add(y,x,mk(z1,z2));}dj();return 0;
}

$\textup{\textbf{{\color{black}翻转有向图(turn)}}}$

考场思路

没有任何技术含量的暴力，每次都改边，然后去跑一边tarjan，看强连通分量是否改变

正解思路

分类讨论一下，对于两点u,v,有四种情况：
1. v->u 是否可联通
2. u->v 是否只有唯一路径
然后就很简单了，对于每个询问，直接对上面两种情况分类讨论即可
1. 1为真 2为真 -> same
2. 1为真 2为假 -> diff
3. 1为假 2为真 -> diff
4. 1为真 2为假 -> same

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}return s*f;
}
const int N=2e5+5;
int n,m;
int ver[N],head[N],ne[N],tot;
int f1[1005][1005],f2[1005][1005];
vector<int> v[N];
int x[N],y[N];
void dfs(int x,int st,int *f){if(f[x]) return ;f[x]=st;for(int y : v[x])dfs(y,st,f);
}
signed main(){freopen("turn.in","r",stdin);freopen("turn.out","w",stdout);n=read(),m=read();for(int i=1;i<=m;i++){x[i]=read(),y[i]=read();v[x[i]].push_back(y[i]);}for(int i=1;i<=n;i++){f1[i][i]=f2[i][i]=1;for(int j : v[i]) dfs(j,j,f1[i]);reverse(v[i].begin(),v[i].end());for(int j : v[i]) dfs(j,j,f2[i]);}for(int i=1;i<=m;i++){if(f1[x[i]][y[i]]!=f2[x[i]][y[i]]){//是否存在除当前边之外的路径if(f1[y[i]][x[i]]==0) cout<<"diff\n";//是否在一个强连通分量中else cout<<"same\n";}else {if(f1[y[i]][x[i]]>0) cout<<"diff\n";else cout<<"same\n";}}return 0;
}

$\textup{\textbf{{\color{black}在表格里造序列(table)}}}$

考场思路

考场上的我大脑空白......

正解思路

设 $f_m(n)$表示满足以下要求的的所有序列数量：

序列长度为 m
序列中元素均为 [1,n]内的整数；
序列中元素的最大公约数为 1

那么最大公约数为d的序列数量为$f_m(\frac{n}{d})$

而我们所要求的答案则是：

:::align{center}

$\quad\sum_{i=1}^{n}\sum_{j=1}^nf_m(\frac{n}{gcd(i,j)})$

::::

化简一下，即

:::align{center}

$ \begin{aligned} \quad\sum_{d=1}^{n}f_m(\frac{n}{d})\ast\sum_{i=1}^{n}\sum_{j=1}^{n}&(bool)[gcd(i,j)==d]\\ <&=>\\ \quad\sum_{d=1}^{n}f_m(\frac{n}{d})\ast\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}&(bool)[gcd(i,j)==1] \end{aligned} $

::::

然后就是超纲算法杜教筛