河工院首届工业设计大赛程序组(挑战赛)题解
本文最后更新于 70 天前,其中的信息可能已经有所发展或是发生改变。

寻找ACMer


思想:

  • 签到题
  • 按照题意遍历字符串,不断向后寻找包含 ACMer 完整字符串的数量即可

std标程:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){

    string s; cin >> s;
    int idx = 0;
    int ans = 0;
    while(s.find("ACMer", idx) != -1) {
        ans ++; idx = s.find("ACMer", idx) + 1;
    }
    cout << ans << endl;

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

欧拉幻树苗


思想:

  • 树形DP
  • 始化每一个节点为独立的连通分量,即每个节点自身就是一个树的根。
  • 读取树的结构,确保我们可以通过 g 数组访问到每个节点的孩子节点。
  • 读取特殊边,并使用并查集合并特殊边的两个端点。由于题目保证特殊边的两个端点深度相同,合并这些端点不会导致环的出现。
  • 然后开始广度优先搜索。从根节点(节点1)开始,用队列来记录接下来需要访问的节点。
  • 对于当前节点 t,如果它是叶子,将 find(t) 的路径数加到答案中(即cnt[find(t)]),因为从叶子节点可以直接走到根节点。
  • 遍历当前节点t的所有孩子节点,将父节点到当前节点的路径数累加到孩子节点上(需要通过find函数找到孩子节点所在的连通分量),然后将这些孩子节点加入队列中以进行下一轮搜索。
  • 当队列为空时,所有节点都被访问过,搜索结束。最后输出计算的答案 ans。

std标程:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N   =   1e6  +  3;
const int INF   =   0x3f3f3f3f, mod   =   1e9  +  7;
const double eps   =   1e-6, PI   =   acos(-1);

int f[N], cnt[N];  // f数组用于并查集,cnt数组用于记录路径数

vector<int> g[N];  // g数组用来存储树的结构

int find(int x){
    return f[x] == x ? x : f[x]  =  find(f[x]);
}

void solve() {
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++) f[i] = i; // 初始化
    for(int i = 1; i < n; i ++){
        int x, y; cin >> x >> y; // 读取树的结构
        g[y].push_back(x); // 假设每条边是从子节点指向父节点
    }
    for(int i = 1; i <= m; i ++){
        int x, y; 
        cin >> x >> y; // 输入特殊边
        f[find(x)] = find(y); // 合并特殊边的端点
    }
    queue<int> q;
    q.push(1);
    cnt[1] = 1; // 根节点的路径数为1
    int ans = 0; // 结果变量
    while(!q.empty()){
        int t = q.front();
        q.pop();
        if(g[t].empty()) (ans += cnt[find(t)]) %= mod; // 如果t是叶子节点,累加路径数
        for(auto i:g[t]){
            (cnt[find(i)] += cnt[find(t)]) %= mod; // 将当前节点的路径数累加到其孩子节点
            q.push(i); // 将孩子节点加入队列
        }
    }
    cout << ans; 
}

int main(){

    IOS;

    int _   =   1;
    //cin >> _;
    while(_ --){
        solve();
    }

    return 0;
}

疯狂蓝桥杯

本题主要考察四舍五入,C语言中是四舍六入,但是需要四舍五入,则在结果后面加上0.001即可。

std标程:

#include<bits/stdc++.h>

using namespace std;
#define int long long 
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,x,y;
        cin>>n>>m>>x>>y;
        int z=n*y,zz=m*x;
        int zzz=z*zz/__gcd(z,zz);
        int i=zzz/z,j=zzz/zz;
        double s=sqrt(n*n*i*i+m*m*j*j) * 2; 
        s+=0.001;
        printf("%.2lf\n",s);
    } 
    return 0;
} 

Inception Ⅰ

用数组(如st)记录每个数字出现的次数,从1枚举到 (m + 1)/ 2 (不含),所有 st[i] * st[m - i]的和,注意要开long long~

std标程:

#include <iostream>

using namespace std;

const int N = 1e6 + 20;
int n, m, st[N];
long long ans;

int main()
{
    int x;
    cin >> n >> m;

    for(int i = 1; i <= n; i ++)
    {
        cin >> x;
        st[x] ++;
    }

    for(int i = 0; i < m - i; i ++)
    {
        ans += (long long)st[i] * st[m - i];
    }

    cout << ans;
    return 0;
}

Inception Ⅱ

循环枚举判断是否存在连续三个字母/四个元素组成的回文数组,(易证所有长度大于2的回文都包含这两种回文之一),定义数组记录下标为 i 的元素向后找最近的回文数组右端点的距离,如 1 1 2 2 1,对应记录数组应为 4,3,0,0,0。对每次查找的时间复杂度缩小到O(1)。

std标程:

#include <iostream>

using namespace std;

const int N = 1e6 + 20;
int n, q[N], s[N];

int main()
{
    int t;
    scanf("%d %d", &n, &t);

    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &q[i]);
    }

    for (int i = 1; i <= n; i ++)
    {
        //偶数回文
        if (i + 3 <= n)
        {
            if(q[i] == q[i + 3] && q[i + 1] == q[i + 2]) s[i] = 3;
        }
        //奇数回文
        if (i + 2 <= n)
        {
            if (q[i] == q[i + 2]) s[i] = 2;
        }
    }

    int f = 0;
    for (int i = n; i > 0; i --)
    {
        if (s[i] && !f) f = 1;
        if (f && !s[i]) s[i] = s[i + 1] + 1;
    }

    int l, r;
    while(t --)
    {
        scanf("%d %d", &l, &r);

        if (!s[l]) printf("NO\n");
        else if (l + s[l] <= r) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

Inception Ⅲ

易证,当 n == 1 或 n == 2 时,图腾陀螺可一步取胜,除此之外,Belinra均可胜利(想什么呢,这可是Belinra的主场,给你先手是客套,怎么可能让你轻易取胜)

std标程:

#include <iostream>

using namespace std;

int main()
{
    int n; cin >> n;
    if (n == 1 || n == 2) cout << "None life is but a dream .";
    else cout << "Wake up now !";
    return 0;
}

憧憬成为AK大神


思想:

  • 贪心
  • 有题目可知,到了某一个点都不能可能再往回走(回头一定不是最优解,否则在原来就已经进去AK了)
  • 先对页面编号排序,然后用一个大根堆来维护从起始页面切换到当前这个页面的已AK的场次所消耗的时间
  • 如果所有的时间消耗(切换界面的时间+对应场次让出的时间)已大于规定的时间,则该方向上的时间不可避免
  • 所以只能少切换界面,因为每一场比赛都AK一次,即将让出时间最大的页面跳过即可

std标程:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

priority_queue<LL> q;

PLL a[N];

bool cmp(PLL &a, PLL b) {
    return a.fi < b.fi;
}

LL n, m, ans, res, sum, idx;

void solve(){
    cin >> n >> m;
    for (int i = 0; i <= n; i ++) {
        LL x, y; cin >> x >> y;
        a[++ idx].fi = x;
        a[idx].se = y;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; i ++) {
        res += a[i].fi - a[i - 1].fi; //切换到 i 页面所用时间 
        q.push(a[i].se); // sum 的欲望 
        sum ++;
        res += a[i].se;
        while(!q.empty() && res > m) //如果用的时间多于m,直接ak掉 
        {
            sum --;
            res -= q.top();
            q.pop();
        }
        if(res > m) break; 
        ans = max(ans, sum); 
    }
    cout << ans << endl;
}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

高精度拼接

由于每添加一个数都需要满足 a % b == 0,故第一次从 0 到 9 枚举,如果存在满足条件的数直接输出即可,紧接着输出 n - 1 个 0,否则输出 -1

std标程:

#include <stdio.h>

int main()
{
    int a, b, c, ans = -1;
    scanf("%d %d %d", &a, &b, &c);
    for (int i = 0; i <= 9; i ++)
    {
        if ((a * 10 + i) % b == 0)
        {
            ans = a * 10 + i;
            break;
        }
    }
    if (ans != -1)
    {
        printf("%d", ans);
        for (int i = 1; i <= c - 1; i ++)
            printf("0");
    }
    else
    {
        printf("-1");
    }
    return 0;
}

逆矩阵


  • 签到题,模拟

std标程:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){
    int n; cin >> n;
    int size = n;
    n *= n;
    vector<vector<int>> ans(size, vector<int>(size, 0));
    int num = 1;
    int top = 0, st = size - 1, left = 0, right = size - 1;
    while(num <= n) {
        for(int i = top; i <= st && num <= n; i++) {
            ans[i][left] = num++;
        }
        left++; 
        for(int i = left; i <= right && num <= n; i++) {
            ans[st][i] = num++;
        }
        st--;
        for(int i = st; i >= top && num <= n; i--) {
            ans[i][right] = num++;
        }
        right--;
        for(int i = right; i >= left && num <= n; i--) {
            ans[top][i] = num++;
        }
        top++;
    }
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (ans[i][j] != 0) {
                cout << ans[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇