玖的数学&算法录
0%

Codeforces补题

发表于 更新于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

受队友影响，也开始在博客更新自己补题的记录

(1/1000)

1713 C（1200分）

C. Build Permutation

题目大意： 问对索引 0~n-1,需构造一个{a_i + i}均是完全平方数的排列组合，问是否能实现，实现输出该排列组合，否则输出-1。

模拟、构造

通过打表找规律不难发现这是一个环状的答案

而同时会发现 该排列组合实际上是一直存在的，不存在-1的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1: 0 
2: 1 0 
3: 1 0 2 
4: 0 3 2 1 
5: 4 3 2 1 0 
6: 0 3 2 1 5 4 
7: 1 0 2 6 5 4 3 
8: 1 0 7 6 5 4 3 2 
9: 0 8 7 6 5 4 3 2 1 
10: 9 8 7 6 5 4 3 2 1 0 
11: 0 3 2 1 5 4 10 9 8 7 6 
12: 4 3 2 1 0 11 10 9 8 7 6 5 
13: 0 3 2 1 12 11 10 9 8 7 6 5 4 
14: 1 0 2 13 12 11 10 9 8 7 6 5 4 3 
15: 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 
16: 0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
17: 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
18: 1 0 7 6 5 4 3 2 17 16 15 14 13 12 11 10 9 8 
19: 1 0 2 6 5 4 3 18 17 16 15 14 13 12 11 10 9 8 7 
20: 0 3 2 1 5 4 19 18 17 16 15 14 13 12 11 10 9 8 7 6

代码实现：对于到0~n-1的数，找到最大的平方数t*t，使得满足(n - 1) + u等于t * t即可，同时注意倒着打印就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void JiuCherish(){
    int n;
    cin >> n;
    int now = n, w = n;
    while(n)
	{
	    int t = sqrt(n);
	    while(!( n - 1 <= t * t and t * t <= 2 * ( n - 1 ))) t++;
	    int u = t * t - ( n - 1 );
	    int len = n - u;
	    for(int i=1;i<=len;i++)
	    {
	        a[now] = t * t - now + 1;
	        now--;
	    }
	    n -= len;
	}
    for(int i=1;i<=w;i++){
        cout << a[i] <<" ";
    }
    cout << endl;
}

1715 C（1700分）

题意：给定一个数组，该数组的价值为

$$\displaystyle \sum_{l=1}^{n}\sum_{r=l}^{n}g(l,r)$$

其中g(l,r)表示在[l,r]的范围内，能分出连续不同段的数量，问每次单点修改，求数组的总价值。

模拟

初始化：在最开始约定，如果当前值与前一个值不同，那么就会多出i倍的n-i+1，否则只是多出n-i+1

单点修改：

显然我们需要考虑当前数组修改前后是否有变化，以flag1,flag2记录未修改的时候是否和前者相等或后者相等。flag3，4则是记录修改后是否相等。如果修改后均没变化，那么答案就是初始化的答案，如果有变化，那么分成①前不同：修改代价是**(n - index+ 1)(index - 1)* ②后不同：修改代价是：**(n-index)(index)*

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
void solve(){
    int n,m;
    cin >> n >> m;
    ll sum = 0;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        if(a[i] != a[i - 1] || i == 1){
            sum += 1ll * (n - i + 1) * i;
        } else{
            sum += n - i + 1;
        }
    }
    a[0] = -1 , a[n + 1] = -1;
    while(m --){
        int index,x;
        cin >> index >> x;
        bool flag1 = 0,flag2 = 0,flag3 = 0,flag4 = 0;
        if(a[index] == a[index - 1]) flag1 = 1;
        if(a[index] == a[index + 1]) flag2 = 1;

        a[index] = x;

        if(a[index] == a[index - 1]) flag3 = 1;
        if(a[index] == a[index + 1]) flag4 = 1;
        if(flag1 == flag3 && flag2 == flag4){
            cout << sum << endl;
        } else{
            if(flag1 != flag3){
                ll num = 1ll * (index - 1) * (n - index + 1);
                if(flag1 == 0) sum -= num;
                else sum += num;
            }
            if(flag2 != flag4){
                ll num = 1ll * index * (n - index);
                if(flag2 == 0) sum -= num;
                else sum += num;
            }
            cout << sum << endl;
        }
    }
}

1691D（1800分）

1738D （1900分）

题意：给定一组数组a[i]和一个阈值k，约定x=a[i],两种情况如下：

Case 1: 如果a[i]<=k,那么b[x]为在a[i]前第一个大于k的值，如果不存在，那么b[x]=n+1；

Case 2: 如果a[i]>k,那么b[x]为在a[i]前第一个小于等于k的值，如果不存在，那么b[x]=0；

现在给你一组b数组，求阈值k和原来的数组，输出任意一组解

构造

1681D（1700分）

题意：

给你一个数 x ,你对他进行若干次下列操作，使其的长度等于n。

操作：选择一个在 x 的十进制表达中出现过的数位 y , 令 x * y 变为 x ，求最少次数，如果做不到返回 -1。

dfs

先放一开始的数字进队列，将到m的数字每一位进行一次遍历，之后分别相乘并且放入队列中，直到位数大于等于m

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
int dfs(ll s){
    int cnt[11];
    memset(cnt,0,sizeof(cnt));
    std::map<long long,long long> vis;
    std::queue<std::pair<ll,ll>> q;
    q.push({s,0});
    while(q.size()){
        std::pair<ll,ll> now = q.front();
        q.pop();
        if(now.fi == 0){
            return now.se;
        }
        if(vis[now.fi]){
            continue;
        }
        vis[now.fi] = now.se;
        long long t = now.fi,len = 0;
        while(t){
            cnt[t % 10] = 1;
            t /= 10;
            len++;
        }
        if(len >= n){
            return now.se;
        }
        for(int i=2;i<=9;i++){
            if(cnt[i]){
                q.push({now.fi * i,now.se + 1});
            }
        }
        memset(cnt,0,sizeof(cnt));
    }
    return -1;
}       
void JiuCherish(){
    std::cin >> n >> m;
    std::cout << dfs(m) << endl;
}