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