首页 > 其他分享 >Codeforces Round 977 (Div. 2)(B-C2)

Codeforces Round 977 (Div. 2)(B-C2)

时间:2024-10-10 10:13:21浏览次数:6  
标签:977 int st maxn ls C2 Div mx define

B:

感觉最近几题都用了这种继承的思想。然后就把n方转化为一个递推的问题。
我写了一个跟题解不同的做法是取同余也挺巧妙的。

#include<bits/stdc++.h>
using namespace std;
#define CI const int&
#define int long long
const int maxn=2e5+10;
int a[maxn],vis[maxn],cnt[maxn];
void solve(){
    int n,x;cin>>n>>x;
    for(int i=0;i<=n;i++)vis[i]=0,cnt[i]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<=n)vis[a[i]]++;
    }
    for(int i=0;i<=n;i++){
        if(vis[i]==0&&cnt[i%x]==0){
            return cout<<i<<endl,void();
        }
        if(vis[i])vis[i]--;
        else cnt[i%x]--;
        if(vis[i]>0)cnt[i%x]+=vis[i];
    }
}
signed main(){
    int t;cin>>t;while(t--)solve();
}

C1:

甚至不需要发现性质也能写的贪心。

C2:

性质其实就是找一个值在b中第一次出现的顺序是否与a排列顺序相符。
由此很容易发现是严格递增的,然后维护手段也很多。线段树写起来很简单,也算是权值线段树了。
就是得套个set。然后ai,bi还有下标的关系要考虑清楚,还有删除操作。

#include<bits/stdc++.h>
using namespace std;
#define CI const int&
#define int long long
#define ls(x) (x*2)
#define rs(x) (x*2+1)
const int maxn=1e6+10;
int a[maxn],b[maxn],c[maxn],n,m,q;
int mx[maxn],mn[maxn],t[maxn];
set<int>st[maxn];
void push_up(int p){
    mx[p]=max(mx[ls(p)],mx[rs(p)]);
    mn[p]=min(mn[ls(p)],mn[rs(p)]);
    if(t[ls(p)]&&t[rs(p)]&&mx[ls(p)]<mn[rs(p)])t[p]=1;
    else t[p]=0;
}
void upd(int p,int l,int r,int q,int k){
    //cout<<l<<r<<endl;
    if(l==r){
        mx[p]=mn[p]=k;t[p]=1;
        return;
    }
    int mid=(l+r)/2;
    if(q<=mid)upd(ls(p),l,mid,q,k);
    else upd(rs(p),mid+1,r,q,k);
    push_up(p);
    //cout<<p<<' '<<t[p]<<'k'<<endl;
}
void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)st[i].clear();
    for(int i=1;i<=n;i++){
        cin>>a[i],c[a[i]]=i;
        if(st[a[i]].size()==0)st[a[i]].insert(m+i);
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];st[b[i]].insert(i);
    }
    set<int>::iterator it;
    for(int i=1;i<=n;i++){
        it=st[a[i]].begin(),upd(1,1,n,c[a[i]],*it);
    }
    if(t[1])cout<<"Ya"<<endl;
    else cout<<"TIDAK"<<endl;
    while(q--){
        int i,j;cin>>i>>j;
        st[b[i]].erase(i);//
        upd(1,1,n,c[b[i]],*st[b[i]].begin());
        b[i]=j;
        st[j].insert(i);
        it=st[j].begin();
        upd(1,1,n,c[j],*it);
        if(t[1])cout<<"Ya"<<endl;
        else cout<<"TIDAK"<<endl;
    }
}
signed main(){
    int t;cin>>t;while(t--)solve();
}

标签:977,int,st,maxn,ls,C2,Div,mx,define
From: https://www.cnblogs.com/lyrrr/p/18455755

相关文章

  • cf2009 Codeforces Round 971 (Div. 4)
    A.Minimize!签到题。计算\((c-a)+(b-c)\)的最小值,其实值固定的,等于\(b-a\)。inta,b;voidsolve(){cin>>a>>b;cout<<b-a<<endl;}B.Osu!mania签到题。给定一个4k下落式的网格,求#下落顺序。直接数组记录就好了。intn;constintN=500;chars[......
  • codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报
    解题历程:看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后......
  • Codeforces Round 804 (Div. 2)(C - D)
    CC观察题意,模拟样例,首先\(0\)不能动,因为相邻的\(mex\)会改变,然后\(1\)也是如此,所以我们固定了\(0\)和\(1\),设两个指针\(l\)和\(r\)表示固定的位置,那么此时在他们两个中间的数可以随便移动,假设有\(x\)个空位,那么如果\(2\)在里面,\(2\)的选......
  • ERC20智能合约demo
    ERC20智能合约demoERC20.solIERC20.solERC20.sol//SPDX-License-Identifier:MITpragmasolidity^0.8.20;import{IERC20}from"./IERC20.sol";contractERC20isIERC20{mapping(address=>uint256)publicoverridebalanceOf; mapping(address......
  • (概述)TMS320C203PZ、TMS320C203PZA、TMS320C203PZ80、TMS320C203PZ57、TMS320C203PZA57
    TMS320C2x是TMS230C2系列数字信号处理器(DSP)的新一代产品,它采用静态CMOS集成电路制造技术,其结构设计以TMS320C2x系列为基础,并按低功耗进行优化。先进的哈佛结构、片内外围模块、片内存储器和高度专业化指令系统的结合是&#39;C2xx器件工作灵活性和高速度的基础。TMS320C203为100脚PZ......
  • AT_jsc2021_h Shipping 题解
    不算难的一道题。思路考虑原图是一个基环树。首先在树上部分的路径是固定的,我们没有办法抉择。唯一需要考虑的是在环上的那一部分。在环上我们每一个路径有两种选择。如何考虑到所有情况。我们每一次断掉环上的一条边。这样每一个路径就变成固定的了。我们只需要快速计算......
  • [AGC064C] Erase and Divide Game 题解
    DescriptionTakahashi和Aoki玩游戏。先在黑板上写若干个数,由\(N\)个互不相交的区间\([l_i,r_i]\)组成。两人轮流操作,每次操作先删去所有的奇数/偶数,再把剩下的数除以\(2\)(向下取整),无法操作的人输。Takahashi先手,假设两人都采用最优策略,问谁能获胜。\(1\leqN\leq10^......
  • Codeforces Round 970 (Div. 3) D. Sakurako‘s Hobby
     链接cf_Sakurako‘sHobby大意:给一堆点和边,并给出点的颜色,输出每个点能遍历到几个黑点思路:1、这些点边里面有拓扑结构,也有环2、先处理拓扑排序的一些点,依次遍历无父节点的即可,之后就会剩下环3、有环的说明每个点都能去到环内任意一点,那么直接就记录一个sum,然后递归......
  • QC2.0 3.0 4.0 的区别
    一、简介QC,即QuickCharge,是美国高通公司专为配备Qualcomm骁龙处理器的终端而研发的快速充电技术。截至目前,Qualcomm已经发布了四代快速充电技术,分别为QuickCharge1.0,QuickCharge2.0,QuickCharge3.0和QuickCharge4.0。以下图表为大家列出三个版本的快充所能支持的电压,最......
  • Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)
    目录写在前面A签到B贪心,枚举C1贪心C2贪心,枚举DDPE1/E2Kruscal重构树,树上背包写在最后写在前面补题地址:https://codeforces.com/contest/2021。上大分失败呃呃呃呃我不要上班呜呜A签到考虑仅有三个数\(a,b,c(a<b<c)\)时最优操作,手玩下发现最优操作顺序一定是......