$ \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,有四种情况:
- v->u 是否可联通
- u->v 是否只有唯一路径
- 然后就很简单了,对于每个询问,直接对上面两种情况分类讨论即可
- 1为真 2为真 -> same
- 1为真 2为假 -> diff
- 1为假 2为真 -> diff
- 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} \)
::::
然后就是超纲算法杜教筛
code:
\(\textup{\textbf{{\color{black}zzzyyds(holiday)}}}\)
考场思路
感觉像dp,但不知道怎么做
正解思路
\(\color{#FFFFFF}{我不会}\)
code:
总结
- 调整了做题顺序,先都把题看了几眼,发现3,4题有点难,去做1,2题了
(好像没什么变化)。 - 细节方面——昨天数组开小,今天数组开大(但是我在本地和bbc上也没出问题,lemon上跑就MLE了)
- 看问题要抓住本质?T2直接做的暴力和优化,分析有点少。
\(\Huge \color{white}{每个地方都有问题}\)