长沙学院飞腾迈创杯2022年新生赛（全题解）

题集链接；

官方题解；

OP

标准的新生赛，所以补得比较快~
下次出题的时候结构可以参考一下这场，难度分布还比较适用；

A 小贪一手

贪心

思路

出于取模的性质，我们可以直接构造~
由于保证了解一定存在，也不需要担心无解的问题；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int t;
    cin>>t;
    int x,y,n;
    while(t--)
    {
        scanf("%d%d%d",&x,&y,&n);
        int bas=n/x*x+y;
        if(bas>n)bas-=x;
        printf("%d\n",bas);
    }
    return 0;
}

B A+B Problem (very easy)

模拟，字符串处理

思路

注意：题目中输入的-为英文的连字符，并非数学的减号；

先处理出所有合法数字的字符串对整型的映射，再在每次+或字符串结束时分割字符串，映射到数字并计算；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string, int> mp;
string bas[100] = {};
int main()
{
    mp["zero"] = 0;bas[0]="zero";
    mp["one"] = 1;bas[1]="one";
    mp["two"] = 2;bas[2]="two";
    mp["three"] = 3;bas[3]="three";
    mp["four"] = 4;bas[4]="four";
    mp["five"] = 5;bas[5]="five";
    mp["six"] = 6;bas[6]="six";
    mp["seven"] = 7;bas[7]="seven";
    mp["eight"] = 8;bas[8]="eight";
    mp["nine"] = 9;bas[9]="nine";
    mp["ten"] = 10;
    mp["eleven"] = 11;
    mp["twelve"] = 12;
    mp["thirteen"] = 13;
    mp["fourteen"] = 14;
    mp["fifteen"] = 15;
    mp["sixteen"] = 16;
    mp["seventeen"] = 17;
    mp["eighteen"] = 18;
    mp["nineteen"] = 19;
    mp["twenty"] = 20;bas[20]="twenty";
    mp["thirty"] = 30;bas[30]="thirty";
    mp["forty"] = 40;bas[40]="forty";
    mp["fifty"] = 50;bas[50]="fifty";
    mp["sixty"] = 60;bas[60]="sixty";
    mp["seventy"] = 70;bas[70]="seventy";
    mp["eighty"] = 80;bas[80]="eighty";
    mp["ninety"] = 90;bas[90]="ninety";
    for (int i = 21; i <= 99; i++)
    {
        if (bas[i].length() <= 1)
        {
            bas[i] = bas[i / 10 * 10] + '-' + bas[i % 10];
            mp[bas[i]] = i;
        }
    }
    int t;
    string gt;
    cin >> t;
    while (t--)
    {
        cin >> gt;
        int p = 0;
        int ans = 0;
        for (int i=0;; i++)
        {
            if (gt[i] == '+' || !gt[i])
            {
                ans += mp[gt.substr(p, i - p)];
                p = i + 1;
                //printf("%d ", ans);
                if(!gt[i]) break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C Alice and Bob

博弈论

思路

内容已补全

由于每次最大拿取量的限制，对于偶数m粒棋子，每一轮（各操作一次）的后手（与全局的先后手无关）可以控制两人操作完只剩 m−1−⌈m/2⌉m-1-\lceil m/2\rceil 粒（对于奇数m粒棋子后手无法控制）；

由于最后一轮完成后剩余0枚，我们可以解得上一个关键点为2，由2推出再上一个关键点为6……以此类推就会发现关键点的分布规律；

对于初始棋子数，如果恰好为关键点，则可以保证后手（全局的）必胜，否则先手者可以使棋子点数到达关键点，此时后手则必败了（可以认为全局先手第一次操作后到达关键点，此后全局后手变为回合先手，全局先手可以控制总棋子数到达关键点）；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>ok;
int main()
{
    for(int i=2;i<=1000;i=i*2+2)
    {
        ok.push_back(i);
    }
    //cout<<ok[ok.size()-1];
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int f=0;
        for(int i=0;i<ok.size()&&!f;i++)
        {
            if(n<ok[i])break;
            else
            {
                if(n==ok[i])f=1;
            }
        }
        if(f)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

D 进化

模拟，搜索，贪心

思路

所有运算项均为正数；
对于所有乘法项，显然乘法项越后计算结果越大；

我们可以将运算项视为不可通行块，找到当前区域边界上的所有运算项，将加法项直接计算，如果没有加法项，则选择倍率最低的乘法项运算；
运算项运算后便认为是可通行块，循环以上步骤，直到当前边界上没有新的运算块；

由于数据很小，我们可以放心大胆地多次bfs；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> mp[10][10]; // type,num//-1->no,0->ok,1->add,2->mut
pair<int, int> tmp[70];
bool rch[10][10];
int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
int n, m;
int ctmp = 0;
void bfs(int x, int y)
{
    queue<pair<int, int>> que;
    if (!mp[x][y].first)
        que.push({x, y}), rch[x][y] = 1;
    else if (mp[x][y].first > 0)
    {
        tmp[ctmp++] = {x, y};
    }
    while (!que.empty())
    {
        int nowi = que.front().first, nowj = que.front().second;
        que.pop();
        for (int k = 0; k < 4; k++)
        {
            int nni = nowi + di[k], nnj = nowj + dj[k];
            if (nni >= 1 && nni <= n && nnj >= 1 && nnj <= m)
            {
                if (!mp[nni][nnj].first && !rch[nni][nnj])
                    que.push({nni, nnj}), rch[nni][nnj] = 1;
                else if (mp[nni][nnj].first > 0 && !rch[nni][nnj])
                    tmp[ctmp++] = {nni, nnj}, rch[nni][nnj] = 1;
            }
        }
    }
}
int main()
{
    int k, ni, nj, tx, ty, t, v;
    cin >> n >> m;
    string g;
    for (int i = 1; i <= n; i++)
    {
        cin >> g;
        for (int j = 0; j < m; j++)
        {
            mp[i][j + 1].first = (g[j] == '#') ? -1 : 0;
            if (g[j] == 'S')
                ni = i, nj = j + 1;
        }
    }
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        scanf("%d%d%d%d", &tx, &ty, &t, &v);
        mp[tx][ty] = {t, v};
    }
    ll ans = 1;
    while (1)
    {
        ctmp = 0;
        memset(tmp, 0, sizeof tmp);
        memset(rch, 0, sizeof rch);
        bfs(ni, nj);
        if (!ctmp)
            break;
        int addd = 0;
        pair<int, int> mnm = {0, 0};
        for (int i = 0; i < ctmp; i++)
        {
            if (mp[tmp[i].first][tmp[i].second].first == 1)
                ans += mp[tmp[i].first][tmp[i].second].second,
                    mp[tmp[i].first][tmp[i].second].first = 0, addd = 1;
            else if (mp[tmp[i].first][tmp[i].second].first == 2 &&
                     (mnm == make_pair(0, 0) ||
                      mp[tmp[i].first][tmp[i].second].first < mp[mnm.first][mnm.second].first))
            {
                mnm = {tmp[i].first, tmp[i].second};
            }
        }
        if (!addd)
        {
            ans *= mp[mnm.first][mnm.second].second;
            mp[mnm.first][mnm.second].first = 0;
        }
    }
    cout << ans;
    return 0;
}

E 防疫物资

树的直径

思路

题目描述便确定了题中所给是一棵树；

我们可以发现在每一个送货回路内，任意两节点都可以认为被走了一次（走过的道路可以组成路径），如果将这两个节点用道路连接，那么这两点原路径上的道路都可以被少走一次；

依此，我们找出这棵树上距离最远的两点即可，就是树的直径；
答案可以表示为原路径长-直径长+1；

树的直径可以由 双dfs法 或者 dp法 求得，时间复杂度相同，这里使用的是前者；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>rod[100005];
ll d[100005];
int pos;
int ds=-1;
void dfs(int u, int f,int lth)
{
    ds++;
    d[u]=d[f]+lth;
    if(d[u]>d[pos])pos=u;
    for (int i = 0; i < rod[u].size(); i++)
    {
        if (rod[u][i] == f)
            continue;
        dfs(rod[u][i], u,1);
        ds++;
    }
}
ll tree_r(int n)
{
	for(int i=1;i<=n;i++)d[i]=0;
    pos=0;
    dfs(1,1,0);
    int lth=ds;
    // cout<<lth;
    for(int i=1;i<=n;i++)d[i]=0;
    dfs(pos,pos,0);
    return lth-d[pos]+1;
}
int main()
{
    int n,u,v;
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        rod[u].push_back(v);
        rod[v].push_back(u);
    }
    cout<<tree_r(n);
    return 0;
}

F 有挂

线段树 / 树状数组

思路

区间和线段树模板题；

也许也可以用差分+树状数组解决；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5;
struct
{
    int l, r;//l,r为节点的左右界
    ll sum, lt;//sum为节点值，lt为懒标记
} segt[N << 2 | 1];
void pushdown(int p)//对懒标记进行下传
{
    if (segt[p].lt)
    {
        segt[p << 1].sum += segt[p].lt * (segt[p << 1].r - segt[p << 1].l + 1);
        segt[p << 1 | 1].sum += segt[p].lt * (segt[p << 1 | 1].r - segt[p << 1 | 1].l + 1);
        segt[p << 1].lt += segt[p].lt;
        segt[p << 1 | 1].lt += segt[p].lt;
        segt[p].lt = 0;
    }
}
void icg(int p, int cl, int cr, ll d)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
    {
        segt[p].sum += d * (segt[p].r - segt[p].l + 1);
        segt[p].lt += d;
        return;
    }
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    if (cl <= mid)
        icg(p << 1, cl, cr, d);
    if (cr >= mid + 1)
        icg(p << 1 | 1, cl, cr, d);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}
ll ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val += ick(p << 1, cl, cr);
    if (cr >= mid + 1)
        val += ick(p << 1 | 1, cl, cr);
    return val;
}
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0;
    if (cl == cr)
    {
        segt[p].sum=0;
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}
int main()
{
    int n,m,x,op,l,r,k;
    cin>>n>>m>>x;
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==1)
        {
            scanf("%d",&k);
            icg(1,l,r,k/x+(!(k%x==0)));
        }
        else
        {
            printf("%lld\n",ick(1,l,r));
        }
    }
    return 0;
}

G

数位dp，感谢汪佬（wxy）；

思路

构造状态表示 f[i][j]f[i][j] 为以 i 结尾长度 m 的区间，如果按照 j 的二进制表示（从低到高第k位（第0位开始表示）为1代表第i-k日打球，0代表该日不打球），欢乐度合法的最大值（若 j 的表示非法，则该值即为 0 ）；

则有转移方程（状态合法时）

f[i][(j<<1)的末m位]=f[i−1][j]f[i][(j<<1)+1的末m位]=f[i−1][j]+a[i]f[i][(j<<1)的末m位]=f[i-1][j]\\ f[i][(j<<1)+1的末m位]=f[i-1][j]+a[i]

其中取末m位的过程通过位运算完成；

由于m最大为8，二进制枚举每个状态不会造成很大的复杂度压力；

__builtin_popcount(t)是封装好的 bitcount 函数；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int f[N][1 << 9], n, m, a[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        for (int s = 0; s < (1 << m); ++s)
        {
            int t = (s << 1) & ((1 << m) - 1);
            if (__builtin_popcount(t) <= m / 2)
                f[i][t] = max(f[i][t], f[i - 1][s]);
            if (__builtin_popcount(t) + 1 <= m / 2)
                f[i][t | 1] = max(f[i][t | 1], f[i - 1][s] + a[i]);
        }
    int ans = 0;
    for (int s = 0; s < (1 << m); ++s)
        ans = max(ans, f[n][s]);
    cout << ans;
}

H 爱美之心人皆有之

st表，二分
参考并简化了这份代码；

思路

st表是一种 O(nlog⁡n)O(n\log n) 时空复杂度预处理，O(1)O(1) 时间复杂度求区间最大 / 小值的数据结构；

对于以 i 为左端点的所有区间而言，随着右端点的右移，区间极差会单调递增，我们可以依此二分；

找到区间极差等于 k 的最左右端点和最右右端点，便可以求出区间个数；
需要注意无解的情况；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int mi[N][21], ma[N][21], lg[N], a[N];
int ck_mi(int l, int r)
{
    int k = lg[r - l + 1];
    return min(mi[l][k], mi[r - (1 << k) + 1][k]);
}
int ck_ma(int l, int r)
{
    int k = lg[r - l + 1];
    return max(ma[l][k], ma[r - (1 << k) + 1][k]);
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
    {
        ma[i][0] = mi[i][0] = a[i], lg[i] = log2(i);
    }
    for (int i = 1; i <= 20; i++)
    {
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
        {
            mi[j][i] = min(mi[j][i - 1], mi[j + (1 << (i - 1))][i - 1]);
            ma[j][i] = max(ma[j][i - 1], ma[j + (1 << (i - 1))][i - 1]);
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int l1 = i, r1 = n;
        while (l1 < r1)
        {
            int mid = (l1 + r1) >> 1;
            if (ck_ma(i, mid) - ck_mi(i, mid) >= k)
                r1 = mid;
            else
                l1 = mid + 1;
        }
        int l2 = i, r2 = n;
        while (l2 < r2)
        {
            int mid = (l2 + r2 + 1) >> 1;
            if (ck_ma(i, mid) - ck_mi(i, mid) <= k)
                l2 = mid;
            else
                r2 = mid - 1;
        }
        if(ck_ma(i, l1) - ck_mi(i, l1) == k)
            ans += l2 - l1 + 1;
        // printf("%d %d %d\n",i,l1,l2);
    }
    cout << ans;
    return 0;
}

I 签签签到

愚人节快乐

思路

在这里插入图片描述
在这里插入图片描述

脑子空空，注意转义，也可以用raw字符串（ C++11功能）；

代码

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    cout<<"%d%\\n\"";
    return 0;
}
1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    cout<<R"(%d%\n")";
    return 0;
}
算法竞赛 > 比赛与题集
长沙学院飞腾迈创杯2022年新生赛（全题解）
https://tanyuu.github.io/2022.01-06/长沙学院飞腾迈创杯2022年新生赛（全题解）/
作者
F Juny
发布于
2022年5月8日
许可协议