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
T2
[？]
枚举所有边，判断是否满足它连接的两个点度数分别为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","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 = 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 y,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,y,v};
deg[x]++,deg[y]++;
prewor(x,y,v),prewor(y,x,v);
}
for(int i = 1;i < n; ++i){
}
printf("%lld\n%lld\n",cnt,mx);
return 0;
}
/*
7
1 3 2
2 3 1
3 5 1
5 4 2
4 6 3
5 7 3
*/
View Code
T3
[搜索+剪枝]
每个水管可以看做是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","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 = 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,0,0};
const int dy[6] = {0,0,1,-1,0,0};
const int dz[6] = {0,0,0,0,1,-1};
inline bool ok(int x,int y,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 y,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,y_+dy[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],_y+dy[i],_z+dz[i],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(),y = 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 1
3 1 1 z
1 4 3 x
2 3 3
*/
View Code