K - Stack Sort

You are given a permutation with $n$ numbers, $a_1, a_2, \dots, a_n (1\leq a_i\leq n, a_i\neq a_j\textrm{ when }i\neq j)$ .You want to sort these numbers using $m$ stacks. Specifically, you should complete the following task:
Initially, all stacks are empty. You need to push each number $a_i$ to the top of one of the $m$ stacks one by one, in the order of $a_1,a_2,\ldots, a_n$ . After pushing all numbers in the stacks, you pop all the elements from the stacks in a clever order so that the first number you pop is $1$ , the second number you pop is $2$ , and so on. If you pop an element from a stack $S$ , you cannot pop any element from the other stacks until $S$ becomes empty.
What is the minimum possible $m$ to complete the task?

通过分析可以发现，我们要把连续⼀段弹到同⼀个栈⾥。考虑两个连续的数 x，x+1如果在⼀开始的序列⾥⾯x在前⾯，那么不能在同⼀个栈⾥，否则可以。所以答案就是统计多少个x+1在x前⾯

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        unordered_set<int> s;
        int ans=0;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            if(s.count(x+1)) ans++;
            s.insert(x);
        }
        cout<<n-ans<<'\n';
    }
    return 0;
}

M - Best Carry Player

简要题面

给定一个数组 $a_1,a_2,...,a_n$ ，请找出正确的排序使得计算这个数组的和时运行的速度最短，请找出最少的进位次数。

输入格式

本题有多组数据。
第一行一个整数 $T$ ，表示数据组数。对于每组数据：第一行一个整数 $n$ 。接下来一行 $n$ 个整数，表示输入的数组 $a$ 。

输出格式

对于每组数据，输出最小的进位次数。

说明/提示

对于 $100 \%$ 的数据： $1 \leq \sum n \leq 10^5$ ， $1 \leq a_i \leq 10^9$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int add(int x,int y){
    int t=0;
    int res=0;
    while(x||y){
        int tx=x%10;
        int ty=y%10;
        if(tx+ty+t>9) res++;
        t=(tx+ty+t)/10;
        x/=10,y/=10;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=2;i<=n;i++){
            ans+=add(a[i-1],a[i]);
            a[i]+=a[i-1];
        }
        cout<<ans<<'\n';
    }
    return 0;
}

E - Identical Parity

Let the value of a sequence be the sum of all numbers in it.Determine whether there exists a permutation of length $n$ such that the values of all subsegments of length $k$ of the permutation share the same parity. The values share the same parity means that they are all odd numbers or they are all even numbers.
A subsegment of a permutation is a contiguous subsequence of that permutation. A permutation of length $n$ is a sequence in which each integer from $1$ to $n$ appears exactly once.

#include <bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int x,y;
        int a=n/k+1,b=n/k;
        int d=exgcd(a,b,x,y);
        int m=(n+1)/2;
        if(m%d){
            cout<<"No\n";
            continue ;
        }
        a/=d,b/=d,m/=d;
        int xx=x*(m%b)%b;//通解形式：x*(m/d)+b/d;
        if(xx<0) xx=xx+b;
        int yy=(m-a*xx)/b;
        if(yy<0||xx>n%k) cout<<"No\n";
        else{
            if(0<=xx&&xx<=n%k&&0<=yy&&yy<=k-(n%k)) cout<<"Yes\n";
            else{
                int l1=-xx*a,r1=(n%k-xx)*a;
                int l2=(yy+n%k-k)*b,r2=yy*b;
                int l=max(l1,l2),r=min(r1,r2);
                int ab=a*b;
                if(l>r) cout<<"No\n";
                else if(r/ab>0&&r/ab*ab>=l) cout<<"Yes\n";
                else cout<<"No\n";
            }
        }
    }
    return 0;
}

A - Tower

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[510],b[510];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        set<int> s;
        for(int i=1;i<=n;i++){
            int tmp=a[i];
            while(tmp){
                s.insert(tmp);
                tmp/=2;
            }
        }
        int ans=LONG_LONG_MAX;
        for(int sta:s){
            for(int i=1;i<=n;i++){
                if(a[i]<=sta) b[i]=sta-a[i];
                else{
                    int tmp=a[i];
                    int cnt=0;
                    while(tmp/2>=sta){
                        tmp/=2;
                        cnt++;
                    }
                    b[i]=min(tmp-sta+cnt,sta-tmp/2+1+cnt);
                }
            }
            sort(b+1,b+n+1);
            int res=0;
            for(int i=1;i<=n-m;i++)  res+=b[i];
            ans=min(ans,res);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

2022 ICPC 亚洲区域赛济南站