2022 International Collegiate Programming Contest, Jinan Site - Codeforces AEKM

A. Tower

思路：思维+贪心

由于我们只能进行和\ 的操作。显然的，我们能大幅度改变一个数是除的操作，并且最后化成的一样的那个数一定不会大于当且的任何一个数，因为这样肯定会多花步数。那么进一步思考，考虑处理出最后可能的答案(可能变成的那个数)，这些数一定是原数组某个数或者由它除以二得到的。为什么呢？考虑只有的操作，那么最后的答案一定是通过加减变成其中的中位数。那么对于多了一个除以2呢？由于先除以2再加减相对于先加减再除以二步数不会变多。注意到，我们选择的数\2以后，一定会通过加减变成其中的中位数，

处理出来以后，我们去每一种情况，然后取最小的。

注意要去重。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m;
ll ans[N],a[N],b[N],cnt;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        vector<int>ans;
        for(int i = 1;i <= n; i++)
        {
            cin>>a[i];
            ll x = a[i];
            while(x)
            {
                ans.push_back(x);
                x/=2;
            }
        }
        sort(ans.begin(),ans.end());
        unique(ans.begin(),ans.end())-ans.begin();
        // for(int i = 1;i <= cnt; i++)
        //     cout<<ans[i]<<" ";
        // cout<<"\n";
        ll res = 1e18;
        int cnt = ans.size();
        for(int i = 0;i < cnt; i++)
        {
            ll x = ans[i];
           // cout<<"x = "<<x<<"\n";
            ll c = 0;
            for(int j = 1;j <= n; j++)
            {
                b[j] = 1e18;
                if(a[j]==x){
                    b[j] = 0;continue;
                }
                if(a[j]<x)b[j] = x-a[j];
                else{
                    ll t = a[j],tmp = 0;
                    //cout<<"t = "<<t<<"\n";
                    while(t>x)
                    {
                        if(t>x&&(t/2)<=x){
                            b[j] = min(tmp+t-x,tmp+1+(x-t/2));
                            break;
                        }
                        tmp++;
                        t/=2;
                    }
                    //cout<<"tmp = "<<tmp<<"b[j] ="<<b[j]<< "\n";
                }
            }
            sort(b+1,b+1+n);
            // for(int j = 1;j <= n; j++)
            //     cout<<b[j]<<" ";
            // cout<<"\n";
            for(int j = 1;j <= n-m; j++)
                c += b[j];
            res = min(res,c);
        }
       cout<<res<<"\n";
    }
    return 0;
}

E. Identical Parity

思路：思维+

我们可以把题目看成一个长度为的区间在长度为的数组上滑动。每当我们前进一格，如果出去一个，那么下一个必须进来一个，如果出去一个，那么下一个必须进来一个。那意味着什么呢？

对于下标为:

上的奇偶性要是一样的，即。

我们考虑按上述方法把原序列按照下标分成块，每块去分配奇偶性。

包含数字个数为的块数有块，包含数字个数为的块数有块。

又由于整个序列上应该有个位置是奇数，有个位置上是偶数。

那么就考虑

含义就是：取个长度为的，和个长度为的放奇数(恰好填满所有奇数，剩下的放偶数就可以了。那么只需要我们的是不是满足。

如何判断呢？考虑先用求出一个题解。

那么通解就是。

那么：
$由于要求是整数，就是说 ② ④ 式有分数，为了处理这个问题，两边同乘得$
接下来看这两个不等式两边有没有交集，再确定区间里面有没有的倍数，这样能保证是整数。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a/b*x;
    return d;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        ll a = n/k+1,b = n/k,m = (n+1)/2,x,y;
        ll d = exgcd(a,b,x,y);
        if(m % d){
            cout<<"No\n";
            continue;
        }
        a /= d;
        b /= d;
        m /= d;
        ll xx = (ll) x * (m % b) % b;
        if(xx < 0)  xx = xx + b;
        ll yy = (ll)(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{
                ll l1 = -xx*a,r1 = (n%k-xx)*a;
                ll l2 = -(k-n%k-yy)*b,r2 = yy*b;
                ll l = max(l1,l2),r = min(r1,r2);
                ll 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;
}

法二：打表找规律

k:    1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25
n : 1  1
n : 2  0 1
n : 3  0 1 1
n : 4  0 1 1 1
n : 5  0 1 1 1 1
n : 6  0 1 0 1 1 1
n : 7  0 1 1 1 1 1 1
n : 8  0 1 0 1 1 1 1 1
n : 9  0 1 0 1 1 1 1 1 1
n : 10 0 1 0 1 0 1 1 1 1 1
n : 11 0 1 0 1 1 1 1 1 1 1 1
n : 12 0 1 0 1 1 1 1 1 1 1 1 1
n : 13 0 1 0 1 1 1 1 1 1 1 1 1 1
n : 14 0 1 0 1 0 1 0 1 1 1 1 1 1 1
n : 15 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1
n : 16 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1
n : 17 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 18 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
n : 19 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 20 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 21 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 22 0 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
n : 23 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 24 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
n : 25 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

我们发现，为偶数的时候一定是可以的，那么为奇数的时候呢？发现的分布是倒着的等差序列。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        if(k%2==0){
            cout<<"Yes\n";
            continue;
        }
        
        n -= k;
        ll t1 = n/(k+1);
        ll t2 = n%(k+1);
        ll t = k-t1*2;
        if(t<0)cout<<"No\n";
        else if(t2<t)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

K. Stack Sort

思路：只要当前数的下一个数不存在。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
       map<int,int>cnt;
       int n,ans = 0;
       cin>>n;
       for(int i = 1;i <= n; i++)
       {
            int x;
            cin>>x;
            if(!cnt[x+1])ans++;
            cnt[x]++;
            //cout<<"cnt[x+1] = "<<cnt[x+1]<<"\n";

       }
       cout<<ans<<"\n";
    }
    return 0;
}

M.Best Carry Player

思路：由于顺序不影响进位，直接模拟加法过程即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m,res;
ll add(ll a,ll b)
{
    ll t = a+b;
    int a1 = 0,b1 = 0;
    while(a||b)
    {
        a1 += a%10;
        a/=10;
        b1 = b%10;
        b/=10;
        a1 = (a1+b1>=10?1:0);
        res += a1;
    }
    return t;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        res = 0;
        cin>>n;
        ll a,b;
        cin>>a;
        for(int i = 2;i <= n; i++){
            cin>>b;
            a = add(a,b);
        }
        cout<<res<<"\n";

    }

    return 0;
}

Nannan blog

2022 ICPC 济南 AEKM

2022 International Collegiate Programming Contest, Jinan Site - Codeforces AEKM

A. Tower

E. Identical Parity

K. Stack Sort

M.Best Carry Player