至于j/s的大模拟，可以放在最后做，确保自己其他三道题拿不到其他分的时候全力冲刺，且可以先冲子任务。 对拍相关： lca: 最短路： floyd：（可以用来骗分，确信。 tarjan缩点： 拓扑排序： 边双：考前把这个看一遍：
考场策略应该是,10min解压+读题+建文件夹，
先打暴力，别被一道题卡死（！！就比如去年的J组T1）
别死磕，别死磕，别死磕
尤其早上的J组只有3.5h，一定要注意时间分配。
相信自己，心态不要炸，当成正常的模拟赛对待。
如果非常慌可以选择深呼吸或者先打自己会的分。
下考前5min反复检查：
数组大小，long long，freopen，调试删了吗，子任务分治，多测清空
必要时可以选择对拍，s组的目标就是暴力打满别挂！
时刻有紧迫感，强迫自己思考。
不要忘记取模，不要打错模数，记得输出-1。考前复习资料
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i=2;i<=n;i++){
int x=rand()*rand()%(i-1)+1;
cout<<x<<" "<<i<<endl;//树
}
for(int i=1;i<=m-n+1;i++){
int x=rand()*rand()%n+1;
int y=rand()*rand()%n+1;
if(x==y) continue;
cout<<x<<" "<<y<<endl;//先建树再建图
}
}
点击查看代码
//lca
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
for(int i=0;i<=20;i++){
f[u][i+1]=f[f[u][i]][i];
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
f[v][0]=u;
dfs(v,u);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--){
if(dep[f[x][i]]>=dep[y])//>=!!!
x=f[x][i];
if(x==y) return x;
}
for(int i=20;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i],y=f[y][i];
}
}
return f[x][0];
}
点击查看代码
bool vis[maxn];
int dis[maxn];
struct node{
int dis,pos;
bool operator<(const node &x)const{
return x.dis<dis;
}
};
void dij(int x){
memset(vis,0,sizeof(vis));
memset(dis,0x7f7f7f7f,sizeof(dis));
priority_queue<node> q;
dis[x]=0;
q.push((node){0,x});
while(!q.empty()){
node tmp=q.top();
q.pop();
int u=tmp.pos,d=tmp.dis;
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]) q.push((node){dis[v],v});
}
}
}
}
点击查看代码
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);
}
}
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=10015;
int n,m,a[maxn],s;
struct edge{
int to,nxt,fr;
}e[10*maxn],ed[10*maxn];
int head[maxn],edgenum;
void add_edge(int u,int v){
e[++edgenum].nxt=head[u];
e[edgenum].fr=u;
e[edgenum].to=v;
head[u]=edgenum;
}
int low[maxn],dfn[maxn],tim,vis[maxn],vol[maxn];
stack<int> st;
void tarjan(int x){
low[x]=dfn[x]=++tim;
st.push(x);
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x]){
int y;
while(y=st.top()){
st.pop();
vol[y]=x;
vis[y]=0;
if(x==y) break;
a[x]+=a[y];
}
}
}
int h[maxn],in[maxn],dis[maxn];
int topo(){
queue<int> q;
int tot=0;
for(int i=1;i<=n;i++){
if(vol[i]==i && !in[i]){
q.push(i);
dis[i]=a[i];
}
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=h[x];i;i=ed[i].nxt){
int v=ed[i].to;
dis[v]=max(dis[v],dis[x]+a[v]);
in[v]--;
if(in[v]==0) q.push(v);
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
add_edge(u,v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=m;i++){
int x=vol[e[i].fr],y=vol[e[i].to];
if(x!=y){
ed[++s].nxt=h[x];
ed[s].to=y;
h[x]=s;
in[y]++;
}
}
cout<<topo()<<endl;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct edge{
int nxt,to;
}e[1005];
int in[1005],head[1005],edgenum;
int n,dep[1005],ans;
void add_edge(int u,int v){
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
void toposort(){
queue<int>q;
for(int i=1;i<=n;i++) {
if(in[i]==0){ //应提前预处理此数组
q.push(i);
dep[i]=1;
}
}
while(!q.empty()){
int x=q.front();
q.pop();
cout<<x<<" ";
for(int i=head[x];i;i=e[i].nxt) {
int v=e[i].to;
dep[v]=dep[x]+1; //记录顺序
ans=max(ans,dep[v]);
in[v]--; //一定要记得入度减
if(in[v]==0) q.push(v);
}
}
}
int main(){
cin>>n;
int x;
for(int i=1;i<=n;i++){
while(cin>>x){
if(!x)break;
in[x]++;
add_edge(i,x);
}
}
toposort();
return 0;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int n,m;
struct edge{
int to,nxt;
}e[2*maxn];
int head[maxn],edgenum=1;
void add_edge(int u,int v){
e[++edgenum].nxt=head[u];
e[edgenum].to=v;
head[u]=edgenum;
}
int dfn[maxn],low[maxn],tim,cnt,col[maxn];
int st[maxn],top;
bool b[2*maxn];//i是否为割边
int tot[maxn];
vector<int> ans[maxn];
stack<int> s;
void tarjan(int u,int fa){
dfn[u]=low[u]=++tim;
s.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
b[i]=b[i^1]=1;//该边及其反向边均为桥
}
}
else if(i!=(fa^1))
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++cnt;
while(1){
int t=s.top();
s.pop();
col[t]=cnt;
if(u==t) break;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
add_edge(u,v);
add_edge(v,u);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i,0);
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
tot[col[i]]++;
ans[col[i]].push_back(i);
}
int now=1;
while(tot[now]){
cout<<tot[now]<<" ";
for(int i=0;i<ans[now].size();i++)
cout<<ans[now][i]<<" ";
now++;
cout<<endl;
}
}
10.26。
疑似要挂分了，T1不保证一定对，T2还不一定有40，160是一个SN稳一等的分数，J组随便考，不挂可以300+
今年比去年考前不焦虑好多，考完焦虑好多，你妈。
为什么这么重视结果呢？可能是我真的努力了，如果真的爆单了我真的会哭的。
好煎熬好痛苦啊，不敢想象APJ国赛day1考完什么心情，这可能就是我和人家的差距。
Update on 11.10:
考完花了将近两天努力把自己从噩梦里努力解脱出来，当然距离今天已经有足足两周的时间了，所以还是决定来补游记。
Day-7--0：
停了两周作业+一周课，考了5场模拟赛，最后两天是全真模拟（写代码确认表那种+文件测试。
印象非常深刻的是有一天只有T1可改，T2是神秘折半搜索，T3的std 27k，T4忘了。
最后一天据说非常简单，然而看完T1之后遂傻眼（下考场发现是萌萌题），据说最高分300+，这个时候觉得自己能考100+不错了，最后达成了目标/kk
Day 1:
前一天很早睡了（没有跟去年一样各种内耗焦虑非常好！）早上起来莫名激动，然而坐上车才开始后知后觉紧张担心自己考不好怎么样，但是被我的困打败了/shui，途中一直在做非常奇怪的梦。
到的很早，没有拍合照环节，走了巨大远的路到了考场楼下，然后在旁边树下把复习资料看了一半，问了同学得知不会考拓扑排序之后遂扔，然后进考场。
哇好巨大的考场，哇在一楼诶。
你说得对但是我挡板呢？？？？
电脑时间不负众望地不准，于是8:25拿到了PDF密码，感谢和蔼可亲的监考员使用先进的极域下发密码的方式省去了我眯着眼睛尝试密码的时间。在D盘写建好文件夹好头文件，开题！
T1疑似签到题啊秒了，T2看起来好长，不过不难差不多也秒了，T3有点意思，像小学数学，T4好神秘！
于是开考前就过了T1T2的大样例：）
T1简单捏，四个数组秒了，谨记考前一天bobo告诉我们一定要养成好习惯存D盘，免得蓝屏，所以初版程序全存D盘了，想着最后再往里面拖（伏笔）
诶怎么没过样例，哦是我复制没改完，改一个字符就过了。另存为到下发文件夹（伏笔*2）一下测大样例也过了，扔。
T2简单捏，模拟一下秒了，诶怎么又没过样例，哦是我题读错了，要求能到的个数啊那没事了，改完过了所有样例，重复了和T1一样的存盘过程。
T3不能再送了吧，但是特殊性质暗示都到我脸上了总不能不会，手玩一下找了找规律，发现个别点如10过不去，于是特判了一下。非常担心假了于是写了个搜再写了个拍，拍上了之后又加了几组特判过了拍，稍微安心了一点，看T4！
此时2h+，没事优势在我！
花了10min看懂题，但是不会dp啊只能特殊性质，发现特殊性质1很显然，写写写。写完企图获得更多的分，一直思考到了还剩20min仍然一无所获，于是开始摆烂。
但是我没有发现特殊性质1是有大样例，10min了赶紧测一下，没过！！！急急急但是急不出来了，所以开始检查文件。
文件是监考员一个一个压缩提交的，第一次见，但是在考场上呆了30+min才出，玩了30+min的纸牌成功通关，结果是没时间吃饭了/kk。
下午考S！
和早上一个考场甚至机位都只是往右移了两个。手动调完时间后，拿pdf密码，开题，此时还是有点紧张紧张紧的。
飞速把四道题浏览了一遍，T1看起来很可做啊，T2是物理题，T3不是大模拟嬴赢赢，T4神秘题。
先开T1，诶这不排个序二分一下做完了。等等我没读错题吧，于是再读了两遍1发现没有错于是开写，写完调了一会过了前两个样例。发现自己过不去最后一个样例，输出了一下发现有点假，于是改了一会过了。
T2读懂题花了20min，不会啊，先写特殊性质，写了2h仍然只有40，第一个数二分是明显的，不过第二个数一直不对，调了很久无果。
在心态快崩的时候开了T3，一眼dp，不会先搜一下。过了小样例看T4。
发现看不懂。
于是开始调T2，最后写了30p光荣跑路，特殊性质到最后都不会。:）
最后20min提前开始查文件，把我在D盘存的文件一个一个往文件夹里拖（伏笔），还剩5min的时候反复检查freopen，突然发现没开（但此时我记得我关c++文件的时候全部都开过freopen了），这个时候还没有意识到事情的严重性，慌慌张张开了。
下考，监考员一个一个压缩文件提交。只能在座位上等。
最炸裂的事情这时发生了，在等待的过程中我发现T2的代码不是最后一版代码！！！因为子任务我写了很长，此时我文件夹里的detect.cpp只有40行，我才意识到我的代码被另存为在下发文件里了，把自己真正的文件找了回来之后，监考员看了一眼我18:36更改的文件夹帮我提交了。
然而我刚交完，发现自己T1也出现了这样的问题，把T1拉下来跑一下最后一个点，发现没过！！！
当时急的手都在抖，想申请再交一次，于是慌忙举手。好像在对讲机询问之后同意了。
完了这么写写不出来我的崩溃;-;
我当时一度以为交不了了自己要爆蛋了，整个人差点哭出来，一直在问能不能再交一次，我说代码修改时间没变只是存错了、在得到同意的答复后慌慌张张把自己的T1改过来，把提交的压缩包删了之后再交了一次（为什么可以呢是因为我代码的修改时间没变），感觉整个人都在发抖非常紧张+崩溃。
出考场，回去的路上一直在担心自己存错盘，然后担心着担心着想起早上也是这么干的（伏笔回收），更自闭了。
于是就有了文章开头。
Day ？（11.04）：
查分日，期中考试第一天。
CCF鸽了两次后504了很久，最后查到了。
J-280，T1挂了（upd 11.07：时候改了一个字符就过了，应该是最后一版代码另存为的原因:)
S-130，T3搜索挂了，应该也是这个原因哈哈，不过有惊无险T1T2没事。
深深认识到了自己和大家的差距，即使没挂也是机房垫底分，还是人太菜的原因。
希望能苟进noip，进不去的话下个赛季加油;-;
存盘警钟长鸣了属于是，不要在考场上成天干毁自己心态的事:)
标签：head,int,T1,2024,maxn,low,edgenum,游记,CSP From： https://www.cnblogs.com/wann-042013/p/18502974