NOI模拟22(APIO2022)


开题看见都是交互,然后懵逼了,踏下心来做呗!

然后顺序开题,看了半天T1没啥效果,于是就先做T3去了,找到了一个比较简单的做法,分还是挺高的,但是是大众做法,是个人就会的那种

T2,啥也不会了写的暴力,但是势能分析一下,不能缩就停就有60pts了,再小小的搞一下就有100,但是这个挺难的

T1 火星

不会,没改,好像是一个点用两个括号,然后匹配去

T2 游戏

首先我们发现一个点最多被更新k次,于是我们有了nk的做法,也叫势能分析

发现我们每次都缩的话太浪费时间了,我们只需要在成环之后判断就行了,那么我们可以到了一半之后再缩

这里利用了线段树的区间,因为线段树的区间可以保证区间的中点是不降的

并且一个点只会被缩logk次,于是复杂度就对了!!

AC_code
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=3e5+5;
int n,m,l[N],r[N];
vector<int> e[N],re[N];
void init(int n,int m){
    ::n=n;::m=m;
    fo(i,m+1,n)r[i]=n+1;
    fo(i,1,m)l[i]=r[i]=i;
}
bool check(int x,int y);
bool dfs(int x){
    for(int y:e[x])if(check(x,y))return true;
    for(int y:re[x])if(check(y,x))return true;
    return false;
}
bool check(int x,int y){
    if(x<=m&&y<=m)return y<=x;
    if(l[x]>r[y])return true;
    int mx=l[x]+r[x]>>1,my=l[y]+r[y]>>1;
    if(l[x]>my){
        l[y]=my+1;
        if(l[y]==r[y])return true;
        if(dfs(y))return true;
    }
    if(r[y]<=mx){
        r[x]=mx;
        if(l[x]==r[x])return true;
        if(dfs(x))return true;
    }return false;
}
int add_teleporter(int x,int y){
    x++,y++;
    e[x].push_back(y);re[y].push_back(x);
    return check(x,y);
}

T3 排列

朴素的二进制拆分,我们发现太多了

于是合并两个点!!!

AC_code
#include<bits/stdc++.h>
#include "perm.h"
using namespace std;
#define ll long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
vector<int> ans,res,lsh;int n,sta[10005];
vector<int> construct_permutation(long long k){
	ans.clear();res.clear();n=1;
	while(k>=(1ll<<n))ans.push_back(n-1),n++;
	n--;k-=(1ll<<n);int now=1,top=0,sb=0;sta[top]=100;
	fu(i,n-1,0)if(k>>i&1){
		if(top>=2&&i&&(k>>i-1&1)){
			sb++;
			while(ans.size()>i-1)res.push_back(ans.back()),ans.pop_back();
			ans.push_back(sta[top-2]+sb);
			while(res.size())ans.push_back(res.back()),res.pop_back();
			i--;continue;
		}
		sta[++top]=sta[top]+100;
		while(ans.size()>i)res.push_back(ans.back()),ans.pop_back();
		ans.push_back(sta[top]);
		while(res.size())ans.push_back(res.back()),res.pop_back();
	}
	// for(int i:ans)cerr<<i<<" ";cerr<<endl;
	lsh=ans;sort(lsh.begin(),lsh.end());
	for(int &i:ans)i=lower_bound(lsh.begin(),lsh.end(),i)-lsh.begin();
	// for(int i:ans)cerr<<i<<" ";cerr<<endl;
	return ans;
}

原创文章,作者:bd101bd101,如若转载,请注明出处:https://blog.ytso.com/267041.html

(0)
上一篇 2022年6月14日
下一篇 2022年6月14日

相关推荐

发表回复

登录后才能评论