文章/答案/技术大牛

发布

社区首页 >专栏 >如果牛客多校你都能 hold 了，ACM 金牌还远吗？

如果牛客多校你都能 hold 了，ACM 金牌还远吗？

ACM算法日常

发布于 2021-09-28 08:27:46

90500

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

每年的暑假，所有的 XCPC 竞赛者几乎都会不约而同的参加在牛客上主办的多校联合训练。

今天我们来看一下 2019 年牛客训练第一套题目。

题目地址

https://ac.nowcoder.com/acm/contest/881

Problem A

题意：给定两个

1

$1$

n

$n$

的排列

{a_{i}}, {b_{i}}

$\{a_i\},\{b_i\}$

，求最大的

m

$m$

，使得

R M Q (a, l, r) = R M Q (b, l, r)

$RMQ(a,l,r)=RMQ(b,l,r)$

对所有

1 \leq l \leq r \leq m

$1 \le l \le r \le m$

成立，其中

R M Q (c, l, r)

$RMQ(c,l,r)$

是

c_{l}, c_{l + 1}, \dots, c_{r}

$c_l,c_{l+1},\dots,c_r$

中最小元素的下标。

题解：考虑对任意

m

$m$

判断是否满足条件。我们发现，若

R M Q (a, 1, m) \neq R M Q (b, 1, m)

$RMQ(a,1,m) \neq RMQ(b,1,m)$

则肯定不满足条件，否则对所有

l \leq m \leq r

$l \le m \le r$

，

R M Q (a, l, r) = R M Q (b, l, r)

$RMQ(a,l,r)=RMQ(b,l,r)$

。此时对

(l, m - 1)

$(l,m-1)$

和

(m + 1, r)

$(m+1,r)$

递归求解就可以判断

1 m

$1~m$

是否满足条件。

因此，对

m

$m$

二分求解，就可以找到最大的

m

$m$

。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],b[maxn],fa[maxn][20],fb[maxn][20];
int geta(int x,int y){
    return a[x]<a[y]?x:y;
}
int getb(int x,int y){
    return b[x]<b[y]?x:y;
}
void init(){
    for (int i=1;i<=n;i++) fa[i][0]=i;
    for (int i=1;(1<<i)<=n;i++) for (int j=1;j+(1<<i)-1<=n;j++)
        fa[j][i]=geta(fa[j][i-1],fa[j+(1<<(i-1))][i-1]);
    for (int i=1;i<=n;i++) fb[i][0]=i;
    for (int i=1;(1<<i)<=n;i++) for (int j=1;j+(1<<i)-1<=n;j++)
        fb[j][i]=getb(fb[j][i-1],fb[j+(1<<(i-1))][i-1]);
}
int querya(int l,int r){
    int k=int(log(double(r-l+1))/log((double)2));
    return geta(fa[l][k],fa[r-(1<<k)+1][k]);
}
int queryb(int l,int r){
    int k=int(log(double(r-l+1))/log((double)2));
    return getb(fb[l][k],fb[r-(1<<k)+1][k]);
}
bool check(int l,int r){
    if (l>=r) return true;
    int ma,mb;
    ma=querya(l,r); mb=queryb(l,r);
    if (ma!=mb) return false;
    int m=ma;
    return check(l,m-1)&&check(m+1,r);
}
int sear(int l,int r){
    if (r-l==1) return l;
    int m=(l+r)/2;
    if (check(1,m)) return sear(m,r);
    else return sear(l,m);
}
int main(){
    int i;
    while (~scanf("%d",&n)){
        for (i=1;i<=n;i++) scanf("%d",&a[i]);
        for (i=1;i<=n;i++) scanf("%d",&b[i]);
        init();
        printf("%d\n",sear(1,n+1));
    }
    return 0;
}

Problem B

题意：求

\frac{1}{π} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^{n} (a_{i}^{2} + x^{2})} d x

$\frac{1}{\pi}\int_0^{\infty}\frac{1}{\prod_{i=1}^n(a_i^2+x^2)}{\rm d}x$

。

题解：可以把分式的连乘转换成分式的和，再分别积分。

我们发现，

n \prod i = 1 (a_{i}^{2} + x^{2}) = n \sum i = 1 \frac{1}{(x^{2} + a_{i}^{2}) \prod_{j = 1}^{n} (a_{j}^{2} - a_{i}^{2}) (j! = i)}

$\prod_{i=1}^n(a_i^2+x^2)=\sum_{i=1}^{n}\frac{1}{(x^2+a_i^2)\prod_{j=1}^n(a_j^2-a_i^2)(j!=i)}$

。

利用此性质，将乘积的积分转换成积分的和，易解。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e3+5;
void exgcd(ll a,ll b,ll &x,ll &y){
    if (!b){
        x=a; y=0; return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
ll inv(ll n){
    ll x,y;
    exgcd(n,mod,x,y);
    return x;
}
ll a[maxn];
int main(){
    int i,j,n;
    ll ans,t;
    while (~scanf("%d",&n)){
        for (i=0;i<n;i++) scanf("%lld",&a[i]);
        ans=0;
        for (i=0;i<n;i++){
            t=2*a[i]%mod;
            for (j=0;j<n;j++) if (j!=i)
                t=t*(a[j]*a[j]%mod-a[i]*a[i]%mod)%mod;
            ans=(ans+inv(t))%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
    return 0;
}

Problem C

题意：给定一个

n

$n$

维空间中的点

(a_{1}, a_{2}, \dots, a_{n})

$(a_1,a_2,\dots,a_n)$

，求一个点

(p_{1}, p_{2}, \dots, p_{n}) (n \sum i = 1 p_{i} = 1, a_{i} >= 0)

$(p_1,p_2,\dots,p_n)(\sum_{i=1}^n p_i=1,a_i>=0)$

，使得两点距离最短。

题解：显然，若没有

p_{i} >= 0

$p_i>=0$

的限制，使得每一个

a_{i} = p_{i}

$a_i=p_i$

相等即可。但加上限制之后，为了最小化影响，应该对

> 0

$>0$

的

p_{i}

$p_i$

均等的减少一定量的值补给

< 0

$<0$

的缺口。

一种实现方法是：对

p_{i}

$p_i$

进行排序，统计

< 0

$<0$

的

p_{i}

$p_i$

的和。从小到大遍历

> 0

$>0$

的

p_{i}

$p_i$

：

如果

p_{i}

$p_i$

小于将当前的缺口平均分摊给每一个正数的均摊值，说明

p_{i}

$p_i$

要被减到

0

$0$

，将缺口减去

p_{i}

$p_i$

。

否则，对于当前的

p_{i}

$p_i$

以及之后的每一个

p_{i}

$p_i$

，均摊缺口。

由于要求输出分数，运算过程中分子分母的大小可能超过 long long 能存储的范围，但答案没有超出范围，用 __int128 存储即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef __int128 ll;
const int maxn=1e4+5;
ll gcd(ll a,ll b){
    ll c=a%b;
    while(c) a=b,b=c,c=a%b;
    return b;
}
struct frac{
    ll a,b;
    frac(){
        a=0; b=1;
    }
    frac(ll n){
        a=n; b=1;
    }
    frac(ll _a,ll _b){
        a=_a; b=_b;
    }
    void adj(){
        ll c=gcd(a,b);
        a/=c; b/=c;
        if (b<0){
            a=-a; b=-b;
        }
    }
    void write(){
        if (b==1){
            printf("%lld\n",(long long)a);
            return;
        }
        printf("%lld/%lld\n",(long long)a,(long long)b);
    }
};
frac operator + (frac a,frac b){
    frac c;
    c.a=a.a*b.b+b.a*a.b;
    c.b=a.b*b.b;
    c.adj();
    return c;
}
frac operator - (frac a,frac b){
    frac c;
    c.a=a.a*b.b-b.a*a.b;
    c.b=a.b*b.b;
    c.adj();
    return c;
}
frac operator * (frac a,frac b){
    frac c;
    c.a=a.a*b.a; c.b=a.b*b.b;
    c.adj();
    return c;
}
frac operator / (frac a,frac b){
    frac c;
    c.a=a.a*b.b; c.b=a.b*b.a;
    c.adj();
    return c;
}
bool operator < (frac a,frac b){
    return (a-b).a<0;
}
frac a[maxn],p[maxn];
int id[maxn];
bool cmp(int i,int j){
    return p[i]<p[j];
}
int main(){
    int i,n,m;
    long long t;
    frac sum,rest,ans;
    while (~scanf("%d%d",&n,&m)){
        sum=frac(0,1);
        for (i=0;i<n;i++){
            scanf("%lld",&t);
            a[i].a=t;
            a[i].b=m;
            sum=sum+a[i];
        }
        for (i=0;i<n;i++) p[i]=a[i]-(sum-frac(1,1))/frac(n,1);
        for (i=0;i<n;i++) id[i]=i;
        sort(id,id+n,cmp);
        rest=frac(0,1);
        for (i=0;i<n;i++){
            if (p[id[i]]<0){
                rest=rest-p[id[i]];
                p[id[i]]=0;
                continue;
            }
            if (p[id[i]]<rest/(n-i)){
                rest=rest-p[id[i]];
                p[id[i]]=0;
                continue;
            }
            p[id[i]]=p[id[i]]-rest/(n-i);
            rest=rest-(rest/(n-i));
        }
        ans=0;
        for (i=0;i<n;i++) ans=ans+(a[i]-p[i])*(a[i]-p[i]);
        ans.write();
    }
    return 0;
}

Problem D

题意：首先考虑转化式子：

c o u n t (x) = \frac{1}{2^{m}} \times n - 1 \sum i = 0 m - 1 \prod j = 0 (1 - (- 1)^{a_{i, j} & x})

$count(x) =\frac{1}{2^m} \times \sum\limits_{i=0}^{n-1}\prod\limits_{j=0}^{m-1}(1-(-1)^{a_{i,j}\&x})$

定义：

i

$i$

与

j

$j$

的奇偶性

| i & j |

$|i\&j|$

表示

i & j

$i\&j$

二进制表示中1的个数的奇偶性

引理：仅考虑二进制位的奇偶性，有

| a & b | + | a & c | = | a & (b \oplus c) |, c o u n t (x) = \frac{1}{2^{m}} \times n - 1 \sum i = 0 m - 1 \prod j = 0 (1 - (- 1)^{| a_{i, j} & x |})

$|a\&b| + |a\&c| = |a \& (b \oplus c)|, count(x) =\frac{1}{2^m} \times \sum\limits_{i=0}^{n-1}\prod\limits_{j=0}^{m-1}(1-(-1)^{|a_{i,j}\&x|})$

再考虑二项展开：

= \frac{1}{2^{m}} \times n - 1 \sum i = 0 \sum T \subseteq S (- 1)^{| ⨁ a_{j} \in T a_{j} & x |}

$=\frac{1}{2^m} \times\sum\limits_{i=0}^{n-1}\sum\limits_{T \subseteq S}(-1)^{|\bigoplus\limits_{a_j\in T}a_j \& x|}$

根据FWT的性质，

F (i) = \sum | j & i | = 0 a_{j} - \sum | j & i | = 1 a_{j}

$F(i) = \sum\limits_{|j\&i|=0}{a_j} - \sum\limits_{|j\&i|=1}{a_j}$

，证明显然，点积乘起来正好是定义的结果。

然后发现这不就是我们要求的吗，考虑对一个数组

a_{i}

$a_i$

做 FWT 正变换，

F W T [i] = \sum | j & i | = 0 a_{j} - \sum | j & i | = 1 a_{j} = \sum j (- 1)^{| j & i |} = c o u n t (i) \times 2^{m}

$FWT[i] =\sum\limits_{|j\&i|=0}{a_j} - \sum\limits_{|j\&i|=1}{a_j}= \sum\limits_{j}(-1)^{|j\& i|} = count(i) \times 2^m$

有多个数列，加起来就好了，没有冲突。

于是我们要算出来的数列是，各个

{a_{i}}

$\{a_i\}$

枚举子集，然后把贡献加到

F

$F$

数组，最后对

F

$F$

做 FWT，再算出来。枚举子集，设异或值为

x

$x$

，

F [x] = F [x] + (- 1)^{| S |}

$F[x] = F[x] + (-1)^{|S|}$

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout  << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


//--------------------------------------------------------------------------------------------

const int MOD = 1e9+7;

const int MAXN = 2e5+5;


namespace fwt {

    typedef int LL;
    template<typename T>
    void fwt(LL a[], int n, T f) {
        // dbg("fwt, int", sizeof(LL));
        for (int d=1; d<n; d<<=1)
            for (int i=0, t=d*2; i<n; i+=t)
                for (int j=0; j<d; ++j)
                    f(a[i+j], a[i+j+d]);
        
    }
    void AND(LL &a, LL &b) {a+=b;}
    void OR(LL &a, LL &b) { b += a;}
    void XOR(LL &a, LL &b) {
        LL x = a, y = b;
        a = (x + y) % MOD;
        b = (x - y + MOD) % MOD;
    }
    void rAND(LL &a, LL &b) { a -= b;}
    void rOR(LL &a, LL &b) { b -= a;}
    void rXOR(LL &a, LL &b) {
        static LL INV2 = (MOD+1) / 2;
        LL x = a, y = b;
        a = (x + y) * INV2 % MOD;
        b = (x - y + MOD) * INV2 % MOD;
    }
}

int n, m, k;

const int MAXM = 11;

int a[MAXN][MAXM], f[1<<21];

void dfs(int a[], int n, int v, int sgn) {
    if (n == m) {
        f[v] += sgn;
        return;
    }
        
    dfs(a, n+1, v^a[n], -sgn);
    dfs(a, n+1, v, sgn);
}

LL bin(LL a, LL b, LL p) {
    LL res = 1;
    for (; b; b>>=1, a=a*a%p)
        if (b & 1)
            res = res * a % p;
    return res;
}

LL inv(LL a, LL p) {
    return bin(a, MOD-2, MOD);
}

int main(int argc, char const *argv[])
{
    dbg(bin(2, 11, MOD));
    while (~scanf("%d%d%d", &n, &m, &k)) {
        memset(f, 0, sizeof(int) * (1<<k));
        for (int i=0; i<n; ++i) {
            for (int j=0; j<m; ++j)
                scanf("%lld", &a[i][j]);
            dfs(a[i], 0, 0, 1);
        }
         for (int i=0; i<(1<<k); ++i)
            dbg(i, f[i]);

        fwt::fwt(f, 1<<k, fwt::XOR);
        
       for (int i=0; i<(1<<k); ++i)
            dbg(i, f[i]);
        
        LL ans = 0;

        LL c = 1;
        LL invm = inv(bin(2, m, MOD), MOD);
        dbg(invm);

        for (int i=0; i<(1<<k); ++i) {
            ans ^= c * f[i]%MOD*invm%MOD;
            c = c * 3 % MOD;
        }
        cout << ans << endl;
        // break;
    }
    return 0;
}

Problem E

题意：求长度为

2 (n + m)

$2(n+m)$

的

01

$01$

序列，使得其中恰好能取出不一定连续的

n

$n$

个

01

$01$

和

m

$m$

个

10

$10$

。

题解：先考虑给定一个序列，如何判断其是否能取出

n

$n$

个

01

$01$

和

m

$m$

个

10

$10$

。我们发现，可以贪心的将新读到的数作为端口

0 -

$0-$

或

1 -

$1-$

，直到对应的端口数量已经满足要求，需要和对应的另一种端口

1 -

$1-$

和

0 -

$0-$

匹配成

10

$10$

和

01

$01$

。如果过程中另一种端口的数量不足，则给定序列不满足性质。

根据这种方法，我们可以将加入字符看作是在平面上移动的过程。横纵坐标分别为

0, 1

$0,1$

的数量，初始位置为

(0, 0)

$(0,0)$

，我们要向右或向上走（即加入

0

$0$

或

1

$1$

），到达

(n + m, n + m)

$(n+m,n+m)$

。根据上面的判断方式，需要满足的限制条件为

- n \leq x - y \leq m

$-n \le x-y \le m$

。将问题转换为在只能向右或向上走，且横纵坐标

x, y

$x,y$

始终满足

- n \leq x - y \leq m

$-n \le x-y \le m$

的情况下，

(0, 0)

$(0,0)$

到

(n + m, n + m)

$(n+m,n+m)$

的路径条数。

O (n^{2})

$O(n^2)$

dp 求解。

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

const int MAXN = 2005;

int dp[MAXN][MAXN];

int n, m;

const int MOD = 1e9+7;

inline void add(int &a, int b) {
    a = (a + b) % MOD;
}

int main() {
    while (~scanf("%d%d", &n, &m) && n+m) {
        for (int i=0; i<=n+m; ++i)
            memset(dp[i], 0, sizeof(int) * (n+m+5));
        dp[0][0] = 1;
        for (int i=0; i<=n+m; ++i)
            for (int j=0; j<=n+m; ++j) {
                if (i+1 <= j+n) add(dp[i+1][j], dp[i][j]);
                if (j+1 <= m+i) add(dp[i][j+1], dp[i][j]);
            }
        cout << dp[n+m][n+m] << endl;
    }

    return 0;
}

Problem F

题意：在一个三角形内随便散点，一次散点的价值是被分出来的最大三角形的面积，求随机散点的期望价值。

题解：小范围随机散点，蒙特卡洛找规律。

可以发现答案是

22

$22$

倍的三角形面积。

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
#define li
struct node{
    ll x,y;
    node(ll _x=0,ll _y=0){
        x=_x; y=_y;
    }
};
node operator - (node a,node b){
    return node(a.x-b.x,a.y-b.y);
}
ll _abs(ll n){
    return n<0?-n:n;
}
ll det(node a,node b){
    return _abs(a.x*b.y-a.y*b.x);
}
int main(){
    node a,b,c;
    while (~scanf("%lld%lld%lld%lld%lld%lld",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y)){
        printf("%lld\n",11*det(b-a,c-a));
    }
    return 0;
}

Problem G

题意：求字符串中有多少本质不同的串，能单射的串也认为是同构的。

题解：参考 SA 求不同子串的方法，对所有的后缀排序以后，总的子串个数减去相邻 LCP 的长度。

同理可以推广到这道题目。

能单射的串也认为是同构的，我们可以通过

l a s t

$last$

串相同来处理。

l a s t [i]

$last[i]$

的值是在

i

$i$

位前，与

i

$i$

位字母相同的最近距离。

从后往前推一遍

l a s t

$last$

，每次往前走一位，最多改变一个位置的值。

处理

l a s t

$last$

的 LCP 可以用二分判断前缀 hash 是否相同。排序也是同样求出 LCP 以后，比较 LCP 的后一位大小。

需要维护历史版本的区间 hash ，一开始写了主席树，这样的话排序需要

O (n l o g^{3} n)

$O(nlog^3n)$

， TLE 。

排序可以去掉一个 log ，用可持久化分块数组实现，这样每次查询历史版本区间 hash 就变成

O (1)

$O(1)$

。

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int maxn=5e4+5,wid=225;
const ULL B=1000003;
const ULL bb=1000003;
ULL power[50010];
struct sub_arr{
    ULL a[wid];
    sub_arr(){ memset(a,0,sizeof(a)); }
    inline void clear(){ memset(a,0,sizeof(a)); }
} node[maxn*3];
int siz;
inline int nnode(){ node[siz].clear(); return siz++; }
struct per_arr{
    int a[wid],b[wid];
    ULL c[wid];
    per_arr(){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
    }
    void operator = (const per_arr &arr){
        memcpy(a,arr.a,sizeof(arr.a));
        memcpy(b,arr.b,sizeof(arr.b));
        memcpy(c,arr.c,sizeof(arr.c));
    }
} arr[maxn],zero;
void change(int las,int now,int pos,int val){
    arr[now]=arr[las];
    int i,n=pos/wid,m=pos%wid;
    arr[now].a[n]=nnode();
    arr[now].b[n]=nnode();
    sub_arr &A=node[arr[now].a[n]],&B=node[arr[now].b[n]];
    memcpy(A.a,node[arr[las].a[n]].a,sizeof(A.a));
    A.a[m]=val;
    B.a[0]=A.a[0];
    for (i=1;i<wid;i++) B.a[i]=B.a[i-1]*bb+A.a[i];
    arr[now].c[0]=0;
    for (i=1;i<wid;i++) arr[now].c[i]=arr[now].c[i-1]*power[wid]+node[arr[now].b[i-1]].a[wid-1];
}
ULL query(int ver,int pos){
    int n=pos/wid,m=pos%wid;
    return arr[ver].c[n]*power[m+1]+node[arr[ver].b[n]].a[m];
}
ULL query2(int ver,int pos){
    int n=pos/wid,m=pos%wid;
    return node[arr[ver].a[n]].a[m];
}
int n,m,a[50010],ner[50010],id[50010];

int s,k,h[100010],b[100010],d[100010];
int lcp(int x,int y){
    int l=0,r=min(n-x,n-y),mid,res=0;
    while(l<=r){
        int mid=l+r>>1;
   //     if (query(h[x],x,x+mid,1,n)==query(h[y],y,y+mid,1,n)) res=mid+1,l=mid+1;
        if (query(x,x+mid)==query(y,y+mid))  res=mid+1,l=mid+1;
        else r=mid-1;
    }
    return res;
}

bool cmp(int x,int y){
    int z=lcp(x,y);
    int lenx=n-x+1,leny=n-y+1;
    if (z==lenx) return true;
    else if (z==leny) return false;
    return query2(x,x+z)<query2(y,y+z);
}
int main(){
    power[0]=1;
    for (int i=1;i<=50000;i++)
        power[i]=power[i-1]*B;
    while(~scanf("%d",&n)){
        siz=1;
        arr[n+1]=zero;
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]),ner[i]=0,id[i]=i;
        s=0; h[n+1]=1;
        for (int i=n;i>=1;i--){
            if (ner[a[i]]>0) change(i+1,i,ner[a[i]],ner[a[i]]-i);
            else arr[i]=arr[i+1];
            ner[a[i]]=i;
        }
        sort(id+1,id+1+n,cmp);
        LL ans=((LL)(n))*((LL)(n+1))/2LL;
        for (int i=1;i<n;i++)
            ans-=(LL)lcp(id[i],id[i+1]);
        printf("%lld\n",ans);
    }
    return 0;
}

Problem H

题意：给一个数列，求所有异或和为0的子集的大小之和。

题解：考虑包含每一个数的子集有多少个，即考虑每一个数的贡献（实在看不懂题解写的线性期望之类的= =，但我觉得指的就是这个）。选取某个数，然后就要考虑剩下的数是否能把他异或成0。于是考虑线性基，非基肯定是可以被基异或成0的，于是答案加上

2^{n - r - 1} * (n - r)

$2^{n-r-1}*(n-r)$

，表示含有任何一个非基数，再加上其他非基数的任意组合，都能最后被基异或成0。然后再考虑包含基数的，同样是枚举每个数，非基中的数再组成一个线性基，再加上基数中的其他数组成一个新的线性基。如果新的线性基包含当前数，答案加上

2^{n - p c n t - 1}

$2^{n-pcnt-1}$

，表示含有这个基数的子集个数，此时的新的线性基包含除了现在这个枚举的基数之外的所有数的异或可能。第一部分

O (64 n)

$O(64n)$

，第二部分

O (64 * 64 * 64)

$O(64*64*64)$

。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


//--------------------------------------------------------------------------------------------

const int MAXM = 64;

struct LinearBasis {
    LL p[MAXM];
    LL P[MAXM];
    int cnt, pcnt;
    bool zero;

    bool insert(LL x) {
        for (int j=MAXM-1; j>=0; --j) {
            if ((x >> j) & 1) {
                if (!~p[j]) {
                    p[j] = x;
                    ++pcnt;
                    return true;
                } else
                    x ^= p[j];
            }
        }
        zero = true;
        return false;
    }

    void init(LL a[], int n) {
        memset(p, -1, sizeof(p));
        for (int i=0; i<n; ++i) {
            insert(a[i]);
        }
    }

    void adjust() {
        for (int j=MAXM-1; j>=0; --j) {
            if (~p[j]) {
                for (int i=j-1; ~i; --i) {
                    if (~p[i] && ((p[j] >> i) & 1))
                        p[j] ^= p[i];
                }
                P[cnt++] = p[j];
            }
        }
    }

    bool exist(LL x) {
        if (x == 0) return zero;
        for (int j=MAXM-1; j>=0; --j) {
            if ((x >> j) & 1) {
                x ^= p[j];
            }
        }
        return x == 0;
    }

    void clear() {
        pcnt = 0;
        memset(p, -1, sizeof p);
        zero = false;
        cnt = 0;
    }
} b1, b2;

const int MAXN = 2e5+5;
int n;

LL a[MAXN];

const int MOD = 1e9+7;

LL bin(LL a, LL b, LL p) {
    LL res = 1;
    for (; b; b>>=1, a=a*a%p)
        if (b & 1)
            res = res * a % p;
    return res;
}

LL inv(LL a, LL p) { return bin(a, MOD-2, MOD);}

int main(int argc, char const *argv[])
{
    while (~scanf("%d", &n)) {
        
        b1.clear();
        b2.clear();
        int r = 0, r2 = 0;
        vector<LL> v;
        for (int i=0; i<n; ++i) {
            scanf("%lld", &a[i]);
            if (b1.insert(a[i])) {
                v.push_back(a[i]);
            } else {
                b2.insert(a[i]);
            }
        }
        r = v.size();
        LL ans = bin(2, n-r-1, MOD) * (n - r) % MOD;
        dbg(ans, r);
        
        assert(v.size() == r);
        for (int i=0; i<r; ++i) {
            b1 = b2;
            for (int j=0; j<r; ++j) {
                if (i != j) {
                    b1.insert(v[j]);
                }
            }

            if (!b1.insert(v[i]))
                ans = (ans + bin(2, n-b1.pcnt-1, MOD)) % MOD;
        }
        printf("%lld\n", ans);

    }
    /* code */
    return 0;
}

Problem I

题意：平面上有一些点，求一条折线分割这些点，折线的左上部分的价值取点的

a

$a$

，折线的右下部分的价值取

b

$b$

，求最大的价值。

题解：不妨假设折线式贴合右下部分的点的。即折线上的点都属于

b

$b$

部分。

考虑 dp ，枚举每一个点位于折线上时的最大价值，在做 dp 的过程中顺便加入每个点，更新所有的状态。

对于一个点

(i, j)

$(i,j)$

，只能从

(x, y) (x < i, y < j)

$(x,y)(x<i,y<j)$

转移到它，而加入这个点以后，之后的点如果位于他的上方，他的贡献为

a

$a$

，如果位于他的下方，他的贡献为

b

$b$

。

这部分直接用线段树维护即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int fa(int u){ return u>>1; }
inline int ls(int u){ return u<<1; }
inline int rs(int u){ return u<<1|1; }
const int maxn=1e5+5,maxm=3e5+5;
const ll inf=1e18;
int l[maxm],r[maxm];
ll tag[maxm],ans[maxm];
void build(int u,int _l,int _r){
    l[u]=_l; r[u]=_r; tag[u]=0; ans[u]=0;
    if (_l==_r) return;
    int _m=(_l+_r)/2;
    build(ls(u),_l,_m);
    build(rs(u),_m+1,_r);
}
void pushdown(int u){
    ans[ls(u)]+=tag[u];
    tag[ls(u)]+=tag[u];
    ans[rs(u)]+=tag[u];
    tag[rs(u)]+=tag[u];
    tag[u]=0;
}
void update(int u){
    ans[u]=max(ans[ls(u)],ans[rs(u)]);
}
ll query(int u,int _l,int _r){
    if (l[u]>_r||r[u]<_l) return -inf;
    if (l[u]>=_l&&r[u]<=_r) return ans[u];
    pushdown(u);
    return max(query(ls(u),_l,_r),query(rs(u),_l,_r));
}
void add(int u,int _l,int _r,ll val){
    if (l[u]>_r||r[u]<_l) return;
    if (l[u]>=_l&&r[u]<=_r){
        ans[u]+=val; tag[u]+=val;
        return;
    }
    pushdown(u);
    add(ls(u),_l,_r,val);
    add(rs(u),_l,_r,val);
    update(u);
}
void change(int u,int n,ll val){
    if (l[u]>n||r[u]<n) return;
    if (l[u]==n&&r[u]==n){
        ans[u]=val; tag[u]=0;
        return;
    }
    pushdown(u);
    change(ls(u),n,val);
    change(rs(u),n,val);
    update(u);
}
struct node{
    int x,y;
    ll val;
};
bool operator < (const node &a,const node &b){
    if (a.y!=b.y) return a.y>b.y;
    if (a.x!=b.x) return a.x<b.x;
    return false;
}
int a[maxn],n,k;
node nd[maxn];
int sear(int val){
    int l,m,r;
    l=0; r=k;
    while (r-l>1){
        m=(l+r)/2;
        if (a[m]>val) r=m;
        else l=m;
    }
    return l;
}
int main(){
    int i;
    ll ans,t1,t2;
    while (~scanf("%d",&n)){
        ans=0;
        for (i=0;i<n;i++){
            scanf("%d%d%lld%lld",&nd[i].x,&nd[i].y,&t1,&t2);
            ans+=t2; nd[i].val=t1-t2; a[i]=nd[i].x;
        }
        sort(a,a+n); k=1;
        for (i=1;i<n;i++) if (a[i]>a[k-1])
            a[k++]=a[i];
        build(1,0,k+1);
        for (i=0;i<n;i++) nd[i].x=sear(nd[i].x)+1;
        sort(nd,nd+n);
        for (i=0;i<n;i++){
            change(1,nd[i].x-1,query(1,nd[i].x-1,k+1));
            add(1,nd[i].x,k+1,nd[i].val);
        }
        printf("%lld\n",ans+query(1,0,k+1));
    }
    return 0;
}

Problem J

题意：比较两个分数的大小。

题解：直接比较会爆 long long ，开 __int128 就好了。

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

LL x,y,a,b;

i128 GCD(i128 x,i128 y)
{
    i128 z=x%y;
    while(z) x=y,y=z,z=x%y;
    return y;
}

int main()
{
    while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b))
    {
        i128 X=x,A=a,Y=y,B=b;
        i128 Z=GCD(A,B);
        Z=A/Z*B;
        X=Z/A*X;Y=Z/B*Y;
        if (X==Y) puts("=");
        else if (X<Y) puts("<");
        else if (X>Y) puts(">");
    }
    return 0;
}