训练记录Codeforces Round 987 (Div. 2)
4/6
前四题都是简单思维题
A. Penchick and Modern Monument
这个题目最贪心的做法是找到出现最多的数，保留种数字不变，其他按照题目要求改大小就行
// Problem: A. Penchick and Modern Monument
// Contest: Codeforces - Codeforces Round 987 (Div. 2)
// URL: https://codeforces.com/contest/2031/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//by codeforcer ——
// ____ _ _ _ _ _ _ ____ _
// / ___|| | | || | | || | | | |___ \ | |
//| | | |_| || |_| || |_| | __) | | |
//| | | _ || _ || _ | |__ < | |
//| |___ | | | || | | || | | | ___) | | |
// \____||_| |_||_| |_||_| |_| |____ / |_|
#include<bits/stdc++.h>
using namespace std;
typedef int E;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;
typedef tuple<LL, LL, LL> PLLL;
typedef pair<long long, long long> PLL;
typedef unsigned long long ULL;
#define endl '\n'
#define vec vector
#define pb push_back
#define pob pop_back
#define fir first
#define sec second
#define maxINT 0x3f3f3f3f
#define maxLL 0x3f3f3f3f3f3f3f3fLL
#define umap unordered_map
#define uset unordered_set
#define maxheap priority_queue<E, vector<E>, less<E>>
#define minheap priority_queue<E, vector<E>, greater<E>>
#define prvec(a) \
for (int i = 0; i < (a).size(); i++) { \
cout << (a)[i] << " "; \
} \
cout << endl;
#define debugvec(a, i, n) \
cout << #a << ": "; \
for (int k = (i); k <= (n); k++) { \
cout << (a)[k] << " "; \
} \
cout << endl;
LL gcd(LL a, LL b) { return (b) ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) { x = 1, y = 0; return a; }LL gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;}
LL qmi(LL a, LL b, LL mod) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}
const int N = 200010;
void solve() {
int n;
cin>>n;
vec<int> a(n + 1);
map<int,int> st;
int mark = 0,cnt = 0;
for(int i = 0;i < n;i ++)
{
cin>>a[i];
st[a[i]] ++;
if(cnt < st[a[i]])
{
mark = a[i];
cnt = st[a[i]];
}
}
cout<<n - cnt<<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;cin >> t;for (int i = 0; i < t; i++)
solve();
return 0;
}
B. Penchick and Satay Sticks
考虑如果满足答案的序列，经过移动后会变成怎样的序列，比如1 2 3 4 5 ，通过题目给的移动方式，有1 3 2 4 5，经过手动模拟可以发现，一个数不能远离应该在的位置超过2，例如3 1 2 4 5是不可能通过1 2 3 4 5移动过来的，所以记录每个a[i]对于应该在的位置多原即可
// Problem: B. Penchick and Satay Sticks
// Contest: Codeforces - Codeforces Round 987 (Div. 2)
// URL: https://codeforces.com/contest/2031/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)
//by codeforcer ——
// ____ _ _ _ _ _ _ ____ _
// / ___|| | | || | | || | | | |___ \ | |
//| | | |_| || |_| || |_| | __) | | |
//| | | _ || _ || _ | |__ < | |
//| |___ | | | || | | || | | | ___) | | |
// \____||_| |_||_| |_||_| |_| |____ / |_|
#include<bits/stdc++.h>
using namespace std;
typedef int E;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;
typedef tuple<LL, LL, LL> PLLL;
typedef pair<long long, long long> PLL;
typedef unsigned long long ULL;
#define endl '\n'
#define vec vector
#define pb push_back
#define pob pop_back
#define fir first
#define sec second
#define maxINT 0x3f3f3f3f
#define maxLL 0x3f3f3f3f3f3f3f3fLL
#define umap unordered_map
#define uset unordered_set
#define maxheap priority_queue<E, vector<E>, less<E>>
#define minheap priority_queue<E, vector<E>, greater<E>>
#define prvec(a) \
for (int i = 0; i < (a).size(); i++) { \
cout << (a)[i] << " "; \
} \
cout << endl;
#define debugvec(a, i, n) \
cout << #a << ": "; \
for (int k = (i); k <= (n); k++) { \
cout << (a)[k] << " "; \
} \
cout << endl;
LL gcd(LL a, LL b) { return (b) ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) { x = 1, y = 0; return a; }LL gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;}
LL qmi(LL a, LL b, LL mod) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}
const int N = 200010;
void solve() {
int n;
cin>>n;
vec<int> a(n + 1);
for(int i = 1;i <= n;i ++)cin>>a[i];
for(int i = 1;i <= n;i ++)
{
if(abs(a[i] - i) > 1)
{
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;cin >> t;for (int i = 0; i < t; i++)
solve();
return 0;
}
C. Penchick and BBQ Buns
这个题目按给的数字n分成两种情况：
- 偶数 一定有对应方式比如n = 6，序列可以是1 1 2 2 3 3，依次类推
- 奇数 有特定的方式能满足这个情况，我们需要让三个位置是相同的一个数，这里以1举例，放1的位置分别记作a b c，根据题目条件有 b - a = \(x^2\) ，c - b = \(y^2\)，\(x^2\) + \(y^2\) = \(c^2\) 看着是不是像勾股数，那么最小的勾股数就是3 4 5了，9 + 16 = 25，
按照题目先把1放在对应位置b[1] = 1,b[10] = 1,b[26] = 1，然后可以发现，1到10这个位置可以放偶数个数，但是10到26只能放奇数个数，看似一定不能满足题目条件，
我们可以通过一个数放在10到26之间一个数放在26右边来让10到26之间放下偶数个数，但是得满足放在10到26之间的数和到大于26的这个数的位置相差是完全平方数，考虑最小的方法，首先1肯定不行，中间隔着一个a[26]，那就只有4了，也就是放一个数在a[23] 一个放在a[27]，剩余没放数的位置就是偶数个了。所以最小满足条件的奇数是27，更大的奇数就只需要在27这个序列后面加两个数就行
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
int a[N] = {0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 1, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 13, 12, 12, 1, 13};
// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27
void solve()
{
int n;cin >> n;
if(n % 2)
{
if(n >= 27)
{
for(int i = 1;i <= 27; ++ i)cout << a[i] << ' ';
for(int i = 28;i <= n; ++ i)cout << i / 2 << ' ';
cout << '\n';
}else{
cout << -1 << '\n';
}
}else
{
for(int i = 1;i <= n; ++ i)cout << (i + 1) / 2 << ' ';
cout << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. Penchick and Desert Rabbit
我们可以发现当从1到i的前缀最大值大于i + 1到n的后缀最小值就可以让i到达i + 1，也就是\(ans_i\) = \(ans_{i + 1}\)，反之， \(ans_i\) 只能等于前缀最大值
// Problem: D. Penchick and Desert Rabbit
// Contest: Codeforces - Codeforces Round 987 (Div. 2)
// URL: https://codeforces.com/contest/2031/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//by codeforcer ——
// ____ _ _ _ _ _ _ ____ _
// / ___|| | | || | | || | | | |___ \ | |
//| | | |_| || |_| || |_| | __) | | |
//| | | _ || _ || _ | |__ < | |
//| |___ | | | || | | || | | | ___) | | |
// \____||_| |_||_| |_||_| |_| |____ / |_|
#include<bits/stdc++.h>
using namespace std;
typedef int E;
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;
typedef tuple<LL, LL, LL> PLLL;
typedef pair<long long, long long> PLL;
typedef unsigned long long ULL;
#define endl '\n'
#define vec vector
#define pb push_back
#define pob pop_back
#define fir first
#define sec second
#define maxINT 0x3f3f3f3f
#define maxLL 0x3f3f3f3f3f3f3f3fLL
#define umap unordered_map
#define uset unordered_set
#define maxheap priority_queue<E, vector<E>, less<E>>
#define minheap priority_queue<E, vector<E>, greater<E>>
#define prvec(a) \
for (int i = 0; i < (a).size(); i++) { \
cout << (a)[i] << " "; \
} \
cout << endl;
#define debugvec(a, i, n) \
cout << #a << ": "; \
for (int k = (i); k <= (n); k++) { \
cout << (a)[k] << " "; \
} \
cout << endl;
LL gcd(LL a, LL b) { return (b) ? gcd(b, a % b) : a; }
LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) { x = 1, y = 0; return a; }LL gcd = exgcd(b, a % b, y, x);y -= a / b * x;return gcd;}
LL qmi(LL a, LL b, LL mod) {LL res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;}
const int N = 200010;
void solve() {
int n;
cin>>n;
vector<int> a(n + 1);
vector<int> pre(n + 4),ed(n + 3,1e9 + 10);
for(int i = 1;i <= n;i ++)
{
cin>>a[i];
pre[i] = max(pre[i - 1],a[i]);
}
ed[n] = a[n];
for(int i = n-1;i >= 1;i --)
{
ed[i] = min(ed[i + 1],a[i]);
}
vec<int> ans(n + 2);
for(int i = n;i >= 1;i--)
{
if(pre[i] > ed[i+1])
{
ans[i] = ans[i + 1];
}else
{
ans[i] = pre[i];
}
}
for(int i = 1;i <= n;i ++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;cin >> t;for (int i = 0; i < t; i++)
solve();
return 0;
}