Codeforces Round #677 (Div. 3) 題解
Codeforces Round #677 (Div. 3) 題解
A. Boring Apartments
題目
題解
簡單簽到題，直接數，小於這個數的\(+10\)。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 2e5 + 10;
int a[maxn];
void solve(){
ll ans = 0;
int n; cin >> n;
int cnt = 0, x = n, c10 = 1;
while(x){
x /= 10;
cnt++;
c10 *= 10;
}
c10 /= 10;
int t = n / c10;
// cout << c10 << " " << cnt << " " << t << endl;
ans += (t - 1) * 10;
cout << ans + (1 + cnt) * cnt / 2 << endl;
}
int main(){
IOS; int t; cin >> t;
while(t--){
solve();
}
return 0;
}
B. Yet Another Bookshelf(思維)
題目
題意
讓書架上所有的書\((a[i] = 1)\) 相鄰。每次可以將相鄰的一段\(1\)(可以是\(1\)個)向左移或者右移。
題解
開始模擬了一遍，但沒過，太菜了。
思路：統計每個\(1\)與其最近\(1\)之間有多少個\(0\)。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 100 + 10;
int a[maxn], b[maxn];
void solve1(){
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> num;
for (int i = 0; i < n; i++){
if(a[i] == 0) num.push_back(0);
if(a[i] == 1) {if(i == 0 || a[i-1] == 0) num.push_back(1); }
// cout << i << " " << a[i] << " " << num.size() << endl;
}
// for (auto x : num) cout << x << " "; cout << endl;
n = num.size();
int cnt = 0, ans = 0x3f3f3f3f;
for (int i = 0; i < n; i++) cnt += (num[i] & 1);
if(cnt == 1){
cout << 0 << endl; return;
}
for (int l = 0; l + cnt - 1 < n; l++){
int r = l + cnt - 1;
int res = 0;
vector<int> c0, c1;
for (int i = 0; i < n; i++){
if(i >= l && i <= r) {if(num[i] == 0) c0.push_back(i);}
else {
if(num[i] == 1) c1.push_back(i);
}
}
for (int i = 0; i < c1.size(); i++){
res += abs(c1[i] - c0[i]);
}
// cout << l << " " << r << " " << res << endl;
ans = min(ans, res);
}
cout << ans << endl;
}
void solve(){
int n; cin >> n;
vector<int> num;
for (int i = 0; i < n; i++){
cin >> a[i];
if(a[i]) num.push_back(i);
}
cout << num.back() - num[0] - 1 - num.size() + 2 << endl;
}
int main(){
IOS; int t; cin >> t;
while(t--){
solve();
}
return 0;
}
C. Dominant Piranha（思維）
題目
題意
水族館裡的食人魚每次可以吃掉比它小的相鄰的食人魚。求最後的那一個食人魚最開始的位置。
題解
找最大值。(比B簡單？)
程式碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 3e5 + 10;
int a[maxn];
void solve(){
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
vector<pi> num;
for (int i = 1; i <= n; i++){
if(i > 1 && a[i] > a[i-1]) num.push_back({a[i], i});
if(i < n && a[i] > a[i+1]) num.push_back({a[i], i});
}
int pos = -1;
for (auto p : num){
if(pos == -1) pos = p.second;
else if(a[pos] < p.first) pos = p.second;
}
cout << (pos == -1 ? -1 : pos) << endl;
}
int main(){
IOS; int t; cin >> t;
while(t--){
solve();
}
return 0;
}
D. Districts Connection(簡單構造)
題目
題意
要在\(n\)個點建建立\(n-1\) 條邊，使\(n\)個點聯通（直接或者間接）。但是相同的幫派間不可以建邊，構造出一個可行的方案。
題解
-
當只有\(1\)個幫派的時候，連接\(n\)個頂點是不可能的。
-
我們可以選一個幫派，記為\(gang1\)，將其中一個點和其他的每一個點連接。這樣保證這個點與不是幫派\(gang1\)的所有的點聯通。 再將幫派\(gang1\)的其他點與不在幫派\(gang1\)的任一點連接，這樣構造保證所有的點互相聯通。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 5e3 + 10;
int a[maxn];
void solve(){
int n; cin >> n;
unordered_map<int, vector<int>> p;
for (int i = 0; i < n; i++){
cin >> a[i];
p[a[i]].push_back(i + 1);
}
if((int)p[a[0]].size() == n){
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
int pos = a[0];
for(auto x : p){
if(x.first == pos) continue;
for(auto c : x.second) cout << 1 << " " << c << endl;
}
for(auto x : p){
if(x.first != a[0]){
pos = x.first;
break;
}
}
vector<int> t = p[a[0]];
int q = p[pos][0];
// cout << "at: " << pos << " " << t.size() << " " << q << endl;
for (int i = 1; i < (int)t.size(); i++){
cout << q << " " << t[i] << endl;
}
}
int main(){
IOS; int t; cin >> t;
while(t--){
solve();
}
return 0;
}
E. Two Round Dances
題目
題解
( 在oeis網上輸入\(12164510040883200\) 就明白了。)
圓排列。
程式碼
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int maxn = 3e5 + 10;
int a[maxn], dp[maxn];
void solve(){
int n; cin >> n;
if(n <= 4){
cout << (n == 2 ? 1 : 3) << endl;
return;
}
n /= 2; n-=1;
ll ans = 1;
for (int i = 1; i <= 2 * n + 1; i++) if(i != n + 1) ans *= i;
cout << ans << endl;
}
int main(){
IOS; int t = 1;
while(t--){
solve();
}
return 0;
}
