2020 CCPC Wannafly Winter Camp Day1 （部分题解）

7-1 1A. 期望逆序对

按中点从小到大排序之后n^2求一遍答案。 赛后补题 by zx

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define inf 0x3f3f3f3f
#define test freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
using namespace std;
int n;
const int maxn=5e3+5,mod=998244353;
PII p[maxn];
bool cmp(PII lhs,PII rhs)
{
    return lhs.first+lhs.second<rhs.first+rhs.second;
}
PLL sol(int l,int r)
{
    int len2=(p[r].second-p[r].first+1); 
    PLL res={0,1ll*(p[l].second-p[l].first+1)*len2%mod};
    LL tmp=0;
    if(p[l].second>p[r].second) 
    {
        tmp+=1ll*(p[l].second-p[r].second)*len2;
        tmp+=1ll*(len2)*(len2-1)/2;
    }
    else if(p[l].second>p[r].first)
    {
        int len1=(p[l].second-p[l].first+1);
        if(p[l].first>p[r].first) tmp+=1ll*len1*(p[l].first-p[r].first)+1ll*len1*(len1-1)/2;
        else tmp+=1ll*(p[l].second-p[r].first)*(p[l].second-p[r].first+1)/2;
    }
    tmp%=mod;
    res.first=tmp;
    return res;
}
LL qpow(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int main()
{
    //test
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d%d",&p[i].first,&p[i].second);
    sort(p,p+n,cmp);
    PLL ans={0,1};
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<i;++j)
        {
            PLL t=sol(j,i);
            ans.first=(ans.first*t.second+ans.second*t.first)%mod;
            ans.second=(ans.second*t.second)%mod;
        }
    }
    cout<<qpow(ans.second,mod-2)*ans.first%mod;
    return 0;
}

7-2 1B. 密码学

签到题，solved by cyh

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define LL long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define test freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
using namespace std;
const int maxn=(1<<21)+5;
int n,m;
int x[1005],y[1005];
string s[1005];
int get_id(char c)
{
    if(c>='a'&&c<='z') return c-'a';
    else return c-'A'+26;
}
char get_c(int num)
{
    if(num<26) return 'a'+num;
    else return num-26+'A';
}
int main()
{
    ios::sync_with_stdio(false);
    //test
    cin>>n>>m;
    for(int i=0;i<m;++i) cin>>x[i]>>y[i];
    for(int i=1;i<=n;++i) cin>>s[i];
    for(int i=m-1;i>=0;--i)
    {
        int l=x[i],r=y[i];
        int sz1=s[l].size(),sz2=s[r].size();
        for(int j=0;j<sz2;++j)
        {
            int t=get_id(s[l][j%sz1]),t2=get_id(s[r][j]);
            s[r][j]=get_c((t2-t+52)%52);
        }
    }
    for(int i=1;i<=n;++i) cout<<s[i]<<'\n';
    return 0;
}

7-3 1C. 染色图

先康康$g(n,k)$g(n,k)等于什么：n个图有k个颜色的话，给每个点分配颜色之后，每两个不同颜色的点连边，直觉告诉我们（事实上也可以证明），分配的越平均，边的数量越多。
令$x = \lfloor\frac{n}{k}\rfloor, y=n\ mod\ k=n-kx$x=⌊kn​⌋,y=n mod k=n−kx
那么有$y$y种颜色染了$x+1$x+1个点，$k-y$k−y种颜色染了$x$x个点。
这种分配下可以连的边数为：$(k-y)*x*(n-x)+k*(x+1)*(n-x+1)$(k−y)∗x∗(n−x)+k∗(x+1)∗(n−x+1)
化出来之后可得$g(n,k)=n^2-n-2nx+(x^2+x)k$g(n,k)=n2−n−2nx+(x2+x)k
因为要求$\sum_{k=l}^{r}g(n,k)$∑k=lr​g(n,k),可以用分块处理这个式子。
值得注意的是不能用求两次前缀和然后相减的套路，会T。原因应该是因为除法分块前面密后面疏，而从1开始求前缀和每次都会从密到疏，而只扫一遍就很快，不过极端数据情况下他们的差别应该不会太大，而这道题这两种方法时间差距接近1000倍……
solve by wwb

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const ll mod = 998244353;
ll n;

ll sol(ll x, ll y){
    ll l = x, r;
    ll ans = 0;
    while(l <= y){
        r = n/(n/l);
        if(r > y) r = y;
        ll t = n/l;
        //cout<<"t:"<<t<<" l:"<<l<<" r:"<<r<<" n:"<<n<<endl;
        ans += (n*n%mod-n-2*n%mod*t)%mod*(r-l+1)%mod;
       // cout<<ans<<endl;
        ans += (t*(t+1)%mod) * ( ( (r+l)*(r-l+1)/2 ) %mod )%mod;


        ans %= mod;
        l = r+1;
    }
    return ans;
}
int main()
{
    //freopen("6.in", "r", stdin);
    int T;cin>>T;
    ll l, r;
    ll inv2 = (mod+1)/2;
    //scanf("%lld%lld%lld", &n, &l, &r);
    while(T--){
        scanf("%lld%lld%lld", &n, &l, &r);
        //ll ans = sol(r) - sol(l-1);
        ll ans = sol(l, r);
        ans %= mod;
        ans = (ans + mod)%mod;
        ans = (ans*inv2)%mod;
        printf("%lld\n", ans);
       // cout<<ans<<endl;
    }
}

7-6 1F. 乘法

想到去二分，这道题在思路上就基本上完成了大半了。然后在二分答案之后分类讨论正负号之后求比判定值小（或者大，取决于写法）的乘积的个数。我这里是分类讨论之后枚举a中的数字然后二分找对应的b中的位置来求的。0处理起来细节繁琐，wa六发之后重构把0单独考虑就好写一些了。
solved by wwb

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define pb push_back
using namespace std;
ll n, m, k;
vector<ll> a1, b1, a2, b2;
ll za, zb;
ll check(ll x){
    ll res = 0;
    if(x < 0){
        for(int i = 0; i < a1.size(); ++i){
            ll t = x/a1[i];
            if(t*a1[i] != x) t++;
            res += b2.end() - lower_bound(b2.begin(), b2.end(), t);
        }
        for(int i = 0; i < b1.size(); ++i){
            ll t = x/b1[i];
            if(t*b1[i] != x) t++;
            res += a2.end() - lower_bound(a2.begin(), a2.end(), t);
        }
    }else{
        res += (ll)a1.size()*(ll)b2.size() + (ll)a2.size()*(ll)b1.size();
        res += zb*(ll)(a1.size() + a2.size()) + za*(ll)(b1.size() + b2.size()) + za*zb;
        if(x == 0) return res;
        for(int i = 0; i < a1.size(); ++i){
            ll t = x/a1[i];
            if(t == 0) continue;
            res += b1.end()-lower_bound(b1.begin(), b1.end(), t);
        }
        for(int i = 0; i < a2.size(); ++i){
            ll t = x/a2[i];
            if(t == 0) continue;
            res += upper_bound(b2.begin(), b2.end(), t)-b2.begin();
        }
    }
    return res;
}
int main()
{
    //cout<<3/-5<<endl;
    cin>>n>>m>>k;
    k = n*m-k+1;
    za = zb = 0;
    for(int i = 0; i < n; ++i){
        ll x; scanf("%lld", &x);
        if(x < 0) a1.pb(x);
        else if(x > 0) a2.pb(x);
        else za++;
    }
    for(int i = 0; i < m; ++i){
        ll x; scanf("%lld", &x);
        if(x < 0) b1.pb(x);
        else if(x > 0) b2.pb(x);
        else zb++;
    }
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());
    sort(b1.begin(), b1.end());
    sort(b2.begin(), b2.end());
    ll l = -1e13, r = 1e13;
    ll ans;
    while(l <= r){
        if(check(mid) >= k) {
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }cout<<ans<<endl;
}
/*
4 4 12
0 0 -2 3
0 -2 -3 -4
*/

7-8 1H. 最大公约数

给n，k，要找一个y使得y与k的gcd与[1,n]内除k外所有数字不同。那么首先我们知道gcd(k,y)一定等于k，否则如果gcd(k,y)=x<k,那么gcd(x,y)=x，不满足。然后乘以[1,n/k]中所有素因子来排除[1,n]中k的倍数的影响。
solved by zx

import math
def isprime(n):
    if n < 2:
        return False
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

T=int(input())
for t in range(1,T+1):
    n,k=map(int,input().split(' '))
    ans=k
    i=2;
    while i*k<=n :
        if isprime(i):
            ans=ans*i
        i=i+1
    print(ans)

7-9 1I. K小数查询

考虑分块，更新的时候整块更新，然后再暴力更新边缘的块。
每个块维护一个排好序的数组。
查询的时候二分答案，然后在每个完整块内用二分在排好序的数组上查询块内多少个数小于等于要check的值。不完整的块暴力处理。
这里分的块大小为$p=\sqrt{nlogn}$p=nlogn​

查询复杂度$O(\frac{n}{p}log(p)+p)$O(pn​log(p)+p)

更新复杂度$O(\frac{n}{p}+p*logp)$O(pn​+p∗logp)
赛后补题 by wwb

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define pb push_back
using namespace std;
const int maxn = 8e4 + 50;
const int inf = 0x3f3f3f3f;
int p, u;
int n, m;
int a[maxn];
int lz[maxn];
int L[maxn], R[maxn];
vector<int> v[10050];
int get_id(int pos){
    return pos/p;
}
void update(int l, int r, int x){
    int id = get_id(l);
    if(L[id] < l){//第一块暴力拆解
        v[id].clear();
        for(int i = L[id]; i <= R[id]; ++i){
            a[i] = min(a[i], lz[id]);
            if(i >= l && i <= r){
                a[i] = min(a[i], x);
            }
            v[id].pb(a[i]);
        }
        sort(v[id].begin(), v[id].end());
        id++;
    }
    if(id >= u) return;
    while(R[id] <= r && id < u){//中间的完整块
        lz[id] = min(lz[id], x);
        id++;
    }
    if(id >= u || L[id] > r) return;
    v[id].clear();
    for(int i = L[id]; i <= R[id]; ++i){
        a[i] = min(a[i], lz[id]);
        if(i >= l && i <= r){
            a[i] = min(a[i], x);
        }
        v[id].pb(a[i]);
    }
    sort(v[id].begin(), v[id].end());
    return;
}
int check(int lim, int l, int r){
    int id = get_id(l);
    int res = 0;
    if(L[id] < l){
        for(int i = l; i <= min(R[id], r); ++i){
            a[i] = min(a[i], lz[id]);
            if(a[i] <= lim) res++;
        }
        id++;
    }
    //cout<<"res:"<<res<<endl;
    if(id >= u) return res;
    while(R[id] <= r && id < u){//中间的完整块
        if(lz[id] <= lim) res += (R[id]-L[id]+1);
        else res += upper_bound(v[id].begin(), v[id].end(), lim) - v[id].begin();
        id++;
    }
    //cout<<"res2:"<<res<<endl;
    //cout<<"id:"<<id<<endl;
    if(id >= u || L[id] > r) return res;
    for(int i = L[id]; i <= r; ++i){
        a[i] = min(a[i], lz[id]);
        if(a[i] <= lim) res++;
    }
    //cout<<"res3:"<<endl;
    return res;
}
int qry(int ll, int rr, int k){
    int l = 1, r = 1e9;
    int ans;
    //check(2, ll-1, rr-1);
    while(l <= r){
       // cout<<"mid:"<<(mid)<<" c:"<<check(mid, ll, rr)<<endl;
        if(check(mid, ll, rr) >= k){
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }
    return ans;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    p = sqrt(n*log(n));
    if(p > n) p = n;
    u = (n-1)/p+1;// id < u
    for(int id = 0; id < u; ++id) {
        lz[id] = inf;
        L[id] = id*p, R[id] = id*p+p-1;
        if(id == u-1) R[id] = n-1;
        for(int i = L[id]; i <= R[id]; ++i) v[id].pb(a[i]);
        sort(v[id].begin(), v[id].end());
    }
    //cout<<"p:"<<p<<" u:"<<u<<endl;
    while(m--){
        int op, l, r, k;
        scanf("%d%d%d%d", &op, &l, &r, &k);
        l--; r--;
        if(op == 1){
            update(l, r, k);
        }else{
            printf("%d\n", qry(l, r, k));
        }
    }
}
/*
3 1
1 2 3
2 1 3 2
*/