清北刷题冲刺 11-03 p.m
分类:
IT文章
•
2022-07-27 14:09:13
三向城
![]()
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y;
int main(){
freopen("city.in","r",stdin);freopen("city.out","w",stdout);
// freopen("Cola.txt","r",stdin);
scanf("%d",&n);
while(n--){
scanf("%d%d",&x,&y);
int ans=0;
while(x!=y){
ans++;
if(x<y)swap(x,y);
x/=2;
}
printf("%d
",ans);
}
return 0;
}
100分 两个同时往上跳
灵魂画师
![]()
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,c,K,mc,cnt[101];
double dp[101][101],ans;
int main(){
freopen("paint.in","r",stdin);freopen("paint.out","w",stdout);
scanf("%d%d%d",&n,&c,&K);
for(int i=1;i<=K;i++){
int l,r;
scanf("%d%d",&l,&r);
for(int j=l;j<=r;j++){
cnt[j]++;
mc=max(cnt[j],mc);
}
}
dp[0][1]=1;
for(int i=0;i<mc;i++){
for(int j=0;j<c;j++){
dp[i+1][j]+=dp[i][j]/2;
for(int k=0;k<c;k++){
dp[i+1][(j*k)%c]+=dp[i][j]/(2*c);
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<c;j++){
ans+=dp[cnt[i]][j]*j;//概率乘以收益
}
}
printf("%.3lf
",ans);
return 0;
}
100分 概率dp
![]()
#include<iostream>
#include<cstdio>
#define maxn 21
using namespace std;
int map[21][21],n,m,sum,num,head[maxn],fa[maxn],mx,mn=0x7fffffff;
bool flag=1;
struct node{
int to,pre,v;
}e[maxn*maxn*2];
void Insert(int from,int to,int v){
e[++num].to=to;
e[num].v=v;
e[num].pre=head[from];
head[from]=num;
}
void dfs(int now,int father){
bool leaf=0;
fa[now]=father;
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
if(to==father)continue;
dfs(to,now);
leaf=1;
}
if(now==n&&leaf==0){
flag=1;
return;
}
}
int main(){
freopen("vanilla.in","r",stdin);freopen("vanilla.out","w",stdout);
// freopen("Cola.txt","r",stdin);
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
mx=max(mx,z);mn=min(mn,z);
x+=1;y+=1;
map[x][y]=map[y][x]=z;
Insert(x,y,z);Insert(y,x,z);
sum+=z;
if(x!=i||y!=i+1)flag=0;
}
if(flag){
sum*=4;
sum-=map[n][n-1]*2+map[1][2]*2;
cout<<sum;
return 0;
}
if(m==n-1){
flag=0;
dfs(1,0);
if(flag){
cout<<sum*4-map[n][fa[n]]*2;
}
else cout<<sum*4;
return 0;
}
while(sum<177)sum*=2;
sum%=177;
if(sum<mx)sum+=mx*2;
cout<<sum;
return 0;
}
