Codeforces Round 889 (Div. 2) A–D

A. Dalton the Teacher

题意

有 $n$ 个数 $a_1,a_2,\ldots,a_n$ 。
现在每次操作可以交换两个数，请求出最少的操作数，使得 $\forall 1\le i \le n, a_i\ne i$ 。

解法

设当前满足 $a_i=i$ 的数数量为 $x$ 。
可以证明，答案为 $\big \lfloor \dfrac{x+1}{2} \big \rfloor$ 。

证明：
必要性：一次操作只能调换两个数的位置，至少需要 $\big \lfloor \dfrac{x+1}{2} \big \rfloor$ 次操作才能调换每一个数。
充分性：我们构造一个合法方案。如果 $x$ 是偶数，我们直接两两一换即可。如果 $x$ 是奇数，我们先将 $x-1$ 两两一换，显然最后一个数一定能在前 $x-1$ 个数中找到一个能和它换的。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 1e5+5;
void solve(int kase){
    int n=read();
    int cnt  =0;
    for(int i=1;i<=n;i++){
        int x=read();
        if(x==i)cnt++;
    }
    printf("%d\n",(cnt+1)/2);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Longest Divisors Interval

题意

给定 $n\ (n \le 10^{18})$ ，求出最长区间 $[l,r]$ ，使得 $\forall l\le i\le r$ ， $n$ 是 $i$ 的倍数（我们定义区间 $[l,r]$ 的长度为 $r-l+1$ ）。

解法

所有的合法最长区间中，一定有一个是从 $1$ 开始的。
证明：
不妨设 $[l,r]$ 是答案的合法最长区间。
$\because$ 在 $x$ 个连续整数中有一个 $x$ 的倍数，
$\therefore$ $[l,r]$ 中包含 $1,2,\ldots,r-l+1$ 的倍数。
$\because$ $\forall l\le i\le r$ ， $n$ 是 $i$ 的倍数，
$\therefore$ $n$ 是 $1,2,\ldots,r-l+1$ 的倍数。
$\therefore$ $[1,r-l+1]$ 是一个合法解，且长度与 $[l,r]$ 相同。

因此只需要从 $1$ 开始不断枚举 $r$ 即可。因为 $\operatorname{lcm} (1,2,\ldots,43)=9419588158802421600>10^{18}$ ，所以最多枚举 $42$ 个数。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    ll n = read<ll>();

    ll x = 1;
    while(n%x==0)x++;

    printf("%lld\n",x-1);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C2. Dual (Hard Version)

题意

给定 $n\ (n\le 20)$ 个数 $a_1,a_2,\ldots,a_n\ (-20\le a_i\le 20)$ 。现在可以进行一次操作，选定 $i,j$ （不一定不同），使得 $a_i\leftarrow a_i+a_j$ 。

要使这个序列单调不减，请构造出一个最多使用 $31$ 次的方案。

解法

注意到若这个序列全部非负，我们可以执行 $a_{i+1}\leftarrow a_{i+1}+a_{i}$ 操作 $n-1$ 次，使得整个序列单调不减。同理若这个序列全部非正，我们也可以执行 $a_{i-1}\leftarrow a_{i-1}+a_{i}$ 操作 $n-1$ 次，使得整个序列单调不减。

上面这个操作需要使用 $19$ 步，因此我们考虑如何在 $12$ 步内将这个序列全部变为同号。

现在序列中既有负数也有正数（如果没有，直接用上面的方法处理）。
不失一般性，我们令最小数的绝对值大于等于最大数的绝对值。考虑两种情况：

正数的个数小于等于 $12$ 个，直接用最小数加给所有正数，在 $12$ 步内将序列变为全负。
正数个数大于等于 $13$ 个，负数的个数小于等于 $7$ 个。我们将任意一个正数用五次操作翻五番（ $a_i\leftarrow a_i+a_i$ ），这样这个数至少等于 $32$ ，然后我们用这个翻五番的数加给每一个负数，这样就可以在 $5+7=12$ 步操作将所有数变为正数。

若最小数的绝对值小于最大数的绝对值，同理。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 25;
int a[N];
void solve(int kase){
    int n=read();
    vector<pii> v;
    for(int i=1;i<=n;i++){
        a[i]=read();
        v.push_back({a[i],i});
    }
    sort(all(v));

    int cntneg=0,cntpos=0;

    for(int i=0;i<n;i++){
        if(v[i].first<0)cntneg++;
        if(v[i].first>0)cntpos++;
    }

    int posmax = max_element(a+1,a+1+n)-a;
    int posmin = min_element(a+1,a+1+n)-a;

    if(cntpos==0){
        printf("%d\n",n-1);
        for(int i=n;i>1;i--){
            printf("%d %d\n",i-1,i);
        }
        return;
    }
    if(cntneg==0){
        printf("%d\n",n-1);
        for(int i=1;i<n;i++){
            printf("%d %d\n",i+1,i);
        }
        return;
    }

    vector<pii> ans;
    if(abs(a[posmin])>=abs(a[posmax])){
        if(cntpos<=12){
            for(int i=0;i<n;i++){
                if(v[i].first>0){
                    ans.push_back({v[i].second,posmin});
                }
            }

            for(int i=n;i>1;i--){
                ans.push_back({i-1,i});
            }
        }
        else{
            for(int i=0;i<5;i++){
                ans.push_back({posmax,posmax});
            }
            for(int i=0;i<n;i++){
                if(v[i].first<0){
                    ans.push_back({v[i].second,posmax});
                }
            }
            for(int i=1;i<n;i++){
                ans.push_back({i+1,i});
            }
        }
    }
    else{
        if(cntneg<=12){
            // printf("cntneg = %d\n",cntneg);
            for(int i=0;i<n;i++){
                if(v[i].first<0){
                    ans.push_back({v[i].second,posmax});
                }
            }

            for(int i=1;i<n;i++){
                ans.push_back({i+1,i});
            }
        }
        else{
            for(int i=0;i<5;i++){
                ans.push_back({posmin,posmin});
            }
            for(int i=0;i<n;i++){
                if(v[i].first>0){
                    ans.push_back({v[i].second,posmin});
                }
            }
            for(int i=n;i>1;i--){
                ans.push_back({i-1,i});
            }
        }
    }


    cout<<ans.size()<<'\n';
    for(auto x:ans){
        cout<<x.first<<' '<<x.second<<'\n';
        a[x.first]+=a[x.second];
    }

    assert(is_sorted(a+1,a+1+n));
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Earn or Unlock

题意

有 $n\ (n\le10^5)$ 张牌，权值为 $v_1\sim v_n$ 。现在只有第一张牌解锁了，后面的牌全部是锁住的。
现在你可以进行操作：选定一张解锁了的牌 $i$ ：

再解锁后面 $v_i$ 张牌；
答案加上 $v_i$ 。

求答案最大值。

解法

注意到一个事实：若总共恰好解锁了 $x$ 张牌，则答案为 $v_1+v_2+\ldots+v_{\max(n,x)}-(x-1)$ 。

设 $dp_{i,j}$ 代表能否使用前 $i$ 张牌恰好解锁 $j$ 张牌。

初始条件： $dp_{0,1}=1$ 。
转移：

$dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-v_i})$

事实上，第二个转移 $dp_{i,j}=dp_{i-1,j-v_i}$ 当且仅当 $j-v_i\ge i$ 时才能成功转移，为此我们在每次操作后，都将 $dp_{i,i}$ 置 $0$ ，保证都是从合法的状态转移的。

对于 $j$ 只需要算到 $2n$ 就够了，显然解锁超过 $2n$ 张牌是更劣的。

用 bitset 优化，复杂度为 $O(\frac{n^2}{w})$ ，勉强够。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
bitset<N> dp;
int a[N];
ll s[N];

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        s[i]=s[i-1]+a[i];
    }

    dp[1]=1;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        dp=dp|dp<<a[i];
        if(dp[i]){
            ans = max(ans, s[i]-i+1);
        }
        dp[i]=0; // 保证是从有效的状态转移的
    }
    for(int i=n+1;i<=n*2;i++){
        if(dp[i]){
            ans = max(ans,s[n]-i+1);
            break; // i 更大答案一定更劣，后面的就不算了
        }
    }

    printf("%lld\n",ans);
    return 0;
}