E-奇环_牛客练习赛106 二分图 鸽笼原理

二分图是没有奇数环的，所以可以把图看作是一个二分图，左边有n1个点，右边有n2个点，那么不存在奇数环的情况下最多有n1*n2条边，可以列出一些式子

通过基本不等式可以得出，m最大是2e5，可以得出n<=896,当n大于896或者

时是一定有奇数环的，其他情况直接判有没有就行

题解 | #E-G#_牛客博客 (nowcoder.net)

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int head[N],cnt;
struct Edge
{int next,to;
}e[N];
void addedge(int from,int to)
{e[++cnt].next=head[from];e[cnt].to=to;head[from]=cnt;
}
int t,n,m,vis[N],dep[N],flag;
map,bool>mp;
void dfs(int u,int fa)
{if(flag) return;dep[u]=dep[fa]+1;vis[u]=1;for(int i=head[u];i;i=e[i].next){if(flag) return;int j=e[i].to;if(j==fa) continue;if(vis[j]==1){int siz=dep[u]-dep[j]+1;//cout<<"u="<>t;while(t--){cin>>n>>m;mp.clear();for(int i=1;i<=cnt;i++) e[i].next=e[i].to=0;for(int i=1;i<=n;i++) head[i]=vis[i]=dep[i]=0;cnt=0;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;if(u>v) swap(u,v);mp[{u,v}]=1;}if(n>896||m<(n*n/4-n/2-100)){cout<<"YES\n";continue;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){if(!mp[{i,j}]) addedge(i,j),addedge(j,i);}flag=0;for(int i=1;i<=n;i++){if(!vis[i]) dfs(i,0);}if(flag) cout<<"YES\n";else cout<<"NO\n";}return 0;
}

F-座位_概率期望

会有两种情况，前i-1个人把第i个座位占掉之后，第i个人可以选前i-1中的一个座位或者第i+1个座位；或者前i-1个人把前i-1个座位占掉之后第i个人可以选择第i个或者是第i+1个座位；可以看出如果第i个人不选第i+1个座位的话那么就形成了前i个人占掉前i个座位的局面，这样的概率是0.5，那么第i个人占掉第i个座位的情况就是前i-1个人占掉前i-1个座位且第i个人选了第i个座位，这样的概率就是0.5*0.5=0.25，那么第i个人占掉第i个座位的期望就是0.25*1+0*(1-0.25)=0.25，由于第1个人和第n个人只能占第1个和第n个所以期望是0.5，所以n个人的期望就是0.5+0.5+(n-2)/4,当n==1的时候特判一下就可以

题解 | #E-G#_牛客博客 (nowcoder.net)

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=998244353;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int n;
signed main()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;if(n==1) cout<<"1\n";else{int inv4=getinv(4);int ans=(1+(n-2)*inv4%mod)%mod;cout<

#include
//#pragma-GCC-optimize("-Ofast");
#define int long long
//#define ll long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=2e6+5;
const int mod=998244353;
const int inf=1e17;
const double pi=acos(-1);
int qpow(int a,int b)
{int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int getinv(int a){return qpow(a,mod-2);}
int p[505],n,dp[505][505][2];
char s[505];
signed main()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;cin>>(s+1);int m=0;for(int i=1;i<=n;i++)if(s[i]=='1') p[++m]=i;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j][0]=dp[i][j][1]=inf;for(int i=0;i<=n;i++)dp[i][0][0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]);dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+abs(p[j]-i));}}int ans=min(dp[n][m][1],dp[n][m][0]);if(ans>n*n) ans=-1;cout<