牛客练习赛49

~~说好的人均3.5道题呢？骗我们打代码~~

A筱玛爱地理

在经济地理学中，交通的联结度表示交通网络的发达程度，通常用贝塔指数来计算与比较。若用$V$表示一个交通网络中结点的数量，用$E$表示边的数量，则贝塔指数的计算方式为：$ \beta = \frac{E}{V}$。

“实践是检验真理的唯一标准”。作为一个热爱地理的好筱玛，她马上就把新学的知识应用到实践当中去。筱玛一口气出了$n$张交通网络规划图，其中第$i$张交通网络$G_i$有$V_i$个结点和$E_i$条边。筱玛一眼就看出了哪张图好、哪张图坏。但是作为一个负责任的好筱玛，她必须带领同学们一起进步。因此，她需要你将所有的$n$张图按照贝塔指数排序，并求出它们各自的贝塔指数在模$10^9+7$意义下的值

直接计算$\beta$(浮点数)，然后排序，再求逆元输出取模之后的结果就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
ll x,y;
const ll mod=1e9+7;
ll qpow(ll x,ll n,ll mod){
    ll res=1;
    while(n){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res%mod;
}
struct node{
    ll v,e;
    double x;
    ll y;
}a[200010];
bool cmp(node i,node j){
    return i.x>j.x;
}
int main(){
    scanf("%lld",&t);
    for(ll i=0; i<t; i++){
        scanf("%lld %lld",&a[i].v,&a[i].e);
        //printf("%lld\n",y*qpow(x,mod-2,mod)%mod);
        a[i].y=a[i].e*qpow(a[i].v,mod-2,mod)%mod;
        //a[i++]=y*qpow(x,mod-2,mod)%mod;
        a[i].x=a[i].e*1.0/a[i].v*1.0;
    }
    sort(a,a+t,cmp);
    for(ll j=0; j<t; j++) printf("%lld\n",a[j].y);
}

筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：
给定一个长度为n的数组A，刚开始每一项的值均为0。
支持以下两种操作，操作共m次：
1 l r ：将$A_i \sim A_j$的每一项的值加上1。
2 l r ：执行操作编号在[l,r]内的所有操作各一次，保证r小于当前操作的编号。
m次操作结束后，你要告诉马爷A数组变成什么样子了。
由于答案可能会很大，你只需要输出数组
A中的每个数在模 $10^9+7$ 意义下的值

方法一：线段树，维护了两棵线段树即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100010;
const ll mod=1e9+7;
struct seg{
    ll l,r;
    ll mark;
    ll val;
}s[maxn*4],ss[maxn*4];
ll a[maxn];
ll b[maxn];
struct node{
    ll op;
    ll l,r;
}x[maxn];
void pushup(ll i){
    s[i].val=(s[i<<1LL].val+s[(i<<1LL)|1LL].val)%mod;
}
void pushdown(ll i){
    if(s[i].mark){
        s[i<<1LL].val=(s[i<<1LL].val+((s[i<<1LL].r-s[i<<1LL].l+1LL)*s[i].mark%mod))%mod;
        s[(i<<1LL)|1LL].val=(s[(i<<1LL)|1LL].val+((s[(i<<1LL)|1LL].r-s[(i<<1LL)|1LL].l+1LL)*s[i].mark%mod))%mod;
        s[i<<1LL].mark=(s[i<<1LL].mark+s[i].mark)%mod;
        s[(i<<1LL)|1LL].mark=(s[(i<<1LL)|1LL].mark+s[i].mark)%mod;
        s[i].mark=0;
    }
}
void build(ll i,ll l,ll r){
    s[i].l=l;
    s[i].r=r;
    s[i].mark=0;
    if(l == r){
        s[i].val=a[l];
        return ;
    }
    ll mid=(l+r)>>1LL;
    build(i<<1LL,l,mid);
    build((i<<1LL)|1LL,mid+1LL,r);
    pushup(i);
}
ll query(ll i,ll l,ll r,ll sl,ll sr){
    if(l>=sl && r<=sr) return s[i].val;
    pushdown(i);
    ll mid=(l+r)>>1LL;
    ll sum=0;
    if(mid>=sl) sum=(sum+query(i<<1LL,l,mid,sl,sr))%mod;
    if(mid<sr) sum=(sum+query((i<<1LL)|1LL,mid+1LL,r,sl,sr))%mod;
    return sum%mod;
}
void updata(ll i,ll l,ll r,ll sl,ll sr,ll val){
    if(l>=sl && r<=sr){
        s[i].val=(s[i].val+(s[i].r-s[i].l+1LL)*val%mod)%mod;
        s[i].mark=(s[i].mark+val)%mod;
        return ;
    }
    ll mid=(l+r)>>1LL;
    pushdown(i);
    if(mid>=sl) updata(i<<1LL,l,mid,sl,sr,val);
    if(mid<sr) updata((i<<1LL)|1LL,mid+1LL,r,sl,sr,val);
    pushup(i);
}
void pushup1(ll i){
    ss[i].val=(ss[i<<1LL].val+ss[(i<<1LL)|1LL].val)%mod;
}
void pushdown1(ll i){
    if(ss[i].mark){
        ss[i<<1LL].val=(ss[i<<1LL].val+((ss[i<<1LL].r-ss[i<<1LL].l+1LL)*ss[i].mark%mod))%mod;
        ss[(i<<1LL)|1LL].val=(ss[(i<<1LL)|1LL].val+((ss[(i<<1LL)|1LL].r-ss[(i<<1LL)|1LL].l+1LL)*ss[i].mark%mod))%mod;
        ss[i<<1LL].mark=(ss[i<<1LL].mark+ss[i].mark)%mod;
        ss[(i<<1LL)|1LL].mark=(ss[(i<<1LL)|1LL].mark+ss[i].mark)%mod;
        ss[i].mark=0;
    }
}
void build1(ll i,ll l,ll r){
    ss[i].l=l;
    ss[i].r=r;
    ss[i].mark=0;
    if(l == r){
        ss[i].val=b[l];
        return ;
    }
    ll mid=(l+r)>>1LL;
    build1(i<<1LL,l,mid);
    build1((i<<1LL)|1LL,mid+1LL,r);
    pushup1(i);
}
ll query1(ll i,ll l,ll r,ll ssl,ll ssr){
    if(l>=ssl && r<=ssr) return ss[i].val;
    pushdown1(i);
    ll mid=(l+r)>>1LL;
    ll ssum=0;
    if(mid>=ssl) ssum=(ssum+query1(i<<1LL,l,mid,ssl,ssr))%mod;
    if(mid<ssr) ssum=(ssum+query1((i<<1LL)|1LL,mid+1LL,r,ssl,ssr))%mod;
    return ssum%mod;
}
void updata1(ll i,ll l,ll r,ll ssl,ll ssr,ll val){
    if(l>=ssl && r<=ssr){
        ss[i].val=(ss[i].val+(ss[i].r-ss[i].l+1LL)*val%mod)%mod;
        ss[i].mark=(ss[i].mark+val)%mod;
        return ;
    }
    ll mid=(l+r)>>1LL;
    pushdown1(i);
    if(mid>=ssl) updata1(i<<1LL,l,mid,ssl,ssr,val);
    if(mid<ssr) updata1((i<<1LL)|1LL,mid+1LL,r,ssl,ssr,val);
    pushup1(i);
}
int main(){
    ll n,m;
    scanf("%lld",&n);
    memset(a,0,sizeof a);
    build(1,1,n);
    scanf("%lld",&m);
    //m=100000;
    for(ll i=1; i<=m; i++){
        scanf("%lld %lld %lld",&x[i].op,&x[i].l,&x[i].r);
        //if(i == 1) x[i].op=1,x[i].l=1,x[i].r=n;
        //else x[i].op=2,x[i].l=1,x[i].r=i-1;
        b[i]=1;
    }
    //for(ll i=1; i<=m; i++) b[i]=1;
    build1(1,1,m);
    //cout<<query1(1,1,m,1,1)<<endl;;
    for(ll i=m; i>0; i--){
        if(x[i].op == 1){
            updata(1,1,n,x[i].l,x[i].r,query1(1,1,m,i,i));
            //printf("%d\n",query1(1,1,m,i,i));
        }
        else{
            updata1(1,1,m,x[i].l,x[i].r,query1(1,1,m,i,i));
            //printf("%lld\n",query1(1,1,m,i,i));
        }
    }
    for(ll i=1; i<=n; i++){
        printf("%lld%c",query(1,1,n,i,i),i<n?' ':'\n');
    }
}

方法二：差分(留坑待补……)

E筱玛爱游戏

两个人轮流从桌面上取走一个数，并把这个数放入集合中。

如果在某次操作结束后，集合中存在一个异或和为0的非空子集，那么进行这次操作的人输。

如果全部取完，则最后操作的人赢。

筱玛和马爷都聪明绝顶，他们都会按照最优策略进行游戏。

马爷作为筱玛的爷爷，决定让筱玛选择先手还是后手。

筱玛为了稳操胜券，想提前知道对于当前的游戏，是先手必胜还是后手必胜。

筱玛想考考你，让你帮他解决这个问题

思路：每一个数都是一个向量，以二进制形式的向量，此时数的异或就是向量的加法(不带进位)，就是求所有向量不相关的集合，其实就是矩阵的秩。然后就要求所有的向量组矩阵的秩，如果秩为偶数，后手赢，否则先手赢。可以通过高斯消元或者线性基，这里是线性基的方法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[100];
int ran(ll x){
    for(ll i=60; ~i; i--){
        if(x>>i & 1){
            if(!a[i]){
                a[i]=x;
                return 1;
            }
            else x^=a[i];
        }
    }
    return 0;
}
int main(){
    scanf("%lld",&n);
    ll ans=0;
    for(ll i=1; i<=n; i++){
        scanf("%lld",&m);
        ans+=ran(m);
    }
    if(ans&1) puts("First");
    else puts("Second");
}

A筱玛爱地理

D筱玛爱线段树

E筱玛爱游戏