2022-1-2

A. Integer Diversity

题目描述

给定 n 个整数 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an。 您选择给定数字的任何子集(可能没有或所有数字)并否定这些数字(即更改 x → ( − x ) x→(-x) x(x))。 您可以实现的数组中不同值的最大数量是多少?

输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 100 ) t(1≤t≤100) t1t100:测试用例的数量。

接下来的几行包含对 t t t 个测试用例的描述,每个测试用例两行。

第一行给出一个整数 n ( 1 ≤ n ≤ 100 ) n (1≤n≤100) n(1n100):数组中整数的个数。

第二行包含 n n n 个整数 a 1 , a 2 , … , a n ( − 100 ≤ a i ≤ 100 ) a_1,a_2,…,a_n (−100≤a_i≤100) a1,a2,,an(100ai100)

输出
对于每个测试用例,打印一个整数:可以实现对数组中的数字求反的数组中不同元素的最大数量。

input
3
4
1 1 2 2
3
1 2 3
2
0 0
output
4
3
1

例如,在第一个示例中,我们可以对第一个和最后一个数字取反,从而获得具有四个不同值的数组 [-1,1,2,-2]

在第二个示例中,所有三个数字都已经不同。

在第三个例子中,否定不会改变任何东西。

题解

首先,让我们用 ∣ a i ∣ |a_i| ai 替换 a i a_i ai。 让 f ( x ) f(x) f(x) 表示在替换后等于 x(或等于 x 或 -x 之前)的数组中的 数。

然后,对于零,我们只能得到 m i n ( 1 , f ( 0 ) ) min(1,f(0)) min(1,f(0)) 不同的值。

对于任何其他数字 x>0,我们可以在数组中得到 m i n ( 2 , f ( x ) ) min(2,f(x)) min(2,f(x)) 个不同的数字。

由于不同的绝对值是独立且有界的,为了得到答案,我们只需要评估总和 m i n ( 1 , f ( 0 ) ) + m i n ( 2 , f ( 1 ) ) + … + m i n ( 2 , f ( 100 ) ) min(1,f(0))+min(2,f(1))+…+min(2,f(100) ) min(1,f(0))+min(2,f(1))++min(2,f(100)。 使用数组可以轻松完成,保持每个 |x| 的出现次数。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
   
    ll n, i, a;
    map<ll, ll>m;
    cin >> n;
    for (int i = 0;i<n;i++){
   
        cin >> a;
        m[abs(a)]++;
    }
    ll sum = m[0] ? 1 : 0;
    for (i = 1; i <= 100; i++)sum += min(m[i], (ll)2);
    cout << sum << endl;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

B - Mirror in the String

题目描述

您有一个字符串 s 1 s 2 . . . s n s_1s_2...s_n s1s2...sn,您站在字符串的左侧并向右看。您想选择一个索引 k ( 1 ≤ k ≤ n ) k (1≤k≤n) k(1kn) 并在第 k k k 个字母后放置一面镜子,以便您看到的是 s 1 s 2 … s k s k s k − 1 … s 1 s_1s_2…s_ks_ks_{k−1}…s1 s1s2sksksk1s1。您能看到的按字典顺序排列的最小字符串是多少?

当且仅当以下条件之一成立时,字符串 a 在字典序上小于字符串 b:

a是b的前缀,但a≠b;
在 a 和 b 不同的第一个位置,字符串 a 有一个字母在字母表中比 b 中的相应字母出现得更早。
输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 10000 ) t(1≤t≤10000) t1t10000:测试用例的数量。

接下来的 t 行包含测试用例的描述,每个测试用例两行。

第一行给出一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1n105):字符串的长度。

第二行包含由 n 个小写英文字符组成的字符串 s。

保证所有测试用例的 n 之和不超过 1 0 5 10^5 105

输出
对于每个测试用例,打印您可以看到的按字典顺序排列的最小字符串。

input
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa

output
cc
cbaabc
aa
bb

笔记
在第一个测试用例中,选择 k=1 以获得“cc”。

在第二个测试用例中,选择 k=3 以获得“cbaabc”。

在第三个测试用例中,选择 k=1 以获得“aa”。

在第四个测试用例中,选择 k=1 来获得“bb”。

题解:

让我们比较 s 1 , s 2 … s k s k s k − 1 … s 1 s_1,s_2…s_ks_ks_{k−1}…s_1 s1,s2sksksk1s1 s 1 s 2 … s k + 1 s k + 1 s k … s 1 s_1s_2…s_{k+1}s_{k+1}s_k…s_1 s1s2sk+1sk+1sks1。 请注意,它们有一个很长的公共前缀 s 1 , s 2 , . . . , s k s_1,s_2,...,s_k s1,s2,...,sk。 下一对要比较的字符是 s k + 1 s_{k+1} sk+1 s k s_k sk。 所以,除非 s 1 s 2 … s k s k s k − 1 … s 1 s_1s_2…s_ks_ks_{k−1}…s1 s1s2sksksk1s1 s 1 s 2 … s k + 1 s k + 1 s k … s 1 s_1s_2…s_{k+1}s_{k+1}s_k…s_1 s1s2sk+1sk+1sks1 的前缀,否则如果 s k + 1 ≤ s k s_{k+1}≤s_k sk+1sk 选择 k + 1 k+1 k+1 是最优的。

进一步推动这个想法,我们可以看到答案是 s 1 s 1 s_1s_1 s1s1 s 1 s 2 … s k s k s k − 1 … s 1 s_1s_2…s_ks_ks_{k−1}…s_1 s1s2sksksk1s1,对于最大的 k k k 使得 s k ≤ s k − 1 s_k≤s_{k−1} sksk1

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
void solve(){
   
    int n;
    cin >> n;
    string s;
    cin >> s;
    string ans = "";
    ans += s[0];
    if (s[0] == s[1] || s[1] > s[0]){
   
        cout << ans;
        reverse(ans.begin(), ans.end());
        cout << ans;
    }
    else{
   
        for (int i = 1; i < n; i++){
   
            if (s[i] <= s[i - 1])
                ans += s[i];
            else
                break;
        }
        cout << ans;
        reverse(ans.begin(), ans.end());
        cout << ans;
    }
    cout << endl;
}

int main()
{
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Representative Edges

题目描述

数组 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an 是好的当且仅当对于每个子段 1 ≤ l ≤ r ≤ n 1≤l≤r≤n 1lrn,以下内容成立: a l + a l + 1 + … + a r = 1 / 2 ( a l + a r ) ⋅ ( r − l + 1 ) a_l+a_{l+1}+…+a_r={1/2}(a_l+a_r)⋅(r− l+1) al+al+1++ar=1/2(al+ar)(rl+1

给定一个整数数组 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an。 在一次操作中,您可以用任何实数替换此数组的任何一个元素。 找到使这个数组良好所需的最少操作数。

输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 100 ) t(1≤t≤100) t1t100:测试用例的数量。

接下来的 t 行中的每一行都包含一个测试用例的描述。

第一行给出一个整数 n ( 1 ≤ n ≤ 70 ) n (1≤n≤70) n(1n70):数组中整数的个数。

第二行包含 n 个整数 a 1 , a 2 , … , a n ( − 100 ≤ a i ≤ 100 ) a_1,a_2,…,a_n (−100≤a_i≤100) a1,a2,,an(100ai100):初始数组。

输出
对于每个测试用例,打印一个整数:您需要替换以使给定数组良好的最小元素数。

input
5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100
output
0
2
0
3
0

题解

请注意,如果数组是好的,则 a k + 2 − a k + 1 = a k + 1 − a k a_{k+2}−a_{k+1}=a_{k+1}−a_k ak+2ak+1=ak+1ak。 换句话说,数组形成一个等差数列。

我们可以固定一个任意元素并将所有其他元素设置为等于它(给我们答案的下限 n-1)。

或者,为了解决剩下的情况,我们可以固定答案中的任意两个元素,推导出等差数列中任意元素的公式,并检查我们必须更改的元素数量。

code:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
   
    int n;cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    int ans=n-1;
    for (int i=0;i<n;i++) {
   
        for (int j=i+1;j<n;j++) {
   
            int d=a[j]-a[i];
            int m=j-i;
            int c=m*a[i]-d*i;
            int cur=0;
            for (int k=0;k<n;k++) {
   
                int num=(d*k+c);
                if(num!=m*a[k]) cur++;
            }
            ans=min(ans,cur);
        }
    }
    cout<<ans<<endl;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}


D. Keep the Average High

题目描述

给定一个整数数组 a 1 , a 2 , … , a n a_1,a_2,…,a_n a1,a2,,an 和一个整数 x x x

您需要选择数组中元素的最大数量,这样对于每个子段 a l , a l + 1 , . . . , a r a_l,a_{l+1},...,a_r al,al+1,...,ar 严格包含一个以上的元素 ( l < r ) (l<r) (l<r),或者:

未选择此子分段中的至少一个元素,或 a l + a l + 1 + … + a r ≥ x ⋅ ( r − l + 1 ) a_l+a_{l+1}+…+a_r≥x⋅(r−l+1) al+al+1++arx(rl+1)
输入
输入的第一行包含一个整数 t ( 1 ≤ t ≤ 10 ) t(1≤t≤10) t1t10:测试用例的数量。

t 个测试用例的描述如下,每个测试用例三行。

第一行给出一个整数 n ( 1 ≤ n ≤ 50000 ) n (1≤n≤50000) n(1n50000):数组中整数的个数。

第二行包含 n 个整数 a 1 , a 2 , … , a n ( − 100000 ≤ a i ≤ 100000 ) a1,a2,…,an (−100000≤a_i≤100000) a1,a2,,an(100000ai100000)

第三行包含一个整数 x ( − 100000 ≤ x ≤ 100000 ) x (−100000≤x≤100000) x(100000x100000)

输出
对于每个测试用例,打印一个整数:您可以选择的最大元素数。

input
4
5
1 2 3 4 5
2
10
2 4 2 4 2 4 2 4 2 4
3
3
-10 -5 -10
-8
3
9 9 -3
5
output
4
8
2
2

题解

注意 a l + a l + 1 + … + a r ≥ x ⋅ ( r − l + 1 ) ⇒ ( a l − x ) + ( a l + 1 − x ) + … + ( a r − x ) ≥ 0 a_l+a_{l+1}+…+a_r≥x⋅(r−l+1)⇒(a_l−x)+(a_{l+1}−x)+…+(a_r−x)≥0 al+al+1++arx(rl+1)(alx)+(al+1x)++(arx)0

从所有元素中减去 x x x 后,问题就简化为选择仅具有非负和连续元素的最大元素数。

请注意,如果存在负和子段,则应该有一个长度为 2 或 3 的负和子段。 很容易看出 x < 0 x<0 x<0, y < 0 ⇒ x + y < 0 y<0⇒x+y<0 y<0x+y<0

因此,为了解决原始问题,我们可以使用一个简单的 D P DP DP,存储最后两个元素,无论它们是否在答案中。

code:


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
   
    ll n;
    cin >> n;
    vector<int> arr(n);
    for(ll i=0;i<n;i++)
        cin >> arr[i];
    ll x;
    cin >> x;
    for(ll i=0;i<n;i++)
        arr[i]-=x;
    vector<bool> marked(n,true);
    for(ll i=1;i<n;i++){
   
        if(arr[i]+arr[i-1]<0 && marked[i-1])
            marked[i]=false;
        if(i>=2 && arr[i]+arr[i-1]+arr[i-2]<0 && marked[i-1] && marked[i-2])
            marked[i]=false;
    }
    ll count=0;
    for(ll i=0;i<n;i++){
   
        if(marked[i])
            count++;
    }
    cout << count << "\n";
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}


🚩🚩🚩有问题欢迎评论区留言讨论,看到后我就会回复的!!!!

【Codeforces Round #763 (Div. 2)】【题解A.B】

【Educational Codeforces Round 120 (Rated for Div. 2)】【题解A-C】

更多CF题解请访问我的的专栏:AtCoder/Codeforces