noip模拟【20171102】_C

概述T1 [数学] 期望得分：100 先通分，求出分子的最小公倍数，再讨论跟共同的分母B*D的关系即可。【code】 #include<bits/stdc++.h>using namespace std;#define ll long long #define File "tile"inline void file(){ freopen(File".in","r",stdi T1

[数学]

期望得分：100

先通分，求出分子的最小公倍数，再讨论跟共同的分母B*D的关系即可。

【code】

#include<bits/stdc++.h>using namespace std;#define ll long long #define file "tile"inline voID file(){    freopen(file".in","r",stdin);    freopen(file".out","w",stdout);} inline int read(){    int x = 0,f = 1; char ch = getchar();    while(ch < ‘0‘ || ch > ‘9‘){if(ch==‘-‘)f = -1; ch = getchar();}    while(ch >= ‘0‘ && ch <= ‘9‘){x = (x<<1) + (x<<3) + ch-‘0‘; ch = getchar();}    return x*f;}//const int mxn = ;int T,A,B,C,D;ll gcd(ll x,ll y){    return y ? gcd(y,x%y) : x;} int main(){    file();    T = read();    while(T--){        A = read(),B = read(),C = read(),D = read();        ll t1 = A*D,t2 = C*B;        ll gcd_ = gcd(t1,t2);            ll mul_ = t1*t2;            ll lcm_ = mul_/gcd_;        ll tmp = gcd(lcm_,B*D);        if(tmp == B*D) printf("%lld\n",lcm_/(B*D));        else printf("%lld/%lld\n",lcm_/tmp,(B*D)/tmp);    }    return 0;}

VIEw Code

[？]

枚举所有边，判断是否满足它连接的两个点度数分别为2和3，计数。

还要记录度数为3的点与之相连非当前枚举到的边的最长长度+当前枚举到的边的长度+与度数为2的点相连的最长的边。

为了求最长长度，需要记录每个点的连边中前三大的。

【code】

#include<bits/stdc++.h>using namespace std;#define ll long long #define file "question"inline voID file(){    freopen(file".in",f = 1; char ch = getchar();    while(ch < ‘0‘ || ch > ‘9‘){if(ch==‘-‘)f = -1; ch = getchar();}    while(ch >= ‘0‘ && ch <= ‘9‘){x = (x<<1) + (x<<3) + ch-‘0‘; ch = getchar();}    return x*f;}const int mxn = 2e5 + 5;int n;struct edge{    int x,y,v;}e[mxn<<1];int deg[mxn];int mx1[mxn],mx2[mxn],mx3[mxn];int to1[mxn],to2[mxn];inline voID prewor(int x,int y,int z){    if(z >= mx1[x]){        mx3[x] = mx2[x],mx2[x] = mx1[x],mx1[x] = z;        to2[x] = to1[x],to1[x] = y;    }else if(z >= mx2[x]){        mx3[x] = mx2[x],mx2[x] = z;        to2[x] = y;        }else if(z > mx3[x]) mx3[x] = z;}ll cnt,mx;inline voID wor(int x,int z){    if(deg[x] >= 3 && deg[y] >= 2)        cnt += (deg[x]-1)*(deg[x]-2)*(deg[y]-1)/2;    if(y==to1[x] && mx3[x]){        if(x==to1[y])             if(mx2[y]) mx = max(mx,mx2[y] + z + mx2[x] + mx3[x]);        //该边为最长边         else if(mx1[y]) mx = max(mx,mx2[x] + mx3[x] + mx1[y] + z);     }else if(y==to2[x] && mx3[x]){        if(x==to1[y])            if(mx2[y]) mx = max(mx,mx1[x] + z + mx3[x] + mx2[y]);        else if(mx1[y]) mx = max(mx,mx1[y] + z + mx1[x] + mx3[x]);    }else {    }}int main(){//    file();    n = read();    for(int i = 1;i < n; ++i){        int x = read(),y = read(),v = read();        e[i] = (edge){x,v};        deg[x]++,deg[y]++;            prewor(x,v),prewor(y,x,v);    }    for(int i = 1;i < n; ++i){            }    printf("%lld\n%lld\n",cnt,mx);    return 0;}/*71 3 22 3 13 5 15 4 24 6 35 7 3*/

VIEw Code

[搜索+剪枝]

每个水管可以看做是2+2（分别朝不同的方向）或者3+1。

直接搜索+剪枝。

根据当前点到终点的曼哈顿距离，可以求出这个点到终点的最少步数。

如果当前点加上到达终点的最小步数，还是没有ans优，直接剪枝。

注意代码细节处理。

【code】

#include<bits/stdc++.h>using namespace std;#define ll long long #define file "plumber"inline voID file(){    freopen(file".in",stdout);}inline int read(){    int x = 0,f = 1; char ch = getchar();    while(ch < ‘0‘ || ch > ‘9‘){if(ch==‘-‘)f = -1; ch = getchar();}    while(ch >= ‘0‘ && ch <= ‘9‘){x = (x<<1) + (x<<3) + ch-‘0‘; ch = getchar();}    return x*f; }const int mxn = 25;int X,Y,Z,m;int st_x,st_y,st_z,st_k;int ed_x,ed_y,ed_z,ed_k;char st_tp,ed_tp;bool v[mxn][mxn][mxn],vis[mxn][mxn][mxn];const int dx[6] = {1,-1,0,0};const int dy[6] = {0,1,0};const int dz[6] = {0,-1};inline bool ok(int x,int z){    return x>0&&x<=X&&y>0&&y<=Y&&z>0&&z<=Z&&!v[x][y][z]&&!vis[x][y][z];}int ans = 13;voID dfs(int x,int z,int d,int cnt){    int dis = (abs(ed_x-x)+abs(ed_y-y)+abs(ed_z-z))/4;    if(dis + cnt >= ans) return;    if(x==ed_x && y==ed_y && z==ed_z){        if(d==ed_k) ans = cnt;        return;    }        if(ok(x+dx[d],y+dy[d],z+dz[d]) && ok(x+dx[d]*2,y+dy[d]*2,z+dz[d]*2)){                vis[x+dx[d]][y+dy[d]][z+dz[d]] = vis[x+dx[d]*2][y+dy[d]*2][z+dz[d]*2] = 1;        int x_ = x+dx[d]*2,y_ = y+dy[d]*2,z_ = z+dz[d]*2;                    for(int i = 0;i < 6; ++i){//2+2            if((i/2) != (d/2)){                if(ok(x_+dx[i],y_+dy[i],z_+dz[i]) && ok(x_+dx[i]*2,y_+dy[i]*2,z_+dz[i]*2)){                    vis[x_+dx[i]][y_+dy[i]][z_+dz[i]] = vis[x_+dx[i]*2][y_+dy[i]*2][z_+dz[i]*2] = 1;                    dfs(x_+dx[i]*2,z_+dz[i]*2,i,cnt+1);                    vis[x_+dx[i]][y_+dy[i]][z_+dz[i]] = vis[x_+dx[i]*2][y_+dy[i]*2][z_+dz[i]*2] = 0;                        }            }        }                if(ok(x+dx[d]*3,y+dy[d]*3,z+dz[d]*3)){                    vis[x+dx[d]*3][y+dy[d]*3][z+dz[d]*3] = 1;                    int _x = x+dx[d]*3,_y = y+dy[d]*3,_z = z+dz[d]*3;            for(int i = 0;i < 6; ++i){                if((i/2) != (d/2)){                    if(ok(_x+dx[i],_y+dy[i],_z+dz[i])){                        vis[_x+dx[i]][_y+dy[i]][_z+dz[i]] = 1;                        dfs(_x+dx[i],_z+dz[i],cnt+1);                        vis[_x+dx[i]][_y+dy[i]][_z+dz[i]] = 0;                    }                }            }                        vis[x+dx[d]*3][y+dy[d]*3][z+dz[d]*3] = 0;        }                        vis[x+dx[d]][y+dy[d]][z+dz[d]] = vis[x+dx[d]*2][y+dy[d]*2][z+dz[d]*2] = 0;            }     }int main(){    file();    X = read(),Y = read(),Z = read(),m = read();    st_x = read(),st_y = read(),st_z = read(),st_tp = getchar();    if(st_tp==‘x‘) st_k = (st_x==1)?0:1;    if(st_tp==‘y‘) st_k = (st_y==1)?2:3;    if(st_tp==‘z‘) st_k = (st_z==1)?4:5;        ed_x = read(),ed_y = read(),ed_z = read(),ed_tp = getchar();    if(ed_tp==‘x‘) ed_k = (ed_x==1)?1:0;    if(ed_tp==‘y‘) ed_k = (ed_y==1)?3:2;    if(ed_tp==‘z‘) ed_k = (ed_z==1)?5:4;        for(int i = 1;i <= m; ++i){        int x = read(),z = read();        v[x][y][z] = 1;    }            dfs(st_x-dx[st_k],st_y-dy[st_k],st_z-dz[st_k],st_k,0);//    printf("%d\n",ans);    ans < 13 ? printf("%d\n",ans) : puts("impossible");        return 0;}/*5 4 3 13 1 1 z1 4 3 x2 3 3*/