微软编程之美复赛的解题报告Word文件下载.docx
- 文档编号:7921508
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:12
- 大小:18.58KB
微软编程之美复赛的解题报告Word文件下载.docx
《微软编程之美复赛的解题报告Word文件下载.docx》由会员分享,可在线阅读,更多相关《微软编程之美复赛的解题报告Word文件下载.docx(12页珍藏版)》请在冰点文库上搜索。
N≤100
样例解释
3*3种交换方法都行。
样例输入
1
2
33
样例输出
Case1:
9
这是一个这场比赛最水的题目,开始竟然wa了三次,因为输出格式,ACM题目做习惯了Case后面喜欢加#号,太不值了,就是一道简单的错排题,可以自行谷歌错排公式。
AC代码(提供的AC代码是大数据小数据都可以通过的):
//bywangruixing
#include<
iostream>
cstdio>
algorithm>
#defineP1000000007
#defineLLlonglong
#defineN160
usingnamespacestd;
LLf[N];
intmain()
{
intcnt,n,x;
scanf("
%d"
&
cnt);
LLans;
f[1]=0;
f[2]=1;
for(inti=3;
i<
N;
i++)
f[i]=(f[i-1]+f[i-2])*(i-1)%P;
for(intrun=1;
run<
=cnt;
run++)
n);
ans=1;
for(inti=1;
=n;
x);
ans=ans*x%P;
}
printf("
Case%d:
"
run);
cout<
<
ans*f[n]%P<
endl;
return0;
第二题是一个投影题目,没有AC,但是思路是有的,就是一个投影,投影后的样子是一个矩形加一个半圆,注意是半圆,不是椭圆,一开始,想错了,没敢下手做,考虑几种情况,然后考虑两圆相交时的情况,扫一遍得到两个点,算出角度,然后长度就好求了,这个几何比较好解,但是当时没有做。
第三题:
最大值
4000ms
给定一棵点和边都带有正权的树,用distance(i,j)表示点i到点j的树上距离(即两点之间的最短路长度),用weight(i)表示点i的点权。
请求解在所有的i,j中,min{weight(i),weight(j)}*distance(i,j)的最大值。
第一行一个整数N,表示有N个节点。
第二行N个整数,分别表示weight(i)(1≤weight(i)≤10^9)。
接下来N-1行,每行3个整数a,b,c(1≤a,b≤N,1≤c≤104),表示节点a和b之间有一条权值为c的边。
”,x表示是第几组数据,然后输出最大值即可。
1≤N≤1000
1≤N≤105
只有i=1,j=2的可选方案,distance(1,2)=1,min{weight(i),weight(j)}=1,所以最大值为1。
12
121
1
这个题目很厉害,我学会了一种方法,以前不知道的,就是转移树的重心。
AC代码:
map>
set>
queue>
ctime>
cmath>
string>
vector>
cstdlib>
cstring>
#defineall(a)a.begin(),a.end()
#defineclr(a)memset(a,0,sizeof(a))
#definefill(a,b)memset(a,b,sizeof(a))
#definepbpush_back
#definempmake_pair
typedeflonglongLL;
typedefvector<
int>
VI;
typedefpair<
int,int>
PII;
pair<
>
VII;
constdoubleeps=1e-8;
constdoublepi=acos(-1.0);
constintMod=1e9+7;
constintN=100000+10;
:
iteratorIT;
structSt{
intl,r,mm;
}st[N<
2];
vector<
vec[N];
intM[N];
intw[N],dis[N],IS[N],nid[N];
booldel[N];
intsize[N],opt[N];
VIall,nn;
longlongans=0;
voidcalc(intu,intfa){
inti,v;
size[u]=1;
opt[u]=0;
all.pb(u);
for(inti=0;
vec[u].size();
i++){
if((v=vec[u][i].first)==fa||del[v])continue;
calc(v,u);
size[u]+=size[v];
opt[u]=max(opt[u],size[v]);
intGetHeart(intu){
inti,minOpt=1e9,heart,v;
all.clear();
calc(u,-1);
for(i=0;
all.size();
v=all[i];
opt[v]=max(opt[v],size[u]-size[v]);
if(opt[v]<
minOpt){
minOpt=opt[v];
heart=v;
returnheart;
boolcmp(inta,intb){
returnw[a]>
w[b];
intmark;
voidgo(intu,intpar){
nid[u]=mark;
for(ITe=vec[u].begin();
e!
=vec[u].end();
++e){
if(!
del[e->
first]&
&
e->
first!
=par){
dis[e->
first]=dis[u]+e->
second,go(e->
first,u);
voidbuild(intl,intr,inti){
st[i].l=l;
st[i].r=r;
st[i].mm=-1;
if(l==r)return;
intmid=(l+r)>
>
1;
build(l,mid,i<
1);
build(mid+1,r,i<
1|1);
intask(intl,intr,inti){
if(l==st[i].l&
r==st[i].r){
returnst[i].mm;
intmid=(st[i].l+st[i].r)>
if(r<
=mid)returnask(l,r,i<
elseif(l>
mid)returnask(l,r,i<
elsereturnmax(ask(l,mid,i<
1),ask(mid+1,r,i<
1|1));
voidmake(intx,intval,inti){
if(st[i].l==st[i].r){
st[i].mm=max(st[i].mm,val);
return;
if(x<
=mid)make(x,val,i<
elsemake(x,val,i<
st[i].mm=max(st[i<
1].mm,st[i<
1|1].mm);
voiddfs(intu,intpar){
u=GetHeart(u);
dis[u]=0;
intSZ=all.size(),idx=0,i;
sort(all.begin(),all.end(),cmp);
mark=++idx;
par!
=e->
first){
first]=dis[u]+e->
nid[u]=0;
build(0,idx,1);
++i){
make(nid[all[i]],dis[all[i]],1);
intres;
if(nid[all[i]]!
=0)res=ask(0,nid[all[i]]-1,1);
elseres=-1;
=idx)res=max(res,ask(nid[all[i]]+1,idx,1));
if(res!
=-1)ans=max(ans,(longlong)w[all[i]]*(res+dis[all[i]]));
del[u]=1;
=par)
dfs(e->
first,u);
intmain(){
inttt,n,i,a,b,c,cal=0;
tt);
while(tt--){
for(i=1;
w[i]);
vec[i].clear();
n;
%d%d%d"
a,&
b,&
c);
vec[a].pb(mp(b,c));
vec[b].pb(mp(a,c));
ans=0;
memset(del,0,sizeof(del));
dfs(1,-1);
++cal);
ans<
endl;
第四题:
广场建设
在某个外星城市中,有n个居民点,他们分布在三维空间里,坐标分别为(xi,yi,zi)(i=1,2,…,n)。
现在我们要建一个广场,广场是通过原点的一个平面Ax+By+Cz=0(A,B,C不全为0)。
请你帮忙确定这个广场的倾斜方向,使得n个居民点到广场的距离的平方和最小。
输入包含多组测试数据,第一行是一个整数T(1≤T≤10),表示测试数据组数。
对于每组测试数据:
第一行是一个整数n,表示点的个数。
(1≤n≤100)
接下来的n行,每行三个整数x,y,z,之间用一个空格分隔。
对每组测试数据输出一行,格式为“Casex:
ABC”。
x表示测试数据组数,A,B,C的意义见题目描述,输出任意一组解即可。
如果根据答案所计算的距离平方和与最优解的绝对误差或相对误差在10-6以内,则认为答案正确。
1≤n≤2
1≤n≤100
001
010
000
1.00.00.0
Case2:
这个题目真是让我长见识了,用到了随机算法,一般很少用,先随机算法得到一些点,通过二分来缩小范围,当缩小到一个精度范围内,就得出所要的点,这个方法比较巧妙,在计算几何里面经常会用到。
这个题当时只A掉了小数据,没有想到这种方法,现在分享给大家。
constdoubleeps=1e-10;
intsgn(doublex){return(x<
-eps)?
-1:
(x>
eps);
}
structPT{
doublex,y,z;
PT(){}
PT(doublex,doubley,doublez):
x(x),y(y),z(z){}
};
PTpt[105];
doubleX2,Y2,Z2,XY,XZ,YZ;
doublework(PTpp)
doublea=pp.x,a2=a*a;
doubleb=pp.y,b2=b*b;
doublec=pp.z,c2=c*c;
doublenow=a2*X2+b2*Y2+c2*Z2+a*b*XY*2+a*c*XZ*2+b*c*YZ*2;
returnnow/(a2+b2+c2);
freopen("
1.txt"
"
r"
stdin);
intcas,T;
srand(330598937);
for(cas=scanf("
&
T);
cas<
=T;
cas++)
intn;
scanf("
X2=Y2=Z2=XY=XZ=YZ=0;
for(inti=0;
i<
i++)
%lf%lf%lf"
x,&
y,&
z);
X2+=x*x;
Y2+=y*y;
Z2+=z*z;
XY+=x*y;
XZ+=x*z;
YZ+=y*z;
PTbt(1,1,1);
doubleans=work(bt);
for(doublestep=1e6;
step>
eps;
step/=2)
=500;
i++)
doubleth1=rand();
doubleth2=rand();
PTp(bt.x+step*sin(th1),bt.y+step*cos(th1),bt.z+step*cos(th2));
doubletmp=work(p);
if(tmp<
ans)ans=tmp,bt=p;
cas);
%.8f%.8f%.8f\n"
bt.x,bt.y,bt.z);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 微软 编程 复赛 解题 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)