2019牛客暑期多校(第二场) 写题记录

A Eddy Walker

你有n个点（0～n-1），按顺序形成一个环，初始时你在0的位子，你随机顺时针走一步或者逆时针走一步
问你全部路过完时停在哪里的概率 除了 0 点 其他是等可能的 特判 一个点 就好

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const int maxn = 1000 + 5;
const int mod = 1e9 + 7;
 
int n, m, t, ans;
 
int q_mod(int a, int b){
    int res = 1;
    for(; b; b >>= 1){
        if(b & 1) res = 1ll*res * a % mod;
        a = 1ll*a * a % mod;
    }
    return res;
}
 
int main(){
    fastio;
    cin >> t;
    ans = 1;
    while(t--) {
        cin >> n >> m;
        if(n == 1){
            ans*=1;
            cout << ans << endl;
        }
        else if(m == 0){
            ans = 0;
            cout << 0 << endl;
             
        }
        else cout << (ans = (1ll*ans * q_mod(n - 1, mod - 2)%mod)) << endl;
    }
    return 0;
}

D Kth Minimum Clique

考察关于团的知识
团 加入一个点 这个点 必须与其他点 相连 相当于 这个点集合 是个完全图
加入这个点 即这个点集合的点 与 未在点集的点 & 运算 当前 点集依然是 之前点集合 便可以加入
BFS 拓展这个团就好 对每个团 记录它最后的点 我们按顺序加入 每次扫它记录最后点位置之后的加入 就可以去重

#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <string>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const int maxn = 105;
 
int n, k;
int w[maxn];
bitset<105> f[maxn];
 
struct node{
    ll val;
    int p;
    bitset<105> vis;
    bool operator < (const node &a)const {
        return val > a.val;
    }
};
 
priority_queue<node> que;
 
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> w[i];
    for(int i = 1; i <= n; i ++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) f[i][j + 1] = s[j] - '0';
    }
    que.push(node{0, 0, bitset<105>(0)});
    while(!que.empty()){
        node tmp = que.top(); que.pop();
        k--;
        if(k == 0) {
            cout << tmp.val << endl;
            return 0;
        }
        bitset<105> v = tmp.vis;
        for(int i = tmp.p + 1; i <= n; i ++) {
            if(((v & f[i]) == v)){
                v[i] = 1;
                int p;
                for(int i = 0; i <= n; i ++) if(v[i]) p = i;
                que.push(node{tmp.val + w[i], p, v});
                v[i] = 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

F Partition problem

这题重点不是剪枝 而是 最后我们统计ans 我们不应该N^2求 必然T 而是在过程中 就进行 对这个分集合 的竞争度计算 就不tle了orz

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
typedef long long LL;
 
int n;
LL v[N + N][N + N], ans;
int a[N], b[N];
 
void dfs(int u, int cnt1, int cnt2, LL sum) {
    if(cnt1 > n || cnt2 > n) return ;
    if(cnt1 == n && cnt2 == n) {
        ans = max(sum, ans);
        return ;
    }
    LL tmp = 0;
    if(cnt1 < n){
        a[cnt1 + 1] = u;
        for(int i = 1; i <= cnt2; i ++) tmp += v[u][b[i]];
        dfs(u + 1, cnt1 + 1, cnt2, sum + tmp);
    }
    tmp = 0;
    if(cnt2 < n) {
        b[cnt2 + 1] = u;
        for(int i = 1; i <= cnt1; i ++) tmp += v[u][a[i]];
        dfs(u + 1, cnt1, cnt2 + 1, sum + tmp);
    }
}
 
int main() {
    cin >> n;
    for(int i = 1; i <= 2 * n; i ++ )
        for(int j = 1; j <= 2 * n; j ++ )
            cin >> v[i][j];
     
    dfs(1, 0, 0, 0);
    cout << ans << endl;
     
    return 0;
}

H Second Large Rectangle

悬线法 单调栈维护都是一样的东西
只要记录下标就好 去重
当时我写的很暴力啊 23333 全枚举出来居然没有T

#include <bits/stdc++.h>
 
using namespace std;
const int maxn = 1000 + 5;
 
int n, m;
int h[maxn][maxn];
int q[maxn], l[maxn], r[maxn];
 
int sol(int l[], int a[]){
    a[0] = -1;
    int t = 0;
    for(int i = 1; i <= m; i ++ ) {
        while(a[q[t]] >= a[i]) t --;
        l[i] = q[t] + 1;
        q[ ++ t ] = i;
    }
    return 0;
}
 
struct node{
    int a,b,c,d;
    int ar;
    bool operator < (node const &aaa) const {
        return ar > aaa.ar;
    }
};
 
vector<node> aa;
 
int ans1, ans2, ans3, ans;
 
int work(int a[], int kk){
    sol(l, a);
    reverse(a + 1, a + 1 + m);
    sol(r, a);
    reverse(a + 1, a + 1 + m);
    int res = 0;
 
    for(int i = 1; i <= m; i ++ ) {
        int le = l[i];
        int ri = m + 1 - r[m - i + 1];
        res = max(res, a[i] * (ri - le + 1));
        if((ri - le + 1) * a[i]) {
                aa.push_back(node{kk - a[i] + 1,l[i], kk , ri, (ri - le + 1) * a[i]});
                if(a[i] > 1) {
                    aa.push_back(node{kk - a[i],l[i], kk , ri, (ri - le + 1) * (a[i] - 1)});
                }
                if((ri - le + 1) > 1) {
                     aa.push_back(node{kk - a[i] + 1,l[i], kk , ri - 1, (ri - le) * (a[i])});
                }
        }
    }
    return res;
}
 
char mp[maxn][maxn];
 
int main(){
    cin >> n >> m;
    int ans = 0;
    for(int i = 1; i <= n; i ++ ) {
        cin >> (mp[i] + 1);
        for(int j = 1; j <=m; j ++ ) {
            if(mp[i][j] == '1') h[i][j] = h[i - 1][j] + 1;
            else continue;
        }
         work(h[i], i);
    }
    int f = 1;
    if(aa.size() == 0) {
        cout << 0 << endl;
        return 0;
    }
   sort(aa.begin(), aa.end());
    int a = aa[0].a, b = aa[0].b , c = aa[0].c, d = aa[0].d;
    for(int i = 0; i < aa.size(); i++) {
        //cout << aa[i].a << " " << aa[i].b << " " << aa[i].c << " " << aa[i].d << " " << aa[i].ar << endl;
        if(a != aa[i].a || b != aa[i].b || c != aa[i].c || d != aa[i].d) {
             f = 0;
            cout << aa[i].ar << endl;
            break;
        }
    }
  // cout << aa.size() << endl;
    if(f) cout << 0 << endl;
    // for(int i = 1; i <= n; i ++ ){
    // for(int j = 1; j <= m; j ++ ){
    // cout << h[i][j] << " ";
    // }cout << endl;
    // }
 
  // cout << ans2 << endl;
    return 0;
}