开题看见都是交互，然后懵逼了，踏下心来做呗！
然后顺序开题，看了半天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/tech/pnotes/267041.html