NOIP2025模擬1
T1：公司的供應鏈（dag）
思路：
大概就是推出性質但是沒寫出來。
我們不難發現，對于一個環來說，把環內全部的邊刪掉是合法的。
然后我們就從一個點開始搜，如果沒有環，就把經過的邊都標記一下，這是要保留的。然后再記錄一下走過的邊數，保證每個環只經過一次。
代碼：
$code$
#include<iostream>
#include<vector>
using namespace std;
const int N=600000+5;
int n,m,cnt[N],f[N],x[N],y[N],ans;
bool vis[N];
vector<pair<int,int>> v[N];
inline int dfs(int x){
if(vis[x]) return x;//有環
vis[x]=1;
while(cnt[x]<(int)v[x].size()){
int flag=dfs(v[x][cnt[x]].second);
if(!flag) f[v[x][cnt[x]].first]=-1;//標記保留的邊
cnt[x]++;//走過的邊數
if(flag!=x&&flag){//后面有個小環
vis[x]=0;
return flag;
}
}
vis[x]=0;
return 0;//無環
}
int main(){
// freopen("dag.in","r",stdin);
// freopen("dag.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x[i]>>y[i];
v[x[i]].push_back(make_pair(i,y[i]));//建邊
}
for(int i=1;i<=n;i++) if(cnt[i]<(int)v[i].size()) dfs(i);//還有邊沒走
for(int i=1;i<=m;i++) if(f[i]==-1) ans++;
cout<<ans<<'\n';
for(int i=1;i<=m;i++) if(f[i]==-1) cout<<x[i]<<" "<<y[i]<<'\n';
return 0;
}
T2：宇宙的卷積（juanji）
思路：
大概就是賽時兩眼一閉數組就開 \(20\) 然后掛了 \(60 ~ pts\) 吧。
有沒有大佬給我講講 \(T2\) 啊！！真的不會啊！！
T3：艦隊的遠征（far）
思路：
看眼式子有點像李超，但是馬上自我否定了。最后選擇跑了 \(n^2\) 遍 \(dij\) 。
其實就是把路徑分為三部分：
\[s→x=>y→t
\]
\(x,y\) 之間的邊是我們新建的特殊邊。
怎么求答案呢？
正著跑一邊最短路求出到 \(s\) 的最短路，反著求一遍最短路到 \(t\) 的最短路，然后維護一下 \((x-y)^2\) 。
然后答案是什么呢？
\[dis1_x+dis2_y+(x-y)^2
\]
整理一下，可得
\[dis1_x+x^2+dis2_y+y^2-2*x*y
\]
我們枚舉每一個 \(x\) ，因此 \(dis1_x+x^2\) 為定值，所以我們只需要維護 \(dis2_y+y^2-2*x*y\) 就好了。
用什么維護呢？用我否定了的李超線段樹。【對不起】
然后呢？
然后就沒了。
感謝 Wx_y大俠 的博客（就是能不能換個題目??）
代碼：
$code$
#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int N=2e6+5,inf=1e18;
int n,m,s,t,x,y,z,dis1[N],dis2[N],ans=1e18,cnt1,cnt2,head1[N],head2[N],tr[N<<1];
bool vis1[N],vis2[N];
struct flower{
int to,nxt,val;
}a[N],b[N];
struct css{
int k,b;
}line[N];
inline void add1(int x,int y,int z){
a[++cnt1].to=y;
a[cnt1].val=z;
a[cnt1].nxt=head1[x];
head1[x]=cnt1;
}
inline void add2(int x,int y,int z){
b[++cnt2].to=y;
b[cnt2].val=z;
b[cnt2].nxt=head2[x];
head2[x]=cnt2;
}
inline void dij1(int s){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
for(int i=1;i<=n;i++) dis1[i]=1e18,vis1[i]=0;
dis1[s]=0;
q.push({0,s});
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis1[x]) continue;
vis1[x]=1;
for(int i=head1[x];i;i=a[i].nxt){
int y=a[i].to;
if(dis1[y]>dis1[x]+a[i].val){
dis1[y]=dis1[x]+a[i].val;
if(!vis1[y]) q.push(make_pair(dis1[y],y));
}
}
}
}
inline void dij2(int s){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
for(int i=1;i<=n;i++) dis2[i]=1e18,vis2[i]=0;
dis2[s]=0;
q.push({0,s});
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis2[x]) continue;
vis2[x]=1;
for(int i=head2[x];i;i=b[i].nxt){
int y=b[i].to;
if(dis2[y]>dis2[x]+b[i].val){
dis2[y]=dis2[x]+b[i].val;
if(!vis2[y]) q.push(make_pair(dis2[y],y));
}
}
}
}
inline int calc(int id,int x){
return line[id].k*x+line[id].b;
}
inline void insert(int rt,int l,int r,int id){
if(!tr[rt]){
tr[rt]=id;
return ;
}
if(l==r){
if(calc(tr[rt],l)>calc(id,l)) tr[rt]=id;
return ;
}
int mid=(l+r)>>1;
if(calc(id,mid)<calc(tr[rt],mid)) swap(id,tr[rt]);
if(calc(id,l)<calc(tr[rt],l)) insert(rt<<1,l,mid,id);
if(calc(id,r)<calc(tr[rt],r)) insert(rt<<1|1,mid+1,r,id);
}
inline int query(int rt,int l,int r,int x){
if(l==r) return calc(tr[rt],x);
int ans=calc(tr[rt],x);
int mid=(l+r)>>1;
if(x<=mid) ans=min(ans,query(rt<<1,l,mid,x));
else ans=min(ans,query(rt<<1|1,mid+1,r,x));
return ans;
}
signed main(){
freopen("far.in","r",stdin);
freopen("far.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
add1(x,y,z);add2(y,x,z);
}
dij1(s);dij2(t);
line[0]=(css){0,inf};
for(int i=1;i<=n;i++) line[i]=(css){-2*i,i*i+dis2[i]};
for(int i=1;i<=n;i++) insert(1,1,n,i);
for(int i=1;i<=n;i++) ans=min(ans,query(1,1,n,i)+i*i+dis1[i]);
cout<<ans<<'\n';
return 0;
}
T4：軍團的陣列線（team）
顯然不會
后言
$songs$
皇家海軍過戰場
日不落帝國踏汪洋
女王手指向何方
東印度之殤
百年玫瑰戰爭狂
鐵甲艦掀起了殖民浪
黃金澆筑的徽章
是榮耀的過往
燈塔的火焰猶閃亮
合眾國航母在啟航
自由的軍隊出邊疆
烈火燃他鄉
衛星畫滿蒼穹上
五大洲遍布我的軍港
手握著北約的韁繩
雄鷹依舊翱翔
圣母院鐘聲繞梁
凡爾賽宮映朝陽
第三帝國軍魂游蕩
凝視這群羊
鋼鐵洪流凜寒冰鑲
核潛艇游蕩在北冰洋
喀秋莎掠過的寒光
照亮了紅場
寒冰埋葬了沙皇
雙頭鷹軍號不再回響
冬宮門前回眸望
蘇維埃榮光
塵封過五帝與三皇
歷經了夏商和漢唐
百年蟄伏不卑不亢
華夏迎曙光
五千年歲月滄桑
文脈傳承至今威萬邦
共和國乘風破浪
征途再起航
翻手為云覆手為霜
執天下牛耳喜怒五常
肩扛世界格局
筑山河恒久輝煌
社稷固若金湯
千百年送走多少列強
未曾浴血染沙場
怎配踏八荒
普天下星辰未央
誰妄想撼動我的權杖
五常眼眸盡琳瑯
看天下興亡
