• 2022/8/9

    ​

    活动地址：CSDN21天学习挑战赛

    1141C - Polycarp Restores Permutation

    假设p[1]为0，那么就可以通过q数组来求出每个p[i]相对于p[1]的增量了，然后找出最小的值这个值就是1，让这个数变为1的代价是x，每个数都加上x原排列就出来了

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=9999973;
    6. const int N = 2e5+5;
    7. ll n,a[200005],vis[400005];
    8. int main(){
    9.     scanf("%lld",&n);
    10.     a[1]=0;
    11.     ll minn=0;
    12.     for(int i=2;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1],minn=min(minn,a[i]);
    13.     for(int i=1;i<=n;i++) a[i]=a[i]+(1LL-minn);
    14.     ll m=0;
    15.     for(int i=1;i<=n;i++){
    16.         if(a[i]>n||a[i]<=0){m=-10;break;}
    17.         if(!vis[a[i]]) vis[a[i]]=1,m++;
    18.     }
    19.     if(m==n){
    20.         for(int i=1;i<=n;i++) printf("%lld ",a[i]);
    21.     }
    22.     else printf("-1");
    23.     system("pause");
    24.     return 0;
    25. }

    1395C - Boboniu and Bit Operations 状压dp 或 思维

    先说状压dp的做法，f[i][j]表示已经求出了c[i],前i个c[i]是否可以或成j，我们枚举a，枚举b,枚举当前状态也就是前i个c[i]或的和，然后枚举a[i]&b[j]的子集也就是c[i]的子集，看看是否可以转移到f[i][j],由于是枚举子集，所以时间复杂度会减少很多

    C. Boboniu and Bit Operations(状压)_issue是fw的博客-CSDN博客

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=9999973;
    6. const int N = 2e5+5;
    7. ll n,m,a[205],b[205],f[205][1<<10];
    8. int main(){
    9.     scanf("%lld%lld",&n,&m);
    10.     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    11.     for(int j=1;j<=m;j++) scanf("%lld",&b[j]);
    12.     f[0][0]=1;
    13.     for(int i=1;i<=n;i++)
    14.     for(int j=1;j<=m;j++){
    15.         ll v=a[i]&b[j];
    16.         for(int u=0;u<(1<<9);u++){
    17.             if((u&v)!=v) continue;//v中的1 u应该都有
    18.             for(int w=v;w;w=(w-1)&v)
    19.                 f[i][u]|=f[i-1][u^w];
    20.             f[i][u]|=f[i-1][u];
    21.         }
    22.     }
    23.     for(int i=0;;i++) 
    24.         if(f[n][i]){printf("%d ",i);break;}
    25.     system("pause");
    26.     return 0;
    27. }

    思维的做法：因为或运算只会让数不变或增加，所以最优的状态应该是不变，所以我们应该让c[i]都相同且尽量最小，如果c[i]不相同的话或出来的值会大于所有的c[i]这显然是不行的，所以最小值应该会出现在所有c[i]都相同的情况下，那我们就枚举测试每个答案行不行就可以了，因为数据范围小也用不到二分

    C. Boboniu and Bit Operations（位运算操作+思维）Codeforces Round #664 (Div. 2)_unique_pursuit的博客-CSDN博客

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=9999973;
    6. const int N = 2e5+5;
    7. ll n,m,a[205],b[205];
    8. bool check(ll s){
    9.     for(int i=1;i<=n;i++){
    10.         ll flag=0;
    11.         for(int j=1;j<=m;j++){
    12.             ll tmp=a[i]&b[j];
    13.             if((tmp|s)==s) flag=1;
    14.             if(flag) break;
    15.         }
    16.         if(!flag) return false;
    17.     }
    18.     return true;
    19. }
    20. int main(){
    21.     scanf("%lld%lld",&n,&m);
    22.     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    23.     for(int i=1;i<=m;i++) scanf("%lld",&b[i]);
    24.     for(int i=0;i<(1<<10);i++){
    25.         if(check(i)){printf("%d",i);break;}
    26.     }
    27.     system("pause");
    28.     return 0;
    29. }

    J-Melborp Elcissalc_"蔚来杯" dp 前缀和小技巧

    这个题也是用到了之前用到的前缀和技巧，但是比之前那个好像更难了点，对于一个前缀和来说，要求有多少区间的和是k的倍数，那我们可以对前缀和数组的每个数都取余k，之后每个数出现了x次就有C(x,2)个区间是k的倍数，0例外是C(x+1,2),因为1个0也满足条件；对于一个数组我们需要知道这个数组用到了0-k-1中的哪些数，这些数出现了多少次以及一共有多少区间符合条件，那我们就设一个dp[i][len][s]表示前i个数中用了len个，可以产生s个符合条件的区间，枚举到i，枚举想要用num个i，那么转移方程就是dp[i][len+num][s+C(num,2)]=dp[i-1][len][s],要是放0的话因为例外所以要是dp[i][len+num][s+C(num+1,2)],代码应该是因为方便转移将i都加了1位

    2022牛客暑期多校训练营7 个人题解 更新至5题 - 知乎 (zhihu.com)

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=998244353;
    6. const int N = 2e5+5;
    7. ll fac[105];
    8. ll qpow(ll a,ll b){
    9.     ll res=1;
    10.     while(b){
    11.         if(b&1) res=res*a%mod;
    12.         a=a*a%mod;
    13.         b>>=1;
    14.     }
    15.     return res;
    16. }
    17. ll getinv(ll a,ll mod){return qpow(a,mod-2);}
    18. ll C(ll x,ll y){//求组合数模板
    19.     return fac[x]*getinv(fac[y],mod)%mod*getinv(fac[x-y],mod)%mod;
    20. }
    21.  
    22. ll n,k,t,dp[70][70][3005],c[105][105];
    23. int main(){
    24.     fac[0]=1;
    25.     for(ll i=1;i<=70;i++) fac[i]=fac[i-1]*i%mod;
    26.     for(ll i=0;i<=64;i++)
    27.     for(ll j=i;j<=65;j++) 
    28.         c[j][i]=C(j,i);
    29.     scanf("%lld%lld%lld",&n,&k,&t);
    30.     dp[0][0][0]=1;
    31.     for(int i=1;i<=k;i++)
    32.         for(int len=0;len<=n;len++)
    33.             for(int s=0;s<=t;s++)
    34.             if(dp[i-1][len][s])
    35.             for(int num=0;num+len<=n;num++){
    36.                 if(i==1) dp[i][num+len][c[num+1][2]+s]=(dp[i][num+len][c[num+1][2]+s]+dp[i-1][len][s]*c[num+len][num]%mod)%mod;
    37.                 else dp[i][num+len][c[num][2]+s]=(dp[i][num+len][c[num][2]+s]+dp[i-1][len][s]*c[num+len][num]%mod)%mod;
    38.             }
    39.     printf("%lld",dp[k][n][t]);
    40.     system("pause");
    41.     return 0;
    42. }

    P1896 [SCOI2005] 互不侵犯 - 洛谷 | 状态压缩dp

    之前做过的一道题，当时的思想没有跟上现在来重新做一遍，这其实很像n皇后问题，之前是用搜索做，现在是用代码更简单的dp来做，用一个二进制数来表示一行的放置情况，预处理出所有合法情况之后枚举每行的情况，和上一行作比较如果可行就枚举已经放了多少个国王来进行转移

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=998244353;
    6. const int N = 2e5+5;
    7. ll n,m,dp[10][1<<9][105];
    8. ll ok[1<<9],cnt=0;
    9. int main(){
    10.     scanf("%lld%lld",&n,&m);
    11.     for(int i=0;i<1<
    12.         if(i&i>>1||i&i<<1) continue;
    13.         ok[++cnt]=i;
    14.     }
    15.     dp[0][1][0]=1;
    16.     for(int i=1;i<=n;i++)
    17.     for(int j=1;j<=cnt;j++)
    18.     for(int k=1;k<=cnt;k++){
    19.         if(ok[j]&ok[k]||ok[j]>>1&ok[k]||ok[j]<<1&ok[k]) continue;
    20.         ll x=__builtin_popcount(ok[j]),y=__builtin_popcount(ok[k]);
    21.         for(int l=y;l<=m-x;l++) dp[i][j][l+x]+=dp[i-1][k][l];
    22.         //第k种情况已经有y个了，前i-2行可能也有放置的国王，所以从y开始枚举
    23.     }
    24.     ll ans=0;
    25.     for(int i=1;i<=cnt;i++) ans+=dp[n][i][m];
    26.     printf("%lld\n", ans);
    27.     system("pause");
    28.     return 0;
    29. }

    P1879 [USACO06NOV]Corn Fields G - 洛谷 | 状压dp

    这题和上一题是差不多的思路，这一个还少了个条件不需要考虑放的个数了，但是需要判断是不是和初始的情况一致，这个一个for循环就可以判断了

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=100000000;
    6. const int N = 2e5+5;
    7. ll n,m,dp[20][1<<12],a[20][20];
    8. ll ok[1<<12],cnt=0;
    9. int main(){
    10.     scanf("%lld%lld",&m,&n);
    11.     for(int i=1;i<=m;i++)
    12.     for(int j=1;j<=n;j++)
    13.         scanf("%lld",&a[i][j]);
    14.     for(int i=0;i<1<
    15.         if(i&i>>1||i&i<<1) continue;
    16.         ok[++cnt]=i;
    17.     }
    18.     dp[0][1]=1;
    19.     for(int i=1;i<=m;i++)
    20.     for(int j=1;j<=cnt;j++)
    21.     for(int k=1;k<=cnt;k++){
    22.         if(ok[j]&ok[k]) continue;
    23.         ll flag=1;
    24.         for(int l=1;l<=n;l++)
    25.             if(ok[j]>>l-1&1!=a[i][n-l+1]){flag=0;break;}
    26.         if(flag) dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
    27.     }
    28.     ll ans=0;
    29.     for(int i=1;i<=cnt;i++) ans=(ans+dp[m][i])%mod;
    30.     printf("%lld\n", ans);
    31.     system("pause");
    32.     return 0;
    33. }

    P2148 [SDOI2009] E&D - 洛谷 | sg函数

    看了一下sg函数，套路就是根据题意打表然后找规律，求出sg函数之后判断异或和

    这是打的表

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=100000000;
    6. const int N = 2e5+5;
    7. ll t,n;
    8. // ll sg(ll a,ll b){
    9. //     if(a%2&&b%2) return 0;
    10. //     if(a%2&&b%2==0) return sg(b,a);
    11. //     if(a%2==0&&b%2) return sg(a,b+1);
    12. //     if(a%2==0&&b%2==0) return sg(a/2,b/2)+1;
    13. // }
    14. // ll db(ll a,ll b){
    15. //     if(dbsg[a][b]) return dbsg[a][b];
    16. //     vectorv;
    17. //     for(ll i=1;i<=a;i++) v.push_back(db(i,a-i));
    18. //     for(ll i=1;i<=b;i++) v.push_back(db(i,b-i));
    19. //     sort(v.begin(),v.end());
    20. //     ll x=0;
    21. //     for(int i=0;i
    22. //         if(x!=v[i]) return dbsg[a][b]=x;
    23. //         x=v[i]+1;
    24. //     }
    25. //     return x;
    26. // }
    27. std::map, ll> sg;
    28.  
    29. int calc(pair c) {
    30.     if (sg.count(c)) return sg[c];
    31.     std::vector<int> s;
    32.     for(int i=1;i<=c.first-1;i++) s.push_back(calc({i, c.first - i}));
    33.     for(int i=1;i<=c.second-1;i++) s.push_back(calc({i, c.second - i}));
    34.     std::sort(s.begin(), s.end());
    35.     s.erase(std::unique(s.begin(), s.end()), s.end());
    36.     ll lst = -1;
    37.     for (auto i : s) {
    38.         if (i != lst + 1) return sg[c] = lst + 1;
    39.         lst = i;
    40.     }
    41.     return sg[c] = lst + 1;
    42. }
    43. int main(){
    44.     for(int i=1;i<=20;i++){
    45.         for(int j=1;j<=20;j++)
    46.         cout<<calc({i,j})<<"\t";
    47.         cout<<"\n";
    48.     }
    49.     system("pause");
    50.     return 0;
    51. }

    这是ac代码

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=100000000;
    6. const int N = 2e5+5;
    7. ll t,n;
    8. ll sg(ll a,ll b){
    9.     if(a%2&&b%2) return 0;
    10.     if(a%2&&b%2==0) return sg(b,a);
    11.     if(a%2==0&&b%2) return sg(a,b+1);
    12.     if(a%2==0&&b%2==0) return sg(a/2,b/2)+1;
    13. }
    14. int main(){
    15.     scanf("%lld",&t);
    16.     while(t--){
    17.         ll res=0;
    18.         scanf("%lld",&n);
    19.         for(int i=2;i<=n;i+=2){
    20.             ll a,b;
    21.             scanf("%lld%lld",&a,&b);
    22.             res^=sg(a,b);
    23.         }
    24.         if(res) printf("YES\n");
    25.         else printf("NO\n");
    26.     }
    27.     system("pause");
    28.     return 0;
    29. }

  • 相关阅读:
    Windows 的 PowerShell 提供了哪些命令
    FSC认证助您进入日新月异的时尚领域
    2023计算机毕业设计SSM最新选题之java企业员工信息管理系统677du
    猿创征文｜python求解四位数 青少年编程电子学会python编程等级考试三级真题解析2021年03月
    Linux基本使用
    虹科方案 | 汽车CAN/LIN总线数据采集解决方案
    C语言条件运算符——三元表达式例题（素材来自C技能树）
    删除不成功的免密登录重新做免密
    SpringMVC工作原理
    堆栈的类型及特点
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126247216