2024.10.10 鮮花(原 I 的交互程序改)
Roads in E City
夜曲
一群嗜血的螞蟻 被腐肉所吸引
我面無表情 看孤獨的風景
失去你 愛恨開始分明
失去你 還有什么事好關心
當鴿子不再象征和平
我終于被提醒
廣場上喂食的是禿鷹
我用漂亮的押韻
形容被掠奪一空的愛情
啊 烏云開始遮蔽 夜色不干凈
公園里 葬禮的回音 在漫天飛行
送你的白色玫瑰
在純黑的環境凋零
烏鴉在樹枝上詭異的很安靜
靜靜聽 我黑色的大衣
想溫暖你日漸冰冷的回憶
走過的 走過的 生命
啊 四周彌漫霧氣
我在空曠的墓地
老去后還愛你
為你彈奏肖邦的夜曲
紀念我死去的愛情
跟夜風一樣的聲音
心碎的很好聽
手在鍵盤敲很輕
我給的思念很小心
你埋葬的地方叫幽冥
為你彈奏肖邦的夜曲
紀念我死去的愛情
而我為你隱姓埋名
在月光下彈琴
對你心跳的感應
還是如此溫熱親近
懷念你那鮮紅的唇印
那些斷翅的蜻蜓 散落在這森林
而我的眼睛 沒有絲毫同情
失去你 淚水混濁不清
失去你 我連笑容都有陰影
風在長滿青苔的屋頂
嘲笑我的傷心
像一口沒有水的枯井
我用凄美的字型
描繪后悔莫及的那愛情
為你彈奏肖邦的夜曲
紀念我死去的愛情
跟夜風一樣的聲音
心碎的很好聽
手在鍵盤敲很輕
我給的思念很小心
你埋葬的地方叫幽冥
為你彈奏肖邦的夜曲
紀念我死去的愛情
而我為你隱姓埋名
在月光下彈琴
對你心跳的感應
還是如此溫熱親近
懷念你那鮮紅的唇印
一群嗜血的螞蟻 被腐肉所吸引
我面無表情 看孤獨的風景
失去你 愛恨開始分明
失去你 還有什么事好關心
當鴿子不再象征和平
我終于被提醒
廣場上喂食的是禿鷹
我用漂亮的押韻
形容被掠奪一空的愛情
給個鏈接 this
首先考慮詢問,發現 \(s\) 的隨機性太強了,基本是沒有針對 \(s\) 的希望了。
容易想到如何判斷一條邊橋(包括后面的指將修過的邊單拿出來組成的圖的橋):將其斷開,在左右端點分別算 \(20\) 次判聯通,因為至少有一邊的概率 \(\ge \frac{1}{2}\),正確率還是很高的。
考慮怎么構造橋,顯然是將不是橋的斷開,剩下的一定是橋,并且構成了一棵樹,因為邊一定是 \(1\)。
考慮我們斷開的邊其中的 \(1\),可以先加入,在斷掉環上的一個點,判斷斷掉以后是否聯通即可(對于斷邊的左右端點)。
給一個交互庫吧:
Code
#include<bits/stdc++.h> // 交互題什么的最討厭了
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
mt19937 rnd(ull(new char)*ull(new char));
const int N=1e5+3;
struct Gph{
int hd[N],to[N<<1],nt[N<<1],wt[N<<1],tot=1;
void Add(int u,int v,int w){wt[++tot]=w,to[tot]=v,nt[tot]=hd[u],hd[u]=tot;}
void ADD(int u,int v,int w){Add(u,v,w),Add(v,u,w);}
#define For_to(i,u,v,g) for(int i=g.hd[u],v=g.to[i];i;i=g.nt[i],v=g.to[i])
}g;
bool p[N]; int ss;
int ca[N],cb[N]; bool wt[N],vis[N];
bool Get(int u){
p[u]=1; bool fg=0;
if(u==ss) return 1;
For_to(i,u,v,g) if(!vis[i>>1]&&g.wt[i]&&!p[v]) fg|=Get(v);
return fg;
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cout<<1<<endl;
int n=6,m=10;
cout<<n<<' '<<m<<endl;
for(int i=1;i<n;++i){cb[i]=rnd()%i+1; g.ADD(ca[i]=i+1,cb[i],wt[i]=1); cout<<i+1<<' '<<cb[i]<<endl;}
for(int i=n;i<=m;++i){while(ca[i]==cb[i]) ca[i]=rnd()%n+1,cb[i]=rnd()%n+1; g.ADD(ca[i],cb[i],wt[i]=rnd()%2),cout<<ca[i]<<' '<<cb[i]<<endl;}
while(1){
char opt; cin>>opt;
if(opt=='-'){int i; cin>>i; assert(!vis[i]); vis[i]=1;}
else if(opt=='+'){int i; cin>>i; assert(vis[i]); vis[i]=0;}
else if(opt=='?'){
int s=rnd()%n+1; cin>>ss;
memset(p,0,sizeof(p)),cout<<Get(s)<<endl;
}
else{
assert(opt=='!');
for(int i=1;i<=n;++i){int w; cin>>w; assert(w==wt[i]);}
return 0;
}
}
}
用管道做 OI 交互即可,可以看 this
P

本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18456314
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號