Codeforces Round 905 (Div. 3)
A. Morning
解题思路:
首先\(4\)个数字都要打印出来，所以\(ans\)起始值为\(4\)。
接着就是从左向右移动绝不回头，鼠标移动的距离和就是两两数字之差。
注意：这里\(0\)位置其实是\(10\).
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
string s;
cin >> s;
char cur = '1';
int ans = 4;
for (int i = 0; i < 4; i++)
{
if (s[i] == '0')
{
s[i] = '9' + 1;
}
ans += abs(s[i] - cur);
cur = s[i];
}
cout << ans << endl;
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B. Chemistry
解题思路：
回文串中最多有一种字母出现奇数次。
所以，我们的最小合法操作步数就是让出现奇数次的字母最多为\(1\)种。
如果初始情况出现奇数次的字母大于一个（有\(m\)个），那么我们就要判断是否\(k \geq m - 1\)。
如果奇数次的字母有一个，那么若\(k\)为偶数，我们一定有方案使减完\(k\)个字母后，奇数次字母只有一个；若\(k\)为奇数，那么我们一定有方案使减完\(k\)个字母后，全部都是出现偶数次的字母，也合法。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> cnt(30);
for (auto c : s)
{
cnt[c - 'a']++;
}
int ji = 0;
int ou = 0;
for (int i = 0; i < 26; i++)
{
if (cnt[i])
{
if (cnt[i] & 1)
{
ji++;
}
else
{
ou++;
}
}
}
int res = max(0, ji - 1);
k -= res;
if (k >= 0)
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C. Raspberries
解题思路:
本题\(k\)很小，可直接暴力计算到达出现第一个\(k\)的倍数的最短距离。
当\(k = 4\)的时候，有因子\(2\)。因此还要讨论到达序列得到有两个\(2\)的倍数的最短距离。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
bool f = false;
int ans = 1e9;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] % k == 0)
{
f = true;
}
int t = a[i];
int cnt = 0;
while (t % k)
{
t++;
cnt++;
}
ans = min(ans, cnt);
}
if (k == 4)
{
int fb = 1e9;
int sb = 1e9;
for (int i = 1; i <= n; i++)
{
int cnt = 0;
int t = a[i];
while (t % 2)
{
t++;
cnt++;
}
if (fb >= cnt)
{
sb = fb;
fb = cnt;
}
else if (sb > cnt)
{
sb = cnt;
}
}
ans = min(ans, sb + fb);
}
if (f)
{
cout << 0 << endl;
}
else
{
cout << ans << endl;
}
// cout << n << ' ' << k << endl;
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D. In Love
解题思路:
若当前集合中至少有两个线段，如果当前最小的右端点小于当前最大左端点，答案就是\(yes\)。
注意：不能按\(pair<int,int>\)来排序。
举例:\((1,5),(5,6),(2,4)\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
multiset<int> a, b;
int m = n;
int cnt = 0;
while (m--)
{
string s;
cin >> s;
int l, r;
cin >> l >> r;
if (s == "+")
{
a.insert(l);
b.insert(r);
}
else
{
a.erase(a.lower_bound(l));
b.erase(b.lower_bound(r));
}
if ((a.size() > 1 && (*a.rbegin() > *b.begin())))
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E. Look Back
解题思路:
设存在\(a,b\).其中\(a \leq b <2a\)。那么\(b*2^{k-1}<a * 2^k < b*2^k\)。
所以，预处理得到初始相邻元素之间的操作次数差。接下来从左向右递推，记录当前值要大于等于右值需要加上的操作次数即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
ll lowbit(ll x)
{
return x & -x;
}
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1), f(n + 1);
ll ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (i > 1)
{
if (a[i] < a[i - 1])
{
ll x = a[i - 1];
ll y = a[i];
int cnt = 0;
while (y < x)
{
y <<= 1;
cnt++;
}
f[i] = cnt;
}
}
}
for (int i = 2; i <= n; i++)
{
if (f[i])
{
f[i] += f[i - 1];
}
else
{
ll x = a[i];
ll y = a[i - 1];
ll cnt = 0;
while (y < x)
{
cnt++;
y <<= 1;
}
if (y > x)
{
cnt--;
}
f[i] = max(0ll, f[i - 1] - cnt);
}
// cout << i << ' ' << f[i] << endl;
ans += f[i];
}
cout << ans << endl;
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}