AtCoder Beginner Contest 416(ABCDE)

A - Vacation Validation

翻译：

给你一个长度为 N 的字符串 S，它由 o 和 x 以及整数 L 和 R 组成。

请判断 S 中从第 L 个字符到第 R 个字符的所有字符是否都是 o。

思路：

（模拟）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n,l,r;cin>>n>>l>>r;string s;cin>>s;s = ' '+s;int f = 1;for (int i=l;i<=r;i++){f &= (s[i]=='o');}cout<<(f ? "Yes" : "No")<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;
//    cin>>t;while (t--) solve();return 0;
}

B - 1D Akari

翻译：

给你一个由 . 和 # 组成的字符串 S。

在满足以下所有条件的所有字符串 T 中，找出一个具有最多 o 的字符串。

T 的长度等于 S 的长度。
T 由 .、# 或 o 组成。
当且仅当 $S_i$ = # 时， $T_i$ = #。
如果 $T_i=T_j=o(i<j)$ ，那么在 $T_{i+1},...,T_{j-1}$ 中至少存在一个 #。

思路：

这题S与T的#位置是一一对应的。遍历S,遍历i到#时将右边T[i+1]=o，最后将T自左到右第一个非#变为o。（模拟，贪心）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){string s;cin>>s;bool flag = 0;int n = s.size();char res[n];for (int i=0;i<n;i++){res[i] = s[i];if (s[i]=='#'){if (!flag){for (int j=i-1;j>=0;j--){if (res[j]=='.'){flag = 1;res[j] = 'o';break;}}}if (flag){for (i+=1;i<n;i++){if (s[i]=='.') {res[i] = 'o';break;}else{res[i] = s[i];}}}}}flag = 1;for (int i=0;i<n;i++) flag&=(res[i]=='.');if (flag) res[0] = 'o';for (int i=0;i<n;i++) cout<<res[i];
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;
//    cin>>t;while (t--) solve();return 0;
}

C - Concat (X-th)

翻译：

        给你 N 个字符串 $S_1,...,S_N$ 。

        对于长度为 K 的序列 $(A_1,...,A_K)$ ，其中所有元素都在 1 到 N 之间（包括 N），定义字符串 $f(A_1,...,A_K)$ 为 $S_{A_1}+S_{A_2}+...+S_{A_K}$ 。

        将 $N^K$ 个序列的所有 $f(A_1,...,A_K)$ 按词序排序，找出第 X 个最小的字符串。

思路：

求出所有情况放入数组，排序数组得到第 X 个最小的字符串。（dfs）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n,k,x,m,cnt=0;cin>>n>>k>>x;m = (int)pow(n,k);string s[n+1];vector<string> res(m);vector<int> a(k);for (int i=1;i<=n;i++) cin>>s[i];function<void(int)> dfs = [&](int step) {if (step == k) {string tmp = "";for (int i = 0; i < k; i++) tmp += s[a[i]];res[cnt++] = tmp;return;}for (int i = 1; i <= n; i++) {a[step] = i;dfs(step + 1);}};dfs(0);sort(res.begin(),res.end());cout<<res[x-1]<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;
//    cin>>t;while (t--) solve();return 0;
}

D - Match, Mod, Minimize 2

翻译：

        给你长度为 N 的序列 $A=(A_1,A_2,...,A_N)$ 和 $B=(B_1,B_2,...,B_N)$ ，它们由非负整数和正整数 M 组成。

        当你可以自由地重新排列 A 的元素时，求 $\sum\limits_{i=1}^N((A_i+B_i)\mod M)$ 的最小值。

        已给出 T 个测试案例，请为每个案例找出答案。

思路：

先对A与B取模，要让和最小那么A，B中和大于M的对数应该最大，以此减去更多的M。对A,B升序排序再使用双指针配对。（数学，双指针）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll n,m,res=0;cin>>n>>m;vector<ll> a(n),b(n);for (ll &i:a){cin>>i;i=i%m;res+=i;}for (ll &i:b){cin>>i;i=i%m;res+=i;}sort(a.begin(),a.end());sort(b.begin(),b.end());for (int i=0,j=n-1;i<n;i++){if (a[i]+b[j]>=m){res-=m;j--;}}cout<<res<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;cin>>t;while (t--) solve();return 0;
}

E - Development

翻译：

        AtCoder 国家有 N 个城市（编号从1 到 N）、M 条公路和 K 个机场。

        第 i 条公路双向连接城市 $A_i$ 和 $B_i$ ，需要 $C_i$ 小时的路程。 $D_1,...,D_K$ 城市都有机场，在有机场的城市之间旅行需要 T 小时。

        按顺序处理 Q 个查询。每个查询都是以下三种类型之一：

1 x y t：建造一条在 t 小时内双向连接 x 和 y 两个城市的道路。
2 x: 一个机场建造在城市x。
3：设 f(x,y)为从城市 x 出发，利用公路和机场（如果可以到达）到达城市 y 所需的最小小时数，0（如果无法到达）。求 $\sum^N_{x=1}\sum^N_{y=1}f(x,y)$ 。

思路：

要理解floyd的最外层是作为中间点存在，在执行查询1时，将中间点固定为x,y；执行查询2时，先确定一个超级原点0，将所有x连在0上，此时中间点为x,0，此时两个机场间的距离会变为2t为了平衡将查询1的时间乘2即可；（floyd）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
ll n,m,k,t;
vector<vector<ll>> maze(510,vector<ll>(510,INF));
void solve(){cin>>n>>m;for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) maze[i][j] = INF;for (int i=0;i<=n;i++) maze[i][i] = 0;for (ll a,b,c,i=0;i<m;i++){cin>>a>>b>>c;maze[a][b] = maze[b][a] = min(maze[a][b],2*c);}cin>>k>>t;for (ll a,i=0;i<k;i++){cin>>a;maze[a][0] = maze[0][a] = t;}for (ll kk=0;kk<=n;kk++){for (ll i=0;i<=n;i++){for (ll j=0;j<=n;j++){maze[i][j] = min(maze[i][j],maze[i][kk]+maze[kk][j]);}}}ll q,flag,a,b,c;cin>>q;while (q--){cin>>flag;if (flag==1){cin>>a>>b>>c;maze[a][b] = maze[b][a] = min(maze[a][b],2*c);for (ll i=0;i<=n;i++){for (ll j=0;j<=n;j++){maze[i][j] = min({maze[i][j],maze[i][a]+maze[b][j]+maze[a][b],maze[i][b]+maze[a][j]+maze[b][a]});}}}else if (flag==2){cin>>a;maze[a][0] = maze[0][a] = t;for (ll i=0;i<=n;i++){for (ll j=0;j<=n;j++){maze[i][j] = min({maze[i][j],maze[i][a]+maze[a][0]+maze[0][j],maze[i][0]+maze[0][a]+maze[a][j]});}}}else{ll res = 0;for (ll i=1;i<=n;i++){for (ll j=1;j<=n;j++){if (maze[i][j]!=INF){res+=maze[i][j];}}}cout<<(res>>1)<<'\n';}}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t=1;while (t--) solve();return 0;
}

之后补题会在此增加题解。

思路标准：思路+算法概要+时空复杂度。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/diannao/93570.shtml
繁体地址，请注明出处：http://hk.pswp.cn/diannao/93570.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！