ICPC铜牌题目总结

第46届ICPC亚洲区域赛（昆明）

D: Divisions

题解：我们产生的序列可以是单调非递减的序列，所以我们只需要凑出其中的非递增序列的数量即可，长度为n的相同序列，可以产生2^n-1种可能性，所以我们每次都凑出尽可能多的可能性，也就是让我们的n尽可能大，然后不断地减去2^n-1直到k为0即可，我们便可知道每次的相同数字组成的序列长度了。

#include <iostream>
#include <stack>
#include <cmath>
typedef long long LL;
using namespace std;
LL quick(int n,int m) {LL res=1;while(m>0) {if(m&1)res*=n;n*=n;m>>=1;}return res;
}
int main() {int k;cin>>k;if(k==0) {//特殊情况 cout<<"6"<<endl;cout<<"1 4 5 1 4 3"<<'\n';} else if(k==1) {//特殊情况 cout<<"5"<<endl;cout<<"1 4 5 1 4"<<'\n';} else {k--;//排除空集的1种情况 int sum=0;//序列总长度为sum stack<int>st;while(k>0) {//k为所需要的序列数量 k++;//提前+1,因为每次只能凑2^n-1种情况,所以提前加1 以便后面算2^n尽可能地大 int t=log(k)/log(2);//算2^n的n为多少 st.push(t);//n即为序列长度 sum+=t;k-=quick(2,t);//种类会减少2^n-1种,因为前面已经+1了,所以这里就不减少了 }cout<<sum<<endl;bool f=0;int j=1;while(st.size()) {int t=st.top();st.pop();for(int i=0; i<t; i++) {if(f)cout<<" ";else f=1;cout<<j;}j++;}}
}

第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳）

H: Line Graph Matching

题意：

给定一个无向图，每次取其中临接的两条边，使得最后结果最大，问结果最大为多少？

题解

并查集

每次取最大的那条边，看两边端点属于哪个集合，分情况讨论，若两个端点处于一个集合之中，则查看集合中有无多余的边和次边配对，若无，则当前边为集合多余边，否则，当前边和集合中多余边结合，然后集合中没有多余边。若两个端点分别位于不同集合，若两个集合都无多余边，则次边成为两个集合合称为一个集合之后的多余边，否则，此边和两个集合中较大的多余边结合，然后，两个集合结合为一个集合后的集合的多余边权重为两个集合中较小边的权重，最后输出结果即可。

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
//#define long long int
using namespace std;
typedef long long ll;//总共2e5条边 每条边1e9,总和极限2e14,所以需要long long 
const int N=1e5+10;
struct node{//存储边的信息 int a,b,w;bool operator<(const node &e)const {return w>e.w;}
}edge[2*N];int fa[N];//存储根节点 int find(int x){//并查集 查询根节点 if(fa[x]!=x){fa[x]=find(fa[x]);}return fa[x];
}
int f[N];//存储当前集合中 是否有多余的边,且多余边的权重为多少 
signed main(){int n,m;scanf("%d%d",&n,&m);ll ans=0;for(int i=0;i<n+1;i++)fa[i]=i;//初始根节点皆为自身 for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);edge[i]={u,v,w};}sort(edge,edge+m);//按照边的权重 从大到小排序 for(int i=0;i<m;i++){int a=edge[i].a;int b=edge[i].b;int w=edge[i].w;a=find(a);//查询端点的根节点 b=find(b);//查询端点的根节点 if(a==b){//若两端点处于一个结合中,只需要查看当前集合中是否有多余的边即可 if(!f[a])f[a]=w;//若无多余的边,则当前边为集合中多余的边 else{//若有多余的边 ans+=w+f[a];//则答案+=当前边权重和 集合多余边的权重 f[a]=0;//集合没有多余边了 }}else{//两端点处于不同集合之中 if(!f[a]&&!f[b])f[a]=f[b]=w;//两集合 都无多余的边 else{//若两集合中 有多余的边 ans+=w+max(f[a],f[b]);//则当前边 和两集合中 的较大边结合 f[a]=f[b]=min(f[a],f[b]); //两集合 合并为一集合后, 该集合的多余边权重为两集合的较小边权重 }fa[a]=b;//并查集合并 }}cout<<ans<<'\n';//输出结果 记得 long long 
}

J: Luggage Lock

题意：给定两个序列a,b，问从a序列到b序列最少需要多少步，一步可以将连续的n位数+1或者-1。

题解：bfs，可以知道从a序列到 b序列每一位都需要走多少步，然后会得到需要走的位数，然后我们只需要知道将这个位数变为0000 至少需要走多少步即可。然后我们可以从0000 倒推所有情况，总共10000种情况，直接预处理即可。

本体难点：

1、想不到 bfs，每一步总共只有20种情况

2、想不到只需要考虑需要走多少步即可，不需要看数字本身

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int a[10][4]= {//一个方向 走一步 总共只有10种情况{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1},{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,1,1,0},{0,1,1,1},{1,1,1,1}
};
int g[2]={1,-1};//正负两个方向
int res[10000]; 
int main() {queue<int>que;memset(res,0x3f3f3f,sizeof(res));//初始化que.push(0);int n[4];res[0]=0;while(que.size()) {int t=que.front();int w=t;que.pop();for(int i=0;i<4;i++){int e=t%10;t/=10;n[i]=e;}for(int i=0;i<2;i++){for(int j=0;j<10;j++){int sum=0;//记录走完这一步 会变成什么数for(int q=0;q<4;q++){sum*=10;sum+=(n[q]+g[i]*a[j][q]+10)%10;}if(res[sum]>res[w]+1){//之前没有走到过这个数res[sum]=res[w]+1;que.push(sum);}}}}int t;scanf("%d",&t);for(int i=0;i<t;i++){int b1,b2;scanf("%d%d",&b1,&b2);int sum=0;for(int i=0;i<4;i++){sum*=10;int t1=b1%10;int t2=b2%10;b1/=10;b2/=10;sum+=(t1-t2+10)%10;}printf("%d\n",res[sum]);}
}

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）

B-Mine Sweeper II_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海） (nowcoder.com)

题意：给定两个矩阵，矩阵可以计算数字和，需要把第二个矩阵的数字和变为和第一个矩阵的数字和相等的矩阵，而且只要不超过n*m/2次操作即可，通过找规律可得矩阵的数字和和他逆矩阵的数字和相等，所以在n*m/2的操作范围内，选正反那个区别小的转化成为他就行。

#include <iostream>
using namespace std;
int a[1005][1005],b[1005][1005];
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){getchar();for(int j=1;j<=m;j++){char ch=getchar();if(ch=='X')a[i][j]=1;else a[i][j]=0;}}int sum=0;for(int i=1;i<=n;i++){getchar();for(int j=1;j<=m;j++){char ch=getchar();if(ch=='X')b[i][j]=1;else b[i][j]=0;if(a[i][j]!=b[i][j])sum++;}}if(sum>n*m/2){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]==b[i][j])b[i][j]=1-b[i][j];}}else {for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i][j]!=b[i][j])b[i][j]=1-b[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(b[i][j])printf("X");else printf(".");}printf("\n");}
}

D: Walker

题解：分类讨论+二分

1、某个人速度巨快一个人走完全程

2、两个人互相朝对方的所在的方向走，走到底

3、两个人起点所在的区间每人走一部分，每个人的部分另一个人不能走，采用二分的方式

#include <iostream>
using namespace std;
double l,p1,v1,p2,v2;
const double eps=1e-8;
double c1(){double n1=min((p1+l)/v1,(2*l-p1)/v1);double n2=min((p2+l)/v2,(2*l-p2)/v2);return min(n1,n2);
}
double c2(){if(p1-p2>eps){swap(p1,p2);swap(v1,v2);}double n1=(l-p1)/v1;double n2=p2/v2;return max(n1,n2);
}
double mid;
double c4(double p,double v,double mid){return (min(p,mid-p)+mid)/v;
}
double res;
void c3(){double left=p1;double right=p2;while(right-left>eps){mid=(left+right)/2;double maxleft=c4(p1,v1,mid);double maxright=c4(l-p2,v2,l-mid);res=min(res,max(maxleft,maxright));if(maxleft<maxright){left=mid;}else{right=mid;}}
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%lf%lf%lf%lf%lf",&l,&p1,&v1,&p2,&v2);res=c1();res=min(res,c2());c3();printf("%.10lf\n",res); }
}

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）

F: Fireworks

题意：一个人会做烟火，但是做的不熟练，每做一个需要n分钟，做的完美的概率为p，检查之前所做的所有的烟花质量的时间为m，但是一旦做的里面有一个是完美的，则就可以下班休息了，问最小的休息时间的期望。

题解：概率论+三分

假设已经做了k个烟花了，则检查+制作所花费的时间为（k*n+m)，可以休息的概率为 $1-(1-p)^k)$

则期望为 $k*n+m)/(1-(1-p)^k)$ ，只需要求期望的最大值即可，可以发现，该期望值随着k的增大先增大，后减小，所以通过三分k即可获得答案

#include <iostream>
#include <cmath>
using namespace std;typedef long double ld;
int n,m;
ld p;
long double f(int k){//求期望return ((ld)k*n+m)/((ld)1.0-pow(1.0-p,k));
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d%Lf",&n,&m,&p);//longdouble 输入输出要使用Lfint l=0;int r=0x3f3f3f3f;p*=(1e-4);ld res=(ld)0x3f3f3f3f3f3f3f;while(l<r){//三分模板int lm=l+(r-l)/3;int rm=r-(r-l)/3;ld l1=f(lm),l2=f(rm);res=min(res,min(l1,l2));//要使得期望越小越好if(l1<l2)r=rm-1;else l=lm+1;}printf("%.10Lf\n",res);}
}