#C231101A. 茵蒂克丝(index)

单调栈
题目
发布日期:   2023-11-01
更新日期:   2024-09-23
文章字数:   2k
阅读时长:   11 分

#C231101A. 茵蒂克丝(index)

标签（Label）

  • 单调栈

网址

题目详情 - 茵蒂克丝(index) - Super

题解 - 茵蒂克丝(index) - Super

分析

$\qquad$就是维护单调栈，保证栈内严格单调递减（相等的直接合并），后面暴力拆解输出就好了。

$\qquad$当时就是错在了加入一个数之后没有合并，导致一直出问题。

代码

原来的代码

#include<bits/stdc++.h>
#include<queue>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define Fi first
#define Se second
inline int input(){int x;return cin>>x,x;}
const int inf = 30;
const int N = 1012345;
bool ST;

int n,k,a[N];

int lst[N],nxt[N],id[N],su[N];//链表 
vector<int> ans[N];
queue<P> q;
bitset<N> vst;

void Check(int x){
	if(vst[x]) return; 
	while(su[lst[x]]>su[x] && su[x]<su[nxt[x]] && (lst[x]!=0 || nxt[x]!=n+1))
		ans[id[x]].emplace_back(su[x]),su[x]++;
	if(su[x]==su[nxt[x]] && su[lst[x]]>su[x]) q.push({x,nxt[x]});
	if(su[x]==su[lst[x]] && su[nxt[x]]>su[x]) q.push({lst[x],x});
}

void Solve(){
	For(i,1,n){
		while(su[i-1]>su[i] && su[i]<su[i+1])
			ans[i].emplace_back(su[i]),su[i]++;
//		if(su[i]==su[i+1] && su[i-1]>su[i]) q.push({i,i+1});
//		if(su[i]==su[i-1] && su[i+1]>su[i]) q.push({i-1,i});
	}For(i,1,n-1){
		if(su[i]==su[i+1] && su[i-1]>su[i])
			q.push({i,i+1});
	}For(i,2,n){
		if(su[i]==su[i-1] && su[i+1]>su[i])
			q.push({i-1,i});
	}while(q.size()){
		int x=q.front().Fi,y=q.front().Se;q.pop(); 
//		cout<<x<<' '<<y<<'\n';
		if(!vst[x] && !vst[y]){//如果此时x,y都没有合成 
			nxt[x]=nxt[y],lst[nxt[y]]=x,su[x]++;
			id[x]=id[y],vst[y]=true;//保证id表示末尾 
			Check(x);Check(lst[x]);Check(nxt[x]);//前后有可能可以合成 
		}
	}
}

int pow2[36];//最多操作多少次，输出时请输出pow2[i]+1个零 
void Fix(int x){
	if(x==0) return cout<<"0 ",void();
	int er=pow2[x];
//	printf("x=%d 2^x=%d k=%d\n",x,er,k);
	if(er > k){
		k-=1;//分成2份
		if(k==0) return cout<<x-1<<' '<<x-1<<' ',void();
		int ser=pow2[x-1];
//		printf("x-1=%d 2^(x-1)=%d k=%d\n",x-1,ser,k);
		if(ser > k) Fix(x-1),cout<<x-1<<' ';else
		if(ser == k){For(i,1,k+1) cout<<"0 ";cout<<x-1<<' ';return k=0,void();}else
		if(ser < k){For(i,1,ser+1) cout<<"0 ";k-=ser,Fix(x-1);return;}
	}else 
	if(er == k){
		For(i,1,k+1) cout<<"0 ";
		return k=0,void();
	}else
	if(er < k){
		For(i,1,er+1) cout<<"0 ";
		return k-=er,void();
	}
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	string str("index");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	pow2[0]=1;For(i,1,30) pow2[i]=pow2[i-1]*2;
	pow2[0]=0;For(i,1,30) pow2[i]--;
	
	cin>>n>>k;For(i,1,n) a[i]=input();
	//预处理链表
	For(i,1,n) lst[i]=i-1;su[0]=inf,vst[n+1]=true;//注意: 不是一个环 
	For(i,1,n) nxt[i]=i+1;su[n+1]=inf,vst[0]=true;
	For(i,1,n) id[i]=i,su[i]=a[i];
	//找到所有元素
	Solve();
	//拆分
	For(i,1,n) k-=ans[i].size();
	for(int i=1;i<=n ;i++){
		cout<<a[i]<<' ';
		for(auto co:ans[i]){
			if(k) Fix(co);
			else cout<<co<<' ';
		}
	}return 0; 
}

$\qquad$可见，为了一点小优化，我确实付出了 $1.5hour$ 的心血，$Solve()$函数与后面的输出部分占用了大量的时间空间。其实应该先推到尽量完美，并不是所有的“正解”都很好实现，之后应该掌握做题策略，否则只会浪费更多时间。

我的代码

#include<bits/stdc++.h>
#include<queue>
#include<stack>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define Fi first
#define Se second
inline int input(){int x;return cin>>x,x;}
const int inf = 30;
const int N = 1012345;
bool ST;

int n,k,a[N];

vector<int> ans[N];
stack<P> st;
bitset<N> vst;
void Solve(){
	For(i,1,n){
		while(st.size() && st.top().Fi<a[i]){
			int x=st.top().Fi,id=st.top().Se;st.pop();
			ans[id].emplace_back(x);
			int psh=x+1;
			while(st.size() && st.top().Fi==psh){
				st.pop();psh++;
			}st.push({psh,id});
		}
		int psh=a[i];
		while(st.size() && st.top().Fi==psh){
			st.pop();psh++;
		}st.push({psh,i});
	}
	while(st.size() && st.top().Fi!=30){
		int x=st.top().Fi,id=st.top().Se;st.pop();
		ans[id].emplace_back(x);
		
		int psh=x+1;
		while(st.size() && st.top().Fi==psh){
			st.pop();psh++;
		}st.push({psh,id});
	}
}

queue<int> que;
bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	string str("index");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	
	cin>>n>>k;For(i,1,n) a[i]=input();
	//找到所有元素
	Solve();
	//拆分
	For(i,1,n) k-=ans[i].size();
	For(i,1,n){
		cout<<a[i]<<' ';
		for(auto x:ans[i]){
			que.push(x);
			while(que.front()!=0 && k){
				int y=que.front();que.pop();
				que.push(y-1),que.push(y-1);
				k--;
			}while(que.size()) cout<<que.front()<<' ',que.pop();
		}
	}return 0; 
}

题解代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vint;
typedef vector<vint> vvint;


int read() {
    int a = 0, b = 0;
    char c = getchar();

    while (c < '0' || c > '9')
        b ^= (c == '-'), c = getchar();

    while (c >= '0' && c <= '9')
        a = a * 10 - 48 + c, c = getchar();

    return b ? -a : a;
}

const int N = 1000005;
int n, k, a[N];
vint in[N];

struct dat {
    int v, l, r;
};

void ot(int v) {
    if (v == 0 || k == 0) {
        cout << v << ' ';
        return;
    }

    --k;
    ot(v - 1);
    ot(v - 1);
}

int main() {
    freopen("index.in","r",stdin);
    freopen("index.out","w",stdout);
    n = read(), k = read();

    for (int i = 0; i < n; ++i)
        a[i] = read();

    vector<dat> d(n);

    for (int i = 0; i < n; ++i)
        d[i] = {a[i], i, i};

    for (int t = 0; t < 30; ++t) {
        int m = d.size();
        vector<dat> nd;

        for (int i = 0, c = 0; i < m; ++i) {
            c += d[i].v == t;

            if (d[i].v != t)
                nd.push_back(d[i]);

            if (d[i].v == t && (i + 1 == m || d[i + 1].v != t)) {
                int L = i - c + 1;

                for (int j = L; j + 1 <= i; j += 2)
                    nd.push_back({t + 1, d[j].l, d[j + 1].r});

                if (c & 1) {
                    nd.push_back({t + 1, d[i].l, d[i].r});
                    in[d[i].r].push_back(t);
                    --k;
                }

                c = 0;
            }
        }

        d.swap(nd);
    }

    assert(k >= 0);

    for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';

        for (int v : in[i])
            ot(v);
    }

    cout << '\n';
    assert(k == 0);
    return 0;
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.iohttps://wolfdeer62456.github.io/2023/11/01/C231101A-%E8%8C%B5%E8%92%82%E5%85%8B%E4%B8%9D-index/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
单调栈
赏
  目录