Codeforces Round 964 (Div. 4)A~G1
A. A+B Again?
签到
// 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;
for(int i = 1.;i <= n; i++)
{
int x; cin>>x;
cout<<x%10 + x/10<<"\n";
}
return 0;
}
B. Card Game
签到，但注意一下平局
// 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--)
{
int a1,a2,b1,b2;
cin>>a1>>a2>>b1>>b2;
int win = 0;
//1 1 , 2 2
//1 2 , 2 1
//2,1 , 1 2
//2 2 , 1 1
if((a1 > b1 && a2 >= b2)||(a1 >= b1 && a2 > b2))win++;
if((a1 > b2 && a2 >= b1)||(a1 >= b2 && a2 > b1))win++;
if((a2 > b1 && a1 >= b2)||(a2 >= b1 && a1 > b2))win++;
if((a2 > b2 && a1 >= b1)||(a2 >= b2 && a1 > b1))win++;
cout<<win<<"\n";
}
return 0;
}
C. Showering
因为没有交集，那么直接左断点排序然后一个个判断就行了。
// 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--)
{
int n,s,m; cin>>n>>s>>m;
set<pair<ll,ll>>st;
for(int i = 1;i <= n; i++)
{
ll l,r; cin>>l>>r;
st.insert({l,r});
}
ll last = 0,now = 0;
bool fg = false;
for(auto [l,r] : st)
{
now = l;
if(now-last >= s){
fg = true;
break;
}
last = r;
}
if(m - last >= s)fg = true;
cout<<(fg?"YES":"NO")<<"\n";
}
return 0;
}
D. Slavic's Exam
注意一下是子序列。然后对于目标串每一个字母进行判断是否能存在即可。
// 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,t;
cin>>s>>t;
int lens = s.size();
int lent = t.size();
s = "?" + s;
t = "?" + t;
int cnt = 0;
for(int i = 1;i <= lens; i++)
cnt += (s[i]=='?');
if(cnt >= t.size()){
cout<<"YES\n";
int j = 1;
for(int i = 1;i <= lens; i++)
{
if(s[i] == '?' && j <= lent)s[i] = t[j],j++;
else if(s[i] == '?')s[i] = 'a';
cout<<s[i];
}
cout<<"\n";
continue;
}
bool ok = true;
int j = 1;
for(int i = 1;i <= lent; i++)
{
// cout<<"i = "<<i<<" j = "<<j<<"\n";
while((s[j] != t[i] && s[j] != '?') && j <= lens){
// cout<<s[j]<<" "<<t[i]<<"\n";
j++;
}
// cout<<"!!!j = "<<j<<"\n";
if((s[j] != t[i] && s[j] != '?') || j > lens){
// cout<<"####\n";
// cout<<s[j]<<" "<<t[i]<<"\n";
ok = false;
break;
}
s[j] = t[i];
j++;
}
cout<<(ok?"YES":"NO")<<"\n";
if(ok){
for(int i = 1;i <= lens; i++)
{
if(s[i] == '?')s[i] = 'a';
cout<<s[i];
}
cout<<"\n";
}
}
return 0;
}
E. Triple Operations
题意：给你一段连续数[l,r]。你可以选择任意两个数\(x,y\)进行操作，使得\(x\)变成\(3x\)，\(y\)变成\(\lfloor\dfrac{y}{3}\rfloor\)。
问最少变多少次使得所有都变成0？
思路：很容易想到是先把最小先变成0，然后再操作其他的，这样不会有其他数变大了。
可以用前缀和先预处理出前\(i\)个数变为0的次数\(s[i]\)。对于\([l,r]\)答案就是：最小的数变为0的次数\(\times2\)，加上\(s[r]-s[l]\)。
// 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 s[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
for(int i = 1;i < N; i++)
{
int x = i;
int cnt = 0;
while(x)
{
x /= 3;
cnt++;
}
s[i] = s[i-1] + cnt;
}
while(t--)
{
int l,r; cin>>l>>r;
int cnt = s[l]-s[l-1];
cnt *= 2;
cnt += s[r]-s[l];
cout<<cnt<<"\n";
}
return 0;
}
F. Expected Median
思路：因为只有0和1，那么中位数要么是0要么是1。要算中位数的和，0就不用管了。考虑什么时候1会是中位数，很显然是\(1\)的个数\(\ge0\)的个数的时候。然后用组合数学选出要哪几个\(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 f[N],infact[N];
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void init()
{
f[0] = infact[0] = 1;
for(int i = 1; i <= N; i++)
{
f[i] = i * f[i - 1] % mod;
infact[i] = infact[i - 1] * 1ll * qmi(i, mod-2, mod) % mod;
}
}
ll C(ll a,ll b)
{
return f[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
init();
while(t--){
int n,k; cin>>n>>k;
int cnt0 = 0,cnt1 = 0;
for(int i = 1;i <= n; i++)
{
int x; cin>>x;
cnt0 += (x==0);
cnt1 += (x==1);
}
int mid = (k+1)/2;
ll ans = 0;
for(int i = mid; i <= min(cnt1,k); i++)
{
// cout<<"i = "<<i<<"\n";
// cout<<"C(cnt1,i) = "<<C(cnt1,i)<<"\n";
if(k-i<=cnt0)
ans = (ans + C(cnt1,i)*C(cnt0,k-i)%mod) % mod;
}
cout<<ans<<"\n";
}
return 0;
}
G1. Ruler (easy version)
思路：是一个交互题呀。最多问10次的话，很容易想到是log级别的，二分。
简化一下问题，如果只有一个维度，怎么做呢？是不是突然觉得容易很多了。
如果当前比实际的大说明有问题，如果等于的话说明是正常的。这个就很好写啦。
但是你会想这个是二维的呀，怎么办呢？让一个维度是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;
int main()
{
// ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int l = 2,r = 1000;
while(l < r){
int mid = (l + r)>>1;
cout<<"? 1 "<<mid<<endl;
int in; cin>>in;
if(in == mid)l = mid + 1;
else r = mid;
}
cout<<"! "<<l<<endl;
}
return 0;
}