牛客周赛 Round 60(思维、逆元、组合数、概率DP)

牛客周赛 Round 60(思维、逆元、组合数、概率DP)

---

F题，概率DP不会，学了再补

---

A. 困难数学题

• x ^ x = 0
• 0 ^ x = x
• ^ 表示二进制异或

#include<bits/stdc++.h>

using namespace std;

int main(){

cout << 0 << endl;

return 0;
}

B. 构造序列

注意是ABAB，还是ABABA

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){

    ll a, b;
    cin >> a >> b;
    
    cout << min(a, b) * 2 + (a != b) << endl;
    
return 0;
}

C. 连点成线

统计每行每列出现的最大值和最小值，做差取max即可，

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

vector<int> row[maxn], column[maxn];

int main(){

int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
row[x].push_back(y);
column[y].push_back(x);
}

int res = 0;
for(int i = 1; i <= n; i++){
if(row[i].size() > 1){
sort(row[i].begin(), row[i].end());
res = max(res, *(row[i].end() - 1) - row[i][0]);// row[i].end() 是指针，表示row[i]最后一个元素的后一位的地址
}
if(column[i].size() > 1){
sort(column[i].begin(), column[i].end());
res = max(res, *(column[i].end() - 1) - column[i][0]);
}
}
cout << res << endl;

return 0;
}

D. 我们N个真是太厉害了(思维)

如果当前序列 A，任选元素加和，可以构成出排列 1、2、3、…、mx。

向序列A中加入元素 x 后，如果 x <= mx +1，这时可以构成的排列变为 1、2、3、…、mx、mx+1、…、mx + x。

根据题意，对a排序，依次遍历，不断维护mx，并判断 a[i] 是否小于等于 mx+1。如出现 a[i] > mx+1，则 mx+1 为第一个不能被加和得到的数。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int a[maxn];

int main(){

int ncase;
    cin >> ncase;
    
    while(ncase--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        
        sort(a+1, a+1+n);
        
        int res = -1;
        if(a[1] != 1) res = 1;
        else{
            int mx = 1;
            for(int i = 2; i <= n; i++){
                if(a[i] <= mx + 1) mx += a[i];
                else{
                    res = mx + 1;
                    break;
                }
                if(mx >= n) break; // 一点点优化
            }
        }
        if(res == -1) cout << "Cool!" << endl;
        else cout << res << endl;
    }

return 0;
}

E. 折返跑(小费马定理求逆元、组合数)

对于一次查询 n 和 m，可以理解为在 n-2 个点中选 m - 1 个点出来，选择的方案数即为结果。（n-2：去除掉开始和结尾）

综上：$res=C_{n-2}^{m-1}$

用小费马定理求逆元计算组合数即可。
PS：第一眼以为是DP，稍微写一下状态转移方程，就可以发现是组合数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;

ll qpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return res;
}

ll f[maxn], p[maxn];
ll C(ll a, ll b){
    return f[a] * p[b] % mod * p[a-b] % mod;
}

int main(){

    f[0] = 1;
    for(int i = 1; i < maxn; i++) f[i] = f[i-1] * i % mod;
    for(int i = 0; i < maxn; i++) p[i] = qpow(f[i], mod-2); // 费马小定理求逆元
    
int ncase;
cin >> ncase;
while(ncase--){
ll n, m;
        cin >> n >> m;
n -= 2; m -= 1;
        if(n <= 0 || m <= 0) cout << 1 << endl;
        else cout << C(n, m) << endl;
}

return 0;
}

F. 口吃（概率DP）

先挖坑。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 5;
ll a[maxn], b[maxn];

ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res *= a;
res %= mod;
a *= a;
a %= mod;
b >>= 1;
}
return res;
}

int main(){

int n;
cin >> n;
for(int i = 1; i < n; i++) cin >> a[i];
for(int i = 1; i < n; i++) cin >> b[i];

ll num = 1 + b[1] * qpow(a[1], mod-2) % mod;
ll res = num;
for(int i = 2; i < n; i++){
num = (a[i] + b[i]) * (a[i] + b[i]) % mod + num * b[i] % mod * b[i] % mod;
num = num * qpow(a[i], mod-2) % mod * qpow(a[i], mod-2) % mod;
res = (res + num) % mod;
}

cout << (res + 1) % mod << endl;

return 0;
}

原文地址：https://blog.csdn.net/mldl_/article/details/142344356

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！