Educational Codeforces Round 102 (Rated for Div. 2) 题解 (A-D)

不说了,经典赛后过题,此次一定给出A-D。

A. Replacing Elements

题意

给出一个长度n数组。在一次操作中,你可以取任意三个不同的坐标i、j、k。使得 a_i+a_j=a_k ,这个操作可以进行任意次,问是否能让数组中的所有数小于d。

题解

遍历数组,找出两个最小的数的同时判断数组中所有数是否超过d。if((数组中所有数原本就没有超过d)||(两个最小的数之和小于等于d))就是yes。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int min1=imax,min2=imax;
        int n,d,s,fla=0;
        cin>>n>>d;
        for(int i=0;i<n;i++){
            cin>>s;
            if(s>d)fla=1;
            if(min1>s){
                if(min2>min1)min2=min1;
                min1=s;

            }
            else if(min2>s){
                if(min1>min2)min1=min2;
                min2=s;
            }
        }
        if(min1+min2<=d||fla==0){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }

    }

}

B. String LCM

题意

就是两个字符串a、b公共最短子串的lcm,如果没有公共最短子串输出-1。

题解

使用两个字符串长度的lcm,分别用a和b拼接成两个字符串,如果两个相等就输出,不等就说明没有公共子串。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        string a,b,a1="",b1="";
        cin>>a;
        cin>>b;
        int re=lcm(a.size(),b.size());
        string res="";
        while(a1.size()!=re){
            a1+=a;
        }
        while(b1.size()!=re){
            b1+=b;
        }
        int f=0;
        for(int i=0;i<re;i++){
            if(a1[i]!=b1[i]){
                cout<<-1<<endl;
                f=1;
                break;
            }
        }
        if(f==0) cout<<a1<<endl;
    }

}

C. No More Inversions

题意

给出两个数字n和k,其中n是a数组长度,a数组规律是1,2,3….k,k-1,k-2,…..,k-(n-k)。
inversion关系就是i<j&&a_i>a_j
我们要构建一个新数组b,规律为b[i]=p[a[i]],b数组中inversion关系元素个数不能超过a,同时b的字典序也要最大。
输出数组p。

题解

我们观察以下规律:
a:1 2 3 2
b:1 3 2 3
p: 1 3 2
a:1 2 3 2 1
b:3 2 1 2 3
p: 3 2 1
a: 1 2 3 4 3
b: 1 2 4 3 4
p: 1 2 4 3
a:1 2 3 4 5 6 5 4
b:1 2 3 6 5 4 5 6
p: 1 2 3 6 5 4
我们可以发现,p的前n-(n-k)-1个数是1,2,3,4,……,后面的数是把后面几项倒过来。
我是通过找规律的方式过的,但是仔细想想还是能想出道理。
a数组的后2*(n-k)+1项是对称的,根据b[i]=p[a[i]],所以b数组的后半段也是对称的,为了不超过a数组中inversion关系的个数,我们只能对a数组的后2*(n-k)项进行修改。同时,为了保证字典序最大,b数组后半段规律就是k,k-1,k-2….k-(n-k)……k-1,k-2。
有了a和b,据此我们就能求出p。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n,k;
        cin>>n>>k;
        int j=0;
        for(int i=1;i<=k;i++){
            if(i<k-(n-k)) cout<<i<<" ";
            else {
                cout<<k-j<<" ";
                j++;
            }
        }
        cout<<endl;

    }

}

D. Program

题意

x的初始值为0,遇到+就加1,遇到-就减一。问去掉[l,r]区间内的运算,在运算过程中能得到几个值?

题解

这道题乍一看像是线段树一类区间维护的题,实际上仔细看看不是。
我们可以模拟一遍x,存到数组中,x增减一定是连续的,在未去掉某个区间的时候,就是最大值和最小值的差再+1(还有0)。
在删除一个区间后,被分解为了前后两段,两段中间的操作过程我们可以忽略,只计算出对x的增减即可。然后我们求出前缀最大值、最小值和后缀最大值、最小值,前缀最大值就是、最小值对应前一个区间,后缀最大值、最小值对应后面的区间,我们用后缀最大值、最小值分别减去删除区间的增减,就得到了删除后后面区间的最大值和最小值,然后和前一个区间取max、min,求出整体最大值和最小值,相减加一,就得到结果了。
例如,对于第二个样例:
x的值:0 1 0 1 2
前缀最大值:0 1 1 1 2
前缀最小值:0 0 0 0 0
后缀最大值:2 2 2 2 2
后缀最小值:0 0 0 1 2
删除区间[2,3],在1处前缀最大值、最小值为1,0。在4处后缀最大值、最小值为2,2。删除区间的增减为0(x[3]-x[1]),所以整体最大值为2,最小值为0,结果为3。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
struct node{
    int top;
    int bottom;
    int num;
    /*bool operator < (node a){
        if(h!=a.h)
            return h < a.h;
        return w < a.w;
    }
    */
};
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _;
    cin>>_;
    while(_--){
        int n,m;
        cin>>n>>m;
        char c;
        int num=0;
        vector<node> s;
        node nod;
        nod.top=0;
        nod.bottom=0;
        nod.num=0;
        s.push_back(nod);
        for(int i=1;i<=n;i++){
            cin>>c;
            if(c=='+')num++;
            else num--;
            nod.num=num;
            if(num>s[i-1].top) nod.top=num;
            else nod.top=s[i-1].top;
            if(num<s[i-1].bottom) nod.bottom=num;
            else nod.bottom=s[i-1].bottom;
            s.push_back(nod);
        }
        node s2[n+1];
        nod.top=s.back().num;
        nod.bottom=s.back().num;
        nod.num=0;
        s2[n]=nod;
        for(int i=n-1;i>=0;i--){
            nod.top=max(s[i].num,s2[i+1].top);
            nod.bottom=min(s[i].num,s2[i+1].bottom);
            nod.num=0;
            s2[i]=nod;
        }
        int a,b;
        for(int i=0;i<m;i++){
            cin>>a>>b;
            int top=s[a-1].top;
            int bottom=s[a-1].bottom;
            //cout<<top<<" "<<bottom<<endl;
            if(b==n){
                cout<<top-bottom+1<<endl;
                continue;
            }
            int top2=s2[b+1].top-(s[b].num-s[a-1].num);
            int bottom2=s2[b+1].bottom-(s[b].num-s[a-1].num);
            //cout<<top2<<" "<<bottom2<<endl;
            cout<<max(top,top2)-min(bottom,bottom2)+1<<endl;
        }
    }
}

题目来源于https://codeforces.com/contest/1473

知识共享许可协议
Text is available under CC BY-NC-SA 4.0 unless otherwise stated.

除非特殊声明,本站所有内容均以 CC BY-NC-SA 4.0协议授权。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇