竟然做了一晚上才AC
發題解警示自己犯糖
一道思維題,推公式即可
首先手玩一下樣例發現 m=1,m=2均無法成功,直接輸出
如果大于2一定存在范圍[L,R]可以勝利
對于最小值,不難想到對于完全圖可以使n最小,且完全圖的合法炸彈數一定小于一個m條邊的m元環(在環內連接邊一定不會更劣嘛)
所以根據公式可知 n*(n-1)>=m,暴力時間復雜度 O(nT) 太劣了,考慮預處理+二分優化,時間復雜度 O(Tlogn+n),比較優
再考慮最大值,注意到對于一條邊,讓它的貢獻最大必然是連接兩個孤立點,這樣它的貢獻是兩個點,發現連成鏈或者環每個邊的貢獻都不如它優,這樣我們每一條邊獲得了兩個點的貢獻,同時會有一個炸彈合法,我們只能讓m-1個炸彈合法,所以最大有2*(m-1)個點,最后一條邊隨意連接兩個孤立的連通塊即可。
花火真可愛awa
代碼:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m;
const int N=4e5+10;
int f[N];
void init()
{
for(int i=1; i<=1e5;i++) {
f[i]=i*(i-1);
}
}
int check(int x)
{
int l=1,r=1e5;
while(l<r)
{
int mid=(l+r)>>1;
if(f[mid]>=x) r=mid;
else l=mid+1;
}
return r;
}
signed main(){
int T;
cin>>T;
init();
while(T--)
{
cin>>m;
if(m<=2) cout<<"Lose!";
else
{
cout<<check(2*m)<<" ";
cout<<2*(m-1);
}
cout<<endl;
}
}
浙公網安備 33010602011771號