第十二届蓝桥杯大赛软件赛决赛

带宽

1Mbps = 1Mb/s = 1/8 MB/s

所以每秒最多下载200/8 = 25MB的内容

纯质数

思路：开个大小为10的数组，记录0-9的素数，然后就是暴力跑。我的结果是21844

#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
#define  sc(n) scanf("%d",&n)
#define  fori(n) for(int i=0;i<n;i++)
#define  forin(n) for(int i=1;i<=n;i++)

int a[10];
int main(){
    a[2] = 1;
    a[3] = 1;
    a[5] = 1;
    a[7] = 1;
    int ans = 0;
    for (int i = 1; i <= 20210605;i++){
        int t = i;
        int flag = 1;
        while(t){
            if(a[t%10]==0){
                flag = 0;
                break;
            }
            t /= 10;
        }
        if(flag)
            ans++;
    }
    cout << ans << endl;
}

完全日期

思路：也是暴力，遍历每一天判断一下就好啦。

最小权值

思路：不知道是不是我理解有问题，根节点的权值是固定的何来最小一说？？？我的思路就是来一个数组C保存子树节点数量，数组W保存权值，然后递归就行。结果是2667336761。

#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
#define  sc(n) scanf("%d",&n)
#define  fori(n) for(int i=0;i<n;i++)
#define  forin(n) for(int i=1;i<=n;i++)

ll a[maxn];
ll b[maxn];
void di1(int now){
    if(now>2021)
        return;
    di1(now * 2);
    di1(now * 2 + 1);
    a[now] = a[now * 2] + a[now * 2+1] +1;
}
void di2(int now ){
    if(now>2021)
        return;
    di2(now * 2);
    di2(now * 2 + 1);
    b[now] = 1 + 2 * b[now * 2] + 3 * b[now * 2 + 1] + a[now * 2] * a[now * 2] * a[now * 2 + 1];
}
int main(){
    di1(1);
    di2(1);
    cout << b[1] << endl;
}

大写

签到题就不说了。

F:123

思路：明显的找规律题，首先要求连续的l-r这一段的和，那么我门可以拆成两部分，分别求1~R 和1~L，这样ans = (1~R) 部分- (1~(L-1))部分，那么问题就转换成给定一个右边界K，如何求前K项和。看下图我们可以先求出能最大的到的n，然后计算前n*(n+1)/2个项的和，然后再计算第n * (n+1)/2 +1项 到 K项的和。那么问题就解决了。通过找规律发现n=4时前10项和等于1*4 + 2 * 3 + 3 * 2 + 4 *1 ，那么规律就很明显了。时间复杂度为sqrt(N)。

#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
#define  sc(n) scanf("%d",&n)
#define  fori(n) for(int i=0;i<n;i++)
#define  forin(n) for(int i=1;i<=n;i++)


int caln(ll r){
    int n = 1;
    while(n*(n+1)/2<=r)
        n++;
    return n - 1;
}
ll cal(ll k){
    int n = caln(k);
    int ret = 0;
    int l = 1, r = n;
    int len = n/2;
    while(len--){
        ret += l * r;
        l++;
        r--;
    }
    ret *= 2;
    if(n%2){
        ret += ((n / 2 + 1) * (n / 2 + 1));
    }
    int yu = k - n * (n + 1) / 2;
    ret += yu * (yu + 1) / 2;
    return ret;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        int l, r;
        cin >> l >> r;
        cout << cal(r) - cal(l - 1) << endl;
    }
}

异或变换

思路：找规律，这个是存在周期规律，只要找到一个周期行了。

二进制问题

思路：给定一个n求1到n中二进制满足k个1，随便一个N二进制比如：100011110111 ，我们可以对每一位进行分类讨论，

比如在第一个1上，我们有两种选择，在这个位置上放一个1，或者不放1。

• 不放1的情况下，在剩下的11位中找k个位置放1就是有C11(k)中情况,而且这样得到的数据不会超过n，满足条件。
• 放1的情况下，我们就找第二个1，也就是从左往右数第5位，重复上一条，直到把1放完位置。

翻转括号序列

思路：只会暴力骗分。

异或三角

思路：不会。只能想到4的30次方复杂度的算法，仅供参考。3个数字，我们可以暴力搜索每1位的数字，因为要求满足条件2，因此每一位上存在的序列只有一下4种｛0,0,0｝，｛1,1,0｝，｛1，0,1｝，｛0,1,1｝。那么在每一位上遍历这4中情况就可以了。

总结

这次体验还行，除了第一题猜错了很心疼以外，别的会做的也做的差不多了。总体感觉比省赛简单。省赛是真的噩梦，答题没几个会做的全是暴力骗分，居然也给我吊车尾苟进国赛。