补题地址http://oj.hzjingma.com/p/7870?view=classic

A:字节计算

$1KB=1024B,1MB=1024KB$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int main() {
    printf("%.0f\n", 12.5 * 1024 * 1024);
    return 0;
}

B:合法括号序列

4对括号直接枚举所有情况,判断括号序列是否合法采用栈。

直接枚举的复杂度高达$O(n2^n)$,更优的方法是卡特兰数,hdu1023是个100的卡特兰数。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int ans;
char s[17];
bool check() {
    stack<char> ss;
    for(int i = 0; i < 8; i++) {
        if(s[i] == ')' && !ss.empty() && ss.top() == '(') ss.pop();
        else ss.push(s[i]);
    }
    return ss.empty();
}
void dfs(int id) {
    if(id == 8) {
        if(check()) ans++;
        return ;
    }
    s[id] = '(';
    dfs(id + 1);
    s[id] = ')';
    dfs(id + 1);
}
int main() {
    dfs(0);
    cout << ans << endl;
    return 0;
}

C:蓝桥单词

排列组合,7个字母任意排列但有两个A,结果为$7!/2!$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int main() {
    cout << 7 * 6 * 5 * 4 * 3 << endl;
    return 0;
}

D:无向连通图

$n$个节点的无向连通图最少有$n-1$条边。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int main() {
    cout << 2018 << endl;
    return 0;
}

E:反倍数

$n$的范围只有$10^6$,直接枚举即可AC。

$n$的范围到了$10^{18}$,把问题转化为求a的整数倍或b的整数倍或c的整数倍,容斥一下即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a, b, c;
int ans;
int main() {
    cin >> n >> a >> b >> c;
    for(int i = 1; i <= n; i++)
        if(i % a && i % b && i % c) ans++;
    cout << ans << endl;
    return 0;
}

F:单词加密

模拟一下即可。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

string s;
int main() {
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == 'x') s[i] = 'a';
        else if(s[i] == 'y') s[i] = 'b';
        else if(s[i] == 'z') s[i] = 'c';
        else s[i] += 3;
    }
    cout << s << endl;
    return 0;
}

G:螺旋矩阵

对于所有评测用例,$2 \leq n,m \leq 1000$,这个数据范围直接模拟即可。

2018年第九届蓝桥杯【C++省赛B组】【第七题:螺旋折线】没有对比就没有差距。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int r, c, t;
int a[1177][1177];
void to_right(int x, int y);
void to_up(int x, int y) {
    for(; x > 0; x--) {
        if(a[x][y]) break;
        a[x][y] = ++t;
    }
    if(a[x + 1][y + 1] == 0) to_right(x + 1, y + 1);
}
void to_left(int x, int y) {
    for(; y > 0; y--) {
        if(a[x][y]) break;
        a[x][y] = ++t;
    }
    if(a[x - 1][y + 1] == 0) to_up(x - 1, y + 1);
}
void to_down(int x, int y) {
    for(; x <= n; x++) {
        if(a[x][y]) break;
        a[x][y] = ++t;
    }
    if(a[x - 1][y - 1] == 0) to_left(x - 1, y - 1);
}
void to_right(int x, int y) {
    for(; y <= m; y++) {
        if(a[x][y]) break;
        a[x][y] = ++t;
    }
    if(a[x + 1][y - 1] == 0) to_down(x + 1, y - 1);
}
int main() {
    scanf("%d%d", &n, &m);
    scanf("%d%d", &r, &c);
    to_right(1, 1);
    printf("%d\n", a[r][c]);
    return 0;
}

H:摆动序列

设状态$dp[i][j]$表示前$i$项以$j$结尾的摆动序列有多少种,则有状态转移方程:

$$ dp[i+1][j] = \begin{cases} \sum_{k = 1}^{j-1} dp[i][k], \quad i\%2=0\\ \sum_{k = j+1}^{n} dp[i][k], \quad i\%2=1 \end{cases} $$

若直接求解时间复杂度会是$O(n^3)$,注意到状态转移方程中的$dp[i][k]$会被多次使用到,前缀和优化一下可以达到$O(n^2)$。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m, p = 10000;
int dp[1177][1177];
int main() {
    scanf("%d%d", &n, &m);
    for(int j = 1; j <= m; j++) dp[1][j] = (dp[1][j - 1] + 1) % p;
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(i % 2 == 0) {//偶数项比前一项小
                dp[i][j] = ((dp[i - 1][m] - dp[i - 1][j]) % p + p) % p;
            } else {//奇数项比前一项大
                dp[i][j] = dp[i - 1][j - 1];
            }
            //前缀和
            dp[i][j] = (dp[i][j] + dp[i][j - 1]) % p;
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

I:村庄建设

最小生成树板子题

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
double cost[1177][1177];
struct point {
    double x, y, h;
} a[1177];
double get_cost(int i, int j) {
    double ret = (a[i].h - a[j].h) * (a[i].h - a[j].h);
    ret += sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));
    return ret;
}
bool vis[1177];
double lowc[1177];
double Prim() {
    double ans = 0;
    memset(vis, false, sizeof(vis));
    vis[0] = true;
    for(int i = 1; i < n; i++) lowc[i] = cost[0][i];
    for(int i = 1; i < n; i++) {
        double minc = INF * 1000000.0;
        int p = -1;
        for(int j = 0; j < n; j++) {
            if(!vis[j] && minc > lowc[j]) {
                minc = lowc[j];
                p = j;
            }
        }
        if(p == -1) return -1;
        ans += minc;
        vis[p] = true;
        for(int j = 0; j < n; j++) {
            if(!vis[j] && lowc[j] > cost[p][j]) {
                lowc[j] = cost[p][j];
            }
        }
    }
    return ans;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i].x >> a[i].y >> a[i].h;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            cost[i][j] = cost[j][i] = get_cost(i, j);
        }
    }
    printf("%.2f\n", Prim());
    return 0;
}

J:郊外植树

枚举+剪枝,直接枚举每棵树选与不选的时间复杂度不低于$O(2^n)$,稍微优化一下:如果之前枚举过的结果中最大值是ans,当前方案面积和为num,若num+后面所有树的面积都小于ans,则可直接结束此次枚举。

这样虽然能AC,但从时间复杂度上来说不是很可靠。。。搜索的复杂度总是难以证明。。。遂询问群内大佬们得到的解决方案:

  • meet in middle
  • 听说可以折半然后sosdp合并
  • 折半 + 一个子集最大值
  • 子集dp

额。。。大佬们会,但我不会,大概意思是需要分成两半来搜索再合并答案。

暴力搜

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int b[37], tot;
bool f[37][37];
int ans, sum[MAXN];
struct point {
    int x, y, r, area;
} a[37];
bool check(int i, int j) {
    int dist = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
    return dist >= (a[i].r + a[j].r) * (a[i].r + a[j].r);
}
void build() {
    tot = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            f[i][j] = f[j][i] = check(i, j);
        }
    }
    sum[n - 1] = a[n - 1].area;
    for(int i = n - 2; i >= 0; i--) sum[i] = sum[i + 1] + a[i].area;
}
void dfs(int id, int num) {
    if(id == n) {
        ans = max(ans, num);
        return;
    }
    //剪枝
    if(num + sum[id] <= ans) return;
    //选用id
    bool conflict = false;
    for(int i = 0; i < tot; i++) {
        if(!f[b[i]][id]) {
            conflict = true;
            break;
        }
    }
    if(!conflict) {
        b[tot++] = id;
        dfs(id + 1, num + a[id].area);
        tot--;
    }
    //不选用id
    dfs(id + 1, num);
}
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
        a[i].area = a[i].r * a[i].r;
    }
    build();
    dfs(0, 0);
    printf("%d\n", ans);
    return 0;
}

总结

模拟赛这么水是为了给新生增加信心吗???令人迷惑的行为,和省赛的差距有点大,无论是题型还是题意还是数据范围,18年的螺旋折线19年的后缀表达式跟这些题目难度不在一个级别上。。。

Last modification:April 22nd, 2020 at 03:29 pm
如果觉得我的文章对你有用,请随意赞赏