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） t（1≤t≤100）：测试用例的数量。

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

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

第二行包含 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​(−100≤ai​≤100)。

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

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 s1​s2​...sn​，您站在字符串的左侧并向右看。您想选择一个索引 k ( 1 ≤ k ≤ n ) k (1≤k≤n) k(1≤k≤n) 并在第 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 s1​s2​…sk​sk​sk−1​…s1。您能看到的按字典顺序排列的最小字符串是多少？

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

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

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

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

第二行包含由 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​,s2​…sk​sk​sk−1​…s1​ 和 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 s1​s2​…sk+1​sk+1​sk​…s1​。 请注意，它们有一个很长的公共前缀 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 s1​s2​…sk​sk​sk−1​…s1 是 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 s1​s2​…sk+1​sk+1​sk​…s1​ 的前缀，否则如果 s k + 1 ≤ s k s_{k+1}≤s_k sk+1​≤sk​ 选择 k + 1 k+1 k+1 是最优的。

进一步推动这个想法，我们可以看到答案是 s 1 s 1 s_1s_1 s1​s1​ 或 s 1 s 2 … s k s k s k − 1 … s 1 s_1s_2…s_ks_ks_{k−1}…s_1 s1​s2​…sk​sk​sk−1​…s1​，对于最大的 k k k 使得 s k ≤ s k − 1 s_k≤s_{k−1} sk​≤sk−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;
    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 1≤l≤r≤n，以下内容成立： 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​)⋅(r−l+1）。

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

输入
输入的第一行包含一个整数 t （ 1 ≤ t ≤ 100 ） t（1≤t≤100） t（1≤t≤100）：测试用例的数量。

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

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

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

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

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+2​−ak+1​=ak+1​−ak​。 换句话说，数组形成一个等差数列。

我们可以固定一个任意元素并将所有其他元素设置为等于它（给我们答案的下限 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​+…+ar​≥x⋅(r−l+1)。
输入
输入的第一行包含一个整数 t （ 1 ≤ t ≤ 10 ） t（1≤t≤10） t（1≤t≤10）：测试用例的数量。

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

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

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

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

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

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​+…+ar​≥x⋅(r−l+1)⇒(al​−x)+(al+1​−x)+…+(ar​−x)≥0。

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

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