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
英文地址，請注明出處：http://en.pswp.cn/diannao/93570.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！