前言：wssb
Dalton the Teacher
题意：给定一个排列，每次可以交换两个元素，求使得 \(\forall i\in[1,n],a_i\neq i\) 的最小操作数。
一次可以操作两个元素，故答案为 \(\lceil\frac{\sum_{i=1}^n[a_i=i]}{2}\rceil\)
Longest Divisors Interval
题意：给定若干个 \(n\)，求最长的区间 \([l,r]\)，使得 \(lcm(l,l+1,……,r)|n\)
wssb，这个题猜了结论不敢写，推NM个组合数在乱整
引理：在最优方案中，必定存在一种，使得 \(l=1\)
证明：
根据模运算的周期性，在任意区间 \([l,r]\) 的整数中，有且仅有一个数是 \(r-l+1\) 的倍数。
扩展一下，变为在任意区间 \([l,r]\) 中，最少有一个数是 \(k (1\le k\le r-l+1)\) 的倍数。
那么，接着变为 \(lcm(1,\dots,r-l+1)|lcm(l,\dots ,r)\)
由此，若存在 \([l,r]\)，使得 \(lcm(l,\dots,r)|n\)，而 \(lcm(1\dots r-l+1)|lcm(l,\dots r)\)。
故有 \(lcm(1\dots r-l+1)|n\)，所以 \([1,r-l+1]\) 是一个等长等效的解。
而又有： \(\forall i\in[l,r],i|lcm(l,\dots r)\)
由此，我们从1开始枚举，直到不是 \(n\) 的约数为止。最多枚举50个·。
Dual
直接讲C2。
题意：有 \(n (1\le n\le 20)\) 个数，其中 \(-20\le a_i\le 20\)，每一次可以令 \(a_i\longleftarrow a_i+a_j(1\le i,j\le n)\)，注意 \(i=j\) 也是可行的。求使得原序列单调不减的操作方案。注意你的操作方案不能超过31次。
C1，C2打了两个完全不同的做法，谁知道两个做法粘在一起就过了。。
对于构造题，可以拆分问题：一个简化的形式+将一般问题化为简化的形式。我们一般先考虑前者再考虑后者。这个思想可以在后面的 F 见到
首先来考虑只有正数/负数的情况，显然我们可以做前/后缀和以最多 \(n-1\) 次的代价完成任务。那么我们还剩下 \(32-n\) 次操作。
然后考虑将正常情况化为正数/负数。有两个办法：
- 找到最大/最小值，将负/正数加上它使得其变为负数
- 将一个值自增最多5次再将正负数化掉
注意到操作1的次数是 \(c\)，这取决于最大/最小值的最值关系
而操作2的次数是 \(5+c_{\min}\)，将正数负数较少的那个化掉。
则当 \(n\) 取最大值时，最终还有 \(12\) 次操作。此时有两个选择： \(c\le 12\)，或者 \(5+c_{\min}\)
这是最关键的部分：当 \(c\le 12\) 时，我们用操作1解决问题，否则必然有 \(c_{\min}\le 7\implies 5+c_{\min}\le 12\)。
所以根据 \(c\) 的值选择两种操作即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
#define N 505050
int n,m,a[505];
struct node{
int x,y;
}ans[505];
int tot=0;
signed main(){
int t;cin>>t;
while(t--){
cin>>n;int c1=0,c2=0;tot=0;for(int i=1;i<=n;i++)cin>>a[i];
int mn=0x3f3f3f3f,mx=-0x3f3f3f3f;
for(int i=1;i<=n;i++)mx=max(mx,a[i]),mn=min(mn,a[i]);
if(mn>=0){
for(int i=2;i<=n;i++)ans[++tot]={i,i-1};
}
else if(mx<=0){
for(int i=n-1;i;--i)ans[++tot]=(node){i,i+1};
}
else {
for(int i=1;i<=n;i++)c1+=(a[i]<0),c2+=(a[i]>0);
if(12<c1){
int id=-1;
for(int i=1;i<=n;++i)if(a[i]==mn){
id=i;break;
}
while(mx+mn>0){
ans[++tot]={id,id};mn+=mn;
}
a[id]=mn;
for(int i=1;i<n;i++)if(a[i]>0)ans[++tot]={i,id},a[i]+=mn;
for(int i=n-1;i;i--)if(a[i]>a[i+1])a[i]+=a[i+1],ans[++tot]={i,i+1};
cout<<tot<<" \n";
for(int i=1;i<=tot;i++)cout<<ans[i].x<<" "<<ans[i].y<<"\n";
continue;
}
else if(12<c2){
int id=-1;
for(int i=n;i;--i)if(a[i]==mx){
id=i;break;
}
while(mx+mn<0){
ans[++tot]={id,id};mx+=mx;
}
a[id]=mx;
for(int i=2;i<=n;i++)if(a[i]<0)ans[++tot]={i,id},a[i]+=mx;
for(int i=2;i<=n;i++)if(a[i]<a[i-1])a[i]+=a[i-1],ans[++tot]={i,i-1};
}
else {
int mn=0x3f3f3f3f,mx=-0x3f3f3f3f;
for(int i=1;i<=n;i++)mx=max(mx,a[i]),mn=min(mn,a[i]);
if(mx+mn>0){
int id=-1;
for(int i=1;i<=n;i++){
if(a[i]==mx){
id=i;break;
}
}
for(int i=1;i<=n;i++)if(a[i]<0){
ans[++tot]=(node){i,id};
}
for(int i=2;i<=n;i++)ans[++tot]={i,i-1};
}
else{
int id=-1;
for(int i=1;i<=n;i++){
if(a[i]==mn){
id=i;break;
}
}
for(int i=1;i<=n;i++)if(a[i]>0){
ans[++tot]=(node){i,id};
}
for(int i=n-1;i;--i)ans[++tot]=(node){i,i+1};
}
}
}
cout<<tot<<" \n";
for(int i=1;i<=tot;i++)cout<<ans[i].x<<" "<<ans[i].y<<"\n";
}
}
Earn or Unlock
题意：最初有一堆牌，自顶向下编号 \(1\sim n\)，最初只有第一张牌是解锁了的，每一次操作选择最顶上的牌 \(i\)(如果没有解锁亦或者牌拿完了就结束游戏)，选择以下两种操作：
- 按顺序解锁 \(a_i\) 张牌(已解锁的牌跳过，总解锁 \(a_i\) 张)。
- 获得收益 \(a_i\)。
求最后所得最大收益。
题解：
已经解锁的牌肯定都要用完。
考虑一种均摊的思想，其实选择操作一，本质上是选择将解锁的和自己总共 \(i+1\) 张牌的收益减一。显然代价是一样的。由此可以推出：
若解锁了 \(k\) 张牌，则答案为 \(1+\sum_{i=1}^k(a_i-1)\)。这是因第一张牌本身已经解锁。所以，我们只需要求出哪些 \(k\) 可以被解锁即可。
这本质上是求 \(a_1\sim a_n\) 可以凑出哪些数，但有一定限制。
设 \(f_{i,j}\) 表示前 \(i\) 个数是否可以凑出 \(j\)，则有 \(f_{i,j}=f_{i-1,j}|f_{i-1,j-a_i}\)
用二进制数 \(f_i\) 表示的话，则有 \(f_i=f_{i-1}|(f_{i-1}\times 2^{a_i})\)。保留原来的，或者将原来的所有牌数加上 \(a_i\)
但考虑是不是真的可以这样转移呢？注意到能用 \(a_i\) 转移，则代表其原本可以凑出的数 \(\ge i\)。
所以我们要求转移时 \(f_{i-1}\) 的 \(i-1\) 位必须全部为0，可以使用另一个答案数组记录当前位的答案，然后在更新 \(f_i\) 后将 \(f_{i,i}\) 赋值为 0
注意到可能我们会将所有牌拿完而还有剩余次数，所以多扩展一倍，维护到 \(f_{2n}\)。当然 \(a_i=0(i>n)\)
#include<bitset>
#include<iostream>
#define N 205050
#define int long long
using namespace std;
bitset<N>f;
int a[N],n,s[N],ans[N];
signed main(){
ios::sync_with_stdio(false);
cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
s[0]=1;
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]-1;
f[1]=1;
for(int i=1;i<=n;i++){
f|=(f<<a[i]);
ans[i]=f[i];f[i]=0;
}
for(int i=n+1;i<=n<<1;i++){
ans[i]=f[i];s[i]=s[i-1]-1;
}
int res=0;
for(int i=1;i<=n<<1;i++){
if(ans[i])res=max(res,s[i]);
}
cout<<res<<"\n";
}
Expected Destruction
题意：有 \(n\) 个 \(1\sim m\) 的数，这些数字严格单调递增，在每一时刻，会随机选择某一个数 \(a_i\)，将其删去。若剩下的数中没有数与 \(a_i+1\) 相等，且 \(a_i+1\le m\)，则插入 \(a_{i}+1\)，否则不插入。求使得最后没有数剩下的最小方案数。
题解；注意在本题中，一个数没被删之前，排名比它小(自大到小)的那个数也不会被删，所以本质上问题是独立的。我们需要将 \(a_i\) 合并到 \(a_{i+1}\) 上，此时 \(a_i\) 就会噶掉。如果我们将两个数相等不重复插入理解为一种合并的话，那么我们就要合并 \(a_i,a_{i+1}\)，最终 \(a_n\) 与 \(m+1\) 合并。所以， \(a_i,a_{i+1}\) 的合并其实是一个独立于其他数字之外的问题，发掘相对关系，划分同类子问题
设 \(f_{i}\) 为将 \(a_i,a_{i+1}\) 合并在一起的期望次数，\(a_{n+1}=m+1\)。则答案为 \(\sum f_i\).。
设 \(g_{i,j}\) 为将 \(i,j(i<j)\) 合并为一个数的期望操作次数，对于任意一次对这两个数的操作，概率都是 \(\frac{1}{2}\)，所以:
注意当 \(i=j\) 时，\(g_{i,j}=0\)。当 \(j=m+1\) 时，\(g_{i,j}=m-i+1\);
用记忆化搜索即可。
#define int long long
int f[N][N],n,m,a[N],ans;
const int p=1e9+7;
const int inv=p+1>>1;
int dfs(int x,int y){
if(x==y)return 0;
if(f[x][y]!=-1)return f[x][y];
if(y==m+1)return m+1-x;
return f[x][y]=(1+dfs(x+1,y)+dfs(x,y+1))*inv%p;
}
signed main(){
cin>>n>>m;
memset(f,-1,sizeof f);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)for(int j=i+1;j<=m;j++)f[i][j]=dfs(i,j);
ans+=m+1-a[n];
for(int i=2;i<=n;i++)ans=(ans+f[a[i-1]][a[i]])%p;
cout<<ans<<"\n";
}
Michael and Hotel
有趣的问题。
题意：交互题，给一张不知道边指向的图，有有向边 \((i,a_i)\)，不知道 \(a_i\) 的取值。每一次可以询问 \(u,k,T\)，得到点 \(u\) 走完 \(k\) 步后的终点是否在 \(T\) 中，在2000次询问之内，求出与1在同一连通块的集合.\(n\le500\)
这是一颗内向基环树，如果可以知道1所在连通块的环，则在 \(n\) 次内可以跳到环上的点，都与1在同一连通块。我们的问题化为找环。
首先，我们可以在9次操作内找到点 \(i\) 走 \(k\) 步后的落脚点，这可以通过 \(\log n\) 的类似快速排序的算法实现
其次，我们找到点 \(1\) 走 \(n\) 步后的点，这个点在环上。我们先考虑顺着这个点找到 \(k\) 个在环上的点，通过前一个点进行九次操作，代价 \(9k\)
（如果这一步找到重复点，说明环已经找到，直接跳到最后一步）
然后，我们不断倍增这个步长，最初为 \(k\)。然后新的能够跳在上面来的数，则说明其在该连通块内，且至少能够搜集到 \(\min(len-k,k)\) 个环上的点。当搜集到的数 \(\le len-k\)，说明环早已收集完毕，退出即可。
我们不断倍增，直到 \(2k'>n\)，此时可以确定整个环绝对已经囊括其中，再最后扫一遍所有未确定的点，走 \(n\) 次是否到环上即可
操作次数为：\(9k+\sum_{i=0}^{2^ik<n}(n-2^ik)+n-2^{i_{\max}}k<2000\)，\(k\) 取 \(n\) 除八向上取整的值即可，算下来达不到2000
本质来讲，这是通过用 \(9\) 使得环长扩大1，还是用 \(n-c\)，使得环长扩大两倍这两种方案的平衡解决了问题。
#include<bits/stdc++.h>
using namespace std;
int n,vis[5050];
vector<int>g,f;
int get(int l,int r,int k,int id){
if(l==r)return l;
int mid=l+r>>1;
cout<<"? "<<id<<" "<<k<<" "<<mid-l+1<<" ";for(int i=l;i<=mid;i++)cout<<i<<" ";
cout<<"\n";cout.flush();
int x;cin>>x;
if(x)return get(l,mid,k,id);
return get(mid+1,r,k,id);
}
bool ask(int x,int k){
cout<<"? "<<x<<" "<<k<<" "<<g.size()<<" ";
for(auto x:g)cout<<x<<" ";cout<<"\n";cout.flush();
int m;cin>>m;return m;
}
int c=63;
int main(){
cin>>n;c=n>8?(n+7)/8:1;
// g.push_back(1);
int k=get(1,n,n,1);
g.push_back(k);vis[k]=1;
for(int i=1;i<c;i++){
int x=get(1,n,1,g.back());if(vis[x]==1){
c=g.size();
for(int i=1;i<=n;i++)if(vis[i]==0&&ask(i,n-c))g.push_back(i);
sort(g.begin(),g.end());
cout<<"! "<<g.size()<<" ";for(auto x:g)cout<<x<<" ";return 0;
}
g.push_back(x);vis[x]=1;
}c=g.size();
for(auto x:g)vis[x]=1;
while(c<n){
int cnt=0;
for(int i=1;i<=n;i++)if(!vis[i]){
if(ask(i,c))g.push_back(i),vis[i]=1,++cnt;
}
if(cnt<c)break;
c+=c;
}
// if(c>n)c/=2;
for(int i=1;i<=n;i++)if(vis[i]==0&&ask(i,n))vis[i]=1,g.push_back(i);
sort(g.begin(),g.end());
cout<<"! "<<g.size()<<" ";for(auto x:g)cout<<x<<" ";
}