牛客网暑期ACM多校训练营（第五场

A gpa
签到题，然而博主没做过01分数规划，看完题解才知道怎么做，但是对01分数规划还是不太了解。。
题解已经写得十分详细了，直接贴代码了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{
    int s,c;
}nodes[maxn];
double d[maxn];
int n,k;
const double eps=1e-10;
int sgn(double x)
{
    if(fabs(x)<eps)return 0;
    if(x>0)return 1;
    return -1;
}
bool check(double num)
{
    double res=0;
    for(int i=1;i<=n;i++)
    {
        d[i]=nodes[i].s*(nodes[i].c-num);
        res+=d[i];
    }
    sort(d+1,d+1+n);
    for(int i=1;i<=k;i++)
        res-=d[i];
    if(sgn(res)>=0)return 1;
    return 0;

}

int main()
{

    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&nodes[i].s);
    for(int i=1;i<=n;i++)
        scanf("%d",&nodes[i].c);
    double l=0,r=1e9;
    for(int t=1;t<=50;t++)
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.10f\n",l);
    return 0;

}

B div
能做出这题需要一定的数学知识，所以博主没做出来。。
我们来一步一步分析吧。
设x=n2+a$x=n^2+a$
所以(n2+a)|n4$(n^2+a)|n^4$—————————————————(1)
又(n2+a)|(n2+a)(n2−a)=n4−a2$(n^2+a)|(n^2+a)(n^2-a)=n^4-a^2$—————–(2)
所以(1)-(2)可得(n2+a)|a2$(n^2+a)|a^2$
所以a2=t∗(n2+a)$a^2=t\ast (n^2+a)$
我们可以知道a的范围是1≤a≤2n$1\le a\le 2n$，所以t=1,2,3
接下来就和题解一样了。但我要仔细说一下t=2,3的时候的情况。
当t=2时，可以将式子变成(a−1)2=2n2+1$(a-1{)}^2=2n^2+1$,这个式子形如x2−2y2=1$x^2-2y^2=1$,这个式子十分特殊，形如x2−Dy2=1(D为非平方数)$x^2-D{y}^2=1(D为非平方数)$ 的式子被称为佩尔方程。它具有一个通解式子。只要知道初始解就能知道所有解了。而初始解只需要暴力就能得出。
它的递推式为
xn+1=x0xn+Dy0yn$x_{n+1}=x_0{x}_n+D{y}_0{y}_n$
yn+1=y0xn+x0yn$y_{n+1}=y_0{x}_n+x_0{y}_n$
所以你只要把式子化成这种形式就能做出来了。
由于数据范围高达101000${10}^{1000}$，因此要用大数

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct BigInt {
    static const int BASE = 100000000;      //基数
    static const int WIDTH = 8;             //基宽
    vector<int> s;                          //存储

    //构造函数 -- 使用LL
    BigInt(long long num = 0) { *this = num; }

    //赋值运算符 -- 使用LL
    BigInt operator = (long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while(num > 0);
        return *this;
    }
    //赋值运算符 -- 使用string
    BigInt operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for(int i = 0; i < len; i++) {
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start, end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return *this;
    }

    //比较运算符
    bool operator < (const BigInt& b) const {
        if(s.size() != b.s.size()) return s.size() < b.s.size();
        for(int i = s.size()-1; i >= 0; i--)
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        return false; //相等
    }
    bool operator >  (const BigInt& b) const{ return b < *this; }
    bool operator <= (const BigInt& b) const{ return !(b < *this); }
    bool operator >= (const BigInt& b) const{ return !(*this < b); }
    bool operator != (const BigInt& b) const{ return b < *this || *this < b; }
    bool operator == (const BigInt& b) const{ return !(b < *this) && !(*this < b); }

    //重载输入输出
    friend ostream& operator << (ostream &out, const BigInt& x) {
        out << x.s.back();
        for(int i = x.s.size()-2; i >= 0; i--) {
            char buf[20];
            sprintf(buf, "%08d", x.s[i]);
            for(int j = 0; j < strlen(buf); j++) out << buf[j];
        }
        return out;
    }
    friend istream& operator >> (istream &in, BigInt& x) {
        string s;
        if(!(in >> s)) return in;
        x = s;
        return in;
    }

    //加法
    BigInt operator + (const BigInt& b) const {
        BigInt c; c.s.clear();
        for(int i = 0, g = 0; ; i++) {
            if(g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if(i < s.size())    x += s[i];
            if(i < b.s.size())  x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }

    //加等于
    BigInt operator += (const BigInt& b) {
        *this = *this + b;
        return *this;
    }



//减法 -- 大减小 -- 其他的在外部处理
    BigInt operator - (const BigInt& b) const {
        BigInt c; c.s.clear();
        if((*this) == b) return c = 0;
        for(int i = 0, g = 0; ; ++i) {
            if(g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = -g; g = 0;
            if(i < s.size())    x += s[i];
            if(i < b.s.size())  x -= b.s[i];
            if(x < 0) x += BASE, ++g;
            c.s.push_back(x);
        }
        for(int i = c.s.size()-1; i >= 0 && c.s[i] == 0; --i) c.s.pop_back();
        return c;
    }


    //乘法 -- 未使用FFT
    BigInt operator * (const BigInt& b) const {
        int s1 = s.size(), s2 = b.s.size();
        vector<LL> v(s1+s2+1,0);
        BigInt c; c.s.resize(s1+s2, 0);
        for(int i = 0; i < s1; ++i)        //相乘
        for(int j = 0; j < s2; ++j) {
            v[i+j] += (LL)s[i]*b.s[j];
        }
        for(int i = 0; i < s1+s2; ++i) {    //进位
            v[i+1] += v[i]/BASE;
            v[i] %= BASE;
            c.s[i] = v[i];
        }
        for(int i = c.s.size()-1; i >= 0 && c.s[i] == 0; --i) c.s.pop_back();
        return c;
    }

    //除法 -- 二分
    BigInt operator / (const BigInt& b) const {
        int s1 = s.size(), s2 = b.s.size();
        int len = s1-s2;
        BigInt c, x = *this, y = b;
        if(len < 0) return c = 0;

        c.s.resize(len+1, 0);
        for(int i = len; i >= 0; --i) {
            //先将除数对齐
            y.s.resize(s2+i,0);
            for(int j = s2+i-1; j >= 0; --j) {
                if(j >= i) y.s[j] = b.s[j-i];
                else y.s[j] = 0;
            }
            //再二分找商
            int L = 0, R = BASE; BigInt t;
            while(L < R) {
                int mid = (L+R)>>1;
                t = mid;
                if(t*y > x) R = mid;
                else L = mid+1;
            }
            c.s[i] = L-1;
            //更新被除数
            t = L-1;
            x = x - t*y;
        }
        for(int i = c.s.size()-1; i >= 0 && c.s[i] == 0; --i) c.s.pop_back();
        return c;
    }

    //取模
    BigInt operator % (const BigInt& b) const {
        return (*this) - (*this)/b * b;
    }

    //开方 -- 二分 -- 浮点数可放大1e4精确一位
    BigInt Sqrt() {
        BigInt L = 1, R = *this;
        while(L < R) {
            BigInt mid = (L+R)/2;
            if(mid*mid > *this) R = mid;
            else L = mid+1;
        }
        return L-1;
    }

};
int main()
{
    BigInt n;
    cin>>n;
    BigInt x=3;
    BigInt y=2;
    BigInt ans;
    BigInt three=3,four=4,two=2;
    while(y<n)
    {
        BigInt lastx=x;
        x=three*x+four*y;
        y=two*lastx+three*y;
    }
    ans=y;
    x=7;
    y=2;
    BigInt seven=7,twofour=24;
    while(three*y<n)
    {
        BigInt lastx=x;
        x=seven*x+twofour*y;
        y=two*lastx+seven*y;
    }
    if(three*y<ans)
        ans=three*y;
    cout<<ans<<endl;
}

D inv
我们要将a数组插进b数组中，实际上a数组中的数不会互相影响。所以我们只要算出b数组对当前插进的数的影响就行了。如果想到那么相当于差不多做出来了。假如之前插的是x，现在就要插x+2了，我们可以发现除了x+1这个数，b数组中的每个数对x+2的影响与对x的影响都不会变，所以我们只要处理x+1对x+2的影响和对x的影响的区别就行了。
显然，对于x+1之前的位置，逆序对数都需要加1，而之后的位置都要减1。每次处理完后取最小值就行了。至于为什么这样做是对的。读者可以自己思考一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;

#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
struct node
{
    long long lazy;
    long long minval;
}nodes[maxn<<2];

void pushup(int rt)
{
    nodes[rt].minval=min(nodes[rt<<1].minval,nodes[rt<<1|1].minval);
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        nodes[rt].lazy=0;
        nodes[rt].minval=l;
        return;
    }
    int m=l+r>>1;
    build(ls);
    build(rs);
    pushup(rt);
}

void pushdown(int rt)
{
    if(nodes[rt].lazy)
    {
        nodes[rt<<1].lazy+=nodes[rt].lazy;

        nodes[rt<<1].minval+=nodes[rt].lazy;
        nodes[rt<<1|1].lazy+=nodes[rt].lazy;
        nodes[rt<<1|1].minval+=nodes[rt].lazy;
        nodes[rt].lazy=0;
    }
}

void update(int L,int R,int C,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        nodes[rt].lazy+=C;
        nodes[rt].minval+=C;
        return;
    }
    pushdown(rt);
    int m=l+r>>1;
    if(L<=m)update(L,R,C,ls);
    if(R>m)update(L,R,C,rs);
    pushup(rt);
}

int IDX[maxn];
#define lowbit(x) x&-x
int sum[maxn];
void add(int x)
{
    while(x)
    {
        sum[x]+=1;
        x-=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x<maxn)
    {
        res+=sum[x];
        x+=lowbit(x);
    }
    return res;
}
int b[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    long long now=0;
    for(int i=1;i<=n/2;i++)
    {
        scanf("%d",&b[i]);
        IDX[b[i]]=i;
        now+=query(b[i]/2);
        add(b[i]/2);
    }
    build(0,n/2,1);
    long long ans=now;
    for(int i=1;i<=n;i+=2)
    {
        ans+=nodes[1].minval;
        int idx=IDX[i+1];
        update(0,idx-1,1,0,n/2,1);
        update(idx,n/2,-1,0,n/2,1);
    }
    printf("%lld\n",ans);
    return 0;
}

F take
这题比赛的时候没做出来，脑子抽了果然就回不来了。实际上思路很显然，只要算出维护当前点比它大的数都不出现的概率就行了。这里用树状数组就完事了。
还有一点要说明的是，这里必须要维护后缀积，一开始我维护的前缀积一直过不了，还以为自己写错了，实际上如果维护前缀积，前面加入乘了一个0，那么后面的就算不出正确结果了。所以题目需要你维护前缀还是后缀，就乖乖的那样写好了。。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int maxn=1e5+5;
#define lowbit(x) x&-x
int sum1[maxn];
void add(int x,int val)
{
    while(x)
    {
        sum1[x]=(1LL*sum1[x]*val)%mod;
        x-=lowbit(x);
    }
}
int query1(int x)
{
    int res=1;
    while(x<maxn)
    {
        res=(1LL*res*sum1[x])%mod;
        x+=lowbit(x);
    }
    return res;
}
struct node
{
    long long p,d;
}nodes[maxn];
long long extgcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0&&b==0)return -1;//无最大公约数
    if(b==0){x=1;y=0;return a;}
    long long d=extgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;//返回gcd(a,b)
}
//****************求逆元******************************
//ax=1(mod n)
long long mod_reverse(long long a,long long n)
{
    long long x,y;
    long long d=extgcd(a,n,x,y);
    if(d==1)return (x%n+n)%n;
    return -1;
}
int Y[maxn];
int main()
{
    for(int i=0;i<maxn;i++)sum1[i]=1;
    int n;
    scanf("%d",&n);
    long long p,d;
    long long inv100=mod_reverse(100,mod);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld %lld",&p,&d);
        Y[i]=d;
        nodes[i].p=p*inv100%mod;
        nodes[i].d=d;
    }
    Y[n+1]=0;
    sort(Y+1,Y+1+n+1);
    int ynum=unique(Y+1,Y+1+n+1)-Y-1;

    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int idx=lower_bound(Y+1,Y+1+ynum,nodes[i].d)-Y;
        long long tmp=1LL*query1(idx)%mod;
        ans=(ans+1LL*nodes[i].p*tmp%mod)%mod;
        add(idx,(mod+1-nodes[i].p)%mod);
    }
    printf("%lld\n",ans);
    return 0;
}

H subseq
找出a中下标字典序第k小的严格递增子序列。
实际上我们想维护出每个位置的严格递增子序列就能做出来了。
那么维护的过程也十分简单，求个后缀和就行了。具体见代码吧。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int a[maxn],b[maxn];
long long sum[maxn];
#define lowbit(x) x&-x
void add(int x,long long val)
{
    while(x)
    {
        sum[x]=sum[x]+val;
        if(sum[x]>1e18)sum[x]=1e18;
        x-=lowbit(x);
    }
}
long long query(int x)
{
    long long res=0;
    while(x<maxn)
    {
        res+=sum[x];
        if(res>1e18)res=1e18;
        x+=lowbit(x);
    }
    return res;
}
long long dp[maxn];
vector<int>V;
int main()
{
    int n;
    long long k;
    scanf("%d %lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int bnum=unique(b+1,b+1+n)-b-1;
    for(int i=n;i>=1;i--)
    {
        a[i]=lower_bound(b+1,b+1+bnum,a[i])-b;
        long long tmp=query(a[i]+1);
        dp[i]=tmp+1;
        if(dp[i]>1e18)dp[i]=1e18;
        add(a[i],dp[i]);
    }
    //for(int i=1;i<=n;i++)cout<<dp[i]<<endl;
    for(int i=1;i<=n;i++)
    {
        if(k==0)break;
        if(V.size()&&a[V[V.size()-1]]>=a[i])continue;
        if(dp[i]>=k)
            V.push_back(i),k--;
        else k-=dp[i];
    }
    if(k>0||V.size()==0)
        puts("-1");
    else
    {
        printf("%d\n",V.size());
        for(int i=0;i<V.size();i++)
        {
            if(i!=0)printf(" ");
            printf("%d",V[i]);
        }
        puts("");
    }
    return 0;
}

I vcd
题解写的十分详细了。。直接贴代码吧。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=998244353;
int sum[maxn];
#define lowbit(x) x&-x
void add(int x,int val)
{
    while(x<maxn)
    {
        sum[x]+=val;
        x+=lowbit(x);
    }
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=sum[x];
        x-=lowbit(x);
    }
    return res;
}

struct Point
{
    int x,y;
    Point(int x,int y):x(x),y(y){}
    Point(){}
    bool operator<(const Point&b)const
    {
        if(x!=b.x)
            return x<b.x;
        return y<b.y;
    }
}Points[maxn];
int Y[maxn];
int cnt[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&x,&y);
        Points[i]=Point(x,y);
        Y[i]=y;
    }
    sort(Points+1,Points+1+n);
    sort(Y+1,Y+1+n);
    int ynum=unique(Y+1,Y+1+n)-Y-1;
    for(int i=1;i<=n;i++)
    {
        int idx=lower_bound(Y+1,Y+1+ynum,Points[i].y)-Y;
        Points[i].y=idx;
        cnt[idx]++;
    }
    long long ans=0;
    int j;
    for(int i=n;i>=1;i--)
    {
        j=i;
        while(j>=1&&Points[j-1].x==Points[i].x)j--;
        for(int k=j;k<=i;k++)
        {
            int they=Points[k].y;
            int tmp=query(ynum)-query(they);
            int tmp2=query(they-1);
            ans=(ans+1LL*tmp*tmp2%mod)%mod;
        }
        for(int k=j;k<=i;k++)
            add(Points[k].y,1);
        i=j;
    }
    ans=(ans+1LL*n*(n-1)/2);
    //int nowhave=n;
    for(int i=1;i<=ynum;i++)
    {
        ans=((ans-1LL*cnt[i]*(cnt[i]-1)/2)%mod+mod)%mod;
    }
    ans=(ans+n)%mod;
    printf("%lld\n",ans);
}

继续加油~~