首页 > 其他分享 >The 2021 China Collegiate Programming Contest (Harbin) JBEID

The 2021 China Collegiate Programming Contest (Harbin) JBEID

时间：2023-09-21 22:33:08浏览次数：52  
标签：cnt const Contest int ll Programming cin long Collegiate

The 2021 China Collegiate Programming Contest (Harbin) JBEID

J. Local Minimum 模拟

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

思路：直接\(for\),预处理出每一行每一列的最小值，然后去\(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 = 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

题意：给你一个序列\(A_1,A_2,...,A_n\) ,我们选择该序列的一个子序列\(A_{b_1},A_{b_2},...,A_{b_m}\)。我们说它是有魔法的，当且仅当\(m\)是偶数，且\(A_{b_1}+A_{b_2} = A_{b_3}+A_{b_4}=...=A_{b_{m-1}}+A_{b_m}\)。找出满足条件的最大的子序列长度。
思路：因为\(A_i\)范围只有\(100\)，那么两个数的和只在\(2～200\)之间。那么我们可以枚举两个数的和是多少去\(dp\)。

定义：\(dp[i][sum]\)表示，前\(i\)个两个和为\(sum\)的最长序列是多少。

那么\(dp[i][sum] = max(dp[i][sum],dp[last[j]-1][sum]+2)\)，其中\(last[j]\)表示上一个为\(j\)的数出现在哪(边做边去更新\(last\)数组)，用这个\(j\)和我们当前的\(a[i]\)配对，贡献就是从上一个\(j\)前面的贡献\(+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 = 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 思维

题意：给你\(n\)个非负整数\(A_1,A_2,...,A_n\)，问你是否存在有且仅有一个正整数\(M\)，使得\(A_i = 2^{i-1}\bmod M\).如果有就输出\(M\),否则输出\(-1\)。

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

注意：

  1. 不能先预处理幂次，因为你无法预处理出\(1e5\)个，那么你应该在得出可能的\(M\)之后，边算边模。
  2. 一开始的\(1\)也要模\(M\)。
  3. 如果有\(a[i]>M\)的也不满足。
// 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 二进制+思维

题意：给你一个正整数序列\(A_1,A_2,...,A_n\),你需要进行一些操作把它们都变成\(0\)。每次操作呢，你可以选一些下标，对它们减去\(2\)的幂次\(2^0,2^1,...,2^m\)。问最少的操作次数。

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

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

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

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

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

image

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

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

不断调整(\(O(NlogN)\))，直到是单调递减的为止，同时这样调整是均匀的能保证\(1\)的个数最小化。最后的答案就是调整完之后的\(cnt_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 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 暴力二进制枚举

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

对于\(check\)，看看\(q\)需要删除什么会得到\(b\)，然后去比较看看\(cnta\)和\(cntb\)是不是完全一样即可。

特别要小心和注意的是\(a\ne0,b\ne0,a*q\%p==0\),还有记得开\(int128\)

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

标签：cnt,const,Contest,int,ll,Programming,cin,long,Collegiate
From： https://www.cnblogs.com/nannandbk/p/17721142.html

相关文章

  • AtCoder Beginner Contest 313 Ex Group Photo
    洛谷传送门AtCoder传送门考虑若重排好了\(a\)，如何判断可不可行。显然只用把\(b\)排序，把\(\min(a_{i-1},a_i)\)也排序（定义\(a_0=a_{n+1}=+\infty\)），按顺序逐个判断是否大于即可。这启示我们将\(\min(a_{i-1},a_i)\)排序考虑。考虑从大到小加入\(a_i\)，那么......
  • 2019, XII Samara Regional Intercollegiate Programming Contest
    \(ProblemA.RoomsandPassages\)倒着处理每个位置正数的最前部的位置。如果是正数，显然答案为后一个位置的答案\(+1\)。如果是负数且前面出现过相应的正数，答案要对这个区间长度\(-1\)的取\(min\)。voidsolve(){intn=read();vector<int>a(n+2),cnt(n+2,-1)......
  • Parallel Programming Basic
    Learnaboutthedifferencebetweentime-efficiency(moreimportant)andwork-efficiencyparallelloopRelativeinstructionsetSSE（StreamingSIMDExtensions）instructionsetAVX（AdvancedVectorExtensions）instructionsetItisx86microprocessorinstruc......
  • AtCoder Grand Contest 017
    链接C.SnukeandSpells容易发现合法序列排序后一定是若干段值域连续的部分组成：可以发现最小次数就是重叠/空出的部分大小。每次修改只会对\(O(1)\)个点\(±1\)，直接维护即可。#include<iostream>#include<cstdio>#include<cstring>#include<vector>#defineN200010......
  • The 2023 ICPC Asia Regionals Online Contest (1)
    Preface这场打的还行，因为学长们都没发挥好被我们队偷了，但感觉发挥的也一般前期开题顺序有点问题导致罚时很高，不过中期写题还是很顺的基本都是一遍过只不过在3h的时候过完F到达8题后就开始坐牢了，虽然这场有两个字符串但徐神把H想复杂了，B可以说前面的建SAM和反串的AC自动机都想到......
  • AtCoder Grand Contest 023 E Inversions
    洛谷传送门AtCoder传送门首先将\(a\)从小到大排序，设\(p_i\)为排序后的\(a_i\)位于原序列第\(p_i\)个位置，\(x_i\)为要填的排列的第\(i\)个数。设\(A=\prod\limits_{i=1}^n(a_i-i+1)\)，则\(A\)为排列的总方案数（考虑按\(a_i\)从小到大填即得）。套路地，统......
  • 2018-2019 ACM-ICPC Brazil Subregional Programming Contest
    \(B.Marbles\)如果是\(Nim\)博弈，题目应该改成到转移所有石子。显然要转化到将所有石子转移到\((1,2)\)或者\((2,1)\)，特判无需到达这两个点的必败态，对其他点使用\(Nim\)博弈判断胜负态。intsg[N][N],vis[N];voidinit(){for(inti=1;i<=100;i++){for(in......
  • Atcoder Regular Contest 165(A~E)
    赛时45min切A~C，降智不会D，罚坐1h，喜提rk70+->rk170+。A-SumequalsLCM可证明结论：若\(N\)只含有一种质因子则无解，否则有解。B-SlidingWindowSort2这么多cornercase的题竟然10min一发入魂，类目了。由于操作是升序排序，且要求最终字典序最大，所以如果存在一个......
  • AtCoder Beginner Contest 320
    A-LeylandNumbera,b=map(int,input().split(''))print(a**b+b**a)B-LongestPalindromes=input()n=len(s)res=0forlinrange(1,n+1):foriinrange(0,n-l):t=q=s[i:i+l]t=t+t[::-1]......
  • The 2023 ICPC Asia Regionals Online Contest (1) ADI
    The2023ICPCAsiaRegionalsOnlineContest(1)AQualifiersRankingRules思路：按位次为第一关键字，场次为第二关键字排序即可。//AConemoretimes//nndbk#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmod=1e9+7;constintN......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99