首页 > 其他分享 >100道cf2000分

100道cf2000分

时间:2022-11-12 11:25:33浏览次数:71  
标签:node int tt mid read cf2000 ask 100

链接

 

考虑线段树维护区间里已配对的括号数,左边还没配对的右括号数,右边还没配对的左括号数。
区间询问,合并两个子区间即可。
int n;
char s[1000010];
struct node 
{
    int c,l,r;
}o[4000010];
node merge(node l,node r)
{
    node tt;
    
    tt.c=l.c+r.c+min(l.l,r.r);
    tt.l=max(0,l.l-r.r)+r.l;
    tt.r=l.r+max(0,r.r-l.l);
    return tt;
}
void build(int x,int l,int r)
{
    if(l==r)
    {
        o[x].c=0;
        if(s[l]=='(')
            o[x].l=1;
        else
            o[x].r=1;
            
        return ;
    }
    int mid=(l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    o[x]=merge(o[x*2],o[x*2+1]);
    
}
node ask(int x,int l,int r,int tl,int tr)
{
    if(tl<=l&&r<=tr)
        return o[x];
    int mid=(l+r)/2;
    if(tr<=mid)
        return ask(x*2,l,mid,tl,tr);
    if(tl>mid)
        return ask(x*2+1,mid+1,r,tl,tr);
    return merge(ask(x*2,l,mid,tl,tr),ask(x*2+1,mid+1,r,tl,tr));
}    
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    build(1,1,n);    
    for(int q=read();q;q--)
    {
        int l=read(),r=read();
        printf("%d\n",ask(1,1,n,l,r).c*2);
    }
}
380C
考虑黑白格地设置,令奇数的上下左右都是偶数,偶数的上下左右都是奇数。

int n,m,x;
void work()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            x=read();
            if((i+j)%2==x%2)
                printf("%d ",x);
            else
                printf("%d ",x+1);
        }
        printf("\n");
    }
}
int main()
{
    for(int t=read();t;t--)
        work();
}
1438C

 

标签:node,int,tt,mid,read,cf2000,ask,100
From: https://www.cnblogs.com/qywyt/p/16882966.html

相关文章

  • #10077. 「一本通 3.2 练习 3」最短路计数
    问1~n的最短路有几个 #include<iostream>#include<cstring>#include<queue>usingnamespacestd;constintN=1e6+2,M=2e6+2;constintinf=0x3f3f3f3f,m......
  • #10075. 「一本通 3.2 练习 1」农场派对
    图上每个点有一头牛,现在牛群聚集到点X上聚会,然后又回到各自的点,而且牛只走最短路径问所有最短路中最长的一条(路径包含来回) 正反跑一次 spfa(X), spfa(i), an......
  • #10074. 「一本通 3.2 例 3」架设电话线
    在加权无向图上求出一条从1号结点到N号结点的路径,使路径上第K+1大的边权尽量小 二分答案md,判断1~n是否存在一条路径,花费不超过md把w<=md的边看作0,否则看作1......
  • 【Vuejs】1000- 一步一步实现 Vue 3 Reactivity
    Vue3中的响应式原理可谓是非常之重要,通过学习Vue3的响应式原理,不仅能让我们学习到Vue.js的一些设计模式和思想,还能「帮助我们提高项目开发效率和代码调试能力」。在这......
  • loj #10069. 「一本通 3.1 练习 4」Tree
    给你一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有K条白色边的生成树。题目保证有解  二分一个增加量md, 给每个白边权值加md,跑一下kruskal,......
  • MBR30100CT-ASEMI大功率肖特基二极管MBR30100CT
    编辑-ZMBR30100CT在TO-220AB封装里采用的2个芯片,其尺寸都是122MIL,是一款大功率肖特基二极管。MBR30100CT的浪涌电流Ifsm为275A,漏电流(Ir)为0.05mA,其工作时耐温度范围为-65~1......
  • #10067. 「一本通 3.1 练习 2」构造完全图
    给一颗最小生成树,构造一个权和最小的完全图  无疑是贪心,模仿kruskal做法 考虑一条树边,它连接了两个块,在块之间的连线中是最小的,构造完全图后,考虑所有这些连线,权值应......
  • loj#10064 黑暗城堡
     求图中的最短路径生成树有多少个?(该生成树中的任意点i,i到1的距离和 原图中的i到1的最短距离相等  跑所有点到1的单源最短路,d[i] ifd[i]==d[y]+z,那么z这个路......
  • SBT10100VCT-ASEMI肖特基二极管SBT10100VCT
    编辑:llSBT10100VCT-ASEMI肖特基二极管SBT10100VCT型号:SBT10100VCT品牌:ASEMI封装:TO-220AB特性:肖特基二极管正向电流:10A反向耐压:100V恢复时间:5ns引脚数量:3芯片个数:2芯片尺寸:58......
  • SBT10100VCT-ASEMI肖特基二极管SBT10100VCT
    编辑:llSBT10100VCT-ASEMI肖特基二极管SBT10100VCT型号:SBT10100VCT品牌:ASEMI封装:TO-220AB特性:肖特基二极管正向电流:10A反向耐压:100V恢复时间:5ns引脚数量:3芯片个数......