Codeforces Round 546 (Div. 2)

2019/03/13 01:48
阅读数 18

<a href="https://codeforces.com/contest/1136" target="_blank" style="font-size:24px;"><strong>传送门</strong></a>

A - Nastya Is Reading a Book (签到)

题意

给出每一章的页数范围,然后告诉你当前看到那一页,求还没看完的章节数目

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
int l[maxn],r[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
    int k;
    scanf("%d",&k);
    int num=n+1;
    for(int i=1;i<=n;i++){
        if(k>r[i])continue;
        else{
            num=i;
            break;
        }
    }
    cout<<n-num+1<<endl;
    return 0;
}

B - Nastya Is Playing Computer Games (模拟)

题意

一排井盖,井盖下面有金币,你需要拿走所有金币,拿走井盖下的金币需要井盖上没有石头

一开始井盖上面都有一个石头。

每一秒你可以进行以下一种操作

1:向左走或者向右走,

2:把一个石头扔到其他任意一个井盖上面

3:取走金币

现在给你起始位置和井盖个数

问你把所有金币取走需要多少步

思路

很明显的一个贪心策略,可以把所有石头都扔到一个不需要的井盖上面 但是第一个扔的还需要再扔回去

然后因为可能要会出生在中间点,所以可以贪心的选择先向左还是向右走

首先 扔石头肯定需要扔n+1次 ,金币也需要捡n次,走路也需要走n-1次 然后就是重复走的距离min(n-k,k-1)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    if(n==1||n==k)printf("%d\n",n*3);
    else{
        int sum=3*n;
        sum+=min((k-1),(n-k));
        printf("%d\n",sum);
    }
    return 0;
}

C - Nastya Is Transposing Matrices (神奇)

题意

矩阵a和b 每次可以把a的一个子矩阵按照左对角线翻转,问你能否使a变成b

思路

一开始题目的反转理解错了没想到,

后来发现 如果对于一个2*2的矩阵一次反转就相当于把左下和右上对调。所以只需要保证这一条线的值都相同就肯定可以通过反转变成B

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
vector<int>v1[500*500+5];
vector<int>v2[500*500+5];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;
            scanf("%d",&a);
            v1[i+j].push_back(a);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int a;
            scanf("%d",&a);
            v2[i+j].push_back(a);
        }
    }

    for(int i=1;i<=n+m;i++){
        sort(v1[i].begin(),v1[i].end());
        sort(v2[i].begin(),v2[i].end());
        if(v1[i]!=v2[i])puts("NO"),exit(0);
    }
    puts("YES");
    return 0;
}

D - Nastya Is Buying Lunch (贪心)

题意

给出一个1-n的数列,然后给你m个关系 如果前面的数正好在后面的数前面一个位置,那么就可以把这两个数交换位置

问你最多可以让最后一个数(a[n])向前走多少步

思路

首先我们可以把点分成两类。

1:可以让n和她交换位置

2:不可以让n和她交换位置

那么题目就是让n最后能有多少个连续的1类点

所以我们考虑贪心能不能把经可能多的一类点向后移动

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=6e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int a[maxn];
map<int,int>mp[maxn];
int vis[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        mp[u][v]=1;
        if(v==a[n])vis[u]=1;
    }
    for(int i=n-1;i>=1;i--){
        if(vis[a[i]]){
            for(int j=i+1;j<n;j++){
                if(mp[a[j-1]].find(a[j])!=mp[a[j-1]].end()){
                    swap(a[j],a[j-1]);
                }
                else break;
            }
        }
    }
    int ans=0;
    for(int i=n-1;i>=1;i--){
        if(vis[a[i]])ans++;
        else break;
    }
    printf("%d\n",ans);
    return 0;
}

E - Nastya Hasn't Written a Legend (线段树)

题意

给你两个序列 $a_1,a_2\dots a_n$ 和 $ k_1,k_2,\dots k_{n-1}$,输入保证$ a_{i}+k_{i}<=a_{i-1}$.

两种操作:

1:区间求$ \sum_{i=l}^{r}a_i$

2:给单点$ a_i$加$x$ 同时会有连锁反应,若$a_p+k_p>a_{p+1}$,则$a_{p+1}$ 更新为$ a_p+k_p$ ,同理更新到$a_p+2$ 知道不能更新

思路

来自群友的做法 (感谢这位巨佬)

首先根据题意会发现一个式子 $$ a_1\leq a_2-k_1\leq a3-k_2-k_2 \dots \leq a_n-\sum_{i=1}^{n-1}k_i $$ 给$p$位置加上值$x$ 之后,$a_p-\sum_{i=1}^{p-1}k_i$也增加了x。更新之前已知$a_p-\sum_{i=1}^{p-1}k_i\leq a_{p+1}-\sum_{i=1}^{p}k_i$ 如果$a_p+k_p+x >a_{p+1}$

那么$a_{p+1}=a_p+k_p+x$ 并且$a_{p+1}-\sum_{i=1}^{p}k_i=a_p-\sum_{i=1}^{p}k_i+x$ $a_{p+2} $同理

最后:

我们令$b_x=a_x-\sum_{i=1}^{x-1}k_i$,我们给$p$单点加上$x$之后的效果:就是把$i\in[p+1,n]$ 内所有小于$b_p+x$的值赋值为$b_p+x$

所有修改我们已经搞定了,用线段树或者其他数据结构维护就可以了,求和就是$\sum_{i=l}^{r}b_i+\sum_{i=l}^{r}\sum_{j=1}^{i-1}k_j$ 更新就是区间赋值了,因为$b_x$ 满足单调不减性所以直接二分查找右端点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int n,m;
ll a[maxn],k[maxn],ks[maxn];
struct SegTree{
    ll sum[maxn<<2],flag[maxn<<2];
    void build(int o,int l,int r){
        flag[o]=inf;
        if(l==r){
            sum[o]=a[l]-k[l-1];return;
        }
        int mid=(l+r)/2;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
    void push_down(int o,int l,int r){
        if(flag[o]==inf)return;
        int mid=(l+r)/2;
        flag[o<<1]=flag[o<<1|1]=flag[o];
        sum[o<<1]=flag[o]*(mid-l+1);
        sum[o<<1|1]=flag[o]*(r-mid);
        flag[o]=inf;
    }
    void update(int o,int l,int r,int ql,int qr,ll v){
        if(ql<=l&&r<=qr){
            flag[o]=v;
            sum[o]=v*(r-l+1);
            return;
        }
        int mid=(l+r)/2;
        push_down(o,l,r);
        if(ql<=mid)update(o<<1,l,mid,ql,qr,v);
        if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,v);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
    ll query(int o,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return sum[o];
        int mid=(l+r)/2;
        push_down(o,l,r);
        ll res=0;
        if(ql<=mid)res+=query(o<<1,l,mid,ql,qr);
        if(qr>mid)res+=query(o<<1|1,mid+1,r,ql,qr);
        return res;
    }
}segtree;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<n;i++)scanf("%lld",&k[i]);
    for(int i=2;i<n;i++)k[i]+=k[i-1];
    for(int i=1;i<n;i++)ks[i]=ks[i-1]+k[i];
    segtree.build(1,1,n);
    scanf("%d",&m);
    while(m--){
        char op[5];int l,r;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='s')printf("%lld\n",segtree.query(1,1,n,l,r)+ks[r-1]-(l>=2?ks[l-2]:0));
        else{
            int L=l,R=n,mid,ans=l;
            ll sum=segtree.query(1,1,n,l,l)+r;
           // cout<<"sum="<<sum<<endl;
            while(L<=R){
                mid=(L+R)/2;
               // cout<<"mid="<<mid<<endl;
                if(sum>segtree.query(1,1,n,mid,mid)){
                    ans=mid;
                    L=mid+1;
                }
                else
                    R=mid-1;
            }
           // cout<<"ans="<<ans<<endl;
            segtree.update(1,1,n,l,ans,sum);
        }
    }
    return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部