bef->NO.11

Veröffentlicht am

NOWCODER TG4 B 区间

题目描述

给出一个序列 a1, …, an。

定义一个区间 [l,r] 是好的，当且仅当这个区间中存在一个 i，使得 ai 恰好等于 al, al+1, …, ar-1, ar 的最大公因数。

求最长的好的区间的长度。

输入描述:

1
2
3
第一行 n，表示序列的长度；

第二行 n 个数 a1,a2,...,an。

输出描述:

1
输出一行一个数，表示最长的好的区间的长度。

示例1

输入

复制

1
2
5
4 6 9 3 6

输出

复制

1
4

说明

1
选择区间 [2,5]，i=4。

备注:

1
2
3
4
5
6
7
8
9
10
11
对于测试点 1、2，n≤ 100；

对于测试点 3、4，n≤ 2,000；

对于测试点 5、6，n ≤ 200,000, ai≤ 100，且数据随机；

对于测试点 7、8、9，n ≤ 200,000；

对于测试点 10，没有特殊限制。

对于所有数据，n≤ 4x 10^6, 1≤ ai≤ 1018。

题解

这道题难度还行，大概TG D1T2难度？

我们考虑题目所要求的那个区间，这个区间的最大公约数必定等于这个区间的最小值，并且其他数都是这个最小值的整数倍。

我们对每个值找出它左边整数倍的最远点，右边也是。问题就解决了。

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define ll long long
#define maxn 4000005
ll Ar[maxn] , n , ans , l[maxn] , r[maxn];
int main()
{
    scanf("%lld",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld",&Ar[i]);
    l[1] = 1 , r[n] = n;
    for(int i = 2 ; i <= n ; ++i)
    {
        int cur = i - 1;
        while(cur >= 1 && Ar[cur] % Ar[i] == 0)
            cur = l[cur] - 1;
        l[i] = cur + 1;
    }
    for(int i = n - 1 ; i >= 1 ; --i)
    {
        int cur = i + 1;
        while(cur <= n && Ar[cur] % Ar[i] == 0)
            cur = r[cur] + 1;
        r[i] = cur - 1;
    }
    for(int i = 1 ; i <= n ; ++i)
        ans = std::max(ans , r[i] - l[i] + 1);
    printf("%lld",ans);
}

Luogu P4917 天守阁的地板

题目描述

为了使万宝槌能发挥出全部魔力,小碗会将买来的地板铺满一个任意边长的正方形(地板有图案,因此不允许旋转,当然,地板不允许重叠)来达到最大共鸣

现在,她能够买到规格为a*ba∗b的地板,为了省钱,她会购买尽可能数量少的地板

现在,她想知道对于每一对a,b(1≤a,b≤n)a,b(1≤a,b≤n),她最少需要购买的地板数量

由于输出可能很大,所以你只需要输出所有答案的乘积即可,为了避免高精度,小碗很良心的让你将答案对19260817取模

输入输出格式

输入格式：

第一行一个整数T,表示数据组数
下面T行,每行一个整数n

输出格式：

共TT行,每行一个整数,表示取模后的答案

输入输出样例

输入样例#1：

1
2
3
4
5
4
1
2
3
100

输出样例#1：

1
2
3
4
1
4
1296
18996121

img

题解

这真是一道好题。

简述题意，对于任意小于n的x*y矩形，将它密铺成正方形所用的最小数量为v，求所有v的和。

显然变成一个正方形，边长得相等，设最小q个在x的方向，t个在y的方向，所用个数为t * q

显然当x,y约分至互质的情况时t * q最小

因此我们所求的就是

由题目数据可知，我们要么On求出1~n的所有答案O1查询，要么对于每次查询是一个线性复杂度以下的算法。

首先看分子的处理

这就是

那么我们该考虑分母的积该如何算了 , 算出来后乘上逆元即可。

我们可以最后平方

我们可以用常用的数论技巧来优化

对于

这就是

因此每次询问的答案的分母就是

最后的答案是

显然欧拉函数作为积性函数可以线性筛，并且只需要一次即可，然后从指数幂的特点来看再用前缀和来优化欧拉函数求和，这样复杂度是

这样做期望得分60

我们可以对分子的k做一个简单的根号优化

有一个著名的结论，对于

的取值不超过

个，这个就不证明了挺麻烦的，进阶指南上有。

那么我们可以对于k的指数幂一样的项一起处理，这样时间复杂度就是

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mod 19260817
#define ll long long
#define maxn 1000005
ll n , T , phi[maxn] , prime[maxn/8] , fac[maxn] , cnt;
bool inprime[maxn];
inline void euler(ll n)
{
    phi[1] = 1;
    for(ll i = 2 ; i <= n ; ++i)
    {
        if(!inprime[i]) phi[i] = i - 1 , prime[++cnt] = i;
        for(int j = 1 ; j <= cnt && i * prime[j] <= n ; ++j)
        {
            inprime[i*prime[j]] = true;
            if(!(i%prime[j])) phi[i*prime[j]] = prime[j] * phi[i];
            else phi[i*prime[j]] = phi[i] * phi[prime[j]];
            if(!(i%prime[j])) break;
        }
    }
    for(int i = 1 ; i <= n ; ++i)
        phi[i] += phi[i-1] ;
}
ll exgcd(ll a , ll b , ll& x , ll& y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return a;
    }
    ll g = exgcd(b , a % b , y , x);
    y -= a/b * x;
    return g;
}
ll inv(ll k)
{
    if(!k || k == 1) return 1;
    ll x , y;
    ll g = exgcd(k,mod,x,y);
    x = (x % mod + mod) % mod;
    return x;
}
inline void pre(ll n)
{
    fac[0] = fac[1] = 1;
    for(int i = 2 ; i <= n ; ++i)
        fac[i] = fac[i-1] * i % mod;
}
inline ll pow(ll x , ll y)
{
    ll ans = 1 , base = x;
    while(y)
    {
        if(y&1) ans = ans * base % mod;
        base = base % mod * base % mod;
        y /= 2;
    }
    return ans;
}
void solve(ll n)
{
    ll ans = pow(fac[n] , 2 * n);
    ll frac = 1;
    ll gx = 0;
    for(int i = 1 ; i <= n ; i = gx + 1)
    {
        gx = n/(n/i);
        // puts("OK");
        ll pw = 2 * phi[n/i] - 1;
        ll base = (fac[gx] % mod * inv(fac[i-1])) % mod ;
        frac = frac * pow(base , pw) % mod;
    }
    printf("%lld\n",ans * inv(frac) % mod * inv(frac) % mod);
}
int main()
{
    scanf("%lld",&T);
    euler(1000000);
    pre(1000000);//the fac
    while(T--)
    {
        scanf("%lld",&n);
        solve(n);
    }
}

三元上升子序列

题目描述

Erwin最近对一种叫”thair”的东西巨感兴趣。。。

在含有n个整数的序列a1,a2……an中，

三个数被称作”thair”当且仅当i<j<k且ai<aj<ak

求一个序列中”thair”的个数。

输入输出格式

输入格式：

开始一个正整数n,

以后n个数a1~an。

输出格式：

“thair”的个数

输入输出样例

输入样例#1：

1
2
4
2 1 3 4

输出样例#1：

1
2

输入样例#2：

1
2
5
1 2 2 3 4

输出样例#2：

1
7

说明

对样例2的说明:

7个”thair”分别是

1 2 3 1 2 4 1 2 3 1 2 4 1 3 4 2 3 4 2 3 4 约定 30%的数据n<=100

60%的数据n<=2000

100%的数据n<=30000

大数据随机生成

0<=a[i]<=maxlongint

题解

显然枚举中间元素，记录左边比他小的和右边比他大的数量。

树状数组轻松

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 30005
#define ll long long
ll n , tot , p[maxn] , ans , BIT[maxn] , l[maxn] , r[maxn];
struct Node{
    ll v , k;
}Ar[maxn] ;
inline bool cmp(Node x , Node y){return x.v < y.v;}
ll C(ll n , ll k)
{
    if(k > n) return 0;
    ll ans = 1;
    for(int i = n - k + 1 ; i <= n ; ++i)
        ans *= i;
    for(int i = 1 ; i <= k ; ++i)
        ans /= i;
    return ans;
}
inline ll lowbit(ll x)
{
    return x & -x;
}
inline void update(ll x , ll v)
{
    if(!x) return;
    for(ll i = x ; i <= n ; i += lowbit(i))
        BIT[i] += v;
}
inline ll query(ll x)
{
    ll ans = 0;
    for(int i = x ; i ; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld",&Ar[i].v) , Ar[i].k = i;
    std::sort(Ar+1,Ar+n+1,cmp);
    for(int i = 1 ; i <= n ; ++i)
        if(Ar[i].v == Ar[i-1].v)
            p[Ar[i].k] = tot;
        else p[Ar[i].k] = ++tot;
    for(int i = 1 ; i <= n ; ++i)
    {
        int k = query(p[i] - 1);
        l[i] = k;
        update(p[i] , 1);
    }
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("l[%d] = %lld\n",i,l[i]);
    std::memset(BIT,0,sizeof(BIT));
    for(int i = n ; i >= 1 ; --i)
    {
        int k = n - i - query(p[i]);
        r[i] = k;
        update(p[i] , 1);
    }
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("r[%d] = %lld\n",i,r[i]);
    for(int i = 1 ; i <= n ; ++i)
        ans += l[i] * r[i];
    printf("%lld",ans);
}

T3 Marisa采蘑菇

题目背景

Marisa是一个爱魔法的女孩子,而火力高而华丽的八卦炉正是她常用的武器,然而,随着时代的进步,Marisa想要升级八卦炉的火力,所以她决定去魔法森林采蘑菇来获得做实验的材料

题目描述

Marisa来到了森林之中,看到了一排nn个五颜六色的蘑菇,编号从1-n1−n,这些蘑菇的颜色分别为col[1],col[2]…col[n]col[1],col[2]…col[n]由于她很挑剔,所以她只会采那些”魔法蘑菇”

一个蘑菇被叫做”魔法蘑菇”,当且仅当它在给定的某段区间内,并且在这段给定区间内与它颜色相同的蘑菇(包括它本身)的个数 与在这个给定区间外这种颜色的蘑菇的个数之差小于等于常数kk

现在Marisa会做出mm个询问,每次询问你[l,r][l,r]中有多少种不同颜色的”魔法蘑菇”

输入输出格式

输入格式：

第一行三个整数n,m,kn,m,k
第二行nn个正整数,表示蘑菇的颜色col[i]col[i]
之后mm行,每行两个正整数l,rl,r,表示Marisa询问的区间的左端点和右端点,数据保证0<l≤r≤n0<l≤r≤n

输出格式：

共mm行,每行一个整数xx,表示询问区间中不同颜色的”魔法蘑菇”的数量

输入输出样例

输入样例#1：

1
2
3
4
5
6 3 2
2 3 2 4 1 2
1 2
2 4
1 6

输出样例#1：

1
2
3
2
3
3

说明

样例说明:
对于区间[1,2][1,2]:
col[1]=2col[1]=2,22这种颜色的蘑菇在区间[1,2][1,2]内出现了11次,在区间外出现了22次,相差为abs(1-2)=1<2abs(1−2)=1<2
col[2]=3col[2]=3,33这种颜色的蘑菇在区间[1,2][1,2]内出现了11次,在区间外出现了00次,相差为abs(1-0)=1<2abs(1−0)=1<2
所以[1,2][1,2]中有两个颜色不同的魔法蘑菇

数据范围: img

注一:本题有三个subtasksubtask,分别为第1-41−4测试点(2020分),第5-105−10测试点(3030分),第1111测试点(5050分)

注二:由于数据可能很大,建议使用读入优化

注三:图片中的a[i]即为col[i]

题解

这道题难度评级要是NOIp D2T3那我NOIp一定不写那题。

这的确是我做过的所有题里统计最巧妙（不可做）的一道题

这个题听成爷说可以莫队打爆力，那看来还是学学数据结构比较好。

首先可以求出每个数(颜色)的出现次数tot[i]tot[i],那么对每个数,如果它在这个区间内出现次数和在区间外的出现次数之差小于等于kk,那么我们可以解出这个数在区间内出现次数的范围为

所以将询问排序,当左端点右移的时候在相应的位置加上−1,1就可以了

写的时候注意细节问题

一部分一部分的说

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;++i)
{
    scanf("%d",&a[i]);
    if(!p[a[i]].size())up[i]=1;
    p[a[i]].push_back(i);
    next[pre[a[i]]]=i;
    tim[i]=tim[pre[a[i]]]+1;
    pre[a[i]]=i;
}

这是预处理出每个颜色的点，每个点的同颜色前驱，同颜色后驱，同颜色计数数量以及每个颜色第一个出现的点。

1
2
3
4
5
6
7
for(int i=1;i<=n;++i)
{
    if(!up[i])continue;//only once
    siz[a[i]]=p[a[i]].size();
    if(siz[a[i]]<=k)update(i,1);
    else update(p[a[i]][(siz[a[i]]-k-1)/2],1),update(p[a[i]][(siz[a[i]]+k)/2],-1);
}

这就是对于每个颜色的起点，我们把颜色的合法区间+1，表示这个颜色可行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int L=1;
for(int i=1;i<=m;++i)
{
    if(q[i].l==L)q[i].ans=query(q[i].r);
    else
    {
        while(L<q[i].l)
        {
            if(siz[a[L]]<=k)
            {
                update(L,-1);
                if(next[L])update(next[L],1);
                L++;
                continue;
            }
            if(tim[L]-1+(siz[a[L]]-k-1)/2<siz[a[L]])update(p[a[L]][tim[L]-1+(siz[a[L]]-k-1)/2],-1);
            if(tim[L]-1+(siz[a[L]]+k)/2<siz[a[L]])update(p[a[L]][tim[L]-1+(siz[a[L]]+k)/2],1);
            if(tim[L]+(siz[a[L]]-k-1)/2<siz[a[L]])
            update(p[a[L]][tim[L]+(siz[a[L]]-k-1)/2],1);
            if(tim[L]+(siz[a[L]]+k)/2<siz[a[L]])
            update(p[a[L]][tim[L]+(siz[a[L]]+k)/2],-1);
            L++;
        }
        q[i].ans=query(q[i].r);
    }
}

按照左端点排序以后，我们可以将左端点以前的点的影响都去掉，也就是说让同颜色的点的下一个来构成这个合法区间，4条更新只是细节。

这时候我们相当于对于每个颜色我们都把可行区间在树状数组找了出来，然后对区间左端点排序以后，我们就可以去掉每个区间左端点之前的对答案的贡献。

这样，我们只对每个点做过8次更新，时间复杂度

就可以通过本题。