首页 > 代码库 > Codeforces Round #FF(255) DIV2 C - DZY Loves Sequences

Codeforces Round #FF(255) DIV2 C - DZY Loves Sequences

2024-07-12 01:15:33   223人阅读

A - DZY Loves Hash

水题，开辟一个数组即可

#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;int main(){    int p,n;    cin >> p >> n;    vector<bool> buckets(302,false);    bool flag = false;    vector<int > x(n);    for(int i  =0  ; i < n ; ++i) cin >> x[i];    int i = 0;    for(i = 0 ; i < n; ++i){        if(!buckets[x[i]%p]) buckets[x[i]%p] = true;        else{ cout<<i+1<<endl; break;}    }    if(i >= n) cout<<-1<<endl;}
开辟一个数组即可

B - DZY Loves Strings

先把给定的字符的值求出来，然后插入权重最大的值即可

#include <iostream>#include <vector>#include <algorithm>#include <string>#include <map>using namespace std;int main(){    string s;    int k;    vector<int> w(26,0);    cin >>s >> k;    for(int i = 0 ; i < 26; ++ i) cin >>w[i];    long long res = 0;    for(int i = 0 ;i < s.length(); ++ i){        res+=w[s[i]-‘a‘]*(i+1);    }    sort(w.begin(),w.end());    for(int i =s.length(); i < s.length()+k; ++ i){        res+=w[25]*(i+1);    }    cout<<res<<endl;}
View Code

C - DZY Loves Sequences

题目的意思是给定一个序列，然后找出一个子序列，改变子序列的一个值，使该子序列严格单调递增，求出满足上述要求最长子序列的长度。

注意一定要是单调递增

思路是将数组分块，每一块都是严格单调递增的

如 7 2 3 1 5 6

分组后为 [7], [2,3], [1,5,6]，影响长度的是组与组之间的间隔

现在记录下每一个组的开始索引和结束索引，以及长度，所求最大子序列长度有三种可能

（1）如果该数组只有一个分组，则该长度就是所求结果的长度

（2）max（每个分组的长度+1），即就是每个分组的长度+改变与其相邻元素的值的最大值

（3）两个分组合并后的值即max(分组 i +　分组　i+1 )的值，注意这里分组有两种情况种情况

　　　　假设分组后两组元素为[astart1 .... aend1], [astart2 ..... aend2]，注意这两组元素是相邻的即 start2 == end1+1

　　　　要满足严格单调递增的情况必须满足 astart2+1-aend1 > 1 或者 astart2 - aend1-1 >1, 要像下面的用例一样[1,2,5],[4,5,7]即可

　　　　如果下面的用例

　　　　　　a、[1,2,4],[3,6,7]这两个分组无法合并 ，因为astart2 -aend1-1 <=1

　　　　　　b、[1,2,5],[3,5,7]这两个分组无法合并, 因为astart2+1-aend1 <=1

#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;struct Node{    int startIdx;    int endIdx;    Node(int a = 0,int b = 0): startIdx(a),endIdx(b){};    int getLength(){return endIdx-startIdx+1;}};int main(){    int n;    cin >>n;    vector<int> a(n+1,0);    vector<Node> aux;    for(int i = 1;i <=n ; ++i) cin >> a[i];    int startIdx = 1, maxLength = 0;    bool flag = false;    for(int i = 1; i < n ; ++i){        if(a[i] < a[i+1]){            if(!flag) {startIdx = i;flag = true;}        }else{            aux.push_back(Node(startIdx,i));            maxLength = max(maxLength,i-startIdx+1);            startIdx = i+1;            flag = false;        }    }    if(startIdx == n ) {aux.push_back(Node(n,n));maxLength = max(maxLength,1);}    else {aux.push_back(Node(startIdx,n));maxLength=max(maxLength,n-startIdx+1);}    for(int i = 0; i < aux.size()-1; ++ i){        if(aux[i+1].startIdx+1<=aux[i+1].endIdx && a[aux[i+1].startIdx+1]-a[aux[i].endIdx] > 1) maxLength =max(maxLength,aux[i+1].getLength()+aux[i].getLength());        if(aux[i].endIdx-1>=aux[i].startIdx && a[aux[i+1].startIdx]-a[aux[i].endIdx-1] > 1 ) maxLength =max(maxLength,aux[i+1].getLength()+aux[i].getLength());        maxLength =max(maxLength,aux[i].getLength()+1);    }    if(aux.size() > 1)  maxLength =max(maxLength,aux[aux.size()-1].getLength()+1);    cout<<maxLength<<endl;}
View Code

 


联系
我们