526互联

2022 International Collegiate Programming Contest, Jinan Site AEKM

发布时间 2023-09-07 19:07:43作者: nannan4128

2022 International Collegiate Programming Contest, Jinan Site - Codeforces AEKM

A. Tower

思路：思维+贪心

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

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

注意要去重。

// 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

思路：思维+\(exgcd\)

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

对于下标为:

\[1,1+k,1+2k,...\\ 2,2+k,2+2K,...\\ ...\\ k,k+k,k+2k...\\ \]

上的奇偶性要是一样的，即\(p_{i} ≡ p_{i+k}\mod 2\)。

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

包含数字个数为\(\lfloor\dfrac{n}{k}\rfloor+1\)的块数有\(n\%k\)块，包含数字个数为\(\lfloor\dfrac{n}{k}\rfloor\)的块数有\(k-n\%k\)块。

又由于整个序列上应该有\(\dfrac{n+1}{2}\)个位置是奇数，有\(\dfrac{n}{2}\)个位置上是偶数。

那么就考虑\(x\times (\lfloor\dfrac{n}{k}\rfloor+1) + y\times \lfloor\dfrac{n}{k}\rfloor = \dfrac{n+1}{2}\)

含义就是：取\(x\)个长度为\(\lfloor\dfrac{n}{k}\rfloor+1\)的，和\(y\)个长度为\(\lfloor\dfrac{n}{k}\rfloor\)的放奇数(恰好填满所有奇数\(\dfrac{n+1}{2}\)，剩下的放偶数就可以了。那么只需要\(check\)我们的\(x,y\)是不是满足\(0\le x\le n\%k,0\le y\le k-n\%k\)。

如何判断呢？考虑先用\(exgcd\)求出一个题解\((xx,yy)\)。

那么通解就是\(x = xx + b\times t,y =yy- a\times t\)。

那么：

\[0\le xx + b\times t\le n\%k\\ -xx\le b\times t\le n\%k-xx ①\\ -xx/b\le t\le (n\%k-xx)/b ②\\ \\ 0\le yy-a\times t\le k-n\%k\\ -yy\le-a\times t \le k-n\%k-yy\\ -( k-n\%k-yy)\le a\times t \le yy③\\ -( k-n\%k-yy)/a\le t \le yy/a④\\ \\ 由于要求是整数，就是说②④式有分数，为了处理这个问题，两边同乘a\times b得:\\ -xx\times a\le a\times b\times t\le (n\%k-xx)\times a\\ -( k-n\%k-yy)\times b\le a\times b\times t \le yy\times b\\ \]

接下来看这两个不等式两边有没有交集，再确定区间里面有没有\(a\times b\)的倍数，这样能保证是整数。

// 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

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

// 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

思路：只要当前数的下一个数不存在\(ans++\)。

// 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;
}