[ 牛 客 ] “補題|總結|題解“ 牛客小白月賽35

[ 傳 送 門 ]

目錄

• B.我(不)是酸菜魚
• • 前言
  • 思路
  • 疑問
  • code:
• C:逆元處理 (闆子題 哭唧唧)
• • 思路
  • CODE:
• H-登入!(字元串 我投降了)
• • 思路
  • 正解CODE
  • 50%CODE

B.我(不)是酸菜魚

前言

• 題做少了 乘積的符号 看成 求和了
• 還有就是範圍也看錯了 以為是(1e15)去了

思路

• 第一步

  我最不懂的一點

  g%(2^k) == 0 ( k 就表示g 的 後導0的個數 ) -----> 為什麼這樣就能被整除了(雖然試了好幾個的确是這樣)

• 第二步

  兩個數相乘所得結果的 後導0 為 這兩個數的後導0個數之和

  (樣例推導)

  

疑問

既然範圍才是2e15 我能不能用 a*b mod p = (a mod p * b mod p) mod p 來優化防止爆longlong

然後就可以預處理2^的數組 之後 每個驗證一遍即可

(好像是不行 看了一下别人代碼 沒人這麼寫)

code:

#include <bits/stdc++.h>
#define  IOS ios::sync_with_stdio(false)

using namespace std;
const int N = 2e5+10;
int n,t,k;

void solve()
{
    cin>>n;
    int sum = 0 ;
    while(n -- )
    {
        int x;

        cin>>x;
        while(x%2 == 0)
            
        {
            sum++;
            x/=2;
        }
    }
    cout<<sum<<endl;
}
int main()
{
    IOS;
    int t;
    solve();

    return 0 ;
}
           

C:逆元處理 (闆子題 哭唧唧)

思路

• 楊輝三角 第n行第m個數的公式為 (具體證明看百度 QAQ 真不會 疏學)

  

  (是以呢 我們直接套 組合數模闆就行 因為這個範圍在1e5範圍左右且 p為質數 1e9+7)

https://oi-wiki.org/math/lucas/(詳情請看)

CODE:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int mod = 1e9+7;
ll fact[N],infact[N];
ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

void init(int n)
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i <=n; i ++ )
    {
        fact[i] = (ll)fact[i - 1] * i % mod;
        infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

ll c(int  a, int b )
{
    return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
    int n;
    cin>>n;
    --n;
    init(n);
    ll ans=1;
    for(int i=1; i<=n; ++i)
        ans=ans*c(n,i)%mod;
    cout<<ans<<endl;
}
           

H-登入!(字元串 我投降了)

思路

直接模拟即可

但是字元串處理emmm

還有的就是 牛客上面分行顯示的可能是一行輸入

正解CODE

#include <bits/stdc++.h>
using namespace std;
string s,s2="name=\"csrfmiddlewaretoken\"",s3="value=\"",s4;
bool flag;
int main()
{
    while(getline(cin,s))
    {
        if(s.find(s2)!=string::npos)
        {
            flag=true;
        }
        if(flag)
        {
            int idx=s.find(s3);
            if(idx==(int)string::npos) continue;
            for(int i=idx+7;s[i]!='\"';i++)
                s4+=s[i];
            cout << s4 << endl;
            return 0;
        }
    }
}
           

50%CODE

#include <bits/stdc++.h>
using namespace std;
string s;
string temp ="value=";
void solve()
{
    string ans;
    while(getline(cin,s))
    {
        int flag =s.find(temp);
        if(flag  != string::npos)
        {
            int len = s.size();
            int len2=ans.size();
            if(len2<len)
            ans = s;
        }

    }
       int idx = ans.find(temp);
     //  cout<<ans[idx+7]<<endl;
     int len  = ans.size();
     for(int i=idx+7;i<len-2;i++)
    cout<<ans[i];
}
int main()
{
    solve();
    return 0;
}