首页 > 其他分享 >P11186 三目运算

P11186 三目运算

时间:2024-10-13 14:11:08浏览次数:4  
标签:return 运算 int 三目 dfs2 flag P11186 include

P11186 三目运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大模拟,利用 ? 和 : 递归地把范围关系和数值组合。模拟比较麻烦。\(O(n)\) 时间复杂度

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 4e6, M = 101010;

string s;
int n, m;
int idx, cnt, id[M];
PIII res[N];
int x, maxv = 100010;

struct Node
{
    int a, b, flag, x; // flag == 1 / 2 = < >, flag == 0 => 数值点
}g[N];

bool check(char x)
{
    return x >= 48 && x <= 57;
}

int dfs() // 得出条件和数值的关系
{
    int u = ++ idx;
    
    int flag = 0, y = 0;
    while (s[x])
    {
        if (s[x] == '<') flag = 1;
        if (s[x] == '>') flag = 2;
        if (check(s[x])) 
        {
            do {
                y *= 10;
                y += s[x] - '0';
                x ++ ;
            } while (check(s[x]));
            // cout << y << endl;
        }
        if (s[x] == '?') 
        {
            x ++ ;
            break;
        }
        if (s[x] == ':') 
        {
            x ++ ;
            break;
        }
        x ++ ;
    }
    
    
    int z = 0;
    if (flag == 0)
    {
        g[u] = {y, 0, 0};
        // cout << x << ' ' << y << endl;
    }
    else g[u] = {dfs(), dfs(), flag, y};
    return u;
}

void dfs2(int x, int l, int r) // 用关系求出范围内的数值
{
    if (l > r) return ;
    if (x > idx) return ;
    int flag = g[x].flag, y = g[x].x;
    
    if (flag) 
    {
        if (flag == 1)
        {
            
            dfs2(g[x].a, l, y - 1);
            dfs2(g[x].b, y, r);
        }
        else 
        {
            dfs2(g[x].a, y + 1, r);
            dfs2(g[x].b, l, y);
        }
    }
    else 
    {
        // printf("%d %d %d\n", l, r, g[x].a);
        res[ ++ cnt] = {l, {r, g[x].a}};
    }
    
}


int main()
{
    cin >> n >> m;
    cin >> s;
    // cout << s << endl;
    x = 0;
    dfs();
    
    dfs2(1, 0, maxv);
    
    for (int i = 1; i <= cnt; i ++ )
    {
        for (int j = res[i].x; j <= res[i].y.x; j ++ ) // 数值写到对应范围上
            id[j] = res[i].y.y;
    }
    while (m -- )
    {
        int a;
        scanf("%d", &a);
        if (a > maxv) a = maxv; // 利用题目信息可知
        printf("%d\n", id[a]);
    }
    
    return 0;
}

标签:return,运算,int,三目,dfs2,flag,P11186,include
From: https://www.cnblogs.com/blind5883/p/18462250

相关文章

  • javascript学习——算术运算符
    算术运算符运算符是处理数据的基本方法,用来从现有的值得到新的值。JavaScript提供了多种运算符,覆盖了所有主要的运算。概述JavaScript共提供10个算术运算符,用来完成基本的算术运算。加法运算符:x+y减法运算符:x-y乘法运算符:x*y除法运算符:x/y指数运算符:x**y......
  • javascript学习——二进制位运算符
    二进制位运算符概述二进制位运算符用于直接对二进制位进行计算,一共有7个。二进制或运算符(or):符号为|,表示若两个二进制位都为0,则结果为0,否则为1。二进制与运算符(and):符号为&,表示若两个二进制位都为1,则结果为1,否则为0。二进制否运算符(not):符号为~,表示对一个二进制位取反。异或......
  • 数字逻辑电路中的逻辑运算法则
    数字逻辑电路中的逻辑运算法则在数字逻辑电路中,逻辑运算是其核心。通过不同的逻辑运算,电路能够执行复杂的计算任务。本文将介绍几种基本的逻辑运算及其规则:与(AND)、或(OR)、非(NOT)、与非(NAND)、或非(NOR)、异或(XOR)和同或(XNOR),并结合C++和Verilog中的运算符号进行讲解。1.与(AND)运算与......
  • 计算机组成原理之浮点数的加减运算
    计算机组成原理之浮点数的加减运算主要涉及以下几个步骤:1、对阶:由于浮点数的阶码不同,小数点位置不同,不能直接进行尾数加减。首先求两数阶码之差,通过小数阶向大数阶看齐的原则,对阶码小的尾数进行移位(右移),每右移一位,阶码加1,直到两数阶码相等。2、尾数加减:对阶后,尾数的小数点......
  • Leetcode--位运算
     小伙伴们,大家好。今天给大家介绍一下位运算。 首先给大家介绍一下常用的位运算符号: &(按位与) |(按位或)^(按位异或)<<(左移)>>(右移) 以a=4,b=6为例: 4的二进制为100,6的二进制为110(假设前名的0省略) a&b=100(每一位进行运算时如果均为1则该位为1否则为0) a|b=110(每......
  • 数据类型及运算
    数据类型名称字节范围char1(characterorinteger)8bits有符号(signed):-128~127无符号:0~225short2短整数16bitssigned:-32768~327670~65535long4长整数32bitssigned:-2147483648~21474836470~4294967295int4integer......
  • JavaScript-条件运算符
    条件运算符条件运算符主要是通过if和问号(?)实现。if语句if语句后面小括号内是判断条件,之后大括号内是在判断条件为真的情况下执行的语句内容。if后面可以接着跟elseif,也可以跟else,但是else必须放在最后,即所有的if和elseif都执行完了之后才能是else。注意在多个ifelse判断的语句......
  • 运算符的基础
    运算符一:二元运算符publicclassDemo01{publicstaticvoidmain(String[]args){//二元运算符//Ctrl+D:复制当前行到下一行inta=10;intb=20;intc=25;intd=25;System.out.println(a+b);......
  • 信息学奥赛复赛复习15-CSP-J2022-01乘方-数据类型、类型转换、数据类型溢出、指数、模
    PDF文档公众号回复关键字:202410091P8813[CSP-J2022]乘方[题目描述]小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数a和b,求a^b的值是多少。a^b即b个a相乘的值,例如2^3即为3个2相乘,结果为2×2×2=8“简单!”小文心想,同时很快就写出了......
  • JavaScript中的运算符
    一、运算符分类运算符:(operator):也称之为叫操作符。是用来实现赋值、比较和执行运算等功能的符号javaScript中常用的运算符:算数运算符递增和递减运算符比较运算符逻辑运算符赋值运算符1.算数运算符概述:算数运算使用的符号,用于执行两个变量或值得算数运算运算符描述......