2024湖南理工学院程序设计竞赛（同步赛）题解

A 寻径指津

因为移动的代价都是1，所以是标准的bfs问题，但是与bfs不同的是四个方向的移动不是相邻的，而是一直移动到边界。

所以，我们只需要找到四个方向移动到达的位置，就可以用基本的bfs解决问题。

寻找往右走达到的点可以这么处理——对于第行的点，我们可以通过从第列往第列开始遍历，初始设置变量，如果碰到在位置为'#'，那么标记，如果碰到的不是'#'，那么位置往右走可以到达的位置就是，前者连单向边指向后者。

一行找连点的复杂度是，每行找完的复杂度就是，同样的原理对其它三个方向进行预处理连边。

连边完成以后进行bfs

参考代码

#include<bits/stdc++.h>

using namespace std;

const int inf=(1<<30);

vector<pair<int,int>> g[1010][1010];
int n,m,d[1010][1010];
char ch[1010][1010];

void bfs(int x,int y)
{
	deque<pair<int,int>> now;
	now.push_back({x,y});
	d[x][y]=0;
	while(!now.empty())
	{
		x=now.front().first,y=now.front().second;
		now.pop_front();
		for(auto k:g[x][y])
		{
			int X=k.first,Y=k.second;
			if(d[X][Y]>d[x][y]+1)
			{
				d[X][Y]=d[x][y]+1;
				now.push_back({X,Y});
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>ch[i][j];
			d[i][j]=inf;
		}
	}
	for(int i=1;i<=n;i++)
	{
		long long now=1;
		for(int j=1;j<=m;j++)
		{
			if(ch[i][j]=='#')
			{
				now=j+1;
			}
			else
			{
				g[i][j].push_back({i,now});
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		long long now=m;
		for(int j=m;j>=1;j--)
		{
			if(ch[i][j]=='#')
			{
				now=j-1;
			}
			else
			{
				g[i][j].push_back({i,now});
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		long long now=1;
		for(int j=1;j<=n;j++)
		{
			if(ch[j][i]=='#')
			{
				now=j+1;
			}
			else
			{
				g[j][i].push_back({now,i});
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		long long now=1;
		for(int j=n;j>=1;j--)
		{
			if(ch[j][i]=='#')
			{
				now=j-1;
			}
			else
			{
				g[j][i].push_back({now,i});
			}
		}
	}
	int x,y;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(ch[i][j]=='S')
			{
				bfs(i,j);
			}
			else if(ch[i][j]=='T')
			{
				x=i;y=j;
			}
		}
	}
	if(d[x][y]==inf)d[x][y]=-1;
	cout<<d[x][y];
	return 0;
}

B 猜数字

签到题

虽然有预想会有少部分同学不知道这个梗，但是实际上比较多（

于是在开赛后不久再加了一条提示

输出 即可

C 滚动数组1

脑筋急转弯

分两种情况考虑

当 时，只需要判断初始状态能否滚动即可

当 时，首先判断初始状态能否滚动，然后如果向左与向右滚动之后的状态都不能滚动，那么一定只能滚动 次，反之则可以通过反复向左向右来回滚动来滚动任意多次。

注意处理最后一个数向右滚动与第一个数向左滚动后满足要求的情况

代码参考

#include<iostream>

using namespace std;

constexpr int N = 2e5 + 10;
int n, k;
int a[N];
bool book[3];

int get(int k) {
    if (k > n)
        return k - n;
    if (k < 1)
        return k + n;
    return k;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++) {
        book[0] |= a[i] == get(i - 1);
        book[1] |= a[i] == get(i);
        book[2] |= a[i] == get(i + 1);
    }

    if (k == 1)
        cout << (book[1] ? "Yes" : "No");
    else
        cout << (book[1] && (book[0] || book[2]) ? "Yes" : "No");
}

D 滚动数组2

思维

可以发现，对于数组中每个元素所能影响的状态是唯一确定的，只需要将这些状态标记上，然后求从起始状态开始连续被标记的长度是否 即可

注意处理 的情况

参考代码

#include<iostream>

using namespace std;

constexpr int N = 2e5 + 10;
int n, k;
bool book[N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        book[(x - i + n) % n] = true;
    }

    for (int i = 0; i < k; i++)
        if (!book[i]) {
            cout << "No";
            return 0;
        }
    cout << "Yes";
}

E 背单词

考察简单数据结构、模拟以及字符串操作

本题可以看作约瑟夫问题的变种

可以使用任何支持 删除的数据结构来维护单词列表
例如(循环)链表[C++ list、 Java LinkedList]，平衡树[C++ set、Java TreeSet]

也可以使用队列，初始将单词全部入队，队头就是当前正在拼写的单词，每次拼写完之后将队头出队并入队尾，就能将要拼写的单词一直保持在队头

静态循环链表版本代码参考

#include<iostream>

using namespace std;

constexpr int N = 2e5 + 10;
int n, m;
string s[N];
int ne[N], la[N];
bool book[N];

void solve() {
    for (int i = 1; i <= n; i++)
        ne[i] = i + 1, la[i] = i - 1;
    ne[n] = 1, la[1] = n;

    int sum = 0;
    for (int idx = 1; true; idx = ne[idx])
        for (int cnt = 1; true; cnt++) {
            if (!m--)
                return;

            string t;
            cin >> t;
            if (t == s[idx]) {
                if (cnt == 1) {
                    la[ne[idx]] = la[idx];
                    ne[la[idx]] = ne[idx];
                    book[idx] = true;
                    if (++sum == n)
                        return;
                }
                break;
            }
        }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    solve();

    for (int i = 1; i <= n; i++)
        if (book[i])
            cout << s[i] << "\n";
}

队列版本代码参考

#include<iostream>
#include<queue>

using namespace std;

constexpr int N = 2e5 + 10;
int n, m;
string s[N];
queue<int> q;
bool book[N];

void solve() {
    for (int i = 1; i <= n; i++)
        q.push(i);

    while (true) {
        int idx = q.front();
        q.pop();

        for (int cnt = 1; true; cnt++) {
            if (!m--)
                return;

            string t;
            cin >> t;
            if (t == s[idx]) {
                if (cnt == 1)
                    book[idx] = true;
                else
                    q.push(idx);
                if (!q.size())
                    return;
                break;
            }
        }
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    solve();

    for (int i = 1; i <= n; i++)
        if (book[i])
            cout << s[i] << "\n";
}

F 孤岛之歌

一条边会对整个图的总度数加 ，所以如果总度数和是奇数，那么无解； 否则，答案为 。

构造方式如下：

  • 对于所有偶度数点，连接若干个自环。偶度数点节点 连接 个自环。
  • 对于所有奇度数点，两两配对连接作为一个连通分量。两奇度数点 具体配对方式为：不妨设 ，那么生成 条边 和 条边 即可。

因为对于奇度数点，必定需要和其他节点连边，不可能自己形成一个连通分量，所以上述方式连通分量数是最大的。

参考代码

#include<iostream>
#include<vector>
using namespace std;
constexpr int N = 2e5 + 10;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> a(n);
    int sum = 0;
    int num[2]{};
    for(int i=0; i<n; ++i) {
        cin>>a[i];
        sum += a[i];
        num[a[i]%2]++;
    }
    if(sum%2 == 1) {
        cout<<"-1\n";
    }else {
        cout<<num[0]+num[1]/2<<"\n";
    }
    return 0;
}

G 区间递减

相关习题

Decreasing String

昨日重现只之摘苹果

区间递增 （2023湖南理工学院新生赛）

结论：“删除”操作的实质是，如果当前整个序列非递减，删除最后一个元素；否则找到第一个满足 的位置 ，在序列中删除 。

解法

下面讨论对于数组 进行操作，直到数组非严格递减（即题中的非递增）为止会删除哪些数。

由图得解

设 为 中第一个最小值的位置，即 中的 。

情况一：

删除的顺序如下，最后只有数组的最小值留下。

alt

情况二： 并且 非严格递减，那么不需要删除。

情况三： 并且 中存在递增关系

我们假设 前面的山顶是 点

  • 那么在 中的元素，只有这段区间的最小值被保留了下来，设这个最小值为 。
  • 在 中的元素，前面一截大于 的会被依次删除
  • 在 中的元素是全局最小值，都会被保留

alt

详细证明

对于一个序列 ，如果不考虑终止，我们对其进行操作，直到全部删除完，等价于以下过程：

我们在 序列上从左扫描至右用一个非递减单调栈来模拟，每次在栈中加入 ​之前，都要把栈顶大于 的元素 掉，而这个 掉的数刚好就对应上述操作的数，并且 的顺序和上述操作相同。

最后栈内留下的数，依次 。

这样，每次 就和删除操作一一对应了。

设 为 中第一个最小值的位置。

  1. 若 ，那么答案等于最终剩余的元素就是这些最小值，答案为 n-最小值个数。

    证明：
    由于 是最左边的最小值，所以对于任意 的位置，一定存在递减关系，他们会被依次全部删除，并且删完后，整个序列仍然有递增关系（），还需要继续操作。

    接下来就是在 上操作了，这时候只要还 ，就会有一个大于 的数被删除，直到剩余数都等于 。

    整个过程中，最小值全部保留下来且仅保留了最小值，答案为 n-最小值个数。

  2. 与第一种情况相反，若 即 之后的元素全是最小值，需要作细致的讨论：

    我们设 为 之前的“山顶”，具体的，先设 ，接下来只要满足 且 ，就把 玩前面移动一次 ，得到最终的 。设 为 之前的“山底”，类似“山顶”定义，满足 关系就往前移动。最终有 。

    （1）若 ，说明整个序列一开始就非递增，答案为 0。

    （2）否则，。注意到这里是存在递增关系的，所以在 入栈之前的所有 操作都会执行，而在 入栈后 会直接入栈。

    我们假设 入栈后的，栈内元素自底向上分别为

    那么此时剩余的元素下标就是

    满足

    接下来的操作就是“把山顶削平”的过程，我们设 为 中最后一个满足 的位置， 为 中第一个满足 的位置，那么最终剩余元素就是 ，所以保留了 i+(n-j+1) 个元素，答案为 n-i-(n-j+1)。

    证明：该过程会删除 ：

    • 当前整个序列的结构是 “^” 形状的，每次会删除最大的一个元素，由之前的讨论我们知道 且 ，所以在删除 之前， 已经被删除完了，此时整个序列满足非严格递减 ，停止。并且在此之前肯定一直存在递增关系 或者 ，所以必须进行到此步。

实现

上面讨论是对一个数组进行的。

对于一个区间，抽取出来后是一样的思路，关键在于找 位置， 位置，以及数区间最小值数量。

的实现方式是用 表找最小值位置；使用 找区间最小值数量。

测题以及正赛大部分选手都用的线段树来维护。

参考 代码如下：

#include<iostream>
#include<map>
#include<vector>
#include<cassert>
#include<functional>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
#define ALL(a) a.begin(),a.end()
using namespace std;
using ll=long long;

template<typename Int>
struct SparseTable {
    vector<vector<int>> f;
    vector<Int> a;
    function<bool(Int,Int)> better;
    SparseTable(const vector<Int>& a, function<bool(Int,Int)> better)
    : a(a), better(better), f(a.size(),vector<int>(__lg(a.size())+1)) {
        int n=a.size(), lg=__lg(n);
        for(int i=0; i<n; ++i)
            f[i][0]=i;
        for (int k=1; k<=lg; ++k)
            for (int i=0; i+(1<<k)-1<n; ++i) {
                int l=f[i][k-1],r=f[i+(1<<(k-1))][k-1];
                f[i][k]=(better(a[l],a[r])?l:r);
            }
    }
    int queryIndex(int l,int r) {
        int k=__lg(r-l+1);
        int i=f[l][k],j=f[r-(1<<k)+1][k];
        return better(a[i],a[j])?i:j;
    }
    Int queryValue(int l,int r) {
        return a[queryIndex(l,r)];
    }
};

map<int,vector<int>> id;
int count_val(int val, int l, int r) {
    auto& v = id[val];
    return upper_bound(ALL(v),r)-lower_bound(ALL(v),l);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n,q;
    cin>>n>>q;
    assert(n>=1 and n<=2e5);
    assert(q>=1 and q<=2e5);

    vector<int> a(n), up(n);
    for(int i=0; i<n; ++i) {
        cin>>a[i];
        assert(a[i]>=1 and a[i]<=1e9);
        id[a[i]].push_back(i);
        up[i] = i;
        if(i and a[i-1]>=a[i]) {
            up[i] = up[i-1];
        }
    }

    SparseTable<int> sp(a, [&](int x,int y){return x<=y;});

    while(q--) {
        int l,r;
        cin>>l>>r;
        assert(l>=1 and l<=n);
        assert(r>=1 and r<=n);
        --l, --r;

        int p = sp.queryIndex(l,r);// p = min_element(a+l, a+r+1)-a
        if(up[r] <= p) {// a[p]=a[p+1]=...=a[r]
            int u = max(l, up[p]);
            if(u == l) {
                cout << "0\n";
                continue;
            }
            int i0 = sp.queryIndex(l, u-1);
            int k = lower_bound(a.begin()+u, a.begin()+p+1, a[i0], greater<int>())-a.begin();
            int remain = count_val(a[i0], l, u-1) + (r-k+1);
            cout << r-l+1 - remain <<"\n";
        }else {
            // 最小值被保留
            cout << r-l+1 - count_val(a[p], l, r) <<"\n";
        }
    }
    return 0;
}


import math
import sys
import bisect

def input():
    return sys.stdin.readline().rstrip()

def ilist():
    return list(map(int, input().split()))

tt = 1
# tt = int(input())

def main():
    n, q = ilist()
    a = ilist()
    assert 1 <= n <= int(2e5)
    assert 1 <= q <= int(2e5)
    assert len(a) == n

    up = [i for i in range(n)]
    id = dict()
    LG = int(math.log2(n))
    lg = [0]*(n+1)
    f = [[0]*(LG+1) for i in range(n)]
    for i in range(n):
        assert 1 <= a[i] <= int(1e9)
        if i and a[i-1] >= a[i]:
            up[i] = up[i-1]
        if id.get(a[i]):
            id[a[i]].append(i)
        else:
            id[a[i]] = [i]
        f[i][0] = i
        lg[i+1] = int(math.log2(i+1))

    for k in range(1, LG+1):
        for i in range(max(0, n-(1 << k)+1)):
            x = f[i][k-1]
            y = f[i+(1 << k-1)][k-1]
            f[i][k] = x if a[x] <= a[y] else y

    def get_id(l, r):
        k = lg[r-l+1]
        i = f[l][k]
        j = f[r-(1 << k)+1][k]
        return i if a[i] <= a[j] else j

    def count_val(val, l, r):
        return bisect.bisect(id[val], r)-bisect.bisect(id[val], l-1)

    def partition_point(l, r, check):
        ans = l
        while l <= r:
            mid = (l+r)//2
            if check(a[mid]):
                l = mid+1
            else:
                ans = mid
                r = mid-1
        return ans

    for i in range(q):
        l, r = ilist()
        assert 1 <= l <= r <= n
        l -= 1
        r -= 1
        p = get_id(l, r)
        if up[r] <= p:
            u = max(l, up[p])
            if u == l:
                print('0')
                continue
            i0 = get_id(l, u-1)
            k = partition_point(u, p, lambda x: x > a[i0])
            print(r-l+1-(count_val(a[i0], l, u-1) + (r-k+1)))
        else:
            print(r-l+1-count_val(a[p], l, r))

for t in range(tt):
    main()

H 憧憬成为数字高手

n个数，数字范围为1~1e5 可以思考x数字会成为哪些数字的因子，时间复杂度为 —— 假设数字x的能力值为dp[x]，那么数字x对后面数字的贡献为 () 初始化dp数字为，预处理个数即可。

直接dfs暴力查找x数的因子，记忆化搜索也可以解决问题，每个数字找因子最多不超过500次，复杂度大概在

参考代码

#include<bits/stdc++.h>

using namespace std;

const int N=2e6+10;

long long n,num[N],sum[N];

long long dfs(long long n)
{
    if(sum[n]!=0)return sum[n];
    sum[n]=1;
    for(int i=1;i<=n/i;i++)
    {
        if(n%i!=0||i>=n)continue;
        sum[n]+=dfs(i);
        if(n/i!=i&&i!=1)sum[n]+=dfs(n/i);
    }
    return sum[n];
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        cout<<dfs(num[i])<<" ";
    }
	return 0;
}

I 选购计划

使用魔法的最优解是只对一个物体使用。

对物体按照从小排序进行dp，当选择到时，如果存在选择物品且成立的方案，此时对物体使用魔法为最优解。即当遍历到时，选即为当前所能找到的最大价值。

枚举到最后一个物品，从中选最大值即为答案，时间复杂度为o(n^2)——最大是 个物品和 容量的01背包问题。

参考代码

#include<bits/stdc++.h>

using namespace std;

const int N=2e6+10;
const long long INF=(1ll<<60);

long long n,m,V;
bool st[N];
long long num[N],dp[N];

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
    }
    for(int i=1;i<=V;i++)
    {
        dp[i]=-INF;
    }
    long long ans=-1;
    sort(num+1,num+n+1);
    for(int i=1;i<=n;i++)
    {
        if(V>=num[i])ans=max(ans,dp[V-num[i]]+1+num[i]*m);
        for(int j=V;j>=num[i];j--)
        {
            dp[j]=max(dp[j-num[i]]+1,dp[j]);
        }
    }
    cout<<ans;
    return 0;
}

J 想吃KFC

求价钱总和然后判断是否比 大，如果比 大，则需要补 块钱，反之则不需要补钱，即 块钱

参考代码

#include<iostream>

using namespace std;

int main() {
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << max(0, sum - 50);
}
全部评论

相关推荐

11-30 20:19
门头沟学院 C++
点赞 评论 收藏
分享
11-27 19:34
哈尔滨理工大学 C++
点赞 评论 收藏
分享
11-02 12:31
燕山大学 机械工程师
点赞 评论 收藏
分享
10-30 17:07
University of California Riverside UE4
某些HR能不能有点职业素养
朋友圈挂人骂人巨婴😅😅
我已成为0offer的糕手：别惯着，胆子都是练出来的，这里认怂了，那以后被裁应届被拖工资还敢抗争？
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-27 10:46
点赞 评论 收藏
分享
评论
3
收藏
分享

全站热榜

正在热议
# 25届秋招总结 #
443978次浏览 4530人参与
# 春招别灰心，我们一人来一句鼓励 #
42406次浏览 539人参与
# 地方国企笔面经互助 #
7998次浏览 18人参与
# 同bg的你秋招战况如何？ #
77531次浏览 569人参与
# 实习必须要去大厂吗？ #
55848次浏览 962人参与
# 虾皮求职进展汇总 #
116797次浏览 890人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
11767次浏览 295人参与
# 实习，投递多份简历没人回复怎么办 #
2455211次浏览 34864人参与
# 提前批简历挂麻了怎么办 #
149986次浏览 1979人参与
# 在找工作求抱抱 #
906190次浏览 9423人参与
# 如果公司给你放一天假，你会怎么度过？ #
4772次浏览 56人参与
# 你投递的公司有几家约面了？ #
33212次浏览 188人参与
# 投递实习岗位前的准备 #
1196124次浏览 18551人参与
# 机械人春招想让哪家公司来捞你？ #
157657次浏览 2267人参与
# 双非本科求职如何逆袭 #
662475次浏览 7397人参与
# 发工资后，你做的第一件事是什么 #
12822次浏览 62人参与
# 工作中，努力重要还是选择重要？ #
36023次浏览 384人参与
# 简历中的项目经历要怎么写？ #
86972次浏览 1517人参与
# 参加完秋招的机械人，还参加春招吗？ #
20162次浏览 240人参与
# 我的上岸简历长这样 #
452100次浏览 8090人参与
牛客网
牛客企业服务