BUPT2014新生暑假个人排位赛06

本文主要是介绍BUPT2014新生暑假个人排位赛06，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

BOJ 447 修路

用prim计算最小生成树，用并查集计算连通块

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------const int MAXN=100010;
const int V=10010;struct Node
{int x,y,s;
}e[200010];int fa[V];
int vis[V];
int n,m;int find_fa(int x)
{if(fa[x]==x)return x;elsereturn fa[x]=find_fa(fa[x]);
}void Merge(int x,int y)
{fa[x]=y;
}int main()
{while(read(n)&&read(m)){int ans=0;for(int i=1;i<=n;i++)fa[i]=i,vis[i]=0;for(int i=0;i<m;i++){read(e[i].x);read(e[i].y);read(e[i].s);if(e[i].s==0)Merge(find_fa(e[i].x),find_fa(e[i].y));}for(int i=1;i<=n;i++)vis[find_fa(i)]=1;for(int i=1;i<=n;i++)if(vis[i])ans++;printf("%d\n",ans-1);}return 0;
}

BOJ 445 高兴

带权的欧拉环路问题，商旅问题

用状态压缩DP

我的姿势比较奇葩，0表示的是用过的，1表示没有用过的

当然，如果你将它理解成从终点加到起点也是可以的

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define INF 0x3f3f3f3fusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------int e[22][22],dp[1<<19][20];
int n;int find(int s,int c)
{if(dp[s][c]>0)return dp[s][c];if(s==(1<<n)-1)return 0;int res=-INF;for(int i=0;i<n;i++){if(s&(1<<i))continue;res=max(res,find(s|(1<<i),i)+e[c][i]);}return dp[s][c]=res;
}int main()
{while(read(n)){int maxx=-INF;memset(dp,0,sizeof(dp));for(int i=0;i<n;i++)for(int j=0;j<n;j++)read(e[i][j]);for(int i=0;i<n;i++){int temp=find(1<<i,i);if(temp>maxx){maxx=temp;}}
//        cout<<po<<endl;printf("%d\n",maxx);}return 0;
}

BOJ 449 排序

变态题，根据出现数字种类的多少进行决策，如果出现数字的种类数大于1000则选择用计数排序

必须仔细计算复杂度

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3f
#define ll long longusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n) {if(n < 0) {putchar('-');n = -n;}int len = 0,data[20];while(n) {data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}//-----------------------------------------------------------------------int a[10001]={0},vis[10001]={0};int main()
{int n,i;while(read(n)){int temp;int tot=0;for(i=0;i<n;i++){read(temp);if(!a[temp])vis[tot++]=temp;a[temp]++;}if(tot<=1000){sort(vis,vis+tot);write(vis[0]);a[vis[0]]--;for(i=0;i<tot;i++)while(a[vis[i]]>0){putchar(' ');write(vis[i]);a[vis[i]]--;}}else{for(i=0;i<10001;i++)if(a[i]){write(i);a[i]--;break;}for(;i<10001;i++)while(a[i]>0){putchar(' ');write(i);a[i]--;}}putchar('\n');}return 0;
}

BOJ 444 爱好和平

树形DP

ans[ i ] = max { max { son[ u ] , n - son[ i ] }，其中 u 为 i 的子节点，son[ i ] 记录的是 i 的所有子孙加上它自己， ans[ i ]表示将 i 点炸毁后LUKE联盟的最高威胁

我们在建树的时候建立的是双向边，因此在进行DP处理的时候，要注意，u 点不可以是 i 点的父亲节点

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3fusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------const int MAXN=100010;struct Node
{int to,next;
}e[2*MAXN];int head[MAXN],tot=0;
int n,m,minn=INF,dp[MAXN],ans;
int pre[MAXN];
bool vis[MAXN];void add(int x,int y)
{e[tot].to=y;e[tot].next=head[x];head[x]=tot++;e[tot].to=x;e[tot].next=head[y];head[y]=tot++;
}int dfs(int x)
{int maxx=0;vis[x]=1;for(int i=head[x];i!=-1;i=e[i].next){int y=e[i].to;if(vis[y])continue;pre[y]=x;int temp=dfs(y);maxx+=temp;}return dp[x]=maxx+1;
}int main()
{while(read(n)&&read(m)){int u,v,po;minn=INF;memset(head,-1,sizeof(head));memset(dp,0,sizeof(dp));memset(vis,0,sizeof(vis));tot=0;for(int i=0;i<m;i++){read(u),read(v);add(u,v);}dfs(1);for(int i=1;i<=n;i++){ans=n-dp[i];for(int j=head[i];j!=-1;j=e[j].next){int y=e[j].to;if(pre[i]!=y)ans=max(ans,dp[y]);}if(minn>ans){minn=ans;po=i;}}printf("%d\n",po);}return 0;
}

BOJ 450 萌学妹的手机 BNUOJ 34962

原题出自BNUOJ34962

首先，按照将坐标轴改变，新坐标轴间夹角为60 °， nx = x - y / tan(60°) ny = y / sin(60°)

根据原直角坐标（也可以直接根据斜角坐标）枚举周围基站的坐标，答案可以简化为，里起点和终点最近的两个基站之间的最小穿越次数。

然后找出规律，如下图（60°的那个为y轴），将y较小的点挪到（0,0）点，则起点的 y 坐标一定是正的，

当 x>=0 的时候为 x + y （斜角坐标的曼哈顿距离）

当 x<0 的时候，max ( - x , y )，如下图所示。这里的 x ，y 为斜角坐标下的坐标

ps::下面的代码没有将点固定到原点，但是是同样的决策，根据对称性可以得出同样的结论。

<pre name="code" class="cpp">#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
const int maxn = 3 * 1e5;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
//---------------------------const double eps = 1e-6;
const double INF = 1e50;
const double PI=acos(-1.0);
double L;struct Point
{int x,y;
};double dist(double a,double b,double x,double y)
{return (a-x)*(a-x)+(b-y)*(b-y);
}Point locate(double x,double y)
{int a=floor(x-y/sqrt(3)+eps);int b=floor(y/sin(PI/3)+eps);Point res;double mm=INF;for(int i=a-1;i<=a+1;i++){for(int j=b-1;j<=b+1;j++){double a,b;b=(double)j*sin(PI/3);a=(double)i+(double)b/sqrt(3.0);if(mm>dist(a,b,x,y)){mm=dist(a,b,x,y);res.x=i;res.y=j;}}}return res;
}int main()
{int T;read(T);while(T--){scanf("%lf",&L);L*=sqrt(3); double x,y;scanf("%lf %lf",&x,&y);Point s=locate(x/L,y/L);scanf("%lf %lf",&x,&y);Point e=locate(x/L,y/L);
//        printf("%d %d ==\n",s.x,s.y);
//        printf("%d %d ==\n",e.x,e.y);if((s.x<e.x&&s.y<e.y)||(s.x>e.x&&s.y>e.y))printf("%d\n",abs(s.x-e.x)+abs(s.y-e.y));elseprintf("%d\n",max(abs(s.x-e.x),abs(s.y-e.y)));}return 0;
}

这篇关于BUPT2014新生暑假个人排位赛06的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！