首页 > 其他分享 >『模拟赛』CSP-S模拟6

『模拟赛』CSP-S模拟6

时间:2024-09-28 17:35:23浏览次数:8  
标签:ch int st qr define CSP 模拟 fo

Rank

一般

恼了怎么又狠狠挂分啊啊啊啊

image

A. 一般图最小匹配

签。(这么多天终于签上了是吧)

结论是,跟图完全没关系。题意转换完就是从 \(n\) 个数中选出 \(m\) 对差的绝对值之和最小的数。显然我们选的每一对数都应该是这 \(n\) 个数中相邻的一组,sort 一下,设 \(f_{i,j,k}\) 表示到第 \(i\) 个点选了 \(j\) 对有/没有选这个数的最小值,转移方程如下:

\[f_{i,j,0}=min(f_{i-1,j,0},f_{i-1,j,1}) \]

\[f_{i,j,1}=f_{i-1,j-1,0}+a_i-a_{i-1} \]

最终结果即为 \(f_{n,m,0}\) 与 \(f_{n,m,1}\) 中的较小值。

因为赛时觉得可能会爆 int(但事实上容易证明并不会),开 long long 的话 \(5000\times 5000\) 又有可能炸,于是用了滚动数组优化。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 5000 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N];
ll f[2][2501][2];// n; m; choose or not
namespace Wisadel
{
    short main()
    {
        freopen("match.in", "r", stdin) , freopen("match.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) a[i] = qr;
        sort(a + 1, a + 1 + n);
        memset(f, 0x3f, sizeof f);
        f[1][0][0] = 0;
        fo(i, 2, n)
        {
            int zc = i & 1, cz = !zc;
            f[zc][0][0] = f[cz][0][0];
            fo(j, 1, m)
            {
                f[zc][j][0] = min(f[cz][j][0], f[cz][j][1]);
                f[zc][j][1] = f[cz][j - 1][0] + a[i] - a[i - 1];
            }
        }
        printf("%lld\n", min(f[n & 1][m][1], f[n & 1][m][0]));
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 重定向

签。

很水的贪心,从前往后扫只要有能够删一个数使得字典序变小的方案就直接换就行,具体如下:

首先扫出 \(1\) ~ \(n\) 中未出现的数,然后动态维护当前位可出现的数,即到这一位未出现过的数。由于只能删一个数,所以只要遇到能比当前优的操作就记下然后结束遍历。

  • 当 \(a_i \neq 0\) 时
  • 若 \(a_{i+1}=0\),首先考虑整个序列未出现的数中最小的是否比 \(a_i\) 大,若是则直接删掉 \(a_i\) 并令 \(a_{i+1}\) 为那个未出现的最小数;若不是则再考虑到当前位未出现的最小数是否比整个序列未出现的最小数小,若是则我们选择删掉到当前位未出现的最小数在原序列中对应的数,并令 \(a_{i+1}\) 为这个值;若仍不满足,则说明此位无论如何操作都没有能使该序列字典序变小,继续循环即可。

  • 若 \(a_{i+1}\neq 0\),则只用判断是否有 \(a_{i}\gt a_{i+1}\),若是则删掉 \(a_i\) 即可。

  • 当 \(a_i=0\) 时

很简单,判断是否有到当前位未出现的最小数是否比整个序列未出现的最小数小,若是则同上,不是则直接给其赋值整个序列未出现的最小数即可。

有点复杂可能了,赛时有个地方不小心打炸了导致 VSCode 直接罢工了,怎么编译都是“已放弃运行”,auto save 也失灵了,导致有几个细节改了没保存,狠狠挂了 45pts。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, k, kb;
int a[N], yz[N];
set<int> st;
priority_queue<int, vector<int>, greater<int> > q;
namespace Wisadel
{
    short main()
    {
        freopen("repeat.in", "r", stdin) , freopen("repeat.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr; k = 0; st.clear();
            fo(i, 1, n) yz[i] = 0;
            bool kong = 0;
            fo(i, 1, n) a[i] = qr, yz[a[i]] = 1, st.insert(i);
            while(q.size()) q.pop();
            fo(i, 1, n) if(!yz[i]) kong = 1, q.push(i);
            if(kong)
            {// 有空位
                fo(i, 1, n - 1)
                {
                    if(a[i]) st.erase(a[i]);
                    if(a[i] != 0 && a[i + 1] == 0)
                    {
                        if(q.top() < a[i])
                        {
                            k = i;
                            a[i + 1] = q.top();
                            q.pop();
                            q.push(a[i]);
                            break;
                        }
                        else if(*st.begin() < q.top())
                        {
                            kb = *st.begin();
                            k = -1;
                            a[i + 1] = -1;
                            break;
                        }
                    }
                    if(a[i] != 0 && a[i + 1] != 0 && a[i] > a[i + 1])
                    {
                        k = i;
                        q.push(a[i]);
                        break;
                    }
                    if(a[i] == 0)
                    {
                        if(*st.begin() < q.top())
                        {
                            kb = *st.begin();
                            k = -1;
                            a[i] = -1;
                            break;
                        }
                        else
                        {
                            a[i] = q.top();
                            st.erase(a[i]);
                            q.pop();
                        }
                    }
                }
                if(k == 0) k = n;
                fo(i, 1, n)
                {
                    if((k == -1 && kb == a[i]) || k == i) continue;
                    if(a[i] == 0) a[i] = q.top(), yz[q.top()] = 1, q.pop();
                    if(a[i] == -1) a[i] = kb;
                    printf("%d ", a[i]);
                }
            }
            else
            {
                fo(i, 1, n) if(a[i] > a[i + 1]){k = i; break;}
                if(k == 0) k = n;
                fo(i, 1, n)
                {
                    if(k == i) continue;
                    printf("%d ", a[i]);
                }
            }
            printf("\n");
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. 斯坦纳树

虚树?

牛牛错误的情况挺简单的,就是一个非点集中点连了三个点集中点的情况,即:

image

首先认为边权不为 0,发现维护一个点数逐渐增加的这样的图并不好实现,于是考虑倒着做删点操作。当一个点被删掉时,我们称其为虚点。显然若虚点存在则答案为 0。一个显然的结论是:若一个点的边数小于 3,则它不会对答案产生贡献,可以直接删掉,证明就是推出上图的步骤。一点被删掉后需要将与它相连的点两两连边保证树的形态,最后再判断每个子节点是否符合删点的要求再做一遍即可。由于每个点只用删一次,时间复杂度是 \(\mathcal{O(n)}\) 的。

然后再考虑边权就很容易了,我们用并查集维护一下每个点所属的连通块,若边权为零则合并两个连通块即可。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int n, ecnt, sum;
int a[N], fa[N], cnt[N], son[3];
int ans[N];
struct edge{int u, v;} e[N];
set<int> st[N];
namespace Wisadel
{
    int Wfind(int x)
    {
        if(x == fa[x]) return x;
        return fa[x] = Wfind(fa[x]);
    }
    void Wdel(int u)
    {
        if(st[u].size() <= 2 && !cnt[u])
        {
            sum--; int num = 0;
            for(int v : st[u]) son[++num] = v;
            st[u].clear();
            fo(i, 1, num)
            {
                fo(j, 1, num) if(i != j) st[son[i]].insert(son[j]);
                st[son[i]].erase(u);
            }
            fo(i, 1, num) Wdel(son[i]);
        }
    }
    short main()
    {
        freopen("tree.in", "r", stdin) , freopen("tree.out", "w", stdout);
        n = qr;
        fo(i, 1, n) fa[i] = i;
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr, c = qr;
            if(c == 0)
            {
                int _ = Wfind(a), __ = Wfind(b);
                if(_ > __) swap(_, __);
                fa[__] = _;
            }
            else e[++ecnt].u = a, e[ecnt].v = b;
        }
        fo(i, 1, n - 1) st[Wfind(e[i].u)].insert(Wfind(e[i].v)), st[fa[e[i].v]].insert(fa[e[i].u]);
        fo(i, 1, n) a[i] = qr, a[i] = Wfind(a[i]), cnt[a[i]]++;
        fu(i, n, 1)
        {
            ans[i] = !sum, cnt[a[i]]--;
            if(!cnt[a[i]]) sum++, Wdel(a[i]);
        }
        fo(i, 1, n) printf("%d", ans[i]);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

D. 直径

神秘 \(\mathcal{O(n^6\log n)}\) 超级 dp 题。

起码签上 T1 了。

不过 VSCode 爆炸导致挂分还是太戏剧了,也算是经验++吧,虽然不挂 Rank5,但没准就为将来正式比赛攒 rp 了呢?

明天没模拟赛啊,感觉又要状态--了,晚上开 ABC 吧,争取AK(赛后也算)。


完结撒花~

image

标签:ch,int,st,qr,define,CSP,模拟,fo
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18438190

相关文章

  • CSP-S 2022~2023 补题
    下面的代码都是远古代码,不打算重写了。CSP-S2023T1密码锁题意:一个密码锁上有\(5\)个位置,每个位置上的数字是\(0\sim9\)的循环,每次打乱会选择一或两个相邻位置同时循环移动。给定\(n\)个打乱后的状态,求有多少种可能的原状态。\(n\le8\)。容易发现可能的状态数......
  • [DMY]2024 CSP-S 模拟赛 Day 6
    前言离A掉一道题最近的一次。过程看完T1以后,想先构一个\(\mathcal{O}(n^3)\)的暴力,但是发现只有10pts,而且算法复杂度接近\(\mathcal{O}(n^4)\),所以果断放弃。把链的限制写了(然后亏大了),然后开始在CS上面画画。画了一会发现一个简单的dp思路,但是是\(\mathcal{O}(n^......
  • CSP & NOIP 模拟赛记录
    9.18(lanos212)T1签到,10mins内过了。T2乍一看有点困难,题目太形式化,不太直观,先跳过去思考T3了,T3没有什么DP的思路,但是这种题显然需要DP。看了一眼T4,被一堆式子糊脸恶心了,没有怎么思考。接下来一个小时在思考T2和T3,突然发现T2只需要每次求最短路就可以了,那么就是......
  • 信息学奥赛复赛复习06-CSP-J2020-02直播获奖-向上取整、向下取整、整数除法、最大值、
    PDF文档公众号回复关键字:2024092812020CSP-J题目1优秀的拆分[题目描述]NOI2130即将举行。为了增加观赏性,CCF决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为w%,即当前排名前w%的选手的最低成绩就是即时的分数线更具体地,若当前已评出了p个......
  • 项目实战:Qt+OSG爆破动力学仿真三维引擎测试工具v1.1.0(加载.K模型,子弹轨迹模拟动画,支持
    若该文为原创文章,转载请注明出处本文章博客地址:https://hpzwl.blog.csdn.net/article/details/142454993长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软硬结合等等)持续更新中…Qt开发专栏:项目实战......
  • 第一章数据管理【4’】(DAMA-CDGA 2022年以后历年模拟题真题汇总,基本包含所有考点。)
    1、以下哪个不是DAMA-DMBOK的数据管理框架图?(知识点:第一章数据管理)A.DAMA车轮图B.DMBOK金字塔图C.环境因素六边形图D.知识领域语境关系图参考答案:B题目解析:DMBOK2第一章数据管理1.3.3,DAMA-DMBOK框架2、以下关于数据管理原则描述正确的是?(知识点:第一章数据管理)A.......
  • 第二章数据伦理处理【2’】(DAMA-CDGA 2022年以后历年模拟题真题汇总,基本包含所有考点
    1、数据伦理处理在业务驱动中有供给者、参与者、消费者三方共同构成,以下哪个成员不属于消费者一方?(知识点:第二章数据伦理处理)A.员工B.管理人员C.监管部门D.变更经理参考答案:D题目解析:P29.数据伦理处理语境关系图2、在数据处理伦理的活动中,下列哪项不属于活动之一?(知......
  • 第三章数据治理【10’】(DAMA-CDGA 2022年以后历年模拟题真题汇总,基本包含所有考点。)
    1、数据治理的驱动因素大多聚焦于减少风险或者改进流程,以下关于改进流程的描述中哪项不正确:(知识点:第三章数据治理)A.有效和持续地响应监管要求B.通过数据的完整一致性提升业务绩效C.定义和定位组织中的数据,确保元数据被管理和应用D.利用数据全周期治理来管理特定数据的......
  • DAMA-CDGA 模拟试题 示例50道题
    1、关于元数据管理原则说法正确的是 A.确保员工了解如何访问和使用元数据。B.制定、实施和审核元数据标准,以简化元数据的集成和使用。C.创建反馈机制,以便数据使用者可以将错误或过时的元数据反馈给元数据管理团队。D.以上都对正确答案:D答案解析:P322.目标和原则2......
  • 基于R语言的统计模拟——假设检验
    一、模拟目的    在统计学的广阔领域中,参数估计与假设检验构成了分析数据、验证假设的核心工具,其中,参数估计进一步细化为点估计与置信区间估计,为我们提供了参数值及其不确定性的量化视角。然而,值得注意的是,尽管这些方法在大样本情形下展现了强大的稳健性和有效性,但在处......