打得抽象。T3,T4放俩难的板子。由于是MX的题，就不放题意了。
邻间的骰子之舞
发现复制操作不会超过\(64\)次，而粘贴操作肯定是越均匀越好，直接二分暴力跑就行了。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
// FILE *InFile = stdin,*OutFile = stdout;
FILE *InFile = freopen("dice.in","r",stdin),*OutFile = freopen("dice.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int ull
int n,x,y,mx;
inline bool check(int mid){
rep(i,0,mx,1){
if(i*x >= mid) break;
if(!i){
if((mid - i*x)/y + 1 > n) return true;
continue;
}
int j = (mid - i * x) / y,val = 1,aver = j / (i + 1),last = j-aver*(i + 1);
rep(k,0,i,1){
if (last > 0) val += (aver + 1)*val,last --;
else val += aver * val;
if (val > n) return true;
}
}
return false;
}
inline void solve(){
cin>>n>>x>>y;mx = log2(n);
int l = 1,r = 1e19,ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) ans = mid,r = mid - 1;
else l = mid + 1;
}
cout<<ans+x<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
星海浮沉录
用\(set\)维护每个数出现的位置，用\(multiset\)维护每个数可以贡献的长度，用线段树维护区间最大值，线段树上二分即可。\(set\)插入哨兵节点会更方便一点。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
// FILE *InFile = stdin,*OutFile = stdout;
FILE *InFile = freopen("star.in","r",stdin),*OutFile = freopen("star.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
int n,q,a[N];
set<int> pos[N];
multiset<int> mx[N];
#define ins insert
struct Segment_Tree{
struct segment_tree{
int l,r,val;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define val(x) tree[x].val
}tree[N<<2];
inline void pushup(int k){val(k) = max(val(k<<1),val(k<<1|1));}
void build(int k,int l,int r){
l(k) = l,r(k) = r;
if(l == r) return val(k) = *mx[l].rbegin(),void();
int mid = (l + r) >> 1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
pushup(k);
}
void upd(int k,int pos,int val){
if(l(k) == r(k)) return val(k) = val,void();
int mid = (l(k) + r(k)) >> 1;
if(pos <= mid) upd(k<<1,pos,val);else upd(k<<1|1,pos,val);
pushup(k);
}
int qry(int k,int x){
if(l(k) == r(k)) return l(k);
int ls = k<<1;
if(val(ls) >= x) return qry(k<<1,x);
else return qry(k<<1|1,x);
}
}T;
inline void solve(){
cin>>n>>q;
rep(i,1,n,1) cin>>a[i];
rep(i,0,n+1,1) pos[i].ins(0);
rep(i,1,n,1){
auto it = pos[a[i]].ins(i).first;
it--;mx[a[i]].ins(i - *it - 1);
}
rep(i,0,n+1,1){
auto it = pos[i].ins(n+1).first;
it--;mx[i].ins(n - *it);
}
T.build(1,0,n+1);
auto del = [&](int val,int s){
auto it = pos[val].lower_bound(s);
int p1,p2;
it--;mx[val].erase(mx[val].lower_bound(s-*it-1));p1 = *it;it++;
it++;mx[val].erase(mx[val].lower_bound(*it-s-1));p2 = *it;
mx[val].insert(p2-p1-1);
pos[val].erase(s);
};
auto add = [&](int val,int s){
auto it = pos[val].upper_bound(s);
int p1,p2;
p2 = *it;it--;p1 = *it;
mx[val].erase(mx[val].lower_bound(p2-p1-1));
mx[val].insert(p2-s-1);
mx[val].insert(s-p1-1);
pos[val].ins(s);
};
auto change = [&](int val,int s,int t){
del(val,s);add(val,t);
T.upd(1,val,*mx[val].rbegin());
};
rep(test,1,q,1){
int op,x;cin>>op>>x;
if(op == 1){
if(a[x] == a[x+1]) continue;
change(a[x],x,x+1);
change(a[x+1],x+1,x);
swap(a[x],a[x+1]);
}
else cout<<T.qry(1,x)<<'\n';
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
勾指起誓
如题目名，勾誓。FMT板子，不会。
第八交响曲
双调排序板子，不会的自行bdfs吧。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
// FILE *InFile = stdin,*OutFile = stdout;
FILE *InFile = freopen("symphony.in","r",stdin),*OutFile = freopen("symphony.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
int n,lgn;
inline void solve(){
cin>>n;lgn = 1<<__lg(n-1)+1;
auto print = [](int a,int b){if(b <= n) cout<<"CMPSWP R"<<a<<" R"<<b<<' ';};
cout<<__lg(lgn)*(__lg(lgn)+1)/2<<'\n';
rep(i,1,lgn-1,i){
rep(j,1,lgn,i*2) rep(k,0,i-1,1) print(j+k,j+i*2-1-k);
cout<<'\n';
for(int j = i/2;j >= 1;j /= 2){
rep(k,1,lgn,j*2) rep(p,0,j-1,1) print(k+p,k+j+p);
cout<<'\n';
}
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
p
