牛客算法周周练2

A
看到要去前导0，直接字符串模拟了，倒着的时候从第一个不为0的数字开始计算这个数字大小，加上原来数字即可

#include
using namespace std;
typedef long long ll;
int main(){
   char s[10];
   cin>>s;
   int sum=0;
   for(int i=0;i<strlen(s);i++) sum=sum*10+s[i]-'0';
   int flag=0;
   int a=0;
   for(int i=strlen(s)-1;i>=0;i--){
      if(s[i]!='0'){
         flag=1;
      }
      if(flag){
         a=a*10+s[i]-'0';
      }
   }
   cout<<sum+a<<endl;
   return 0;
}

B
问题：将一些数字取任意个相加能不能拼凑出3600的倍数，就是背包有无解的问题。
两种做法。
第一种：直接bitset优化.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        bitset<3600> q;
        for(int i=1;i<=n;i++){
          int x;cin>>x;
          x%=3600;
          //右端第一部分是说已经有的基础上再加一个x， 第二部分是溢出3600的部分取余
          q |= (q << x) | (q >> (3600-x));
          q[x]=1;//将x添加上去
        }
        if(q[0]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

   return 0;
}

感谢评论区hx073269大哥指正第二种是个假算法复杂度爆掉了应该是数据水了。当然有兴趣的可以看下？(狗头
第二种，想一下，如果n≥3600一定有解，为什么？证明如下：
设 $图片说明$
如果对于n个sum取余3600后，余数在0到3599之间都有位置，显然有解。
如果在0~3599有的位置没有，说明至少存在两个位置的sum%3600后的值一样，那么区间的一段就是3600的倍数。得证。
所以n≥3600 直接输出YES
否则跑个背包判断有无解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> a(n+1);
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n>=3600) cout<<"YES"<<endl;
        else
        {
            vector<vector<int>> dp(n+1,vector<int>(3600));
            dp[0][0]=1;
            for(int i=0;i<n;i++){
                for(int j=0;j<3600;j++){
                    if(dp[i][j]){
                        dp[i+1][j]+=dp[i][j];
                        dp[i+1][(j+a[i+1])%3600]+=dp[i][j];
                    }
                }
            }
            if(dp[n][0]>1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }

   return 0;
}

C
判断l到r之间有多少个完全平方数，然后判断端点l是不是完全平方数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){

    int n;
    cin>>n;
    while(n--)
    {
        ll l,r;
        cin>>l>>r;
        ll s1=sqrt(l)+0.000001,s2=sqrt(r)+0.000001;
        ll num=s2-s1;
        if(s1*s1==l) num++;
        cout<<num<<endl;
    }
    return 0;
}

D
考虑开一个二维数组cnt[n][3]
cnt[i][0]表示i受到的波及次数，
cnt[i][1]表示i对儿子节点的波及次数
cnt[i][2]表示i对孙子节点的波及次数
那么对于每次询问，i肯定对i的儿子和孙子造成了波及，所以cnt[i][1]++,cnt[i][2]++
那么往上考虑，i也对他父亲和爷爷造成了波及所有 cnt[f[i]][0]++,cnt[f[f[i]][0]++
还有一点要注意，i本身和i的同父亲的兄弟也会收到波及，那么这里我们要怎么加呢？直接加到i的父亲节点对儿子节点的波及即可，也就是cnt[f[i]][1]++，这样就同时加入了i本身和他兄弟受到的影响
那么对于每个点i，受到的波及次数就是cnt[1][0]+cnt[f[i]][1]+cnt[f[f[i]][2]
即自身收到子节点的波及次数+父亲对自己的波及次数+爷爷对自己的波及次数

所以dfs求出每个点的父亲后按照上述过程模拟即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1<<20;
vector<int>e[maxn];
int cnt[maxn][3];///自己、儿子、孙子
int f[maxn];
void dfs(int x,int fa){
    f[x]=fa;
    for(auto it:e[x]){
        if(it==fa) continue;
         dfs(it,x);
    }
}
int main(){
    ios::sync_with_stdio(0);
   int n,m;cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1,0);
    f[0]=maxn-1;
    while(m--){
        int a;cin>>a;
        cnt[a][1]++,cnt[a][2]++;
        cnt[f[a]][1]++,cnt[f[a]][0]++;
        cnt[f[f[a]]][0]++;
        cout<<cnt[a][0]+cnt[f[a]][1]+cnt[f[f[a]]][2]<<endl;
    }
   return 0;
}

E
E题中的式子其实就是斐波那契数列的几何意义
图片说明
其实就是问n是不是斐波那契数，是的话输出它的阶乘在m进制下有多少个0，质因数分解完事。
不是的话，就是问1~13皇后有多少种分布方式。
懒得写了。。（其实是太菜了）还是补了一下

牛客算法周周练2

全站热榜

创作者周榜