Codeforces Round 891 (Div. 3) A-F 题解 + 做题总结
下面的数字是对应区间里所有数字的f值，可以看到，右边最开始所有数字的值从4到1，然后当s为x2的时候x2的值变为了4，左边多出了一个[x1,x2)的区间，并且对应的f值变成了1。的时候，可以发现x1的f值为4,(x1,x2]中的所有数字的值都为3,(x2,x3]中所有数字的值都为2,(x3,x4]中所有数字的值都为1。的时候，[x1,x2)中所有数字的值都为1,(x2,x3]中所有数字的值都为2
A. Array Coloring （模拟，数论）
给定你一个数组，要求你对数组里的所有数字进行染色，要求每种颜色至少进行一次染色，问你是否可以让两种颜色的数字和的奇偶性相同。
模拟一下各种情况就可以发现，只有当奇数的个数为奇数的时候不行，判断一下即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353;
const int N=1000100;
void init() {
}
int a[N];
void solve() {
init();
int n;
cin>>n;
int num = 0;
for(int i=1;i<=n;i++) {
cin>>a[i];
if(a[i]%2) num ++;
}
if(num %2) cout<<"NO\n";
else cout<<"YES\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
B. Maximum Rounding(贪心，数论)
给定你一个n位数，你可以对某个位进行四舍五入，问你能够得到的最大数字是多少。注意n的范围是 2 * 10 5 ^5 5
显然越高位进行进位结果越大，遍历一遍找到最高位能够进位的地方，让最高位之前的位全部变为0，然后在向更高位遍历是否能够继续进位即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353;
const int N=1000100;
void init() {
}
int a[N];
void solve() {
init();
string s;
cin>>s;
int n=s.length();
int sign=-1;
for(int i=0;i<n;i++) {
if(s[i]-'0'>=5) {
sign=i;
break;
}
}
if(sign==-1) {
cout<<s<<"\n";
return ;
}
for(int i=n;i>=0;i--) {
if(s[i]>'9') {
s[i]='0';
if(i!=0)
s[i-1]+=1;
}
if(i >= sign) {
if(s[i]-'0'>=5)
{
s[i]='0';
if(i!=0)
s[i-1]+=1;
}
else s[i]='0';
}
else {
if(s[i]-'0'>=5) {
s[i]='0';
if(i!=0)
s[i-1]+=1;
}
else break;
}
}
if(s[0]=='0') cout<<1;
cout<<s<<"\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
C. Assembly via Minimums(排序，模拟)
给定一个n * (n-1) / 2长度的数组，其中每个数字都是 a i a_i ai 和 a j a_j aj 的最小值 (i < j)，但是数字是随机打乱的，要求你构造一个数组能让里面的数字都是 a i a_i ai 和 a j a_j aj 的最小值。
其实很好想，你把他排序后就会发现，最小的数字肯定出现了n-1次，第二小的数字出现了n-2次，以此类推，所以只要将给定的数组进行排序，然后找第一个数字，第1 + (n-1) 个数字 ……以此类推便可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353;
const int N=1000100;
void init() {
}
int a[N];
void solve() {
init();
int n;
cin>>n;
for(int i=1;i<=n * (n-1) / 2;i++) cin>>a[i];
sort(a+1,a+(n * (n-1) / 2)+1);
int add = n-1;
int now = 1;
while(now < n * (n-1) / 2) {
cout<<a[now]<<" ";
now += add;
add--;
}
cout<<a[n * (n-1) / 2]<<" "<<a[n * (n-1) / 2 ]<<"\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
D. Strong Vertices（数论，模拟）
给定两个长度为n的数组a,b，其中如果 a u a_u au - a v a_v av ≥ b u b_u bu - b v b_v bv ，就连接一条从u 到 v的有向边，问你有多少个节点是有所有到其他节点的有向边。
这道题不难，推一下公式变成 a u a_u au - b u b_u bu ≥ a v a_v av - b v b_v bv ，所以我们只要找到 a i a_i ai - b i b_i bi 的最大值有多少个就好。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
const int N=1000100;
void init() {
}
int a[N];
int b[N];
void solve() {
init();
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int maxvalue= - 2 * MOD;
map<int,int>mp;
for(int i=1;i<=n;i++) {
maxvalue = max(maxvalue,a[i]-b[i]);
mp[a[i]-b[i]]++;
}
cout<<mp[maxvalue]<<"\n";
for(int i=1;i<=n;i++) {
if(a[i]-b[i]==maxvalue) cout<<i<<" ";
}
cout<<"\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
E. Power of Points(数论+模拟)
这题我没那么好描述，直接上图吧
这里可以找一下规律，假设现在给定一个数组[
x
1
x_1
x1,
x
2
x_2
x2,
x
3
x_3
x3,
x
4
x_4
x4],首先设s为
x
1
x_1
x1的时候，可以发现x1的f值为4,(x1,x2]中的所有数字的值都为3,(x2,x3]中所有数字的值都为2,(x3,x4]中所有数字的值都为1。当s变为
x
2
x_2
x2的时候，[x1,x2)中所有数字的值都为1,(x2,x3]中所有数字的值都为2 ,(x3,x4]中所有数字的值都为1,而
x
2
x_2
x2的值依旧是4.
用图表示如下：
下面的数字是对应区间里所有数字的f值，可以看到，右边最开始所有数字的值从4到1，然后当s为x2的时候x2的值变为了4，左边多出了一个[x1,x2)的区间，并且对应的f值变成了1。
观察上图不难总结出规律：s值变化的时候，减少(xi,xi+1]的f值之和，同时增加[xi,xi+1)的f值之和，此时他们的f值之和就是左边区间个数 * 区间的数字个数
代码如下，结合图片更好理解
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
const int N=1000100;
void init() {
}
int a[N];
int b[N];
void solve() {
init();
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int maxvalue= - 2 * MOD;
map<int,int>mp;
for(int i=1;i<=n;i++) {
maxvalue = max(maxvalue,a[i]-b[i]);
mp[a[i]-b[i]]++;
}
cout<<mp[maxvalue]<<"\n";
for(int i=1;i<=n;i++) {
if(a[i]-b[i]==maxvalue) cout<<i<<" ";
}
cout<<"\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
F. Sum and Product(数论，韦达定理)
给定一个数组，同时给定q次询问，每次询问会给定两个数x,y,要求你找出有多少对数能够满足 a i a_i ai + b j b_j bj = x 同时 a i a_i ai * b j b_j bj = y。
这道题如果还记得韦达定理求根公式就会好做很多。这道题的条件就是形如韦达定理
如此一来我们只需按照韦达定理求根来求解这两个解，然后根据这两个解的数量输出结果便可
注意判断是否有解以及解的个数
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
const int N=1000100;
void init() {
}
int a[N];
void solve() {
init();
int n;
cin>>n;
map<int,int>mp;
for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
int q;
cin>>q;
while(q--) {
int x,y;
cin>>x>>y;
int delta = x * x - 4 * y;
if(delta < 0) {
cout<<0<<" ";
continue;
}
int num1 = (x + sqrt(delta) ) / 2;
int num2 = (x - sqrt(delta)) / 2;
if(num1 + num2 != x || num1 * num2 != y) {
cout<<0<<" ";
continue;
}
if(num1 == num2) cout<<mp[num1] * (mp[num2] - 1) / 2<<" ";
else {
cout<<mp[num1] * mp[num2] <<" ";
}
}
cout<<"\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
总结：这场是找规律推公式为主的，做下来最大的感觉就是还需要多注意一些隐藏条件或者是判断边界等方面。
个人还是没能做到足够的仔细，仍需要多训练自己的专注力
集算法之大成！助力oier实现梦想！
更多推荐
23
0- 0
已为社区贡献3条内容
所有评论(0)