The 2023 Guangdong Provincial Collegiate Programming Contest

2024-03-19 09:12

本文主要是介绍The 2023 Guangdong Provincial Collegiate Programming Contest,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

I. Path Planning

嗯,怎么说呢,一般二维图,数据不是很大的比如n*m*log级别允许的,如果一眼不是bfs,可以考虑结合一下二分

本题可知,只能向下或者向右,那么我们就像如果答案为x,那么一定会有一条0到x-1的路存在,

我们再想一条路肯定是先右再下,然后重复进行的,类似于一个楼梯的样子。

二分我们知道了,但是check里面如何判断才能配合二分呢,对于我们check的mid ,我们可以先按行排序再按列排序,然后按这个先行后列的顺序按我们的原图找0~mid-1的数,然后只看列是否满足即可,也就是上一个的列值小于等与目前的列值。

int n, m;
int a[N];
bool check(int mid)
{int last = -1;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (a[(i - 1) * m + j] <= mid - 1){if (j < last)return false;last = j;}}}return 1;
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[(i - 1) * m + j];}}int l = 0, r = n * m;while (l < r){int mid = l + r + 1 >> 1;if (check(mid))l = mid;elser = mid - 1;}cout << r << endl;
}

B. Base Station Construction

题意:就是跟你一堆区间,每个区间里面必选选一个点,问最小花费。

我们考虑从dp下手,定义f[i] 为代表前 i 个位置且第 i 个位置必选选的最小花费,

定义完成以后我们考虑如何转移,显然我们要选的哪个点 J 要满足 在 \left [ j+1,i-1\right ] 之间不包含完整的一个区间不然就漏掉了,转移方程那就是 f[i]=minf[j]+a[i]. 我们知道了 j 的区间范围但是不能 n方的去转移,我们考虑用单调对列来维护 一下 f[j] ,那么问题就解决了,最后我们在n+1位置建一个单点区间,以便于我们不用循环最后一个区间来找最小值了。

struct node
{int l, r;bool operator<(const node &w) const{if (r != w.r)return r < w.r;return l < w.l;}
} p[N];
int a[N], b[N], que[N];
void solve()
{int n, m;cin >> n;vector<int> f(n + 10); // f[i]表示前i个位置且第i个位置必选的最小花费for (int i = 1; i <= n; i++)cin >> a[i];a[++n] = 0;cin >> m;for (int i = 1; i <= m; i++){int l, r;cin >> l >> r;p[i] = {l, r};}sort(p + 1, p + 1 + m);priority_queue<PII> q;for (int i = 1, j = 0, k = 0; i <= n; i++){while (j <= m && p[j].r < i)q.push({p[j].l, p[j].r}), j++;if (q.size() && q.top().xx > k)k = q.top().xx;b[i] = k;}int hh = 0, tt = 0; // 一开始里面有个0,相当于第一个限制区间,前面没有限制区间,也就是可以选单点,提前push一个0for (int i = 1; i <= n; i++){int k = b[i];while (hh <= tt && que[hh] < k)hh++;f[i] = f[que[hh]] + a[i];cout << f[i] << endl;while (hh <= tt && f[que[tt]] >= f[i])tt--;que[++tt] = i;}cout << f[n] << endl;
}

这篇关于The 2023 Guangdong Provincial Collegiate Programming Contest的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/825491

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

HNU-2023电路与电子学-实验3

写在前面: 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能,设计 8 重 3-1 多路复用器。 3.分析模型机的功能,设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理,设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器; 2.用 VERILOG 语言设计模型机的 8 重 2-1 多

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

CF Bayan 2015 Contest Warm Up A.(模拟+预处理)

A. Bayan Bus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/problem/A The fi

2023 CCPC(秦皇岛)现场(第二届环球杯.第 2 阶段:秦皇岛)部分题解

所有题目链接:Dashboard - The 2023 CCPC (Qinhuangdao) Onsite (The 2nd Universal Cup. Stage 9: Qinhuangdao) - Codeforces 中文题面: contest-37054-zh.pdf (codeforces.com) G. Path 链接: Problem - G - Codeforces

AtCoder Beginner Contest 369 D - Bonus EXP 动态规划

原题链接: https://atcoder.jp/contests/abc369/tasks/abc369_d 思路:   这道题为什么要用动态规划呢,其实,对于第i个怪物,我们有打与不打两种处理方式,而对于打,我们是获得两倍的经验值,还是一倍的经验值,与我们打了奇数只怪物还是打了偶数只怪物有关了,因此我们定义dp[i][0] 为前i只怪物总共打了偶数次,dp[i][1] 为前i只怪物总