A. Dalton the Teacher
题意：给出一个排列，问使得排列变为1,2,...,n的最小的交换操作次数
Solution
统计a[i]!=i的个数，答案就是除以二向上取整
void solve()
{
int n;cin>>n;
int res=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(x==i)res++;
}
cout<<(res+1)/2<<"\n";
}
B. Longest Divisors Interval
题意：给出一个数，求出最长的区间的长度，使得区间中的每个数都是这个数的因数
Solution
从1开始找，直到找到不是因数的，假设[l,r]都是是n的因数，那么显然[1,r/l]也是
void solve()
{
int n;cin>>n;
int res=0;
for(int i=1;i<=n;i++)
{
if(n%i==0)res++;
else break;
}
cout<<res<<"\n";
}
C. Dual
题意：给出一个数组a，可以进行最多31次操作，每次操作可以选两个数i,j，并进行a[i]+=a[j]，构造一个操作序列，使得数组变为不降序列
Solution
统计大于0的数和小于0的数的个数，如果都为0则无需操作，如果其中一个为0则进行一趟前缀和/后缀和即可
如果都不为0，则考虑两种操作，分别是把大于0的都变为小于0的然后再后缀和，或是把小于0的都变为大于0的，再进行前缀和
都跑一遍然后对两种操作次数取小
int a[25];
int b[25];
int mx[25];
int mi[25];
void solve()
{
int n;cin>>n;
vector<pii>ans;
int pos=0;
int cnt0=0,cnt1=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i==1)mx[i]=mi[i]=a[i];
else
{
mx[i]=max(mx[i-1],a[i]);
mi[i]=min(mi[i-1],a[i]);
}
if(a[i]>0)cnt1++;
else if(a[i]<0) cnt0++;
}
if(mx[n]==0&&mi[n]==0)
{
cout<<"0\n";
return;
}
if(cnt0==0)
{
for(int i=2;i<=n;i++)
{
while(a[i]<a[i-1])
{
a[i]+=a[i-1];
ans.push_back({i,i-1});
}
}
cout<<ans.size()<<"\n";
for(auto it:ans)
{
cout<<it.first<<" "<<it.second<<"\n";
}
}else if(cnt1==0)
{
for(int i=n-1;i>=1;i--)
{
while(a[i]>a[i+1])
{
a[i]+=a[i+1];
ans.push_back({i,i+1});
}
}
cout<<ans.size()<<"\n";
for(auto it:ans)
{
cout<<it.first<<" "<<it.second<<"\n";
}
}
else
{
for(int i=1;i<=n;i++)b[i]=a[i];
vector<pii>ans1;
vector<pii>ans2;
for(int i=1;i<=n;i++)
{
if(b[i]==mx[n])
{
pos=i;
break;
}
}
while(abs(b[pos])<abs(mi[n]))
{
b[pos]+=b[pos];
ans1.push_back({pos,pos});
}
for(int i=1;i<=n;i++)
{
if(b[i]<0)
{
ans1.push_back({i,pos});
}
}
for(int i=2;i<=n;i++)ans1.push_back({i,i-1});
for(int i=1;i<=n;i++)b[i]=a[i];
for(int i=1;i<=n;i++)
{
if(b[i]==mi[n])
{
pos=i;
break;
}
}
while(abs(b[pos])<abs(mx[n]))
{
b[pos]+=b[pos];
ans2.push_back({pos,pos});
}
for(int i=1;i<=n;i++)
{
if(b[i]>0)
{
ans2.push_back({i,pos});
}
}
for(int i=n-1;i>=1;i--)ans2.push_back({i,i+1});
if(ans1.size()>ans2.size())
{
cout<<ans2.size()<<"\n";
for(auto it:ans2)cout<<it.first<<" "<<it.second<<"\n";
}else
{
cout<<ans1.size()<<"\n";
for(auto it:ans1)cout<<it.first<<" "<<it.second<<"\n";
}
}
}
D. Earn or Unlock
题意：给出n张牌，最开始只有第一张牌是解锁状态，其它牌都被锁住了，每张牌上有一个点数a[i]，每次可以进行一种操作：
1.解锁顶上的未解锁的a[i]张牌
2.获得a[i]的胜利点数
问最后能得到的最大点数是多少
Solution
定义\(dp_{i}\)表示能否通过若干次解锁操作刚好解锁到i，那么可以遍历a，初始化dp[1]=1，每次令dp|=dp<<a[i]，从而转移答案，而对于当前可以刚好解锁的情况，我们需要在更新答案后将其变为0，因为在更新完答案后它就不能转移到其他的位置了，此外，考虑到可能会超过n的范围，我们可以将bitset扩大到2n，以检测最后一次解锁操作的更新位置大于n的情况
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
bitset<200005>dp;
dp[1]=1;
int ans=0;
for(int i=1;i<=n;i++)
{
dp|=dp<<a[i];
if(dp[i])
{
ans=max(ans,s[i]-i+1);
dp[i]=0;
}
}
// cout<<dp<<"\n";
for(int i=n+1;i<=2*n;i++)
{
if(dp[i])
{
ans=max(ans,s[n]-i+1);
dp[i]=0;
}
}
cout<<ans<<"\n";
}