当前位置：网站首页>HDU - 3183 A Magic Lamp Segment Tree

HDU - 3183 A Magic Lamp Segment Tree

2022-08-09 07:03:00 【swust_fang】

Topic link

The meaning of the title: The number after deleting k values ​​from the number string is the smallest, not counting the leading 0

Idea: In fact, it is the smallest lexicographical order, then we must determine the smallest value one by one, then for the i bit, in fact, find out whether the smallest number in the i+1~i+k bit is more than the current position.Small, if any, delete all the middle ones.So in fact, it is to find the minimum subscript of the minimum value of i+1~i+1+k on the right side of a certain i, and we can use the line segment tree to maintain it.Hahaha~ I asked the senior, the senior called me mentally retarded (hh

In fact, the line segment tree maintains a node, just reload it~

It's a pity that there are still n squares of solutions to the problem.

AC Code:

#include#include#include#include#include#include#include#include#include#include#include#define myself i,l,r#define lson i<<1#define rson i<<1|1#define Lson i<<1,l,mid#define Rson i<<1|1,mid+1,r#define half (l+r)/2#define inff 0x3f3f3f3f#define lowbit(x) x&(-x)#define PI 3.14159265358979323846#define min4(a, b, c, d) min(min(a,b),min(c,d))#define min3(x, y, z) min(min(x,y),min(y,z))#define pii make_pair#define pr pair#define li __int128//void print(li x) {if(x>9) print(x/10);putchar(x%10+48);}const int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};typedef long long ll;typedef unsigned long long ull;const ll inFF = 9223372036854775807;const int maxn=1e5+5;const ll mod=1e9+7;using namespace std;int a[maxn];char s[maxn];struct node{int val,pos;bool friend operator<(node ​​s,node e){if(s.val==e.val) return s.pos=r) return tree[i];int mid=half;if(qr<=mid) return query(Lson,ql,qr);else if(ql>mid) return query(Rson,ql,qr);else{node s=query(Lson,ql,mid);node e=query(Rson,mid+1,qr);if(s>k;build(1,1,n);int c=k;for(int i=1;i<=n&&c>0;i++){if(c>=n-i+1){for(int j=i;j<=n;j++)vis[j]=1;break;}if(a[i]==0){vis[i]=0;continue;}node now=query(1,1,n,i+1,min(i+c,n));if(now.val

原网站

版权声明
本文为[swust_fang]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/221/202208090700344380.html

边栏推荐

猜你喜欢

随机推荐