AtCoder Beginner Contest 361
目录
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 ;
}原文地址：https://blog.csdn.net/qq_73575281/article/details/140307337
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！