一套比一套炸,果然我只会做B卷,虽然我B也很差但没差到这种地步

$math$

题解

看似没法做但总会有突破口

$70\%$

发现和小凯的诱惑很像,于是看$gcd$是否为$1$只要为$1$可以凑齐所有数

$n^2$枚举两两$gcd$

$80\%$

我考试时思路

找到每一个数和$mod$的$gcd$,发现只要是任一$gcd$倍数就可以凑出来,于是枚举每一个数和$mod$的$gcd$,瓶颈在于统计答案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 2222222
ll n,k,cnt=0;
ll a[A],dl[A],ok[A];
ll read(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
}
ll gcd(ll x,ll y){
    if(y==0) return x;
    return gcd(y,x%y);
}
int main(){
    n=read(),k=read();    
    for(ll i=1;i<=n;i++)
        a[i]=read(),dl[++dl[0]]=a[i];
    for(ll i=1;i<=dl[0];i++){
        ll g=gcd(dl[i],k);
        if(g==1){
            printf("%lld\n",k);
            for(ll j=0;j<=k-1;j++){
                printf("%lld ",j);
            }
            return 0;
        }
        else {
            for(ll i=g;i<k;i+=g){
                ok[i]=1;
            }
            ok[0]=1;
        }
    }
    for(ll i=0;i<=k;i++){
        if(ok[i]) cnt++;
    }
    printf("%lld\n",cnt);
    for(ll i=0;i<=k;i++){
    if(ok[i])    printf("%lld ",i);
    }
    printf("\n");
}

View Code

$100\%$

其实从$80\%$我们就应该看出可以找到所有数$gcd$,然后只有为$gcd$倍数才可以凑出来

考试时我连这个都没有想到!

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1010101
ll n,k,cnt=0;
ll a[A],dl[A];
ll read(){
    ll f=1,x=0;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f*x;
}
ll gcd(ll x,ll y){
    if(y==0) return x;
    return gcd(y,x%y);
}
int main(){
    n=read(),k=read();
    for(ll i=1;i<=n;i++){
        a[i]=read();
           while(a[i]<0){
            a[i]+=k;
        }
    }
    ll g=gcd(a[1],a[2]);
    g=gcd(g,k);
    for(ll i=3;i<=n;i++)
        g=gcd(a[i],g);
    for(ll i=0;i<k;i+=g){
        cnt++;
        dl[++dl[0]]=i;
    }
    printf("%lld\n",cnt);
    for(ll i=1;i<=dl[0];i++){
        printf("%lld ",dl[i]);
    }
    printf("\n");
}

View Code

english

题解

破题打了很久从$23$日打到$27$日

然而考试两个人当场$AC$

思路还算比较简单,然而很难打,不用说了我码力太弱

$ans1$还算比较简单,和学数数那个题很像,

我们找到以每一个值为最大值的最左$l$,最右$r$

设当前值位置为$now$

那么因为是异或,造成贡献的只有$now-l$中与$r-now$中二进制位相反的

设$0[x][j]$表示$1--x$中第$j$位为$0$数有多少个(这是前缀和)

类似设$1[x][j]$表示$1--x$中第$j$位为$1$数有多少个

那么$now$贡献就为$\sum\limits_{j=1}^{j<=最高位} (0[now][j]-0[l-1][j])*(1[r][j]-1[now-1][j])+(1[now][j]-1[l-1][j])*(0[r][j]-0[now-1][j])$

然后问题又转化为了找到以每一个值为最大值的最左$l$,最右$r$

这里我还是用的我的老方法(愚蠢至极)

void pre(ll l,ll r,ll now,ll nowmax){
    if(l>r) return ;
    lef[now]=l,rig[now]=r;
    if(l==r) {
        len[now]=r-l+1;
        return ;
    }
    maxn=-1,ida=0;
    if(l<=now-1){    
        seg_max(1,l,now-1);
        pre(l,now-1,ida,maxn);
    }
    maxn=-1,ida=0;
    if(now+1<=r){
        seg_max(1,now+1,r);
        pre(now+1,r,ida,maxn);
    }
}

二分套线段树

复杂度玄学说是$n*{log(n)^2}$然而实际跑起来只比单调栈慢$400ms$,学数数还比单调栈快