Codeforces Round 905 (Div. 3)ABCDEG1
A. Morning
思路：签到，直接模拟。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
string s; cin>>s;
int cnt = 0;
int now = 1;
for(int i = 0; i < 4; i++)
{
int t = s[i]-'0';
if(t==0)t = 10;
cnt += abs(now-t);
cnt++;
now = s[i]-'0';
if(now==0)now = 10;
}
cout<<cnt<<"\n";
}
return 0;
}
B. Chemistry
题意：问你能否删掉一些字母之后重排是回文串，且满足删的次数\(\le k\)。
思路：要符合回文串，那么最多只能有一个奇数。那么我们统计奇数的个数-1和k的大小比较即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
map<char,int>mp;
int n,k; cin>>n>>k;
string s; cin>>s;
s = "?"+s;
for(int i = 1;i <= n; i++)
mp[s[i]-'a']++;
vector<int>v;
for(int i = 0;i < 26; i++)
{
if(mp[i]%2)
v.push_back(mp[i]);
}
if(v.size()<=1)
cout<<"Yes\n";
else
{
int sz = v.size();
if(sz-1<=k)
cout<<"Yes\n";
else cout<<"No\n";
}
}
return 0;
}
C. Raspberries
题意：给你一个数组\(a_1,a_2,...,a_n\)。在一次操作里面，你可以选择一个元素让它\(+1\)。找到最小的操作次数使得\(a_1a_2a_3...a_n\)能被\(k\)整除。
思路：这里的突破口是\(k\)和\(a_i\)的范围。其中\(k = 2,3,4,5\)，\(1\le a_i\le 10\)
我们发现\(2,3,5\)都是素数，我们只需要考虑哪一个\(a_i\)能最快变成他们的倍数即可。
对于\(4\)的情况，它是合数，我们需要考虑\(2\)的倍数之积也是\(4\)的倍数。
- 如果有2个偶数那答案是\(0\)
- 如果一个奇数一个偶数答案是\(1\)
- 如果两个奇数答案是\(2\)
对于特判和之前直接变成\(4\)的倍数的情况取\(min\)就是答案啦。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n,k; cin>>n>>k;
ll ans = 1e18;
for(int i = 1;i <= n; i++)
{
cin>>a[i];
if(a[i] % k == 0)
ans = 0;
ans = min(ans,(a[i]/k+1)*k-a[i]);
}
if(ans==0){
cout<<0<<"\n";
continue;
}
if(k==4)
{
int cnt1 = 0,cnt2 = 0;
for(int i = 1;i <= n; i++)
{
int t = a[i] % 4;
if(t == 1)
cnt1++;
else if(t == 2)
cnt2++;
else if(t == 0)ans = 0;
}
if(cnt1>=2) ans = min(ans,2ll);
if(cnt2 >= 2) ans = 0;
if(cnt1>=1&&cnt2>=1)ans = min(1ll,ans);
}
cout<<ans<<"\n";
}
return 0;
}
D. In Love
题意：有\(q\)次操作。操作有以下两种类型：
- \(+lr\) 在多重集合中加入一个线段\((l,r)\)
- \(-lr\) 在多重集合中移走一个线段\((l,r)\)
每一次回答是否存在两个线段没有交集。
思路：我们用两个堆去维护左端点的最大值和右端点的最小值，如果\(mxl>mnr\)则说明存在。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n; cin>>n;
multiset<int,greater<int>>mxl;
multiset<int,less<int>>mnr;
for(int i = 1;i <= n; i++)
{
char op; int l,r;
cin>>op>>l>>r;
if(op=='+')
{
mxl.insert(l);
mnr.insert(r);
if(mxl.size()>=1&&mnr.size()>=1&&*mxl.begin()>*mnr.begin())
cout<<"YES\n";
else cout<<"NO\n";
}
else
{
mxl.erase(mxl.find(l));
mnr.erase(mnr.find(r));
if(mxl.size()>=1&&mnr.size()>=1&&*mxl.begin()>*mnr.begin())
cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
E. Look Back
题意：给你一个数组\(a_1,a_2,...,a_n\)，你可以通过选择一个下标\(i\)让元素\(a_i = a_i*2\)
问你最少多少次使得数组单调不减？
思路：
一开始的写法：
我二分答案去写的，可是会爆\(long\) \(long\)。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
ll qmi(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a;
a = a * a;
b >>= 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
ll cnt = 0;
for(int i = 2;i <= n; i++)
{
if(a[i]<a[i-1])
{
ll l = 1,r = 27;
while(l<=r)
{
int mid = (l+r)>>1;
if(qmi(2,mid)*a[i]>=a[i-1])r = mid-1;
else l = mid + 1;
}
a[i] *= qmi(2,r + 1);
cnt += r + 1;
}
}
cout<<cnt<<"\n";
}
return 0;
}
正解：
我们可以把最终答案分成\(2\)部分即：\(a_i\times 2^x\)。这样就不会爆\(long\) \(long\)啦。
我们分类讨论：
-
\(a[i]\ge a[i-1]\)
我只需要继承\(a[i-1]\)的系数减去\(a[i-1]\)变成\(a[i]\)的\(2\)的次数即：\(log2(a[i]/a[i-1])\)下取整
-
\(a[i]<a[i-1]\)
我只需要继承\(a[i-1]\)的系数加上\(a[i]\)变成\(a[i-1]\)的\(2\)的次数即：\(log2(a[i]/a[i-1])\)上取整
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],t[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int q; cin>>q;
while(q--)
{
int n; cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 2;i <= n; i++)
{
if(a[i] >= a[i-1])
t[i] = max(0ll,(ll)(t[i-1]-floor(log2((double)a[i]/a[i-1]))));
else
t[i] = max(0ll,(ll)(t[i-1]+ceil(log2((double)a[i-1]/a[i]))));
}
ll ans = 0;
for(int i = 1;i <= n; i++)
ans += t[i];
cout<<ans<<"\n";
}
return 0;
}
G1. Dances (Easy version)
题意：对于每组数据，给定两个长度为 \(n\) 的序列 \(a,b\)，其中 \(a_1=1\)， \(a_2\cdots a_n\) 与 \(b_1\cdots b_n\) 由输入得到。
你可以对两个数组任意排序，你需要在两个序列中分别删除 \(k\) 个数， 使得对于剩下 \(n-k\) 个数， 有 \(\forall 1\leq i\leq n-k\rightarrow a_i<b_i\)
求最少删除数
思路：排序+二分。
我们如果要删\(k\)个，一定是删\(a\)的前\(k\)大和\(b\)的前\(k\)小是最优的。我们直接二分答案即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N],b[N];
int n,m;
bool judge(int x)
{
int l1 = 1,l2 = x+1;
while(l1<=n-x)
{
if(a[l1]>=b[l2])return false;
l1++;
l2++;
}
return true;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
cin>>n>>m;
a[1] = 1;
for(int i = 2; i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int l = 0,r = 1e5;
while(l<=r)
{
int mid = (l+r)>>1;
if(judge(mid))r = mid-1;
else l = mid+1;
}
cout<<r+1<<"\n";
}
return 0;
}