Codeforces Round #752 (Div. 2)
A. Era
思路分析：
- 答案其實就是這個數減去它改變位置后的pos即可，
- 對于第一位如果不是1，那么它就要在前面插入\(a[1] - 1\)個數，來使得它能夠\(<= i\)，然后要注意的是，在你插入數之后，位于你剛剛插入的位置及其以后的下標都會增加，增加多少呢？其實累加起來就是\(ans\)，自己推一下就好了，
- 一開始直接想假了，每次都是拿后面那個數減去前面那個數累加，
代碼
#include <bits/stdc++.h>
using namespace std;
long long a[200];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
memset(a, 0, sizeof(a));
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
long long ans = 0;
long long tmp = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] > (tmp + i))
{
ans += (a[i] - tmp - i);
tmp = ans;
}
}
cout << ans << endl;
}
return 0;
}
B. XOR Specia-LIS-t
思路分析：
- 這一題我直接傻逼了（高估了題目難度），想啥按位去了，其實不需要，
- 一開始我直接想到的是如果\(n\)為偶數，那么我們直接把原陣列一個一個分開即可，這樣就有偶數個\(1\)相異或，得到的答案肯定就是\(0\)，
- 然后開始考慮奇數，如果我們能找到一對逆序數的話，我們就可以把那兩個數取出來作為一個整體，那么剩下的數就只有\(n - 2\)個了，也就可以構成\(n - 2\)個\(1\)（奇數個）,然后再加上剛剛那個逆序對的話，也就一共有\(n - 1\)個\(1\)，也就是偶數個\(1\)，異或得到\(0\)，
代碼
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int cnt;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
cnt = 0;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
if (n % 2 == 0)
{
cout << "YES" << endl;
}
else
{
int flag = 0;
for (int i = 1; i <= n; i++)
{
if (i > 1 && a[i] <= a[i - 1])
{
flag = 1;
}
}
if (flag)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}
return 0;
}
C. Di-visible Confusion
思路分析：
- 我們考慮任意一個數\(a_i\)，如果答案是YES的話，它必定會在\(1 - i\)位置間被洗掉，那么我們對于每一個數都去看一下它會不會在\(1 - i\)位置間被洗掉即可，
- 一開始沒用這種做法的原因是，演算法復雜度分析不出來，以為時間不太夠，只能說刷題太少了，哎，
代碼
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
bool ok = 1;
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
bool flag = 0;
for (int j = i + 1; j >= 2; j--)
{
if (a[i] % j)
{
flag = 1;
break;
}
}
ok &= flag;
}
cout << (ok == 1 ? "YES" : "NO") << endl;
}
return 0;
}
D. Moderate Modular Mode
思路分析：
-
我們先進行分類討論，如果\(x > y\)了，那么必然有\(n = x + y\)，因為\((x + y) mod x = y, y mod (x + y) = y\)，
-
那么要考慮的情況就是\(x <= y\)了，我們可以這樣想，
-
當場做的時候屬實沒想到，一直在推數學公式，，，，
代碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll x, y;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> x >> y;
if (x > y)
{
cout << x + y << endl;
}
else
{
cout << (y - y % x / 2) << endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/343959.html
標籤：其他