20161027模拟赛解题报告
By shenben
T1
数学题
模拟即可。
注意开long long
T2
技巧题
图片为本题第一张图。（无奈，图传不上来）
首先第一问图中的“Y 字形”的数量，这么简单，在此不细讲。
详见代码
O（n）累加一下就好了
主要说说第二问怎么搞
预处理 每个点分别与其他那些点相连 权值为第1,2,3大（若没有2，3大，就忽略）。记录一下权值与对应的点的标号。目的是方便下面的判断。
枚举入度>=3的点，即点B（有多个）
再枚举点B相连的D点（不是点A,C）。
Step1：
若<B,D>为D外连边的第1大(权值)，sum=D外连边的第2大(权值)
否则sum=D外连边的第1大(权值)
Step2:
若<B,D>为B外连边的第1大(权值)，sum（累加）+=B外连边的第2大(权值)+ B外连边的第3大(权值)
若<B,D>为B外连边的第2大(权值)，sum（累加）+=B外连边的第1大(权值)+ B外连边的第3大(权值)
若<B,D>为B外连边的第3大(权值)，sum（累加）+=B外连边的第1大(权值)+ B外连边的第2大(权值)
Step3：
对于每种答案取一下大。maxn=max(maxn,sum);
Step4：
最后输出。
注意windows与linux
T3
空间题
第一次 骗了30分
实在是不会啊。
So 就无可奉告了
本次测试在window环境下评测的
T1代码（100分）：
#include<cstdio> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int N=1e5+10; inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } ll T,a,b,c,d,A,B,C,D,zd,zx,tmp,ansf,ansm; int main(){ freopen("tile.in","r",stdin); freopen("tile.out","w",stdout); T=read(); while(T--){ a=read();b=read(); c=read();d=read(); A=a*d;B=b*d; C=c*b;D=b*d; zd=__gcd(A,C); zx=A/zd*C; tmp=__gcd(zx,B); ansf=zx/tmp; ansm=B/tmp; if(ansm==1) printf("%I64d ",ansf); else printf("%I64d/%I64d ",ansf,ansm); } return 0; }
T2代码（100分）：
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10; inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } struct node{ ll v,w,next; }e[N<<1]; ll n,tot,ans,in[N],head[N]; ll maxn; void add(ll x,ll y,ll z){ e[++tot].v=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot; } void bfs(ll x){ ll t=in[x]-1; ll C=t*(t-1)/2; for(ll i=head[x],t;i;i=e[i].next) if(in[e[i].v]>1) ans+=C*(in[e[i].v]-1); } struct data{ pair<ll,ll>own[4]; }B[N]; void first_deal(ll x,ll y,ll z){ if(z>B[x].own[1].second){ B[x].own[3]=B[x].own[2]; B[x].own[2]=B[x].own[1]; B[x].own[1]=make_pair(y,z); } else if(z>B[x].own[2].second){ B[x].own[3]=B[x].own[2]; B[x].own[2]=make_pair(y,z); } else{ B[x].own[3]=make_pair(y,z); } } int main(){ freopen("question.in","r",stdin); freopen("question.out","w",stdout); n=read(); for(ll i=1,x,y,z;i<n;i++){ x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z); in[x]++;in[y]++; first_deal(x,y,z); first_deal(y,x,z); } for(ll i=1;i<=n;i++) if(in[i]>2) bfs(i); for(ll i=1;i<=n;i++){ if(in[i]>2){ for(ll j=head[i],sum;j;j=e[j].next){ if(in[e[j].v]>1){ sum=0; if(B[e[j].v].own[1].first!=i) sum=B[e[j].v].own[1].second; else sum=B[e[j].v].own[2].second; if(B[i].own[1].first!=e[j].v&&B[i].own[2].first!=e[j].v) sum+=e[j].w+B[i].own[1].second+B[i].own[2].second; else if(B[i].own[1].first!=e[j].v&&B[i].own[3].first!=e[j].v) sum+=e[j].w+B[i].own[1].second+B[i].own[3].second; else sum+=e[j].w+B[i].own[2].second+B[i].own[3].second; maxn=max(maxn,sum); } } } } printf("%I64d %I64d",ans,maxn); return 0; }
T3代码（30分）：
#include<cstdio> #include<cstdlib> #include<queue> #include<algorithm> //#include<ctime> using namespace std; const int N=22; inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } struct node{ int x,y,z,step; node(int x=0,int y=0,int z=0,int step=0):x(x),y(y),z(z),step(step){} }; const int dx[]={0,0,0,0,1,-1}; const int dy[]={0,0,1,-1,0,0}; const int dz[]={1,-1,0,0,0,0}; short mp[N][N][N]; bool vis[N][N][N]; int m,X,Y,Z,x1,y1,z1,x2,y2,z2; bool inside(int x,int y,int z){ if(x>0&&x<=X&&y>0&&y<=Y&&z>0&&z<=Z) return 1; return 0; } bool special_judge(int x,int y,int z){ int t;bool f1=0,f2=0,f3=0,f4=0,f5=0,f6=0; t=inside(x-1,y,z); if(t){ if(mp[x-1][y][z]==255) f1=1; } else f1=1; t=inside(x+1,y,z); if(t){ if(mp[x+1][y][z]==255) f2=1; } else f2=1; t=inside(x,y-1,z); if(t){ if(mp[x][y-1][z]==255) f3=1; } else f3=1; t=inside(x,y+1,z); if(t){ if(mp[x][y+1][z]==255) f4=1; } else f4=1; t=inside(x,y,z-1); if(t){ if(mp[x][y][z-1]==255) f5=1; } else f5=1; t=inside(x,y,z+1); if(t){ if(mp[x][y][z+1]==255) f6=1; } else f6=1; return f1&f2&f2&f3&f4&f5&f6; } int tot; int work(){ queue<node>q; q.push(node(x1,y1,z1,0)); while(!q.empty()){ tot++; node h=q.front();q.pop(); for(int i=0,s,nx,ny,nz;i<6;i++){ nx=h.x+dx[i]; ny=h.y+dy[i]; nz=h.z+dz[i]; if(!vis[nx][ny][nz]&&inside(nx,ny,nz)&&mp[nx][ny][nz]!=255){ vis[nx][ny][nz]=1; s=h.step+1; q.push(node(nx,ny,nz,s)); if(nx==x2&&ny==y2&&nz==z2) return s; } } } } int Clac,tmp; char ch1,ch2; int main(){ freopen("plumber.in","r",stdin); freopen("plumber.out","w",stdout); //srand(time(0)); X=read();Y=read();Z=read(); m=read(); x1=read();y1=read();z1=read();ch1=getchar(); x2=read();y2=read();z2=read();ch2=getchar(); mp[x1][y1][z1]=1; mp[x2][y2][z2]=2; for(int i=1,x,y,z;i<=m;i++){ x=read();y=read();z=read(); mp[x][y][z]=255; } if(special_judge(x1,y1,z1)){puts("impossible");return 0;} if(special_judge(x2,y2,z2)){puts("impossible");return 0;} Clac=work(); tmp=Clac/3; if(tmp>20) {puts("impossible");return 0;} printf("%d",tmp); return 0; }