• 欢迎光临~

Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) A-D 题解

开发技术 开发技术 2022-08-01 次浏览

A. Two 0-1 Sequences

 大致翻译:

两个长度为n和m的二进制序列a和b(题目保证n >= m)

两个操作:

op1: 改变a(2) 为min(a(1), a(2)),并且移除a(1)

op2: 改变a(2) 为max(a(1), a(2)),并且移除a(1)

每次操作后,原先的a(i)变成a(i + 1), 长度减少1,即前移。

  a二进制序列能否通过这两个操作变成b二进制序列?

解题思路:刚开始想的是判断a2后缀跟a1后缀是否相同,再判断,a1前面有没有1和0(因为有1和0,就表示op1和op2可以随意完成)。写的时候又陆陆续续发现需要几个特判,想a1长度为1等。

于是就debug,慢慢发现只要前面有a2的第一个数字,并且后缀相同就可以对了。最终写出来了。

不过我写的查找是自己造轮子,我发现大佬就是用stl中的count()来写的,就拿过来改进了改进自己的code

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define rep(i,x,n) for(int i = x; i <= n; i++)
 
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 10021;
 
void solve() {
    int n, m;
    cin>>n>>m;
    string a, b;
    cin>>a>>b;
    if(a.substr(n-m+1) == b.substr(1) && count(a.begin(), a.begin() +n - m + 1, b[0])) {
        puts("YES");
    } else puts("NO");
}
void test();
int main()
{
    int n;
    cin>>n;
    while(n--) solve();
 
    return 0;
}

B. Luke is a Foodie

  大致翻译:

对于a数组中的每一个元素,满足 |v−ai|≤x, (x是固定的值,由题目给出, v是可以变化调动的值)

问最少需要调动几次v,才能使得a数组中所有元素满足|v−ai|≤x

解题思路:

用数组的话存不下1e9+21的int型,而且题目是要找改了几次v。由|v- ai| <= x这个可以发现,区间差的最大值小于二倍的x范围内,v就不会改。因此发现存max,min,每次相减,判断是否满足在范围内,满足不改,不满足将max,min赋值为k(读入值)

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;
 
#define rep(i,x,n) for(int i = x; i <= n; i++)
 
typedef long long LL;
typedef pair<int,int> PII;
 
//const LL N = 1e9+21;
//LL arr[N];
void test();
int main()
{
    //test();
    LL t;
    cin>>t;
    while(t--) {
        LL n,x;
        scanf("%lld %lld", &n, &x);
        LL cnt = 0;
        LL ma, mi;
        scanf("%d", &ma);
        mi = ma;
        rep(i,2,n) {
            LL k;
            scanf("%lld", &k);
            if(mi > k) mi = k;
            if(ma < k) ma = k;
            if(abs(ma - mi) <= 2*x) {;}
            else {
                cnt++;
                ma = k;
                mi = k;
            }
        }
        printf("%lldn",cnt);
    }
 
    return 0;
}
 

C. Virus

  大致翻译:

一个圆圈内有n个房子(编号为:1、 2、 3 …… n 、 1),最初,其中的m个房子被感染了,每天被感染的房子会感染其相邻的房子(该房子未被感染或未被保护).Cirno每天可以选择一个房子保护,使他永久免疫。问Cirno在最合理的操作下,使房子感染数量最少, 输出最终房屋感染的数量。

解题思路:n跟m较大,即开n数组会溢出,那么就先从m下手。由于是形成一个 ⚪ ,第几个第几个房子就不是那么重要,谁都可以从第一个开始。想一想,要想求最小感染房子,那反过来就是最大未感染房子(正难反易)。最大未感染房子个数,这个... 。 由于每一天房子都会有被感染的可能,怎么就最大未感染房子个数( •̀ ω •́ )y,当然是从两个感染房子间隔最大的先开始咯,从两个感染房子间隔最大的先开始,堵住一个后,第二天感染,未堵住的会向内(当然还有外)感染,然后堵住那个未堵住的房子,一个间隔用两天。通过递增减去4倍的i,可以得到到它时,还有几个未被感染。

里面有一些细节,例如怎么得到第一个跟最后一个的间隔,怎么让间隔由大到小去计算。

Codeforces CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) A-D 题解

 

 

 

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define rep(i,x,n) for(int i = x; i <= n; i++)

typedef long long LL;
typedef pair<int,int> PII;

const int N = 100021;
int arr[N];
int diff[N];
void test();
int main()
{
    test();
    int t;
    scanf("%d", &t);
    while(t--) {
        int n,m;
        scanf("%d %d", &n, &m);
        rep(i,1,m) {
            scanf("%d", &arr[i]);
        }
        sort(arr+1, arr+m+1);
        diff[1] = arr[1] - 1 + n - arr[m];
        rep(i,2,m) diff[i] = arr[i] - arr[i-1] - 1;
        sort(diff+1, diff+m+1, greater<int>());
        int ans = 0;
        rep(i,1,m) {
            diff[i] -= 4*(i-1); // 每次两天,一前一后,形成永久隔离,那么里面的自然而然就是不会被感染的了
            if(diff[i]) {
                n -= (diff[i] == 1?1:(diff[i]-1));
            }
            
        }
        cout<<n<<endl;
    }


    return 0;
}

void test() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}

D. Magical Array

  大致翻译:

定义一个特殊行,执行操作2,其它行执行操作1(执行次数都至少有一次)

给出这些行,让你输出那个是特殊行,以及特殊行操作2的次数。

解题思路:前缀和和差分,思路简单。

学到了 min_element() max_element()

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <memory.h>
using namespace std;

#define rep(i,x,n) for(int i = x; i <= n; i++)

typedef long long LL;
typedef pair<int,int> PII;

const int N = 100021;
LL arr[N];
void test();
int main()
{
    //test();
    int t;
    cin>>t;
    while(t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; ++i) {
            LL pre = 0;
            for(int j = 1; j <= m; ++j) {
                LL x;
                scanf("%lld", &x);
                pre += x;
                arr[i] += pre;
            }
        }
        LL mx = *max_element(arr+0, arr+n);
        LL mi = *min_element(arr+0, arr+n);
        cout<< min_element(arr+0, arr+n) - arr + 1<<" "
            <<mx - mi<<endl;
            memset(arr, 0, sizeof(arr));
    }
   

    return 0;
}

void test() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}

总结:学了几个stl

count() --  返回个数 max_element()  min_element()  --  返回迭代器或地址(数组)。

第一次做codeforces,写的时候太着急了,有些题没理解透彻或者复杂化了,A题用时较长。

加油!!!

喜欢 (0)