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

A. Equivalent Prefixes

很水的单调队列
首先说是处理最低位置一样 那么肯定队首存的下标一样
其次 1 ~ p 位置区间内每部分最小对应下标一样 那样的话 队列每次进入一个元素就可以想到
如果每部分最小下标对应一样 那样队列队尾弹出数量应该是一致的 只需要保证 队列大小一致就完成了
第一个可以去掉 因为弹出一致了

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
 
const int maxn = 1e5 + 5;
deque<int> s1;
deque<int> s2;
int a[maxn], b[maxn];
int n;
 
int main(){
    while(scanf("%d", &n) != -1){
        int f = 0;
        while(!s1.empty()) s1.pop_back();
        while(!s2.empty()) s2.pop_back();
        for(int i = 1; i <= n; i ++) scanf("%d", a + i);
        for(int i = 1; i <= n; i ++) scanf("%d", b + i);
        for(int i = 1; i <= n; i ++) {
            while(!s1.empty() && a[s1.back()] > a[i]) s1.pop_back();
            s1.push_back(i);
            while(!s2.empty() && b[s2.back()] > b[i]) s2.pop_back();
            s2.push_back(i);
            if(s1.size() != s2.size()){
                cout << i - 1 << endl;
                f = 1;
                break;
            }
            //if(s1.front() != s2.front()){
            // cout << i - 1 << endl;
            // f = 1;
            // break;
            //} 这个可以去掉 因为 弹出都一致了
        }
        if(!f) cout << n << endl;
    }
    return 0;
}

B. Integration

数学专业就是不一样啊 啥是复变啊 那个是啥定理啊 他给我张纸 我看的一脸懵逼啊 orz
总而言之 1 / [（b * b + x * x）* (c * c + x* x) ]
就是 1 / [ (b * b - c * c ) * (c * c + x * x) ] + 1 / [ (c * c - b * b) * (x * x + b * b)] ;

#include<iostream>
#include<cstdio>
#include <queue>
#define int long long
using namespace std;
typedef long long ll;
 
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
 
int n;
int a[maxn], b[maxn];
 
ll pow_mod(ll a, ll b) {
    ll ans = 1; a %= mod;
    while (b) {
        if (b & 1) {
            ans = ans * a % mod;
            b--;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
 
signed main(){
    while(cin >> n) {
 
        for(int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i] * a[i] % mod;
        int ans = 0;
 
        for(int i = 1; i <= n; i ++) {
 
            int tmp = 2 * a[i] % mod;
 
            int tp = a[i] * a[i] % mod;
 
            for(int j = 1; j <= n; j ++) {
                if(j == i) continue;
                tmp = (tmp * (b[j] - tp)) % mod;
            }
 
            ans = (ans + pow_mod(tmp, mod - 2)) % mod;
        }
 
        cout << (ans+mod)%mod << endl;
    }
    return 0;
}

E. ABBA

贪心的认为 前n个A都是AB的A 后面的都是 BA的 A 补充的 同理B也是
dp[i][j] 代表方案数 i 是 A数量 j 是 B 数量
那么 我们考虑 i_A - nAB_A 数量 应该是 mBA_A 的数量
当出现 i_A - nAB_A < mBA_A 时肯定是A不够 我们选择在之前随便一个位置加上 BA的A 这里就会是 += dp[i][j]的方案数量
B 同理

#include<iostream>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int maxn = 2e3 + 5;
int dp[maxn][maxn];
int n, m;

signed main(){
    while(cin >> n >> m) {
        for(int i = 0; i <= n + m; i ++) {
            for(int j = 0; j <= m + n; j ++) {
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1;
        for(int i = 0; i <= n + m; i ++) {
            for(int j = 0; j <= n + m; j ++) {
                if( i - n < j) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
                }
                if( j - m < i) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
                }
            }
        }
        cout << dp[n + m][n + m] << endl;
    }
    return 0;
}

F. Random Point in Triangle

这题 不用想 肯定猜 1 到 18 的系数 和面积的关系
然后 有一个比较扯的方法
就是三角形 每个边取4等分点 平行相连 我们用这个方法算期望 猜系数
估了下 在 10 到15 之间 试一试 就wa 1发过了…orz

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
  
const ll maxn=1e3+10;
  
ll dp[maxn][maxn];
  
int main(){
    ll a,b,c,d,e,f,g,S;
    while(cin>>a>>b>>c>>d>>e>>f){
        S=11*abs((c-a)*(f-b)-(d-b)*(e-a));
        cout<<S<<endl;
         
    }
    return 0;
}

H. XOR

线性基 处理出64 x 64 表达这些数据的 矩阵
子集大小处理成 我们选取数据的组合方案和
先求出 这n数据 的 线性基 当然他的线性基不唯一
我们先求出一个 那么 这个线性基 和外部的组合方案 就是pow(2, N_R + 1) * (n - r)
其次 我们考虑 多个线性基的情况 他们的方案数 同样也是pow(2, N_R + 1) 组合
为了 避免 我们重复对 剩下的 N_R 进行重复计算 我们只需要 预先处理出N_R基 然后 每次从R基拿一个 暴力搞一遍 看看 这个 vec[i] 是不是可以替代掉 就加上这一次的方案

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
 
int n;
bool vis[maxn];
vector<ll> vec;
ll R[70], N_R[70], tmp[70];
ll a[maxn];
 
ll q_mod(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
bool ins(ll x, ll base[]){
    for(int i = 63; i >= 0; i--){
        if(x & (1ll << i)) {
            if(base[i]) x ^= base[i];
            else{
                base[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
 
int main(){
    while(scanf("%d",&n) != EOF) {
        int r = 0;
        vec.clear();
        for(int i = 0; i <= 63; i ++) R[i] = 0;
        for(int i = 1; i <= n; i ++){
            scanf("%lld", &a[i]);
            vis[i] = 0;
            if(ins(a[i], R)) vis[i] = 1, r++, vec.push_back(a[i]);
        }
        if(r == n) {
            puts("0");
            continue;
        }else{
            ll ans = q_mod(2, n - r - 1) * (n - r) % mod;
            for(int j = 0; j <= 63; j ++) N_R[j] = 0;
             
            for(int i = 1; i <= n; i ++) {
                if(vis[i]) continue;
                ins(a[i], N_R);
            }
         
            for(int i = 0; i < vec.size(); i ++ ) {
                int cnt = 0;
                for(int j = 0; j <= 63; j ++) tmp[j] = 0;
                for(int j = 0; j <vec.size(); j ++ ) {
                    if(i == j) continue;
                    ins(vec[j], tmp);
                }
                 
                for(int j = 0; j <= 63; j ++)
                    if(N_R[j]) ins(N_R[j], tmp);
                 
                if(!ins(vec[i], tmp)) ans = (ans + q_mod(2, n - r - 1) ) % mod ;
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

I. Points Division

A, B 两个位置 有不同权重
不存在a∈A和b∈B，使得xa>=xb且ya<=yb;
也就是 对于所有 A 都在 B 左边上方
dp[i] = max dp[1~i] + b[i];
用线段树处理的是 离散化后 Y轴 每个点对之后位置的贡献度

每次放入一个点 它对之后的点的影响 如果对于 之后某些点低于它 会贡献a[i] 所以我们向y点之前 更新a[i] 的值

如果对于 之后某些点高于它 会贡献b[i] 所以我们向y点之后 更新b[i] 的值

我们每放 一个点到线上 查询 这个点之前可以影响它 的 A 集合 可以贡献最大的值 加上当前这个点的B[i] 是否会变的更大 进行更新
这里不在需要dp数组 因为线段树最后维护就是我们的最大值了
ps 我们很关键的是要补 0 如果 B集合什么都没有的话
我们没有把A的值更新进去 第一个点 1 - 1 会丢掉
补个0X3F点 防止 y + 1 越界

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
 
int n;
struct node {
    int x, y, a, b;
    bool operator < (const node &a) const {
        return x < a.x || (x == a.x && y > a.y);
    }
} a[maxn];
int ly[maxn];
ll ma[maxn << 2], lazy[maxn << 2];
 
void push_up(int rt) {
    ma[rt] = max(ma[rt << 1], ma[rt << 1 | 1]);
}
 
void push_down(int rt) {
    ma[rt << 1 | 1] += lazy[rt] ;
    ma[rt << 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt << 1] += lazy[rt];
    lazy[rt] = 0;
}
 
void build(int l, int r, int rt){
    ma[rt] = lazy[rt] = 0;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
}
 
void update1(int L, int l, int r, int rt, ll c) {
    if(l == r) {
        ma[rt] = max(c, ma[rt]);
        return ;
    }
    if(lazy[rt]) push_down(rt);
    int mid = l + r >> 1;
    if(L <= mid) update1(L, l, mid, rt << 1, c);
    else update1(L, mid + 1, r, rt << 1 | 1, c);
    push_up(rt);
}
 
void update2(int L, int R, int l, int r, int rt, ll c) {
    if(L <= l && R >= r) {
        ma[rt] += c;
        lazy[rt] += c;
        return ;
    }
    if(lazy[rt]) push_down(rt);
    int mid = l + r >> 1;
    if(L <= mid) update2(L, R, l, mid, rt << 1, c);
    if(R > mid) update2(L, R, mid + 1, r, rt << 1 | 1, c);
    push_up(rt);
}
 
ll query(int L, int R, int l, int r, int rt) {
    if(L <= l && R >= r) return ma[rt];
    if(lazy[rt]) push_down(rt);
    int mid = l + r >> 1;
    ll res = 0;
    if(L <= mid) res = max(query(L, R, l, mid, rt << 1), res);
    if(R > mid) res = max(query(L, R, mid + 1, r, rt << 1 | 1), res);
    return res;
}
 
signed main() {
    while(scanf("%lld", &n) != EOF){
        for(int i = 1; i <= n; i ++)
            scanf("%lld %lld %lld %lld", &a[i].x, &a[i].y, &a[i].a, &a[i].b), ly[i] = a[i].y;
        ly[n + 1] = 0, ly[n + 2] = 0x3f3f3f3f;
        sort(ly + 1, ly + 2 + n);
        int cnt = unique(ly + 1, ly + 3 + n) - ly - 1;
         
        for(int i = 1; i <= n; i ++ )
            a[i].y = lower_bound(ly + 1, ly + 1 + cnt, a[i].y) - ly;
         
        sort(a + 1, a + 1 + n);
        build(1, cnt, 1);
        for(int i = 1; i <= n; i ++) {
            ll tmp = query(1, a[i].y, 1, cnt, 1);
            update1(a[i].y, 1, cnt, 1, tmp + a[i].b);
            update2(1, a[i].y - 1, 1, cnt, 1, a[i].a);
            update2(a[i].y + 1, cnt, 1, cnt, 1, a[i].b);
        }
        printf("%lld\n", ma[1]);
    }
    return 0;
}

J. Fraction Comparision

python 嚎啊

while True:
    try:
        x,y,a,b=map(int,input().split())
 
        if x * b > y * a:
            print(">")
        elif x * b < y * a:
            print("<")
        else:
            print("=")
    except:
        break

c 版本
官方题解 菜啊当时