首页 > 其他分享 >[2027届]NOIP2024模拟赛#5

[2027届]NOIP2024模拟赛#5

时间:2024-08-23 17:07:44浏览次数:11  
标签:ch return int 2027 maxn NOIP2024 节点 模拟 mod

%%% Larunatrecy

比赛链接

榜:

image

打得还行吧。

T1

光理解题意就看了10min,理解以后写了写有手就行的暴力。

赛后发现输出 -1 能多拿10分,惨痛错过呜呜呜。

正解的话,我们给每个节点定义两个指标:

  • \(a:\) 即使加入一条入边也依旧存在一种合法的 \(W\)。
  • \(b:\) 即使加入一条出边也依旧存在一种合法的 \(W\)。

那么,对于一个 至少有一条边没有确定方向的节点 \(x\):

  • 如果 \(a,b\) 都不满足,那么直接无解。
  • 如果 \(a,b\) 恰好满足一个,那么该节点所有未确定方向的边都可以确定方向。

注意第二种节点会导致一些别的节点也变成这两种状态之一,这是一个迭代的过程。

完成迭代后,此时每个节点要么 \(a,b\) 都满足,要么它的所有边都已经定向。

接下来,我们考虑如果没有一类节点,那么一定存在一组解,也很简单:

  • 任选一个节点作为根,并把他的儿子节点任意定向,然后递归子树,那么对于每个递归到节点,如果都已经定向就无所谓,否则因为 \(a,b\) 都满足,那么父亲的边怎么定向都是合法的,因此不会出问题。

那么做法呼之欲出:按顺序遍历每条边,如果已经定向就定向,否则这条边可以任意定向,迭代这个过程即可。

复杂度 \(\mathcal{O}(n)\)。

T2

唯一过掉的题。

一开始对于两个性质,分别跑联通块和乘法原理可以搞到40分的优秀成绩。

然后根据性质想正解,可以把原图按照高度阻隔分成多个块,每一个块完全包含低一级的块。现在要求的就是有多少种用互不包含额度块覆盖原图的方法。

由于块可以抽象成一棵树,所以不难想到 Kruscal 重构树,然后 DP式子稍微一推就出来了,每个节点可以由两个儿子节点分别计算合并而来。

然后第一次交的时候数组开小了,幸好检查了,大汗)

lg上面竟然是紫题,经验+1。

点击查看代码
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
// using namespace  __gnu_pbds;
// tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tr;//从小到大
// int findnum(int k){auto it=tr.find_by_order(k-1);return ((it!=tr.end())?(*it):1e9+7);}//查元素
// int findrank(int x){return tr.order_of_key(x)+1;}//查排名
inline int read()
{
	int w = 1, s = 0; char ch = getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;
const int maxn=1e6+10;
const int inf=1e9+7;
int qw(int a, int b)
{
	int ans=1;a%=mod;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int n,m,H;
struct no
{
    int y,d;
};
vector<no> G[maxn];
bool vis[maxn];
void dfs1(int x)
{
    vis[x]=1;
    for(auto i : G[x])
    {
        int y=i.y,d=i.d;
        if(d==1||vis[y])continue;
        dfs1(y);
    }
}
void Sub1()
{
    int num=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs1(i);
            num++;
        }
    }
    cout<<qw(2,num);
    return ;
}
void Sub2(int D)
{
    if(H<=D)
    {
        cout<<qw(H+1,n);
        return ;
    }
    cout<<(qw(D+1,n)+(H-D)%mod)%mod;
    return ;
}
vector<int> GG[maxn];
int tot=0;
int cnt[3000][3000];
struct bi
{
    int x,y,v;
    inline friend bool operator < (bi x,bi y)
    {
        return x.v<y.v;
    }
};
vector<bi> mm;
int fa[maxn],d[maxn];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void dfs3(int x,int h,int d)
{
    cnt[h][x]=d;
    for(auto i : G[x])
    {
        int y=i.y,dd=i.d;
        if(dd>=h||cnt[h][y])continue;
        dfs3(y,h,d);
    }
}
int dp[maxn],c[2];
void dfs(int x,int fa)
{
    int t=0;
    dp[x]=1;
    for(auto y : GG[x])
    {
        if(y==fa)continue;
        c[++t]=y;
        dfs(y,x);
    }
    dp[x]=( ( d[x] - d[c[1]] ) + dp[c[1]] ) % mod
         *( ( d[x] - d[c[2]] ) + dp[c[2]] ) % mod;
}
void Sub3()
{
    int ans=0;tot=n;
    for(int i=1;i<=m+n;i++)fa[i]=i;
    for(auto i : mm)
    {
        int x=i.x,y=i.y,v=i.v;
        int fx=gf(x),fy=gf(y);
        if(fx==fy)continue;
        tot++; d[tot]=v;
        fa[fx]=fa[fy]=tot;
        GG[tot].push_back(fx);
        GG[tot].push_back(fy);
        GG[fx].push_back(tot);
        GG[fy].push_back(tot);
        dp[tot]=
        ( dp[fx] + ( d[tot] - d[fx] ) ) % mod
       *( dp[fy] + ( d[tot] - d[fy] ) ) % mod;
    }
    ans=(dp[tot]-d[tot])%mod;
    // dfs(tot,0);
    cout<<(ans+H)%mod;
}
signed main()
{
#ifdef Lydic
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    freopen("rain.in","r",stdin);
    freopen("rain.out","w",stdout);
#endif
    
    cin>>n>>m>>H;
    int Su2=0;bool f=1;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),v=read();
        if(i==1)Su2=v;
        else if(v!=Su2)f=0;
        G[x].push_back({y,v});
        G[y].push_back({x,v});
        mm.push_back({x,y,v});
    }
    if(H==1){Sub1();return 0;}
    if(f){Sub2(Su2);return 0;}
    sort(mm.begin(),mm.end());
    for(int i=1;i<=m+n;i++)dp[i]=1;
    Sub3();
    return 0;
}

T3

图上邻域区间修改区间查询。

暴力直接模拟。

题目说这是数据结构,但是我把所有数据结构扒出来也没有想到是什么。

就写了暴力分。

正解是一个很神奇的分块,设 \(S\) 把 \(R(i)\) 顺次拼起来得到的长度为 \(2m\) 的序列,那么问题简化为:

  • 给定 \([l,r]\),对于 \(i\in [l,r]\),令 \(w_{S_i}=w_{S_i}+v\)。
  • 给定 \([l,r]\),求出 \(\sum_{i\in [l,r]}w_{S_i}\)。

把序列 \(S\) 分块,考虑每种贡献。

  • 整块/散块对整块,预处理 \(f_{i,j}\) 表示第 \(i\) 个块与前 \(j\) 个位置的贡献,那么询问的时候枚举块 \(i\) 就能得到贡献。
  • 散块对散块,暴力修改。
  • 整块对散块,与第一种类似。

复杂度 \(\mathcal{O}((m+q)\sqrt m)\),需要离线做到线性空间。

T4

题目压根没懂,说的跟shi一样(好像不太好)。

题目看懂以后会一个10分DP部分分,但是是赛后。

CF3500的评分,做出来直接是红黑名阿伟。

正解是一个很复杂的二进制按位区间DP,能做到 \(\mathcal{O}(n^3m)\),但是根本不会。

标签:ch,return,int,2027,maxn,NOIP2024,节点,模拟,mod
From: https://www.cnblogs.com/Lydic/p/18376558

相关文章

  • [2027届]NOIP2024模拟赛#4
    比赛链接先看榜:倒数呜呜呜。T1最简单的一道题,但是我在看到T2以后就先鸽了,然后就一直鸽了……简单来想,每次询问只会改变两个数字,所以与处理之后直接和最后的数字一一对应后就可以做到正确的复杂度。T2就是这道题,卡了我3H……一开始看到的时候直接思路明确。但是规律找的......
  • [赛记] 暑假集训CSP提高模拟27
    最后一场了,还是写写吧;线性只因40pts赛时把与看成或了,最后才发现,结果我的神奇代码交上去得了40pts。。。从高位到低位依次考虑,若这一位是1的数大于m则统计并删除其它的数;否则直接跳过;点击查看代码#include<iostream>#include<cstdio>usingnamespacestd;intn,m;......
  • [赛记] 暑假集训CSP提高模拟26
    这场rank4,应该是暑假以来打的最好的一场了。。。其它时候就没进过前10。。。博弈30pts赛时$O(n^2)$暴力30pts;对于暴力,我们能发现一个性质就是只要有一类边权出现了奇数次,那么先手必胜,所以我们枚举每一个点对,开个数组统计一下即可;不要忘了离散化;对于正解,用到了一个东......
  • 【题解】Solution Set - NOIP2024集训Day14 CDQ分治
    【题解】SolutionSet-NOIP2024集训Day14CDQ分治https://www.becoder.com.cn/contest/5482「CF364E」EmptyRectangles*3000摆烂了。「SDOI2011」拦截导弹CDQ的例题,之前做过(现在试图自己再做出来。第二问只用在第一问里面记录每一次是从哪个\(j\)​转移过来的,以及......
  • 2024.8.23 模拟赛总结
    A.distStatement:给定一棵\(n(n\le10^6)\)个节点带边权的树,定义\(\mathrm{Min}(x,y)\)是\((x,y)\)路径上的边权最小值。求\(\max_{r=1}^n{\sum_{v\nei}\mathrm{Min}(r,v)}\)。Solution:经典套路题。首先注意到一条路径上的只有最小值才会产生贡献,于是对于......
  • WPF 模拟UWP原生窗口样式——亚克力|云母材质、自定义标题栏样式、原生DWM动画 (附我封
    先看一下最终效果,左图为使用亚克力材质并添加组合颜色的效果;右图为MicaAlt材质的效果。两者都自定义了标题栏并且最大限度地保留了DWM提供的原生窗口效果(最大化最小化、关闭出现的动画、窗口阴影、拖拽布局器等)。接下来把各部分的实现一个个拆开来讲讲。一、使用窗口材质特......
  • 移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——6.vector(模拟实现)
    1.存储结构namespacezone{ template<classT>//需要模板 classvector { public:private: iterator_start; iterator_finish; iterator_endofstorage;};}可见,vector内核是由三个指针实现的2.默认成员函数 2.1.构造函数1.初始化列......
  • YC327B [ 20240821 CQYC NOIP 模拟赛 T2 ] 括号串(bracket)
    题意给定\(S\in\{(,),?\}\)。定义深度为括号嵌套的子序列的最大长度除以\(2\)。求出将\(?\)替换为括号的所有括号串的深度之和,对\(998244353\)取模。\(n\le10^6\)。Sol考虑如何把每次贡献只计算一次。不难想到在括号的中心点计算。可以发现,若当前左右括号......
  • 【C/C++ 软件开发模拟面试 集】cmake 相关知识点模拟面试
    摘自:https://zhuanlan.zhihu.com/p/662623216第一轮:基础知识 1.1什么是CMake? 面试官: 请问你能简单描述一下CMake是什么,以及它通常用来做什么吗? 面试者: CMake是一个跨平台的自动化构建系统,主要用来管理软件构建的过程,它使用一个名为CMakeLists.txt的配置文件来指导编......
  • 幽默重开模拟器
    可以按照人口比例得出的概率预测下一次投胎会在哪个国家或地区。https://wwcl.lanzn.com/igaEE285u2jc密码:gzij居然是自己一个一个复制的国家人口数量代码:#include<iostream>#include<string>#include<vector>#include<random>#include<ctime>#include<cstdlib>typede......