2019牛客暑期多校训练营（第九场）

B Quadratic equation

题目链接
题意：模数p为 $1e9+7$ ，输入b和c，保证b、c都小于模数，求x和y满足以下式子

$(x+y) mod\ p =b$

$x*y\ mod\ p =c$

思路：对于这两个式子，我们可以转化成 $(x-y)^2 \equiv (b^2-4*c)\ mod\ p$
对于这个式子，我们可以通过二次剩余得到x-y的结果，再通过 $(x+y) mod\ p =b$ 化简即可

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll p=1000000007;
ll b,c;

ll w;
struct node{
    ll x,y;
    node mul(node a,node b,ll m){
        node ans;
        ans.x=(a.x*b.x%m+a.y*b.y%m*w%m)%m;
        ans.y=(a.x*b.y%m+a.y*b.x%m)%m;
        return ans;
    }

    node qpow(node a,ll b,ll m){
        node ans;
        ans.x=1;ans.y=0;
        while(b){
            if(b&1) ans=mul(ans,a,m);
            a=mul(a,a,m);
            b>>=1;
        }
        return ans;
    }
};

ll qpow(ll a,ll b,ll m){
    ll ans=1;
    ll k=a;
    while(b){
        if(b&1)ans=ans*k%m;
        k=k*k%m;
        b>>=1;
    }
    return ans;
}

ll Cipolla(ll n,ll p){
    n%=p;
    if(!n)return 0;
    if(p==2)return n;
    if(qpow(n,(p-1)/2,p)==p-1)
        return -1;

    ll a,t;
    while(1){
        a=rand()%p;
        t=a*a-n;
        w=(t%p+p)%p;
        if(qpow(w,(p-1)/2,p)==p-1)break;
    }

    node ans;
    ans.x=a;ans.y=1;
    ans=ans.qpow(ans,(p+1)/2,p);
    return ans.x;
}

void input(){
    scanf("%lld%lld",&b,&c);
}

void solve(){
    ll ans=Cipolla(b*b-4*c+p,p);
    if(ans==-1)
        printf("-1 -1\n");
    else{
        ll x=(b+ans)%p*qpow(2,p-2,p);
        x%=p;
        ll y=(b-x+p)%p;
        if(x>y)swap(x,y);
        printf("%lld %lld\n",x,y);
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

D Knapsack Cryptosystem

题目链接
题意：对于给定n(小于等于36)，要求在其中选择任意个数，其总和等于s。
思路：折半枚举，我们可以枚举一半个数物品的选择状态存入map。然后在后半段进行查询。

#include <bits/stdc++.h>

#define maxn 40
typedef long long ll;
using namespace std;

int n;
ll tot;
ll a[maxn];
void input(){
    int i;
    scanf("%d%lld",&n,&tot);
    for(i=0;i<n;i++)
        scanf("%lld",&a[i]);
}

void solve(){
    map<ll,string>m1;
    map<ll,string>m2;

    int i,j;    
    for(i=0;i<(1<<(n/2));i++){
        string vis;
        ll sum=0;

        for(j=0;j<n/2;j++){
            if((i>>j)&1){
                vis.push_back('1');
                sum+=a[j];
            }else
                vis.push_back('0');
        }

        m1[sum]=vis;
    }

    for(i=0;i<(1<<(n-n/2));i++){
        string vis;
        ll sum=0;

        for(j=0;j<n-n/2;j++){
            if((i>>j)&1){
                vis.push_back('1');
                sum+=a[j+n/2];
            }else
                vis.push_back('0');
        }

        m2[sum]=vis;
        if(m1.count(tot-sum)){
            cout<<m1[tot-sum]<<m2[sum]<<endl;
            break;
        }
    }


}

int main(){
    input();
    solve();
}

E All men are brothers

题目链接
题意：有n个人，有m轮会找到两个人成为朋友，朋友关系是相互且可传递的。在每轮前后都会进行询问，即在这n个人中寻找4个人，4个人两两不能存在友谊，询问有多少种选择方法。
思路：首先对于同一集合里的人数，可以通过并查集O(1)维护。
假设存在A、B、C、D、E五个集合，其中字母代表这个集合中的人数。

不合并之前的选择方法数 $=A*B*C*D+A*B*C*E+A*B*D*E+A*C*D*E+B*C*D*E$
我们选择A和B进行合并，合并后的选择方法数 $=(A+B)*C*D*E=A*C*D*E+B*C*D*E$
可发现缺少的为 $A*B*C*D+A*B*C*E+A*B*D*E$ ，提取公因子得到 $A*B*(C*D+C*E+D*E)$
即合并的两个集合人数相乘，再乘上其余集合人数两两相乘之和。
对于 $C*D+C*E+D*E=(C+D+E)^{2}-C^{2}-D^{2}-E{2}$

通过以上公式，可维护O(1)得到结果

#include <bits/stdc++.h>

#define maxn 100005
typedef unsigned long long ull;
using namespace std;

int n,m;

struct Union{
    int fa[maxn];
    ull sz[maxn];
    void init(int n){
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            sz[i]=1;
        }
    }

    int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);
    }

    void mix(int x,int y){
        int fx=find(x);
        int fy=find(y);
        fa[fx]=fy;
        sz[fy]+=sz[fx];
    }
}un;

void solve(){
    scanf("%d%d",&n,&m);
    un.init(n);

    ull ans=0;
    if(n>=4)
        ans=1llu*n*(n-1)/2*(n-2)/3*(n-3)/4;
    printf("%llu\n",ans);

    ull sum=n;
    int x,y;
    for(int i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        if(un.find(x)!=un.find(y))
        {
            int fx=un.find(x);
            int fy=un.find(y);

            ull los=(n-un.sz[fx]-un.sz[fy])*(n-un.sz[fx]-un.sz[fy]);
            los=los-(sum-un.sz[fx]*un.sz[fx]-un.sz[fy]*un.sz[fy]);
            los=los/2;
            los=los*un.sz[fx]*un.sz[fy];
            sum=sum-un.sz[fx]*un.sz[fx]-un.sz[fy]*un.sz[fy]+(un.sz[fx]+un.sz[fy])*(un.sz[fx]+un.sz[fy]); 

            ans=ans-los;
            un.mix(x,y);
        }

        printf("%llu\n",ans);
    }
}

int main(){
    solve();
}

H Cutting Bamboos

题目链接
题意：有n个竹子，每个竹子的高度是hi，每次查询l,r,x,y代表从区间 $[l,r]$ 中寻找到高度H，使得H以上的高度总和占这个区间高度和的 $\frac{x}{y}$
思路：用主席树维护区间 $[l,r]$ 内高度H以下的竹子的高度和以及个数和，然后二分H判断。

#include <bits/stdc++.h>

#define MAXN 200005
#define eps 1e-10
typedef long long ll;
using namespace std;

int n,q;
int cnt;
int h[MAXN];
int T[MAXN];
int lson[MAXN*30],rson[MAXN*30];
ll c[MAXN*30],nu[MAXN*30];
ll sum[MAXN];

ll SUM,NUM;

int Build(int l,int r){//建立空树 
  int root=cnt++;
  c[root]=0;
  nu[root]=0;
  if(l!=r){
    int mid=(l+r)>>1;
    lson[root]=Build(l,mid);
    rson[root]=Build(mid+1,r);
  }
  return root;
}

int update(int root,int pos,int val){//根据插入值，logn的建立树链，即另一个版本主席树 
  int newroot=cnt++;
  int ans=newroot;
  c[newroot]=c[root]+val;
  nu[newroot]=nu[root]+1;
  int l=1,r=100000;
  while(l<r){
    int mid=(l+r)>>1;
    if(pos<=mid){
      lson[newroot]=cnt++;
      rson[newroot]=rson[root];
      newroot=lson[newroot];
      root=lson[root];
      r=mid;
    }else{
      rson[newroot]=cnt++;
      lson[newroot]=lson[root];
      newroot=rson[newroot];
      root=rson[root];
      l=mid+1;
    }
    c[newroot]=c[root]+val;
    nu[newroot]=nu[root]+1;
  }
  return ans;
}

void query(int left_root,int right_root,int l,int r,int k)//左端点版本号的树，右端点版本号的树 
{
    if(l>k) return;
    if(r<=k){
        SUM+=c[left_root]-c[right_root];
        NUM+=nu[left_root]-nu[right_root];
        return;
    }

    int mid=(l+r)>>1;
    query(lson[left_root],lson[right_root],l,mid,k);
    query(rson[left_root],rson[right_root],mid+1,r,k);
}

void solve(){
    scanf("%d%d",&n,&q);
    T[n+1]=Build(1,n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&h[i]);
        sum[i]=sum[i-1]+h[i];
    }

    for(i=n;i>=1;i--)
        T[i]=update(T[i+1],h[i],h[i]);

    int l,r,x,y;
    while(q--){
        scanf("%d%d%d%d",&l,&r,&x,&y);
        double li=0,ri=100000;
        while(abs(li-ri)>eps){
            double mid=(li+ri)/2;
            SUM=NUM=0;
            query(T[l],T[r+1],1,100000,(int)mid);
            NUM=r-l+1-NUM;

            double tot=mid*NUM+SUM;
            double ans=(y-x)*1.0*(sum[r]-sum[l-1])/y;
            if(ans<tot)
                ri=mid;
            else
                li=mid;
        }
        printf("%.15lf\n",li);
    }
}

int main(){
    solve();
}

J Symmetrical Painting

题目链接
题意：存在n个矩形，左上角为(i-1,l)，右下角为(i,r)，寻找一条平行x轴的线，将穿过矩形的对称面积相加，求最大值。
思路：水平线在L，(L+R)/2，R三种情况下才有可能得到最优情况。O(n)维护当前线穿过的矩阵个数和面积。也可以将矩阵看作区间，在区间维护斜率，解决分段函数

#include <bits/stdc++.h>

#define maxn 300005
typedef long long ll;
using namespace std;

int n;
ll l,r;
ll a[maxn*3];

void input(){
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++){
        scanf("%lld%lld",&l,&r);
        a[i*3]=4*l;
        a[i*3+1]=4*r;
        a[i*3+2]=2*l+2*r+1;
    }
}

void solve(){
    sort(a,a+3*n);
    int i;
    ll ans=0,s=0;
    ll last=0,num=0;
    for(i=0;i<3*n;i++){
        s+=(a[i]/2-last)*num;
        last=a[i]/2;

        if(s>ans)
            ans=s;

        if(a[i]%2==1)
            num-=2;
        else
            num++;

//        cout<<last<<' '<<s<<' '<<num<<' '<<ans<<endl;
    }

    printf("%lld\n",ans);
}

int main(){
    input();
    solve();
}