期望得分：100+100+30=230
实际得分：100+100+30=230
1. 三向城
题目描述
三向城是一个巨大的城市，之所以叫这个名字，是因为城市中遍布着数不尽的三岔路口。（来自取名力为0的出题人）
具体来说，城中有无穷多个路口，每个路口有唯一的一个正整数标号。除了1号路口外，每个路口都连出正好3条道路通向另外3个路口：编号为x（x>1）的路口连出3条道路通向编号为x*2，x*2+1和x/2（向下取整）的3个路口。1号路口只连出两条道路，分别连向2号和3号路口。
所有道路都是可以双向通行的，并且长度都为1。现在，有n个问题：从路口x到路口y的最短路长度是多少？
输入格式
第一行包含一个整数n，表示询问数量；
接下来n行，每行包含两个正整数x, y，表示询问从路口x到路口y的最短路长度。
输出格式
输出n行，每行包含一个整数，表示对每次询问的回答。如果对于某个询问不存在从x到y的路径，则输出-1。
样例输入
3
5 7
2 4
1 1
样例输出
0
样例解释
5号路口到7号路口的路径为：5->2->1->3->7，长度为4；
2号路口到4号路口的路径为：2->4，长度为1；
1号路口到本身的路径长度为0；
数据范围
对30%的数据，x,y≤20；
对60%的数据，x,y≤105，n≤10；
对100%的数据，x,y≤109，n≤104。
把大的除以2直到相等
#include<cstdio>
#include<iostream> using namespace std; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
int n,x,y,ans;
read(n);
while(n--)
{
ans=;
read(x); read(y);
while(x!=y)
{
if(x<y) swap(x,y);
x>>=; ans++;
}
cout<<ans<<'\n';
}
}
2. 灵魂画师
题目描述
虽然不知道为什么，但是你一直想用一种神奇的方式完成一幅画作。
你把n张画纸铺成一排，并将它们从1到n编号。你一共有c种颜色可用，这些颜色可以用0到c-1来编号。初始时，所有画纸的颜色都为1。你一共想进行k次作画，第i次作画时，你会等概率随机地选闭区间[Li,Ri]内的画纸的一个子集（可以为空），再随机挑一种颜色bi，并把挑出来的画纸都涂上该颜色。原有颜色a的画纸在涂上颜色b后，颜色会变成(a*b) mod c，这是这个世界的规律。
因为你将颜色用数字来命名了，因此你可以求出在k次作画结束后，每张画纸上的颜色对应的数字相加之和的期望。现在请你编程求一下这个值。
以防万一你不知道什么是期望：如果一个量X，它有p1的概率值为v1，有p2的概率值为v2……pn的概率值为vn，则X的期望值等于。
输入格式
第一行包含3个正整数n, c, k，意义如题所述。
接下来k行，每行包含两个数Li, Ri，表示你每次操作会从哪个区间内随机地选画纸。
输出格式
一行，一个小数，表示答案，四舍五入精确到小数点后3位。
样例输入1
2 3 1
1 2点数、、
样例输出1
2.000
概率DP
dp[k][i][j] 表示操作了k次，第i张画纸改成颜色j的概率
不改转移到 dp[k+1][i][j]
改转移到 dp[k+1][i][j*h%c]
这是n^4
优化：
相同颜色的纸改的结果的概率相同，而且开始都是1
所以i那一维可以压去
即 dp[k][j] 表示一张纸操作了k次，变成颜色j的概率
转移同上
最后的答案=Σ dp[cnt[i]][j] cnt[i]表示i位置被操作了多少次
n^3代码
#include<cstdio>
#include<iostream> using namespace std; double dp[][]; int cnt[],col[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
int n,c,k;
read(n); read(c); read(k);
int mx=; int l,r;
while(k--)
{
read(l); read(r);
for(int i=l;i<=r;i++) cnt[i]++,mx=max(mx,cnt[i]);
}
dp[][]=;
for(int h=;h<mx;h++)
{
for(int j=;j<c;j++)
{
for(int g=;g<c;g++)
dp[h+][j*g%c]+=dp[h][j]/(c*2.0);
dp[h+][j]+=dp[h][j]/2.0;
}
}
double ans=;
for(int i=;i<=n;i++)
for(int j=;j<c;j++)
ans+=dp[cnt[i]][j]*j;
printf("%.3lf",ans);
}
n^4代码
#include<cstdio>
#include<iostream> using namespace std; double dp[][][]; int cnt[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int n,c,k;
read(n); read(c); read(k);
for(int i=;i<=n;i++) dp[][i][]=;
cnt[]=n;
int l,r;
for(int h=;h<k;h++)
{
read(l); read(r);
for(int i=;i<l;i++)
for(int j=;j<c;j++)
dp[h+][i][j]=dp[h][i][j];
for(int i=l;i<=r;i++)
for(int j=;j<c;j++)
{
for(int g=;g<c;g++)
dp[h+][i][j*g%c]+=dp[h][i][j]/(c*2.0);
dp[h+][i][j]+=dp[h][i][j]/2.0;
}
for(int i=r+;i<=n;i++)
for(int j=;j<c;j++)
dp[h+][i][j]=dp[h][i][j];
}
double ans=;
for(int i=;i<=n;i++)
for(int j=;j<c;j++)
ans+=j*dp[k][i][j];
printf("%.3lf",ans);
}
3. 香子兰
题目描述
你承包了一片香子兰花田。现在到了收获的季节，你需要把种下的香子兰全部收获起来，到花店卖掉并取得新的种子，再向田里播种下一季的香子兰。
你的花田一共由n-2片花田组成，编号从1到n-2。算上你的家和花店，一共有n个地点，其中你的家编号为0，花店编号为n-1。即，家、花田、花店都属于地点，且它们都有一个唯一的0~n-1的编号。有m条双向道路连接这些地点。保证所有地点间都是直接或间接连通的。
你需要从家里出发，经过所有的花田进行收获，再到达花店，再从花店出发经过所有花田进行播种，最后重新回到家中。当你经过一片花田的时候，你可以选择收获、播种或者什么事都不做，也就是说你经过一片未收割的花田时可以不立即收割它，播种亦然。然而，播种必须发生在你完成了所有收获并到花店交货之后。在完成最后一个花田的收获后，你必须在到达花店后才能开始播种。也就是说，在你没有收获完所有花田并到花店交货前，即使你已经经过了花店，你也不能进行播种。（啰嗦了这么多但愿讲明白了）
然而还有一个问题。在收割完花朵后，花田会变得光秃秃的，此时土地里的水分会迅速蒸发。考虑到这个问题，更早被收割的花田也理应更早地被播种。具体来说，你必须保证前个被收割的花田也是前个被播种的，其中符号表示向下取整。你不需要保证这些花田收割和播种的顺序完全一致，而只需要保证前名的集合不变即可。
现在，你需要求出完成上述一系列动作走过的最短路程。
输入格式
第一行包含两个整数n, m，表示地点总数和道路条数；
接下来m行，每行包含3个整数xi, yi, zi，表示有一条连接编号为xi和yi 的地点，长为zi的道路。
输出格式
一行，包含一个整数，表示最短路程。
样例输入
4 4
0 1 1
1 2 2
2 3 1
1 3 1
样例输出
10
样例解释
从0出发，先走到1收获（距离1），再走到2收获（距离2），再走到3交货（距离1），再走到1播种（距离1），再走到2播种（距离2），再走到1什么都不干（距离2），再走到0（距离1）。总距离为10。前个被收获和播种的花田集合是{1号花田}。
数据范围
对于30%的数据，有n≤8；
另有10%的数据，有m=n-1，且对1≤i≤m，保证xi=i-1，yi=i；
另有20%的数据，有m=n-1，且每个花田至多只与另外两个花田有道路相连；
对于100%的数据，有n≤20，m≤400，0≤xi, yi≤n-1，xi≠yi，0≤zi≤10000。
状压DP
f[i][j] 表示从家到点i，经过了状态为j的点集
g[i][j] 表示从花店到点i，经过了状态为j的点集
j只包括n-2个花田
Floyd预处理任意两点间的最短距离dis
f[i][j|(1<<k-2)]=min（f[i][j]+dis[i][k]）
k-2 是因为代码中家从1开始编号
枚举所有含(n-2)/2个花田的状态A，剩余的花田为B
如果是收获
枚举A中最后一个收获的花田j，枚举B中第一个收获的花田k
收获的最短路径= min(f[j][i]+g[k][S^i]+dis[j][k])
如果是播种
枚举A中最后一个播种的花田j，枚举B中第一个播种的花田k
播种的最短路径= min(g[j][i]+f[k][S^i]+dis[j][k])
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 21
#define M 401 int dis[N][N]; int f[N][],g[N][]; int bit[N],cnt[]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int cal(int s)
{
int sum=;
while(s) sum+=(s&),s>>=;
return sum;
} int main()
{
freopen("vanilla.in","r",stdin);
freopen("vanilla.out","w",stdout);
int n,m;
read(n); read(m);
int u,v,w;
memset(dis,,sizeof(dis));
for(int i=;i<=n;++i) dis[i][i]=;
while(m--)
{
read(u); read(v); read(w);
++u; ++v;
dis[u][v]=min(dis[u][v],w);
dis[v][u]=min(dis[v][u],w);
}
if(n==) { printf("%d",(dis[][]+dis[][])*); return ; }
for(int k=;k<=n;++k)
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
bit[]=;
for(int i=;i<=n;++i) bit[i]=bit[i-]<<;
int S=bit[n-]-;
for(int i=;i<=S;++i) cnt[i]=cal(i);
int half=n->>;
memset(f,,sizeof(f));
for(int i=;i<n;++i) f[i][bit[i-]]=dis[][i];
for(int i=;i<S;++i)
if(cnt[i]<=half)
{
for(int j=;j<n;++j)
if(f[j][i]<1e9)
for(int k=;k<n;++k)
f[k][i|bit[k-]]=min(f[k][i|bit[k-]],f[j][i]+dis[j][k]); }
memset(g,,sizeof(g));
for(int i=;i<n;++i) g[i][bit[i-]]=dis[n][i];
for(int i=;i<S;++i)
if(cnt[i]<=n--half)
{
for(int j=;j<n;++j)
if(g[j][i]<1e9)
for(int k=;k<n;++k)
g[k][i|bit[k-]]=min(g[k][i|bit[k-]],g[j][i]+dis[j][k]);
}
int x,ans=2e9;
for(int i=;i<S-;++i)
if(cnt[i]==half)
{
x=2e9;
for(int j=;j<n;++j)
if(i&bit[j-])
for(int k=;k<n;++k)
if(!(i&bit[k-]))
x=min(x,f[j][i]+g[k][S^i]+dis[j][k]);
for(int j=;j<n;++j)
if((i&bit[j-]))
for(int k=;k<n;++k)
if(!(i&bit[k-]))
ans=min(ans,x+g[j][i]+f[k][S^i]+dis[j][k]);
}
cout<<ans;
}
中间30分暴力
讨论哪些边走4遍，哪些边走3遍
#include<cstdio>
#include<iostream> using namespace std; int n,m; struct node
{
int u,v,w;
}e[]; int ru[]; namespace solve1
{
void work()
{
int ans=;
for(int i=;i<m;i++) ans+=e[i].w*;
ans+=e[m].w*; ans+=e[].w*;
cout<<ans;
}
} namespace solve2
{
int sum=;
bool f0=false,fn=false; void work()
{
if(ru[]==) f0=true;
if(ru[n-]==) fn=true;
for(int i=;i<=m;i++)
{
if(!e[i].u || !e[i].v)
{
if(f0) sum+=e[i].w*;
else sum+=e[i].w*;
}
else if(e[i].u==n- || e[i].v==n-)
{
if(fn)
{
if(e[i].v && e[i].u) sum+=e[i].w*;
}
else sum+=e[i].w*;
}
else sum+=e[i].w*;
}
cout<<sum;
}
} int main()
{
freopen("vanilla.in","r",stdin);
freopen("vanilla.out","w",stdout);
scanf("%d%d",&n,&m);
bool flag1=true,flag2=true;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
if(e[i].u!=i- || e[i].v!=i) flag1=false;
ru[e[i].u]++; ru[e[i].v]++;
if(e[i].u> && e[i].u<n && ru[e[i].u]>) flag2=false;
if(e[i].v> && e[i].v<n && ru[e[i].v]>) flag2=false;
}
if(flag1) { solve1::work(); return ; }
if(flag2) { solve2::work(); return ; }
else
{
int sum=;
for(int i=;i<=m;i++) sum+=e[i].w;
cout<<sum*;
}
}