HZU蓝桥杯校内第二次选拔赛题解

T1

  • 题意： 从个数中取最大的个数。
    • 对于%的数据，直接取最大的个数,时间复杂度：，或者使用优先队列维护个最大值时间复杂度：。
    • 对于%的数据，根据快速排序分治思路，选取一个数作为基准，如果超过个数比大，就往大于的一边递归，如果没有超过个数比大，就往小一边递归，而且比大的数都在里面。所以我们可以在期望时间复杂度：。
  • 代码： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e6+5;
const int maxm=1e6;
ll sum;
int a[maxn];
ll q_sort(int l, int r, int k) {
    if (l > r) {  return 0; }
    int p = rand() % (r - l + 1) + l; 
    int x = a[p];
    swap(a[r], a[p]);
    int i = l, j = r;
    while(i < j) {
        while(i < j && a[i] < x) i++;   
        if(i < j) { swap(a[i],a[j]); j--; }
        while(i < j && a[j] > x) j--;   
        if(i < j) { swap(a[i],a[j]); i++; }
    }
    swap(a[i], x);
    ll sum = 0;
    for (int j = i; j <= r; j++) sum += a[j];
    if (r - i >= k) {
        sum = q_sort(i + 1, r, k);
    } else if (k > r - i + 1) {
        sum += q_sort(l, i - 1, k - (r - i + 1));
    }
    return sum;
}
int main() {
    int n, k;
    srand(time(0));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    printf("%lld\n", q_sort(1, n, k));
    return 0;
}

T2

  • 题意：寻找一个整数使得公式最小。

    • 对于%的数据，直接暴力枚举寻找最小值即可，时间复杂度：。

    • 对于%的数据，其实这个公式就是数学上的方差公式，所以就是平均数，因为必须是整数，所以处理是大于平均数时最小，还是小于平均数时最小，时间复杂度：。

  • 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
ll a[maxn];
int main() {
    int T, n;
    ll p = 0, x = 0, t;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        p += a[i]; x += p / n; p %= n;
    }   
    if (2 * p <= n) { printf("%lld\n", x);  }
    else { printf("%lld\n", x + 1); }
    return 0;
}

T3

  • 题意：求满足题意的三元组的个数。
    • 对于%的数据，直接暴力三重循环判断即可，时间复杂度：。
    • 对于%的数据，我们可以枚举，然后对维护一个树状数组即可（记得对进行离散化），时间复杂度：。
  • 代码： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
ll c[maxn], L[maxn], R[maxn];
int n, mx, a[maxn], Hash[maxn], len;
int lowbit(int x) { return x & (-x); }
void add(int x, ll v) {
    for (int i = x; i <= mx; i += lowbit(i)) c[i] += v;
}
ll sum(int x) {
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += c[i];
    return ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        Hash[++len] = a[i];
    }
    sort (Hash + 1, Hash + len + 1);
    len = unique(Hash + 1, Hash + len + 1) - Hash - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(Hash + 1, Hash + len + 1, a[i]) - Hash;
        R[a[i]]++;
        mx = max(mx, a[i]);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += sum(a[i] - 1);
        add(a[i], -1 * L[a[i]] * R[a[i]]);
        L[a[i]]++; R[a[i]]--;
        add(a[i], L[a[i]] * R[a[i]]);
    }
    printf("%lld\n", ans);
    return 0;
}

T4

  • 题意：给出。求出第个数字能整除或者整除，但是不能同时整除和。

    • 对于%的数据，暴力枚举每一个数字，进行判断是否满足条件。时间复杂度：。
    • 对于%的数据，很明显当数字越来越大是，满足条件的数字也会越来越多，满足单调性，所以我们可以进行二分答案，判断小于的满足添加的数有多少个即可。时间复杂度：。
    • 注意特判时为即可。

  • 代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
    return b?gcd(b,a%b):a;
}
int main() {
    int T;
    ll n, a, b; cin >> n >> a >> b;
    ll d = a * b / gcd(a, b);
    ll l = 1, r = 1e18;
    ll ans = 0;
    if (a == b) {
        printf("-1\n"); return 0;
    }
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (mid/a+mid/b-mid/d*2>=n) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

T5

  • 题意： 给一长度为的木棍，要求将其切割成若干长度为的小木棍，且小木棍数量尽可能多。

    • 对于%的数据，暴力搜索即可。
    • 对于%的数据，在暴力搜索的过程中加入记忆化数组即可。

  • 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9 + 7;
int a[maxn], dp[maxn];
int dfs(int x) {
    if (x<0) return -inf;
    if (!x) return 0;
    if (dp[x]) return dp[x];
    dp[x]=-inf;
    for (int i=1;i<=4;i++) dp[x]=max(dp[x], dfs(x-a[i])+1);
    return dp[x];
}
int main() {
    int n; cin >> n;
    for (int i=1;i<=4;i++) cin >> a[i];
    cout << max(dfs(n), -1) << endl;
    return 0;
}

T6

  • 题意： 满足 且 % = 的 的个数。

    • 对于%的数据，直接暴力枚举即可。时间复杂度：
    • 对于%的数据，首先我们使用的时间预处理出%的所有余数个数，然后在的时间处理出答案，时间复杂度：
    • 对于%的数据，如果我们能快速预处理出%的所有余数个数，我们就可以在的时间处理出答案，所以如何快速处理出所有余数的个数？处理所有余数时，我们发现可以使用FFT算法快处理出所有余数的个数，处理出来之后我们就可以时间内得到答案。时间复杂度：

  • 代码：

#include<bits/stdc++.h>
#define N 2621450
#define pi acos(-1)
typedef long long ll;
using namespace std;
typedef complex<double> E;
int n,m,l,r[N];
E a[N], b[N];
ll c[N];
void FFT(E *a,int f){
    for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
    for(int i=1;i<n;i<<=1){
        E wn(cos(pi/i),f*sin(pi/i));
        for(int p=i<<1,j=0;j<n;j+=p){
            E w(1,0);
            for(int k=0;k<i;k++,w*=wn){
                E x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y;a[j+k+i]=x-y;
            }
        }
    }
}
ll dp[N], sum[N];
int main(){
    int q, p;
    srand(time(0));
    cin >> q >> p;
    for (int i = 0; i < q; i++) c[i] = p/q;
    for (int i = 1; i <= p%q; i++) c[i]++;
    for (int i = 0; i < q; i++) a[1LL*i*i%q]+=c[i];
    for (int i = 0; i < q; i++) b[i] = a[i];
    for (int i = 0; i < q; i++) sum[1LL*i*i%q] += c[i];
    n=q; m=q;
    m+=n;for(n=1;n<=m;n<<=1)l++;
    for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,1);FFT(b,1);
    for(int i=0;i<=n;i++)a[i]=a[i]*b[i];
    FFT(a,-1);
    for(int i=0;i<=m;i++) dp[i%q] += (ll)(a[i].real()/n+0.5);
    ll ans = dp[0] * sum[0];
    for (int i = 0; i < q; i++) ans += dp[i]*sum[q-i];
    cout << ans << endl;
    return 0;
}

T7

  • 题意：输出话唠的名字
    • 签到题，直接输出个人名字中任意一个即可因为每个人都是话唠。
  • 代码： 
#include <bits/stdc++.h>
using namespace std;
int main() {
    cout << "zhj"<<endl;
    return 0;
}

T8

  • 题意： 给你一个字符串(只含或字符),判断中是否有和这两个子串。签到题暴力过百万
    • 因为该字符串只含或所我们可以暴力枚举子串，所以最多枚举出现两次子串。时间复杂度:
  • 代码： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+5;
const int maxm=1e6;
char str[maxn];
int main() {
    cin >> str + 1;
    int n = strlen(str + 1);
    for (int i = 1; i <= n; i++) {
        if (str[i] == 'W' && str[i + 1] == 'J') {
            for (int j = 1; j < i; j++) {
                if (str[j] == 'W' && str[j - 1] == 'J') {
                    cout << "YES" << endl; return 0;
                }
            }   
            for (int j = i + 2; j <= n; j++) {
                if (str[j] == 'J' && str[j + 1] == 'W') {
                    cout << "YES" << endl; return 0;
                }
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}