首页 > 其他分享 >NOIP2023模拟16联测37 D. 小猫吃火龙果

NOIP2023模拟16联测37 D. 小猫吃火龙果

时间:2023-11-10 22:11:38浏览次数:37  
标签:16 37 while 联测 火龙果 id block

NOIP2023模拟16联测37 D. 小猫吃火龙果

目录

题目大意

有 \(n\) 个物品 \(A\) , \(B\) , \(C\) ,\(A\) 吃 \(B\),\(B\) 吃 \(C\),\(C\) 吃 \(A\),有两种操作,给 \([ l , r ]\) 的 \(x , y\) 互换,求出经过操作后得出什么。

\(n , m \le 2\times10^5\)

思路

分块

维护一个状态 \(c_i\) 表示这个块的 \(A , B , C\) 分别变成了什么。

再维护一个 \(to_{id , x , y}\) 第 \(id\) 块,状态为 \(x\),把 \(y\) 带进去会带出来什么。

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define get_next(now , x) (now == (x + 1) % 3 ? x : now)
using namespace std;
const int N = 2e5 + 5;
int n , m , a[N] , block , to[N][6][3] , t[N];
int c[6][3] = {{0 , 1 , 2} , {0 , 2 , 1} , {1 , 0 , 2} , {1 , 2 , 0} , {2 , 0 , 1} , {2 , 1 , 0}};
int b[6][3] = {{2 , 5 , 1} , {3 , 4 , 0} , {0 , 3 , 4} , {1 , 2 , 5} , {5 , 1 , 2} , {4 , 0 , 3}};
inline int read () {
    char ch = getchar ();
    while (ch != 'A' && ch != 'B' && ch != 'C') ch = getchar ();
    return ch - 'A';
}
// inline int get_next (int now , int x) {
//     if (now == (x + 1) % 3) return x;
//     else return now;
// }
inline void updata (int id) {
    int l = id * block + 1 , r = min ((id + 1) * block , n);
    fu (i , 0 , 5) {
        fu (j , 0 , 2) {
            to[id][i][j] = j;
            fu (k , l , r) 
                to[id][i][j] = get_next (to[id][i][j] , c[i][a[k]]);
        }
    }
}
inline void renew (int id) {
    int l = id * block + 1 , r = min ((id + 1) * block , n);
    fu (i , l , r) a[i] = c[t[id]][a[i]];
    t[id] = 0;
}
inline int rd () {
    int val = 0;
    char ch = getchar ();
    while (ch < '0' || ch > '9') ch = getchar ();
    while (ch >= '0' && ch <= '9') {
        val = val * 10 + (ch - '0');
        ch = getchar ();
    }
    return val;
}
int main () {
    freopen ("training.in" , "r" , stdin);
    freopen ("training.out" , "w" , stdout);
    int x , y , l , r , op , minr , id , type;
    n = rd () , m = rd ();
    fu (i , 1 , n) a[i] = read ();
    if(n>100)block = sqrt (n / 12);
    else block=sqrt(n);
    fu (i , 0 , (n + block - 1) / block) 
        updata (i);
    while (m --) {
        op = rd () , l = rd () , r = rd ();
        if (op) {
            x = read ();
            id = (l - 1) / block;
            minr = min ((l - 1) / block * block + block , r);
            while (l <= minr) {
                x = get_next (x , c[t[id]][a[l]]);
                l ++;
            }
            while (l <= r - block + 1) {
                id = (l - 1) / block;
                x = to[id][t[id]][x];
                l += block;
            }
            id = (l - 1) / block;
            while (l <= r) {
                x = get_next (x , c[t[id]][a[l]]);
                l ++;
            }
            printf ("%c\n" , x + 'A');
        }
        else {
            x = read () , y = read ();
            if (x == y) continue;
            if (x > y) swap (x , y);
            id = (l - 1) / block;
            minr = min ((l - 1) / block * block + block , r);
            type = (x == 0 ? y == 1 ? 0 : 1 : 2);
            renew (id);
            while (l <= minr) {
                if (a[l] == x) a[l] = y;
                else if (a[l] == y) a[l] = x;
                l ++;
            }
            updata (id);
            while (l <= r- block + 1) {
                id = (l - 1) / block;
                t[id] = b[t[id]][type];
                l += block;
            }
            renew (id = (l - 1) / block);
            while (l <= r) {
                if (a[l] == x) a[l] = y;
                else if (a[l] == y) a[l] = x;
                l ++;
            }
            updata (id);
        }
    }
    return 0;
}

标签:16,37,while,联测,火龙果,id,block
From: https://www.cnblogs.com/2020fengziyang/p/17825204.html

相关文章

  • 10/16
    下午学习了程序的异常处理,也就是软件工程中维护的最重要一环。接着又又又是王老师的简单课后测试,两节课我只完成到了手动输入算式的部分,因为随机输出算式的部分插入不正确,导致页面一直出不来随机出题。Java异常处理异常是程序中的一些错误,但并不是所有的错误都是异常,并且错误有......
  • Linux命令(116)之logger
    linux命令之logger1.logger介绍linux命令logger是一个shell命令接口,通过该接口使用rsyslog的系统日志模块可以向系统日志文件(自定义日志文件)写入一行信息2.logger用法logger[参数][message]logger参数参数说明-i记录进程ID-t在日志中的每一行添加一个标签-p指定自定义的日志设......
  • JAVA生成16位唯一字符串
      importlombok.extern.slf4j.Slf4j;importjava.util.Random;importjava.util.UUID;publicclassRandomUtils{privatestaticlonggetRandom(longn){longmin=1,max=9;for(inti=1;i<n;i++){min*=1......
  • 16、Flink 的table api与sql之连接外部系统: 读写外部系统的连接器和格式以及FileSyst
    文章目录Flink系列文章一、Table&SQLConnectors1、概述2、支持的外部连接3、使用示例:kafka4、Transformtableconnector/formatresources5、SchemaMapping6、Metadata7、PrimaryKey8、TimeAttributes9、ProctimeAttributes10、RowtimeAttributes11、完整示例1)、建表2)、......
  • gitlab由16.4.1升级到16.4.2后样式丢失的处理方法,升级16.5.1和16.5.2 都会出同样的问
    gitlab由16.4.1升级到16.4.2后,主页样式丢失的处理方法1.通过chrome的F12功能,通过报错可以看到多个文件找不到的问题,共计4个CSS文件,1个JS文件,一个SVG文件。更新后正常2.处理办法,在这个目录(/opt/gitlab/embedded/service/gitlab-rails/public/)下,逐个找到对应的文件,并拷贝找不到......
  • linux ImageMagick convert 报错 convert-im6.q16***
    在linux批量处理图片时候报一下错误,导致图片无法按要求转化,运行的命令如下:convert**.jpg-resize512x512new.jpg报错:convert-im6.q16:cacheresourcesexhausted`*.jpg'@error/cache.c/OpenPixelCache/4083.convert-im6.q16:noimagesdefined`./zoom/113.jpg'@erro......
  • 【杂题乱写】AtCoder-ARC116
    AtCoder-ARC116_CMultipleSequences朴素DP是设\(f_{i,j}\)表示第\(i\)个位置填\(j\)的方案数,时间复杂度\(O(n^2\logV)\)。考虑求出元素都不同序列个数,再根据长度乘组合数,这样长度是\(O(\logV)\)的,复杂度\(O(n\log^2V)\)。提交记录:Submission-AtCoder......
  • 09_LCD1602调试工具
    LCD1602调试工具编写代码LCD1602.c#include<REGX52.H>//引脚配置:sbitLCD_RS=P2^6;sbitLCD_RW=P2^5;sbitLCD_EN=P2^7;#defineLCD_DataPortP0//函数定义:/***@briefLCD1602延时函数,12MHz调用可延时1ms*@param无*@retval无*/voidLCD_Delay(vo......
  • [Python]PIL-CVE-2018-16509 复现
    [Python]PIL-CVE-2018-16509复现这个问题跟上一个差不多。exp:%!PS-Adobe-3.0EPSF-3.0%%BoundingBox:-0-0100100userdict/setpagedeviceundefsavelegal{nullrestore}stopped{pop}if{legal}stopped{pop}ifrestoremark/OutputFile(%pipe%pytho......
  • 表碎片整理时shrink和move如何选择 --高水位回收 转:http://blog.itpub.net/29821
    整理表碎片通常的方法是move表,当然move是不能在线进行的,而且move后相应的索引也会失效,oracle针对上述不足,在10g时加入了shrink,那这个方法能不能在生产中使用呢?     shrink的一个优点是能在线进行,不影响表上的DML操作,当然,并发的DML操作在shrink结束的时刻会出现短暂的block;s......