【比赛报告】2018.10.30牛客网线上赛[牛客网NOIP赛前集训营-提高组（第三场）] NOIP练习赛卷二十六
题目链接
A.管道维修 数学期望
题目链接
#include
#include
#include
using namespace std;
typedef long long ll;
#define re register
const int mod=1e9+7;
const int N=210;
templateinline void read(tp&x)
{x=0;re int f=0;re char ch=getchar();while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(f)x=-x;
}
templateinline void write(tp x)
{re int buf[40],p=0;if(x<0)putchar('-'),x=-x;do{buf[p++]=x%10;x/=10;}while(x);for(re int i=p-1;i+1;i--)putchar(buf[i]+48);putchar(' ');
}
templateinline ll mul(tp x,tp y){return 1ll*x*y%mod;}
int n,m;
ll a,b,g[N][N];
ll qpow(ll a,ll b)
{ll ret=1;a%=mod;for(;b;b>>=1){if(b&1)ret=mul(ret,a);a=mul(a,a);}return ret;
}
int main()
{//freopen("in.txt","r",stdin);read(n);read(m);for(re int i=1;i<=n;i++)for(re int j=1;j<=m;j++){read(a);read(b);g[i][j]=mul(a,qpow(b,mod-2));//堵塞概率 }for(re int i=1;i<=n;i++){for(re int j=1;j<=m;j++){re ll t=min(min(i,j),min(n-i+1,m-j+1));re ll ans=0,p=g[i][j],q=g[i][j];for(re int k=1;k 总结
求期望的好题
B.公平竞赛 bfs
题目链接
#include
#include
#include
#include
using namespace std;
inline int read()
{int s=0,f=0;char ch=getchar();while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();if(f)s=-s;return s;
}
const int N=5e3+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
int op,n,m,tot,hd[N<<1],vis[N<<1],len[N<<1],ans[N<<1],minn=INF,pre[N<<1];
struct Edge{int v,nx;
}e[M<<1];
inline void add(int u,int v)
{e[++tot].v=v;e[tot].nx=hd[u];hd[u]=tot;
}
inline void bfs(int s)
{memset(vis,0,sizeof(vis));memset(len,0,sizeof(len));memset(pre,0,sizeof(pre));queueq;while(q.size())q.pop();q.push(s);vis[s]=1;while(q.size()){int u=q.front();q.pop();if(2*len[u]+1>=minn)return;for(int i=hd[u];i;i=e[i].nx){int v=e[i].v;if(v==pre[u])continue;if(!vis[v]){vis[v]=1;q.push(v);pre[v]=u;len[v]=len[u]+1;}else{if(len[u]+len[v]+1n?ans[i]-n:ans[i]);puts("");}}return 0;
}
总结
拆点后在二分图中bfs找最小环
C.急开锁 博弈论+打表
题目链接
#include
typedef long long ll;
int t,k,l,r;
ll len,f[4000010];
int main()
{//freopen("in.txt","r",stdin);scanf("%d",&t);f[0]=1;f[1]=2;while(t--){scanf("%d%lld",&k,&len);l=0;r=1;while(f[r] 总结
无
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！