2020牛客NOIP赛前集训营-提高组（第五场）

A 三元组计数

分析

我们对于三元组的考虑，有一个套路，枚举二元组然后再考虑贡献。那么我们先找到有多少个二元组 $(a,b)$ 满足 $b = ka (k>1)$ 。那么这个根据调和级数可以得到 $\sum_{i=1}^n\frac{n}{i}=n\ln(n)$ 。那么我们就可以直接枚举每个元素的倍数就好了。最后再考虑每个二元组的贡献就好了。总的复杂度为 $O(n\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 100;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int n;
ll ans = 0,A[N];
int main() {
    n = read();
    for(int i = 1;i <= n;i++) {
        for(int j = i * 2;j <= n;j += i) {
            A[j]++;
        }
    }
    for(int i = 2;i <= n;i++) {
        for(int j = i * 2;j <= n;j += i) {
            ans += A[i];    
        }
    }
    cout << ans << endl;
    return 0;
}

B K匹配

分析

仍然是个套路题。我们考虑所有子串，可以通过考虑所有前缀的后缀得到。那么我们先通过 $KMP$ 求出所有的完美匹配点。那么考虑一个位置 $pos$ 时，当这个节点作为后缀的结束点， $end$ 表示离 $pos$ 最近的完美匹配点，那么开头的可取范围就应该是 $[1,end-k+1]$ 。那么 $O(n)$ 扫一次就可以了。那么总的复杂度为 $O(n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + 100;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int n,m,nxt[N];
char s[N],t[N];
bool vis[N];
ll ans = 0;
int main() {
    scanf("%d%d%s%s",&n,&m,s + 1,t + 1);
    for(int i = 2,j = 0;i <= m;i++) {
        while(j && t[j + 1] != t[i]) j = nxt[j];
        if(t[j + 1] == t[i]) j++;
        nxt[i] = j;
    }
    for(int i = 1,j = 0;i <= n;i++) {
        while(j && t[j + 1] != s[i]) j = nxt[j];
        if(t[j + 1] == s[i]) j++;
        if(j == m) {vis[i] = 1;j = nxt[j];}
    }
    for(int i = 1,last = 0;i <= n;i++) {
        if(vis[i]) last = i - m + 1;
        ans += last;
    }
    cout << ans << endl;
}

C 经典字符串问题

分析

经典主席树问题。静态区间第 $K$ 小问题。我们可以先对 $[1,n]$ 数字构成的字符串排序。这个每个数字 $x$ 便对应了一个 $rank_x$ ，因为这里的字符串长度为 $\lg n$ 的，所以可以直接快排，时间复杂度为 $O(n \lg n\log n)$ 。那么我们，之后的问题就是一个主席树的模板了，注意代码中 $x$ 和 $rank_x$ 的对应关系，总的复杂度为 $O(n\log n\lg n+q\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 100;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int lc[N * 40],rc[N * 40],cnt[N * 40],rt[N],n,Q,id[N],size = 0;
struct Node {int pos;char ch[22];}s[N];
bool cmp(Node a,Node b) {
    int len = max(strlen(b.ch+1),strlen(a.ch+1));
    for(int i = 1;i <= len;i++) 
    if(a.ch[i] != b.ch[i]) return a.ch[i] < b.ch[i];
}
void build(int &u,int l,int r) {
    if(!u) u = ++size;
    int mid = l + r >> 1;
    if(l == r) return;
    build(lc[u],l,mid);build(rc[u],mid+1,r);
}
void update(int &u,int la,int l,int r,int pos) {
    u = ++size;lc[u] = lc[la];rc[u] = rc[la];cnt[u] = cnt[la] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(pos <= mid) update(lc[u],lc[la],l,mid,pos);
    else update(rc[u],rc[la],mid+1,r,pos);
}
int ask(int a,int b,int l,int r,int k) {
    if(l == r) return l;
    int res = cnt[lc[b]] - cnt[lc[a]],mid = l + r >> 1;
    if(res >= k) return ask(lc[a],lc[b],l,mid,k);
    else return ask(rc[a],rc[b],mid+1,r,k-res);
}
int main() {
    n = read();Q = read();
    for(int i = 1;i <= n;i++) {
        scanf("%s",s[i].ch + 1);s[i].pos = i;
    }
    sort(s+1,s+1+n,cmp);
    for(int i = 1;i <= n;i++) id[s[i].pos] = i;
    build(rt[0],1,n);
    for(int i = 1;i <= n;i++) update(rt[i],rt[i-1],1,n,id[i]);
    while(Q--) {
        int l = read(),r = read(),k = read();l--;
        if(k > cnt[rt[r]] - cnt[rt[l]]) printf("-1\n");
        else {
            int Id = ask(rt[l],rt[r],1,n,k);
            printf("%s\n",s[Id].ch + 1);
        }
    }
    return 0;
}

D 圆与圆之间的距离是不能一概而论的

先说明这个做法的时间复杂度并不正确。但是在这个数据下可过，应该一个菊花或者链就死了。这里只是提供一种思路。
分析

我们考虑到因为圆只有包含和相离的关系，所以集合与集合的关系构成了一些森林。我们先假想一个大小无限的的圆，包含了所有圆，那么就构成了一棵树。考虑树上的距离，查询 $(u,v)$ 保证 $dep_u<dep_v$ 。如果 $lca \not = u$ 那么答案为 $ans=dep_u+dep_v-2\times dep_{lca}-2$ 否则 $ans=dep_u+dep_v-2\times dep_{lca}-1$ 。这个可以通过画图手模一下就知道了，因为答案为 $path_{u,v}$ 中除开 ${u,v,lca}$ 的节点个数。那么我们现在的问题就是如何建树了，由于本人太菜，没有什么复杂度是对的建树方法，这里大家就当看个笑话。因为考虑到如果 $u$ 的圆包含 $v$ ，那么 $R_u>R_v$ 。然后在建树时递归一下就好了。复杂度 $O(n^2)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 100;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
struct Node{
    int x,y,r,id;
}s[N];
bool cmp(Node a,Node b) {return a.r > b.r;}
int n,dep[N],fa[N][24],Log[N];
vector<int> G[N];
vector<int> S[N];
void dfs(int x,int d) {
    dep[x] = d;
    for(int i = 1;i <= Log[dep[x]];i++) fa[x][i] = fa[fa[x][i-1]][i-1];
    for(auto y : G[x]) dfs(y,d + 1);
}
int lca(int a,int b) {
    if(dep[a] < dep[b]) swap(a,b);
    int k = dep[a] - dep[b];
    for(int i = Log[k];~i;i--) if((k >> i) & 1) a = fa[a][i];
    if(a == b) return a;
    for(int i = Log[dep[a]];~i;i--) if(fa[a][i] ^ fa[b][i]) a = fa[a][i],b = fa[b][i];
    return fa[a][0];
}
bool in(int a,int b) {
    return 1ll*(s[a].r + s[b].r) * (s[a].r + s[b].r) > 
    1ll*(s[a].x - s[b].x) * (s[a].x - s[b].x) + 1ll * (s[a].y-s[b].y) * (s[a].y-s[b].y);
}
void build(int u,int v) {
    for(auto to : S[u]) if(in(to,v)) {build(to,v);return;}
    G[s[u].id].push_back(s[v].id);fa[s[v].id][0] = s[u].id;
    S[u].push_back(v);
}
int main() {
    n = read();
    for(int i = 2;i <= n + 1;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1;i <= n;i++) {
        s[i].x = read();s[i].y = read();s[i].r = read();s[i].id = i;
    }
    sort(s + 1,s + 1 + n,cmp);s[n + 1].id = n + 1;
    for(int i = 1;i <= n;i++) build(n + 1,i);
    dfs(n + 1,1);
    int Q = read();
    while(Q--) {
        int x = read(),y = read();
        int t = lca(x,y);
        if(dep[x] > dep[y]) swap(x,y);
        int ans = dep[x] + dep[y] - dep[t] * 2;
        if(t != x) ans--;ans--;
        printf("%d\n",ans);
    }
}