当前位置：首页 > news >正文

AtCoder Beginner Contest 361

news 来源：原创 2024/9/20 14:47:15

A - Insert

B - Intersection of Cuboids

C - Make Them Narrow

D - Go Stone Puzzle

E - Tree and Hamilton Path 2

F - x = a^b

A - Insert

我们按照题目意思直接模拟即可，不需要使用数组在第k位置的时候额外输出一个x即可

int t,n,m,k,x;
void solve(){cin>>n>>k>>x;for(int i=1;i<=n;i++){int t; cin>>t; cout << t << ' ';if(i==k) cout << x << ' ';}cout << endl;return ;
}

B - Intersection of Cuboids

求是不是有接触面积，如果有的话就是存在一个点在另一个立方体里面，否则就是没有，由于题目都是立方体，所以可以看每一个坐标是不是存在直接远离（不可能存在交点）即可

int x[5],y[5],z[5];void solve(){for(int i=1;i<=4;i++) cin>>x[i]>>y[i]>>z[i];if(x[1]>=x[4] or x[2]<=x[3] or y[1]>=y[4] or y[2]<=y[3] or z[1]>=z[4] or z[2]<=z[3]){cout << "No" << endl;}else{cout << "Yes" << endl;}return ;
}

C - Make Them Narrow

可以知道如果不删除当前最大值或者最小值的话贡献是0，所以可以优先排序，那么要么那就是删除最大值，要么就是删除最小值，枚举所有情况，删除前i个最大的数，就删除m-i个最小的数，注意0<=i<=m


void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);int ans = 2e9;for(int i=0;i<=m;i++){ans = min(ans,a[n-(m-i)]-a[i+1]);} cout << ans << endl;return ;
}

D - Go Stone Puzzle

明显的字符串交换，也就是bfs搜索找最优解，类似八数码，用一个unorderde_map<string,int> 判断是否出现过即可

int t,n,m;void solve(){cin>>n;string a,b; cin>>a>>b;a+=' ',a+=' ';b+=' ',b+=' ';auto bfs = [&](){unordered_map<string,int> mp;mp[a]=0;queue<string> q;q.push(a);while(!q.empty()){auto t = q.front(); q.pop();if(t==b) return mp[b];string x = t;int t1;for(int i=0;i<n+2;i++) if(x[i]==' ') {t1=i; break;}for(int i=0;i<n+1;i++){if(t[i]!=' ' and t[i+1]!=' '){swap(x[i],x[t1]),swap(x[i+1],x[t1+1]);if(!mp.count(x)){mp[x]=mp[t]+1;q.push(x);}swap(x[i],x[t1]),swap(x[i+1],x[t1+1]);}}}return -1;};cout << bfs() << endl;return ;
}

E - Tree and Hamilton Path 2

从某一个点出发，到达所有点的最小值，可以画一个图找找性质，可以发现除了st-ed,即选定的出发点和最后到达的结束点之间的比权，其他所有的边权都两次，问题转化为求解，最短的树的最长直径，可以使用换根或者一次dfs即可，每次求出当前所在子树的两条最长路径，之和即是当前子树的最长直径，然后递归处理即可

LL res;
LL dfs(int u,int fa){LL d1=0,d2=0;for(auto&[v,w]:g[u]){if(v==fa) continue;LL d=dfs(v,u)+w;if(d>d1) d2=d1,d1=d;else if(d>d2) d2=d;}res = max(res,d1+d2);return d1;
}
void solve(){cin>>n;LL ans = 0;for(int i=1;i<n;i++){int a,b,c; cin>>a>>b>>c;g[a].push_back({b,c});g[b].push_back({a,c});ans += 2*c;}dfs(1,-1);ans -= res;cout << ans << endl;return ;
}

F - x = a^b

有个明显的思维就是直接枚举每一个次方，当时为2的时候有1e9个数(1e9^2==1e18)当然会超时，这个时候没有更好的做法，我们考虑不使用2次幂，直接从3次幂开始，则最多1e6个数，符合要求，同时对于2次幂当独计算，答案数量就是sqrtl(n)，当时有些数既是x的次幂又是y的次幂，所以要用set去重，同时注意不把2次幂的数放入set，最后直接加上即可

void solve(){LL n; cin>>n;set<LL> S;int cnt = 10;for(LL i=2;i<=1e6;i++){ // 底数 LL now = i*i*i;if(now>n) break;while(true){LL x = sqrtl(now);if(x*x!=now) S.insert(now);if(now>n/i) break;now *= i;if(now<0) break;}}LL ans = S.size()+sqrtl(n);cout << ans << endl;return ;
}