牛客NOIP暑期七天营-提高组3 Solution

T1

这是一道找规律结论题

此题正解

作者:Asuka_Minato
链接:https://ac.nowcoder.com/discuss/229199?type=101&order=0&pos=6&page=0
来源:牛客网

考虑在$x=1$时,对于每个格子可以填$0/1$。那么所有的格子对应的数都只有一个二进制位。当所有行异或和的异或和等于所有列异或和的异或和时,在前$n-1$行$m-1$列的格子随意的填数,第$n$行和第$m$列总有唯一合法的填数方案

考虑在$x=2^k-1$时,对于每个格子对应的数有$k$个二进制位,且$0/1$不受限制,此时相比于$x=1$,$k$个二进制位相互独立,所以在前$n-1$行$m−1$列的格子随意的填数,第$n$行和第$m$列也总有唯一合法的填数方案

考虑当所有行异或和的异或和不等于所有列异或和的异或和时,矩阵填数一定不合法,此时答案为$0$。否则,矩阵内前$n-1$行$m−1$列可以随意填数,每个位置有$x+1$种填数方案,此时答案为$(x+1)^{(n-1)(m-1)}$

非常正确的结论,不过我还是觉得打个暴力然后找规律快的多

#include <cstdio>

const int N = 1e6;

long long T, n, m, x, p;
long long a[N + 30][2];

long long Pow(long long d, long long mi) {
    long long res = 1, t = d;
    while (mi) {
        if (mi & 1) res = (res * t) % p;
        t = (t * t) % p;
        mi >>= 1;
    }return res;
}

inline void solve() {
    long long w1 = 0, w2 = 0;
    for (int i = 1; i <= n; ++i) {scanf ("%lld", &a[i][0]); w1 ^= a[i][0]; }
    for (int i = 1; i <= m; ++i) {scanf ("%lld", &a[i][1]); w2 ^= a[i][1]; }
    if (w1 != w2) {printf ("0\n"); return ;}
    printf ("%lld\n", Pow(Pow((x + 1) % p, n - 1) % p, m - 1) % p); 
}

int main() {
    scanf ("%lld", &T);
    for (int k = 1; k <= T; ++k) {
        scanf ("%lld%lld%lld%lld", &n, &m, &x, &p);
        solve();
    }return 0;
}

T2 点与面

我以为牛客网上的题解讲的还不错,便在其基础上补一些细节。

作者:Asuka_Minato
链接:https://ac.nowcoder.com/discuss/229199?type=101&order=0&pos=1&page=1
来源:牛客网

我们考虑枚举W型最中间的点,既$p_3$​,我们考虑$p_3$​的左边,要找一个比$p_3>p_2$​,还要找一个$p_1>p_2$,那么实际上,对于$p_3$​左侧,低于$p_3$​的点$p_2$​,对答案的贡献为$p_2$​左侧比$p_2$​大的点,我们这一步可以用BIT维护,得到左右两边的贡献之后,使用乘法原理将他们组合,就能计算出答案。
统计$p_2$​时,直接枚举是单次$O(nlogn)$的,总复杂度$O(n2logn)$可以得到40%的分数,考虑我们刚才维护的信息,和这个类似,我们也可以用类似的方式,再维护一颗BIT来完成统计。 得到左右两边的贡献之后,使用乘法原理将他们组合,就能计算出答案。
总时间复杂度可以做到$O(nlogn)$,拿到全部分数.

此处的类似方式,考虑左边的情况,即用一棵BIT,维护每一个值的逆序对个数,因为过程为边查询边插入,所以每一次查询实际上查询的是当前下标情况下对所有小于当前值的所有点的逆序对总和,顺序对亦然。

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const MAXN=1e5+10,MAXM=1e6,mod=998244353;
int n,maxn,ans;
int Y[MAXN];
int a[MAXM],b[MAXM];
int ni[MAXN],shun[MAXN];
int lowbit(int x){return x & (-x);}
void inserta(int x,int y){
    for(int i=x;i<=maxn;i+=lowbit(i))a[i]+=y;
}
void insertb(int x,int y){
    for(int i=x;i<=maxn;i+=lowbit(i))b[i]+=y;
}
int aska(int x){
    int sum=0;
    for(;x;x-=lowbit(x))sum+=a[x];
    return sum;
}
int askb(int x){
    int sum=0;
    for(;x;x-=lowbit(x))sum+=b[x];
    return sum;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&Y[i]);maxn=max(maxn,Y[i]);
    }
    for(int i=1;i<=n;i++){
        inserta(Y[i],1);
        insertb(Y[i],aska(maxn)-aska(Y[i]));//插入i的逆序对个数
        ni[i]=askb(Y[i]-1)%mod;//查询满足比Y[i]小且在左边的所有点的逆序对总和
    }
    memset(a,0,sizeof(a));memset(b,0,sizeof(b));
    for(int i=n;i>=1;i--){
        inserta(Y[i],1);
        insertb(Y[i],aska(maxn)-aska(Y[i]));//插入i的顺序对个数
        shun[i]=askb(Y[i]-1)%mod;//查询满足比Y[i]小且在右边的所有点的顺序对总和
    }
    for(int i=1;i<=n;i++){
        ans=(ans+(shun[i]*ni[i])%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

T3

线段树

Last modification:August 22nd, 2019 at 06:49 am

Leave a Comment