(3/6) rating: 1761 -> 1801 (+40)

A. Desorting

题意

给定一个序列 a1,a2,…,ana_1,a_2,\ldots,a_n。每一次操作，你可以选定一个下标 ii，给 a1,a2,…,aia_1,a_2,\ldots,a_i 加上 11，给 ai+1,ai+2,…,ana_{i+1},a_{i+2},\ldots,a_n 减上 11。
求要使这个序列变成非有序的，至少需要进行几次操作？

解法

不难发现，序列是非有序的等价于存在下标 ii，使 ai>ai+1a_i>a_{i+1}。因此，我们只需要找到原序列中差最小的两个元素，并将这两个元素弄成无序的即可。
可以发现，操作次数为 ⌊ai+1−ai2⌋+1\lfloor \frac {a_{i+1}-a_{i}}{2}\rfloor +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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 505;
int a[N];
void solve(int kase){
    int n=read();
    for(int i=0;i<n;i++){
        a[i]=read();
    }

    int ans = INT_MAX;
    for(int i=1;i<n;i++){
        ans = min(ans,a[i]-a[i-1]);
    }

    if(ans<0)puts("0");
    else printf("%d\n",(ans)/2+1);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Fibonaccharsis

题意

我们称如下数列为类斐波那契数列：

  • 数列只包含非负整数，并且单调不下降；
  • 对于 n>2n>2，an=an−1+an−2a_n=a_{n-1}+a_{n-2}。

给定 n (1≤n≤2⋅105)n\ (1\le n\le 2\cdot 10^5) 和 k (3≤k≤109)k\ (3\le k \le 10^9)，求出有多少个类斐波那契数列，使得第 kk 项为 nn。

解法 1

考虑枚举第一项和第二项。不难发现，第一项的范围是 0∼n0\sim n，对于第二项，可以进行二分答案找出一个合法的第二项。

这样做的复杂度理论上是 O(nlog⁡n⋅k)O(n\log n \cdot k ) 的，但是因为斐波那契数列的增长速度是一个等比数列，所以不需要加到 kk 项就会超过 nn，最多只需要加 O(log⁡n)O(\log n) 项。因此，复杂度为 O(nlog⁡2n)O(n\log ^2 n)，足够通过本题。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    ll n=read(),k=read();

    auto check = [n,k](ll a,ll b){
        if(a==0 && b==0)return -1;
        ll c;
        for(int i=3;i<=k;i++){
            c = a+b;
            if(c>n)return 0;
            a=b;
            b=c;
        }
        if(c==n)return -2;
        return -1;
    };  

    ll ans = 0;

    for(ll a=0;a<=n;a++){
        if(a!=0 && check(a,a)==0)break;

        ll l=a,r=n;
        while(l<r){
            auto mid=(l+r+1)>>1;

            if(check(a,mid)<0)l=mid;
            else r=mid-1;
        }
        if(check(a,l)==-2)ans++;
    }

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

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

解法 2（更快）

设第一项为 xx，第二项为 yy，观察这个数列的前几项：

x,y,x+y,x+2y,2x+3y,3x+5y,5x+8y,8x+13y,…x,y,x+y,x+2y,2x+3y,3x+5y,5x+8y,8x+13y,\ldots

你发现了规律了吗？设斐波那契数列 {1,1,2,3,5,8,…}\{1,1,2,3,5,8,\ldots\} 为 FF，则 ai=Fi−2x+Fi−1ya_i=F_{i-2}x+F_{i-1} y。
因此，ak=Fk−2x+Fk−1ya_k=F_{k-2}x+F_{k-1}y。这样的复杂度理论是 O(n+k)O(n+k) 的（因为要计算前 nn 项斐波那契数列，尽管可以加速到 O(log⁡k)O(\log k)），但是当 k≥42k\ge 42 的时候，此时已经有 F40>108F_{40}>10^8 了，不论如何都不存在合法的解。因此总复杂度可以做到 O(n)O(n)。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 40+5;
ll f[N];

void solve(int kase){
    ll n=read(),k=read();

    if(k>=42){
        puts("0");
        return;
    }
    
    ll ans = 0;
    for(ll a=0;a<=n;a++){
        ll b = n-a*f[k-2];
        if(b%f[k-1]==0){
            b/=f[k-1];
            if(b>=a)ans++;
        }
    }
    printf("%lld\n",ans);
}

int main(){
    f[1]=f[2]=1;
    for(int i=3;i<N;i++){
        f[i]=f[i-1]+f[i-2];
    }

    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

解法 3（最快）

事实上，在上面的算法基础上，可以继续优化，使本题的复杂度达到 O(log⁡n)O(\log n)。

注意到我们要找的是 Fk−2x+Fk−1y=n (0≤x≤y)F_{k-2}x+F_{k-1}y=n\ (0\le x\le y) 的整数解。

事实上，斐波那契数列任意相邻两项互质，即 ∀i≥2,gcd⁡(Fi,Fi−1)=1\forall i\ge 2,\gcd(F_i,F_{i-1})=1（证明略，因为这是信息竞赛，记住就行了）。那么这个方程总存在整数解（裴蜀定理）。

我们可以用拓展欧几里得算法找出其的一组整数解 (x0,y0)(x_0,y_0)。则其所有解就可以表示为 (x0+kFk−1,y0−kFk−2)(x_0+kF_{k-1},y_0-kF_{k-2})。我们只要找出所有合法的 kk 即可，利用 0≤x≤y0\le x\le y 的条件 O(1)O(1) 求出 kk 的范围。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 40+5;
ll f[N];

void exgcd(ll a,ll b,ll& x,ll& y){
    if(b==0){x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=(a/b)*x;
}

void solve(int kase){
    ll n=read(),k=read();

    if(k>=42){
        puts("0");
        return;
    }
    
    ll x,y;
    exgcd(f[k-2],f[k-1],x,y);
    x*=n,y*=n;

    // 0 <= x+k*f[k-1] 
    // k >= -x/(k[k-1])
    ll mink = ceil(1.0*-x/(f[k-1]));

    // x+k*f[k-1] <= y-k*f[k-2]
    // k*(f[k-1]+f[k-2]) <= y-x
    // k <= (y-x)/(f[k-1]+f[k-2])
    ll maxk = floor(1.0*(y-x)/(f[k-2]+f[k-1]));

    if(maxk<mink)puts("0");
    else printf("%lld\n",maxk-mink+1);
}

int main(){
    f[1]=f[2]=1;
    for(int i=3;i<N;i++){
        f[i]=f[i-1]+f[i-2];
    }

    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Ntarsis’ Set

题意

给定正整数集 SS。每次操作同时删除其中第 a1,a2,…,ana_1,a_2,\ldots,a_n 小的数。
求进行 k (1≤k≤2⋅105)k\ (1\le k\le 2\cdot 10^5) 次操作或，集合中最小的数是几？

解法

不妨考虑反向进行这个操作。一开始集合中只有一个数。
一次操作，我们往 a1−1,a2−2,…,an−na_1-1,a_2-2,\ldots,a_n-n 的位置上插入一个数，进行 kk 次。则最小的数下标增加量就是小于其下标的数的数量。因为这个增加量是单调不下降的，因此可以做到复杂度为 O(n+k)O(n+k)。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

const int N = 2e5+5;
int a[N];

// int vis[N];
void solve(int kase){
    // memset(vis,0,sizeof(vis));
    int n=read(),k=read();

    for(int i=0;i<n;i++)a[i]=read()-i-1;

    if(a[0]!=0){
        puts("1");
        return;
    }
    
    ll ans = 1, delta = 0;
    for(int i=1;i<=k;i++){
        if(ans>a[n-1])ans+=n;
        else{
            while(ans>a[delta])delta++;
            ans+=delta;
        }
    }
    printf("%lld\n",ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Imbalanced Arrays

题意

给定序列 a1,a2,…,ana_1,a_2,\ldots,a_n，要求求出一个满足下列条件的序列 bn{b_n}：

  • −n≤bi≤n,bi≠0-n \le b_i \le n, b_i \ne 0；
  • 不存在 (i,j)(i,j)，使 bi+bj=0b_i+b_j=0；
  • ∀1≤i≤n\forall 1\le i \le n，恰有 aia_i 个 jj，使得 bi+bj>0b_i+b_j>0（i,ji,j 不一定不同）。

判断这样的序列是否存在，如果存在，给出一个合法解。

解法

我们观察到一个事实，如果存在合法解，一定存在一组解，使得所有数的绝对值各不相同。（想一想，为什么？）

我们继续考虑，现在这个序列的绝对值就分别为 1∼n1\sim n。考虑绝对值为 nn 的那个数，其的 aia_i 要么为 00（对应为 −n-n），要么为 nn（对应为 nn）。如果不存在 00 和 nn，则无解。

则我们就成功确定了其中的一个数，对于剩下的数，我们可以同样递归处理长度为 n−1n-1 的数组。

将数组排序后，可以 O(n)O(n) 处理所有的数。总复杂度 O(nlog⁡n)O(n\log n)。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

const int N = 1e5+5;
int ans[N];

void solve(int kase){
    int n=read();
    vector<pii> a;
    for(int i=0;i<n;i++){
        a.push_back({read(),i});
    }
    sort(all(a));

    int l=0,r=n-1;
    while(l<=r){
        if(a[l].first==n-1-r){
            ans[a[l].second]=-(r-l+1);
            l++;
        }
        else if((a[r].first==n-l)){
            ans[a[r].second]=r-l+1;
            r--;
        }
        else{
            puts("NO");
            return;
        }
    }
    puts("YES");
    for(int i=0;i<n;i++){
        printf("%d ",ans[i]);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}