NKOJ 4月9日练习赛800[题解]

A.616问题(签到)

题目

子串是连续的。

果老师最喜爱的字符串是616。

果老师得到了一个纯数字的字符串S，他想知道在可以任意打乱顺序的情况下，最多有多少个不同的子串为616。

当两个子串 S1[l1...r1],S2[l2....r2] 满足 l1不等于l2且r1不等于r2或时它们被认为是不同的。

Input

11
11451419266

Output

1

思路

只需要考虑1和6的个数
让616最多的格式为6161616.....让前后字符串共用6，6的个数比1的个数多一。
设1的个数为cnt1,6的个数为cnt6，则616个数为cnt6-1或者cnt1的个数，取最小值即可，注意没有1或6的情况。
公式：max(min(cnt6-1,cnt1),0)

代码

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main(){
    int cnt1=0, cnt6=0, n;
    string ch;
    cin >> n >> ch;
    for (int i = 0; i < n;i++){
        if(ch[i]=='1')
            cnt1++;
        else if(ch[i]=='6')
            cnt6++;
    }
    cout << max(min(cnt6-1,cnt1),0) << endl;
}

B.计数问题(数学)

题目

何老板给果老师出了一个难题:

求有多少个不同的正整数三元组 (i,j,k) 满足根号i+根号j=根号k ，且i*j<=n。

果老师并不会做，你能略施援手吗？

当两个三元组 (i1,j1,k1),(i2,j2,k2) 满足i1不等于i2或j1不等于j2或k1不等于k2时它们被认为是不同的。

Input

1

Output

1

思路

两边平方得到i+j+根号i乘j=k，所以可以知道i乘j为完全平方数
我们令i*j=X^2,所以枚举小于N的所有X，在把每个X分解后计数即可
注意在x为平方数时只有一种组合，其他情况有两种组合

代码

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    long long n,cnt=0;
    cin >> n;
    for (int i = 1; i * i <= n; i++)
    {
        for (int j = 1; j <= i;j++){
                if(i==j)
                    cnt++;
                else if(i*i%j==0){
                    cnt+=2;
                }
        }
    }
    cout << cnt << endl;
}

C.魔法问题(DP)

题目

果老师n个元素( 编号1~n )，第个元素的能量值为ai。

果老师可以选择至少k个元素来施放一次魔法，魔法消耗的魔力是这些元素能量值的极差。形式化地，若所用元素编号集合为S，则消耗的魔力为选择的集合中的最大值减去最小值的差。

果老师要求每个元素必须被使用恰好一次。

果老师想知道他最少需要多少魔力才能用完所有元素，请你告诉他。

Input

4 2
8 7 114514 114513

Output

2

思路

先把能量值排序
我们设dp[i]为前i个的最小花费即为前i个的最优情况
情况一：dp[i+1]与是前一个dp[i]加上a[i]与a[i-1]的差值即为dp[i+1]=dp[i]+a[i+1]-a[i]
情况二：dp[i+1]与前面断开，连接前k个再加上原数组的差即为dp[i+1]=dp[i+1-k]+a[i+1]-a[i-k+2]
公式为情况一与情况二取最小值

代码

#include<bits/stdc++.h>

using namespace std;

int main(){
    long long n, a[1000005], dp[1000005], k;
    cin >> n >> k;
    for (long long i = 1; i <= n;i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[k] = a[k] - a[1];
    for (long long i = k + 1; i <= n; i++)
    {
        dp[i] = min(dp[i - 1] + (a[i] - a[i - 1]), dp[i - k] + (a[i] - a[i - k + 1]));
    }
    cout << dp[n] << endl;
}

D.通道问题(DP)

题目

果老师n个元素( 编号1~n )，第个元素的能量值为ai。

果老师要求每个元素必须被使用恰好一次。

果老师想知道他最少需要多少魔力才能用完所有元素，请你告诉他。

Input

2
1 2

Output

1

思路

首先将权值去重(权值相等的点连接代价为0)，
设去重之后有𝑚个点，接下来找到最小的二进制位k，满足存在vi的这个二进制位是0且存在vj的这个二进制位是1，答案为2^k*𝑚 − 1
相当于所有的这位是0的点跟𝑗连边，是1的点跟𝑖连边。

代码(出题人)

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, k;
int v[N], va, vo, ans;
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    sort(v + 1, v + n + 1);
    va = 0x7fffffff;
    for (int i = 1; i <= n; i++)
    {
        va &= v[i];
        vo |= v[i];
    }
    v[n + 1] = 2e9;
    for (int i = n; i; i--)
        k += (v[i] != v[i + 1]);
    va ^= vo;
    for (int i = 0; i <= 30; i++)
    {
        int cur = 1 << i;
        if(va&cur) {
            ans = cur * (k - 1);
            break;
        }
    }
    cout << ans << endl;
    return 0;
}