首页 > 其他分享 >2024暑假集训测试23

2024暑假集训测试23

时间：2024-08-12 21:28:27浏览次数：11  
标签：23 int void Tp 集训 2024 read inline mx

前言

image

T2 部分分给得特别足，\(60pts\)，而且他不可能剩下的数据全放菊花，所以得到了 \(76pts\)，但赛时想了很长时间正解，没有想出来，给后面题剩的时间不多，就都胡暴力了，\(T4\) 甚至忘了剪枝，剪完之后 \(20pts\to 60pts\) 没绷住。

说到这儿要吐槽一下 T4 数据水的离谱，什么高级复杂度的都放过去了（当然纯爆搜没放过去），在 CF 上第六个点就 T 了。

赛时有人 T2 的暴力菊花都卡不掉，但是没有 A，好多人造数据没卡掉，我不信邪啊，造了个万花筒（玫瑰花）数据给他卡了，jijidawang 甚至邀请 miaomiao 把这个加到数据里（鞭尸了属于是）。

hack 数据生成器 
#include<bits/stdc++.h>
using namespace std;
signed main()
{
    freopen("/dev/urandom","r",stdin);
    freopen("rand.out","w",stdout);
    srand(getchar()*getchar()*getchar()*time(0));
    puts("1");
    int n=10000,m=40000;
    printf("%d %d\n",n,m);
    for(int i=2;i<=n;i++)
    {
        int w=rand()%1000+1;
        printf("%d %d %d\n",1,i,w);
    }
    int t=0;
    for(int i=2;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            t++;
            int w=rand()%1000+1;
            printf("%d %d %d\n",i,j,w);
            if(t+n-1>=m) return 0;
        }
}

T1 数字三角形

签到题，从后往前处理，能往下铺就往下铺，否则就往左铺，当然反过来也一样，可以证明其一定恰好铺完所有位置且联通。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=510;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
	for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,a[N],ans[N][N];
void dfs(int pos,int sum,int x,int y)
{
	if(sum==0) return ;
	ans[x][y]=pos;
	if(!ans[x+1][y]&&x+1<=n) dfs(pos,sum-1,x+1,y);
	else dfs(pos,sum-1,x,y-1);
}
signed main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=n;i>=1;i--) dfs(a[i],a[i],i,i);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
			write(ans[i][j]),putchar(' ');
		puts("");
	}
}

T2 那一天她离我而去

  • 部分分 \(23pts\)：纯爆搜，能且只能过 \(n=m\) 的基环树数据。

  • 部分分 \(76pts\)：\(n=m\) 的按照上面处理，其他的枚举所有与 \(1\) 连边的点 \(x\) 并断开这条边跑最短路，答案为 \(dis_x+w(1,x)\)，若用 dijkstra 复杂度为 \(O(nm\log n)\)。（好像不特判 \(n=m\) 也是这个分？数据太水。）

  • 部分分 \(76pts\)：有人是这么干的，爆搜加剪枝。

  • 正解：

    会这个正解前需要先会一个同样甚至更暴力的算法，从与 \(1\) 相连的一个点 \(x\) 出发跑最短路，则答案为 \(\min\limits_{y\in son_1}\{dis_y+w(1,y)\}\)，枚举这个 \(x\)，跑完最短路后再枚举 \(y\)，复杂度为 \(O(nm\log n+n^2)\)。

    考虑这么做多个 \(n^2\) 十分唐氏，于是建了个超级汇点，将与 \(1\) 相连的点抽出一部分与 \(1\) 断开去连接 \(n+1\)， 边权和原来一致，那么 \(1\) 作为超级源点跑最短路，最后答案就是 \(dis_{n+1}\)。

    想到这里正解就差不多了，需要满足任意两个节点存在一次二者不同时连接 \(1\) 或 \(n+1\)，想到二进制拆分，将其赋予下标的值，那么任意两点用二进制表示定至少一位不同，那么对于第 \(i\) 位上为 \(1\) 的连接 \(1\)，剩下的连接 \(n+1\)，再跑最短路，做到了不重不漏。

    复杂度 \(O(m\log^2 n)\)。

    CuFeO4 有建最短路 dag 的单 \(\log\) 做法，但我不会 \(dag\)。

    以上复杂度均针对 dijkstra 且菊花图，至于最短路方面，由于没有卡 spfa，所以 spfa 实际更快。

    点击查看代码 
    #include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e4+10,M=8e4+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int T,n,m,cnt,ans,dis[N];
bool vis[N];
pair<int,int>pos[N];
int tot,head[N],to[M],nxt[M],w[M];
int last,_head[N],_to[M],_nxt[M],_w[M];
void add(int x,int y,int z)
{
    nxt[++tot]=head[x];
    to[tot]=y;
    w[tot]=z;
    head[x]=tot;
}
void spfa(int s)
{
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0,vis[s]=1,q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i],z=w[i];
            if(dis[y]>dis[x]+z)
            {
                dis[y]=dis[x]+z;
                if(!vis[y]) 
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
signed main()
{
    read(T);
    while(T--)
    {
        memset(head,0,sizeof(head));
        memset(nxt,0,sizeof(nxt));
        memset(to,0,sizeof(to));
        memset(w,0,sizeof(w));
        cnt=tot=0,ans=0x3f3f3f3f;
        read(n,m);
        for(int i=1,x,y,z;i<=m;i++)
        {
            read(x,y,z);
            if(x>y) swap(x,y);
            if(x==1) pos[++cnt]=make_pair(y,z);
            else add(x,y,z),add(y,x,z);
        }
        memcpy(_head,head,sizeof(head));
        memcpy(_nxt,nxt,sizeof(nxt));
        memcpy(_to,to,sizeof(to));
        memcpy(_w,w,sizeof(w));
        last=tot;
        for(int i=0;(1<<i)<=cnt;i++)
        {
            memcpy(head,_head,sizeof(head));
            memcpy(nxt,_nxt,sizeof(nxt));
            memcpy(to,_to,sizeof(to));
            memcpy(w,_w,sizeof(w));
            tot=last;
            for(int j=1;j<=cnt;j++)
            {
                if(j&(1<<i)) add(1,pos[j].first,pos[j].second);
                else add(pos[j].first,n+1,pos[j].second);
            }
            spfa(1);
            ans=min(ans,dis[n+1]);
        }
        write(ans>=0x3f3f3f3f?-1:ans),puts("");
    }
}

T3 哪一天她能重回我身边

貌似可做，但又不太会，先隔着。

T4 单调区间

  • 原题：Decinc Dividing。

  • 其中的 \(check\) 部分还能单独弄出一个原题：Two Merged Sequences。

  • 部分分 \(20pts\)：纯爆搜。

  • 部分分 \(60pts\)：加个剪枝。

  • 部分分 \(100pts\)：考虑存在单调性，双指针跑，赛时 Pursuing_OIer 是这么写的，直接过了，（CF 过不去）。

  • 正解：

    不同于官方题解的 \(O(n)\) 带常熟做法，这是一个带 \(\log\) 的做法，但由于跑不满且前者带常数，跑出来没怎么慢。

    在写正解之前我们需要一个复杂度更优秀的 \(check\)，前面的 \(check\) 都是爆搜加剪枝的，复杂度玄学可卡。

    这个 \(check\) 贺的官方题解了，是个 DP：

    首先给出一个十分别扭的定义：

    \(f_{i,0}\) 表示第 \(i\) 个元素在 递增 序列中时，递减 序列最后一个元素的 最大值；

    \(f_{i,1}\) 表示第 \(i\) 个元素在 递减 序列中时，递增 序列最后一个元素的 最小值。

    初始值有 \(f_{i,0}=0,f_{i,1}=n+1,f_{l,0}=n+1,f_{l,1}=0\)。

    枚举第 \(i-1\) 个元素在递增序列还是递减序列。然后尝试更新 \(f_{i,0||1}\)，是要 \(f_{r,0}\ne 0||f_{r,1}\ne n+1\) 就说明存在合法方案。

    还可以顺便处理出以 \(i\) 为左端点，其合法的最远右端点，根据其单调性，下面有用。

    check 
    void check(int x)
{
    if(mx[x]) return ;
    f[x][0]=n+1,f[x][1]=0;
    for(int i=x+1;i<=n;i++)
    {
        f[i][0]=0,f[i][1]=n+1;
        if(f[i-1][0]!=0)//a[i-1] 能在递增末尾
        {
            if(a[i]>a[i-1]) f[i][0]=max(f[i][0],f[i-1][0]);//a[i] 接在递增末尾
            if(a[i]<f[i-1][0]) f[i][1]=min(f[i][1],a[i-1]);//a[i] 接在递减末尾
        }
        if(f[i-1][1]!=n+1)//a[i-1] 能在递减末尾
        {
            if(a[i]<a[i-1]) f[i][1]=min(f[i][1],f[i-1][1]);//a[i] 接在递减末尾
            if(a[i]>f[i-1][1]) f[i][0]=max(f[i][0],a[i-1]);//a[i] 接在递增末尾
        }
        if(f[i][0]==0&&f[i][1]==n+1) {mx[x]=i-1; return ;}
    }
    mx[x]=n;//以 x 为左端点能到达最远的右端点
}

    然后根据决策单调性，显然有对于任何 \(i\) 有 \(mx_{i}\ge mx_{i-1}\)，那么对于一个区间 \([l,r]\)，若 \(mx_{l}=mx_{r}\)，则这一段区间的所有 \(mx_i\) 均为 \(mx_l\)，根据此考虑分治，若不相等则递归 \([l,mid],[mid,r]\)，这么做比递归 \([l,mid],[mid+1,r]\) 能少一个 \(check\)，推荐这么写。

    复杂度为 \(O(n\log n)\) 级别的，可以证明，但由于我的证明过程大差不差但不太可观，就不放出来了，懒就直说。

    点击查看代码 
    #include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=true;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x)
{if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x)
{if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,a[N],f[N][2],mx[N];
ll ans;
void check(int x)
{
    if(mx[x]) return ;
    f[x][0]=n+1,f[x][1]=0;
    for(int i=x+1;i<=n;i++)
    {
        f[i][0]=0,f[i][1]=n+1;
        if(f[i-1][0]!=0)
        {
            if(a[i]>a[i-1]) f[i][0]=max(f[i][0],f[i-1][0]);
            if(a[i]<f[i-1][0]) f[i][1]=min(f[i][1],a[i-1]);
        }
        if(f[i-1][1]!=n+1)
        {
            if(a[i]<a[i-1]) f[i][1]=min(f[i][1],f[i-1][1]);
            if(a[i]>f[i-1][1]) f[i][0]=max(f[i][0],a[i-1]);
        }
        if(f[i][0]==0&&f[i][1]==n+1) {mx[x]=i-1; return ;}
    }
    mx[x]=n;
}
void solve(int l,int r)
{
    if(l>=r-1) return ;
    if(mx[l]==mx[r]) for(int i=l;i<=r;i++) mx[i]=mx[l];
    else 
    {
        int mid=(l+r)>>1;
        check(mid);
        solve(l,mid),solve(mid,r);
    }
}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    check(1),check(n);
    solve(1,n);
    for(int i=1;i<=n;i++) ans+=mx[i]-i+1;
    write(ans);
}

总结

感觉……没啥可总结的，最近心情不是特别好但没有特别差，主要是因为今天打的还凑合，不然心态又要炸了。

除了 T4 忘了剪枝别的都挺好的，那个 T2、T3 正解看起来就不像我赛时能想出来的。

附录

  • 今天 T2、T3 选自往届模拟赛【失恋三部曲】（还有一个没放进来），然后昨天是七夕节，今天放这个题目有理由怀疑是故意的（反正不关我事）。

  • 关于 CF 把所有爬都 ban 了，现在交 CF 的题只能上 CF 交了（vjudge 都不行）。

  • 本来所今天没模拟赛的，到了晚上快放学了才把时间改了，以后不要这么做了谢谢（我没什么损失，但貌似好多人都准备今天改题呢），但明天确确实实没有模拟赛，课件都放了。

  • 每天中午起床来机房都和渡劫一样，又困又热离得还远还要抓紧时间不迟到。

  • 今天属于剪枝专场，优秀的剪枝可以给一个纯爆搜的同志加高达 \(84pts\)（我不提是谁）。

标签：23,int,void,Tp,集训,2024,read,inline,mx
From： https://www.cnblogs.com/Charlieljk/p/18355768

相关文章

  • 高级java每日一道面试题-2024年8月12日-设计模式篇-请列举出在JDK中几个常用的设计模
    如果有遗漏,评论区告诉我进行补充面试官:请列举出在JDK中几个常用的设计模式?我回答:在JavaDevelopmentKit(JDK)中，许多设计模式被广泛使用，以帮助实现软件的结构、行为和复用。下面是一些在JDK中常见的设计模式及其简要说明：工厂模式(FactoryPattern)JDK中的java......
  • caxa电子图板2023下载-caxa工艺图表2023中文版下载安装教程
    CAXA是由镇江数字技术研究所有限公司自主研发的中文版CAD/CAM/CNC软件,具有以下特点:软件安装包http://rj.heihuyingyuan.com1.界面简洁,操作流畅,完全支持中文环境。2.集二维绘图、三维建模、CAM加工、CNC编程于一体。3.支持常见CAD文件格式的导入导出。4.包含丰富......
  • BR软件-中文版下载adobe Bridge2023软件下载安装教程BR2023
    软件安装包http://rj.heihuyingyuan.com这里分享几则关于Blender这款3D动画软件的有趣小故事:1.Blender最初是一家动画工作室开发的内部工具,后来以开源方式公开。2.Blender的logo是一只橙色的猴子头骨,这是开发者Renderfarm的昵称。3.早期Blender的界面被用户吐......
  • 2024年新SCI顶刊算法红嘴蓝鹊优化器RBMO优化Transformer模型的多变量时间序列预测
    matlabR2024a以上一、数据集二、2024年新SCI顶刊算法红嘴蓝鹊优化器RBMO红嘴蓝鹊优化算法(Red-billedbluemagpieoptimizer,RBMO)是一种新型的元启发式算法（智能优化算法），灵感来源于红嘴蓝鹊的合作、高效的捕食行为。该成果由ShengweiFu等人于2024年5月发表在SCI顶......
  • 2024年“研究生科研素养提升”系列公益讲座在线测评答案
    2024年研究生科研素养提升个人答案。仅供参考，不少重复，建议全题搜索b站签到同学最早14号收到证书帮忙测评：190去掉文字3308去掉文字7156我的证书：（时长15h及以上＋通过在线测评＝自动发，不用等14号）答案如下：......
  • [题解 hduoj-7522] 2024HDU 暑假多校7 - cats 的最小生成树
    原题链接题意有一个有重边的无向图,每次找到它的最小生成树,并删除生成树的边,直到不存在最小生成树,问被每条边在第几次被删除.思路考虑用类似Kruskal算法,但是是遍历一遍所有边,同时处理出来所有的生成树.具体这样做:如Kruskal一样,把所有边按边权排序,......
  • 每日AI必读资讯 2024-08-12
    原文链接：https://blog.csdn.net/m0_46163918/article/details/14111374601黑匣子被打开了！能玩的Transformer可视化解释工具：TransformerExplainer佐治亚理工学院和IBM研究院开发一款基于web的开源交互式可视化工具「TransformerExplainer」，帮助非专业人士了解Transfor......
  • AutoCAD软件下载+安装+软件最新版2023中文版下载安装CAD2022
    纯净直装全版本（包含2023最新版）软件地址：rj.heihuyingyuan.comAutoCAD是美国Autodesk公司开发的一款computeraideddesign,即计算机辅助设计软件。它主要用于二维描绘和三维建模设计。AutoCAD的主要功能包括:1.二维绘图-可以绘制平面图形,进行几何构建和尺寸标注。......
  • AutoCAD Electrical2023 AutoCAD电气版软件下载安装-亲测可用
    AutoCADElectrical是Autodesk公司推出的一款专门用于电气工程设计的AutoCAD垂直解决方案。它在AutoCAD的CAD平台上,集成了强大的电气设计和智能化功能。纯净直装全版本（包含2023最新版）软件地址： http://321.pwAutoCADElectrical的主要功能包括:-电气符号库-内置完整......
  • 『模拟赛』暑假集训CSP提高模拟19
    Rank小挂，还好。A.数字三角形原[CF1517C]Fillomino2锣鼓Rmj炸了所以挂cf链接。签。倒叙考虑，优先向下，到底或者下面有数就向右，有正确性，复杂度\(\mathcal{O(n^2)}\)。水了篇题解，点点推荐rp++。点击查看代码#include<bits/stdc++.h>constintRatio=0;cons......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99