http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=358
The 2014 ACM-ICPC Asia Mudanjiang Regional Contest
136 – The 2014 ACM-ICPC Asia Mudanjiang Regional Contest
|
题意：给出一个树，找两个点建消防站，使离最近的消防站的距离最远的点的这个距离最小。点有20W个。
题解：这2个消防站肯定在树的直径上，二分这个距离d，分别把2个消防站放在与直径的2个端点距离d的位置。
20W个点，不碉的深搜会Segment Fault，我的深搜可是加了const &的碉深搜，才能过的。
听说的更碉的题解：在直径的中点把树切成两半，分别求直径中点，就得了。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define mf1(array) memset(array, -1, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
const double pi=acos(-1.0);
const double eps=1e-; const int maxn=;
const int maxm=*maxn; int n; struct Edge {
int v,next;
} e[maxm];
int en,head[maxn]; inline void add(const int &x,const int &y) {
e[en].v=y;
e[en].next=head[x];
head[x]=en++;
} int ans[]; int anode,bnode;
int len;
inline void dfs1(const int &x,const int &f,const int &step) {
if(step>len) {
len=step;
anode=x;
}
for(int i=head[x]; i!=-; i=e[i].next) {
if(e[i].v != f) dfs1(e[i].v , x , step+);
}
} bool flag;
int b[maxn],bn;
inline void dfs2(const int &x,const int &f) {
if(x==bnode) {
flag=;
b[bn++]=x;
return;
}
for(int i=head[x]; i!=-; i=e[i].next) {
if(e[i].v != f) {
dfs2(e[i].v , x);
if(flag) {
b[bn++]=x;
return;
}
}
}
} int _dis;
int u[maxn]; inline void dfs3(const int &x,const int &f,const int &step){
if(step>_dis) {
return;
}
u[x]=;
for(int i=head[x]; i!=-; i=e[i].next) {
if(e[i].v != f) dfs3(e[i].v , x , step+);
}
} inline bool ok(const int &dis){
int i;
int nodec=b[dis];
int noded=b[bn--dis];
len=;
_dis=dis;
memset(u,,sizeof(u));
dfs3(nodec,-,);
dfs3(noded,-,);
FOR(i,,n)if(!u[i])return ;
return ;
}
inline void farm() {
int i;
len=;
dfs1(,-,);
//printf("%d!\n",anode);
bnode=anode;
len=;
dfs1(bnode,-,);
//printf("%d!\n",anode);
flag=,bn=;
dfs2(anode,-);
// FOR(i,0,bn-1)printf("%d ,",b[i]);
// printf("(a=%d , b=%d)\n",anode,bnode); int an;
int l=,r=bn-,mid;
while(l<=r){
mid=(l+r)>>;
// printf("%d,%d,%d\n",l,mid,r);
if(ok(mid))r=mid-,an=mid;
else l=mid+;
}
ans[]=an;
ans[]=b[an];
ans[]=b[bn--an];
if(ans[]==ans[])ans[]=(ans[])%n+;
return;
} int main() {
//re;
int T;
int i,j,x,y;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
memset(head,-,sizeof(head));
en=;
REP(i,n-) {
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
farm();
printf("%d %d %d\n",ans[],ans[],ans[]);
}
return ;
}
题意：在棋盘上没有棋的地方随机放棋，直到每一列每一行都有棋，求步数的期望。
题解：DP。dp[i][j][k]表示已经有i行有棋、j列有棋、已经放了k个棋 这种情况的概率。
我们是6000ms险过，也许DP的方式不对？
代码：
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define REP(i,n) for(i=0;i<n;i++)
#define FOR(i,x,y) for(i=x;i<=y;i++)
#define mz(x) memset(x,0,sizeof(x))
#define re freopen("in.txt","r",stdin)
#define pb push_back
#define ll long long
#define maxn 50005
#define mod 1000000009 double dp[][][];
int n,m; double dfs(int x,int y,int z) {
if(x== || y== || z==)return dp[x][y][z]=0.0;
if(dp[x][y][z]>=-0.5)return dp[x][y][z];
dp[x][y][z]=dfs(x-,y,z-)*(n-x+)*y + dfs(x,y-,z-)*(m-y+)*x + dfs(x-,y-,z-)*(m-y+)*(n-x+);
if(x!=n || y!=m) dp[x][y][z]+= dfs(x,y,z-)*(x*y-z+);
dp[x][y][z]/=(double)(n*m-z+);
//printf("(%d,%d,%d) %lf\n",x,y,z,dp[x][y][z]);
return dp[x][y][z];
} double farm(int _n,int _m) {
int i,j,k;
n=_n,m=_m;
FOR(i,,n)FOR(j,,m)FOR(k,,n*m)dp[i][j][k]=-1.0;
dp[][][]=1.0;
FOR(i,,n)dp[i][][i]=dp[i-][][i-]*(n-i+)/(n*m-i+);
FOR(i,,m)dp[][i][i]=dp[][i-][i-]*(m-i+)/(n*m-i+);
double ans=0.0;
FOR(i,,n*m) {
ans+=dfs(n,m,i)*i;
//printf("%d %lf\n",i,dfs(n,m,i));
}
//printf("%.12lf\n",E);
return ans;
} int main() {
//re;
int T;
int n,m;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
printf("%.12lf\n",farm(n,m));
}
return ;
}
直接算，那啥是0的时候那个极限求完就是0。
代码：
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define re freopen("in.txt","r",stdin)
#define pb push_back
#define ll long long
#define maxn 50005
#define mod 1000000009
const double e=2.7182818284590452353602874;
int n;
int p[];
char s[]; double farm() {
double hx=0.0;
sort(p,p+n);
if(s[]=='n') {
for(int i=; i<n; i++) {
if(p[i]!=) hx-=(1.0*p[i]) * (log(1.0*p[i]));
}
hx-=log(0.01)*100.0;
return hx;
} else if( s[]=='d') {
for(int i=; i<n; i++) {
if(p[i]!=) hx-=(1.0*p[i]) * (log10(1.0*p[i]));
}
hx+=200.0;
return hx;
} else if(s[]=='b') {
for(int i=; i<n; i++) {
if(p[i]!=) hx-=(1.0*p[i]) * (log2(1.0*p[i]));
}
hx-=log2(0.01)*100.0;
return hx;
}
} int main() {
//re;
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%s",&n,s);
for(int i=; i<n; i++) {
scanf("%d",&p[i]);
}
printf("%.12lf\n",farm()/100.0);
}
return ;
}
