The 2021 China Collegiate Programming Contest (Harbin) JBEID

J. Local Minimum 模拟

题意：一个数当且仅当它是当前列最小值同时也是当且行的最小值它才算入贡献。

思路：直接,预处理出每一行每一列的最小值，然后去每一个数。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e3 + 10;
ll minc[N],minr[N],c[N][N],a[N][N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            cin>>a[i][j];
            minc[j] = 1e18;
            minr[i] = 1e18;
        }
    }

    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            minr[i] = min(minr[i],a[i][j]);
        }
    }

    for(int j = 1;j <= m; j++)
    {
        for(int i = 1;i <= n; i++)
        {
            minc[j] = min(minc[j],a[i][j]);
        }
    }

    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            if(a[i][j]==minr[i])
                c[i][j]++;
        }
    }

    for(int j = 1;j <= m; j++)
    {
        for(int i = 1;i <= n; i++)
        {
            if(a[i][j]==minc[j])
                c[i][j]++;
        }
    }
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            ans += (c[i][j]>=2);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

B. Magical Subsequence 前缀+DP

题意：给你一个序列 ,我们选择该序列的一个子序列。我们说它是有魔法的，当且仅当是偶数，且。找出满足条件的最大的子序列长度。
思路：因为范围只有，那么两个数的和只在 $～$ 之间。那么我们可以枚举两个数的和是多少去。

定义：表示，前个两个和为的最长序列是多少。

那么，其中表示上一个为的数出现在哪(边做边去更新数组)，用这个和我们当前的配对，贡献就是从上一个前面的贡献。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5+10;
int a[N];
int last[N];
int f[N][210];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i];
    for(int i = 1;i <= n; i++)
    {
        for(int j = 2;j <= 200; j++)
            f[i][j] = max(f[i][j],f[i-1][j]);
        for(int j = 1;j <= 100; j++)
        {
            if(!last[j])continue;
            int sum = j+a[i];
            //last_num = j,now_num = a[i];
            f[i][sum] = max(f[i][sum],f[last[j]-1][sum]+2);
        }
        last[a[i]] = i;
    }
    int ans = 0;
    for(int i = 1;i <= n; i++)
        for(int j = 2;j <= 200; j++)
            ans = max(ans,f[i][j]);
    cout<<ans<<"\n";
    return 0;
}

E. Power and Modulo 思维

题意：给你个非负整数，问你是否存在有且仅有一个正整数，使得.如果有就输出,否则输出。

思路：因为我们知道都是的幂次模,一旦第一个发现小于了它原本应该的数，说明它已经大于了。如果要满足题意，那么此时的应该为。然后去这个是否满足条件即可。

注意：

不能先预处理幂次，因为你无法预处理出个，那么你应该在得出可能的之后，边算边模。
一开始的也要模。
如果有的也不满足。

// 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 a[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i = 1;i <= n; i++)
        {
            cin>>a[i];
        }
        ll m = -1;
        ll mi = 1;
        for(int i = 1;i <= n; i++)
        {
            if(a[i]!=mi)
            {
                m = mi-a[i];
                break;
            }
            mi *= 2;
        }
        if(m==-1)
        {
            cout<<"-1\n";
            continue;
        }
        bool ok = true;
        mi = 1%m;
        for(int i = 1;i <= n; i++)
        {
            //cout<<"mi = "<<mi[i-1]<<"\n";
            if((mi%m!=a[i])||a[i]>m)
            {
                ok = false;
                break;
            }
            mi *= 2;
            mi%=m;
        }
        if(ok)cout<<m<<"\n";
        else cout<<-1<<"\n";
    }


    return 0;
}

I. Power and Zero 二进制+思维

题意：给你一个正整数序列,你需要进行一些操作把它们都变成。每次操作呢，你可以选一些下标，对它们减去的幂次。问最少的操作次数。

思路：由于每次都是减去一段连续的的幂次，最后变为。那么我们可以从二进制考虑。一开始我的思路是统计二进制的每一位有多少个，然后全部转化为的个数，再去计算贡献，但是是错的(不晓得为什么)。以下是我写的错误代码：

// 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 a[N],mi[N],sum[N];
ll cnt[100];
void init()
{
    ll base = 1;
    for(int i = 0; i < 100; i++)
        mi[i] = base,base*=2,sum[i+1] = sum[i]+mi[i];
}
int main()
{
   ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    init();
    while(t--)
    {
        int n;
        cin>>n;
        memset(cnt,0,sizeof(cnt));
        int mx = 0;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        for(int i = 1;i <= n; i++)
        {
            ll x = a[i];
            for(int j = 0;j < 64; j++)
            {
                if((x>>j)&1)
                    cnt[j]++,mx = max(mx,j+1);
            }
        }
        // for(int i = 0; i < 64; i++)
        //     cout<<cnt[i]<<" ";
        // cout<<"\n";
        // cout<<"sum = ";
        //  for(int i = 0; i < 64; i++)
        //     cout<<sum[i]<<" ";
        // cout<<"\n";
        for(int i = 1; i < 64; i++)
        {
            cnt[0] += cnt[i]*mi[i];
        }
       // cout<<"cnt = "<<cnt[0]<<" mx = "<<mx<<"\n";
        ll t = cnt[0];
        ll ans = 0;
        while(t)
        {
            //cout<<"t = "<<t<<"\n";
            ll l = 0,r = mx;
            while(l<=r)
            {
                ll mid = (l+r)>>1;
                if(sum[mid]<=t)l = mid+1;
                else r = mid-1;
            }
            ll pos = l-1;
            ans += t/sum[pos];
            t %= sum[pos];
        }
        cout<<ans<<"\n";
    }
    return 0;
}

那么正解是什么呢？最后队友写出来了。其实一开始的思路是有道理的。一开始我们也是考虑统计二进制的每一位有多少个，然后一层一层的去减，但是问题出现了：万一不够减怎么办呢？然后我就想可以拿后面的去补上。但是问题又来了，怎么补，用哪个去补？

听了队友的分析，了解到最终一定是调整为一段形如：

。其中单调递减的(因为这样才能保证是连续的，可以想象成一个类似于梯形的形状，每次减去一层（这样也不会有不够减的情况），才是最优的)。

![image-20230921002445411](C:\Users\Zhou Yanan\Desktop\image-20230921002445411.png)

那么我们从后往前遍历，当发现当前位置的的个数大于前面的一个位置了，我们就挪一些(均匀一些)到它的前一个(保证前一个位置个数当前位置数的个数)。

if(cnt[i-1]<cnt[i])
 {
     ok = false;
    int d = cnt[i]-cnt[i-1];
    if(d%3==0)
       cnt[i-1]+=d/3*2,cnt[i]-=d/3;
    else
      cnt[i-1]+=(d/3+1)*2,cnt[i]-=(d/3+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 cnt[35];
int a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        memset(cnt,0,sizeof(cnt));
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        for(int i = 1;i <= n; i++)
            for(int j = 0;j < 32; j++)
                if((a[i]>>j)&1)
                    cnt[j]++;
        
        while(1)
        {
            bool ok = true;
            for(int i = 32;i >= 1; i--)
            {
                if(cnt[i-1]<cnt[i])
                {
                    ok = false;
                    int d = cnt[i]-cnt[i-1];
                    if(d%3==0)
                        cnt[i-1]+=d/3*2,cnt[i]-=d/3;
                    else
                        cnt[i-1]+=(d/3+1)*2,cnt[i]-=(d/3+1);
                }
            }
            if(ok)break;
        }
        cout<<cnt[0]<<"\n";
    }
    return 0;
}

D. Math master 暴力二进制枚举

题意：给你一个分数，当分子和分母都存在某一个数的时候可以把这个数删去(前提是分数值保持不变)。由于是级别的，那么对应十进制只有位。我们可以考虑暴力枚举分子化为最简是什么，假设是，那么分子应该相应为。然后我们只要去，找到满足条件的最小的一组。

对于，看看需要删除什么会得到，然后去比较看看和是不是完全一样即可。

特别要小心和注意的是,还有记得开

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
//2^63 = 9223372036854775808
//19位数
int cnta[10],cntb[10];
int sz1,sz2;
string sp,sq;
inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}

bool check(ll b)
{
    for(int i = sz2-1;i >= 0; i--)
    {
        if(sq[i]-'0'==b%10)
            b/=10;
        else cntb[sq[i]-'0']++;
    }
    if(b)return false;//说明全删了，肯定是不行的
    for(int i = 0;i <= 9; i++)
        if(cnta[i]!=cntb[i])return false;
    return true;
}

signed main()
{
    //ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    n = read();
    for(int i = 1;i <= n; i++)
    {
        cin>>sp>>sq;
        sz1 = sp.size(),sz2 = sq.size();
        int p = 0,q = 0;
        for(int i=0;i<sz1;++i) p=p*10ll+(sp[i]-'0');
        for(int i=0;i<sz2;++i) q=q*10ll+(sq[i]-'0');
        ll ansa = p,ansb = q;
        /*
            p/q = a/b;
            b = aq/p;
        */
        for(int i = 0; i < (1<<sz1); i++)
        {
            ll a = 0,b = 0;
            for(int i = 0;i <= 9;i++)
                cnta[i] = cntb[i] = 0;
            for(int j = 0;j < sz1; j++)
            {
                if((i>>j)&1)
                    a*=10ll,a+=sp[j]-'0';
                else cnta[sp[j]-'0']++;
            }

            if(!a||a*q%p)continue;//注意不能为0，且要可aq以被p整除
            b = a*q/p;
            if(check(b))
                ansa = min(ansa,a),ansb = min(ansb,b);
        }
        write(ansa);cout<<" ";write(ansb);cout<<"\n";
    }
    return 0;
}

Nannan blog

The 2021 CCPC 哈尔滨 JBEID