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

『模拟赛』CSP-S模拟2

时间：2024-09-07 19:35:30浏览次数：3  
标签：ch ll len right lx CSP 模拟 left

Rank

非常好数据，使我成为 Rank1（雾

image

数据换源后的

image

狂流——齐秦

北风在吹着清冷的街道
街灯在拉开长长的影子
走过的路 想过的事
仿佛越来越远越来越长
越来越多越难以抛开
多少平淡日子以来的夜晚
你曾是我渴望拥有的企盼
太多分手的记忆
仿佛越来越远越来越长
越来越多越难以抛开
没有人能挽回时间的狂流
没有人能誓言相许永不分离
是我的错
是你错过 喔...
没有人能挽回时间的狂流
没有人能了解聚散之间的定义
太多遗憾 太多伤感
留在心中 像一道狂流
没有人能挽回时间的狂流
没有人能誓言相许永不分离
是我的错
是你错过 喔...
没有人能挽回时间的狂流
没有人能了解聚散之间的定义
太多遗憾 太多伤感
留在心中 像一道狂流
多少平淡日子以来的夜晚
你曾是我渴望拥有的企盼
太多分手的记忆
仿佛越来越远越来越长
越难以抛开
没有人
没有人
没人了解
没人了解
没有人
没有人
没有人
没有人
北风在吹着冰冷的街道

A. 不相邻集合

签。

用 set 维护的，不仅跑得慢讲的时候还被 hack 了。

考虑正解，并查集维护，我们将当前状态下的序列中连续的数合并在一起，设全部集合为 \(T\)，大小分别为 \(s_i\)，则显然有 \(ans=\sum_{i\in T} \lceil {\frac{s_i}{2}} \rceil\)。从 \(1\) 到 \(n\) 遍历时遇到已经有过的元素直接跳过，否则标记并判断相邻元素是否出现过，是则合并二者。合并操作只要更新 \(fa\) 数组，然后先减去二者的贡献再加上合并后的贡献即可。

点击查看代码 
#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 fi first
#define se second
const int Ratio=0;
const int N=3e5+5;
const int mod=1e9+7;
const int inf=1e9;
int n,maxn,ans;
int a[N],fx[N<<1],siz[N<<1];
bool yz[N<<1];
namespace Wisadel
{
    int Wfind(int x)
    {
        if(x==fx[x]) return x;
        return fx[x]=Wfind(fx[x]);
    }
    short main()
    {
        // freopen(".in","r",stdin),freopen(".out","w",stdout);
        n=qr;
        fo(i,1,n) a[i]=qr;
        fo(i,1,500000) fx[i]=i,siz[i]=1;
        fo(i,1,n)
        {
            if(!yz[a[i]])
            {
                yz[a[i]]=1;
                ans++;
                if(yz[a[i]-1])
                {
                    int _=Wfind(a[i]),__=Wfind(a[i]-1);
                    if(_!=__)
                    {
                        fx[_]=__;
                        ans-=(siz[__]+1)/2+(siz[_]+1)/2;
                        siz[__]+=siz[_];
                        ans+=(siz[__]+1)/2;
                    }
                }
                if(yz[a[i]+1])
                {
                    int _=Wfind(a[i]),__=Wfind(a[i]+1);
                    if(_!=__)
                    {
                        fx[_]=__;
                        ans-=(siz[__]+1)/2+(siz[_]+1)/2;
                        siz[__]+=siz[_];
                        ans+=(siz[__]+1)/2;
                    }
                }
            }
            printf("%d ",ans);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 线段树

算是签，赛时思路跟正解压根不沾边，只有 20pts。

正解是记搜。一个显然的结论：长度相同的区间的子树标号和是有共性的，即若当前区间的编号为 \(x\)，则子树编号和都能写作 \(kx+b\) 的形式。那么就能得出做法：正常区间求和，到目标区间返回该区间对应的 \(kx+b\) 值，若未求过该长度的 \(k\) 与 \(b\) 就记搜搜一下就行。

点击查看代码 
#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 fi first
#define se second
const int Ratio=0;
const int N=3e5+5;
const int mod=1e9+7;
const int inf=1e9;
ll n,x,y;
unordered_map<ll,ll>k,b;
namespace Wisadel
{
    #define ls (rt<<1)
    #define rs (rt<<1|1)
    #define mid ((l+r)>>1)
    ll Wqk(ll len)
    {
        if(k.find(len)!=k.end()) return k[len];
        int mi=(len+1)>>1;
        return k[len]=(2*Wqk(mi)+2*Wqk(len-mi)+1)%mod;
    }
    ll Wqb(ll len)
    {
        if(b.find(len)!=b.end()) return b[len];
        int mi=(len+1)>>1;
        return b[len]=(Wqb(mi)+Wqb(len-mi)+Wqk(len-mi))%mod;
    }
    ll Wq(ll rt,ll l,ll r,ll x,ll y)
    {
        if(x<=l&&r<=y) return (rt%mod*Wqk(r-l+1)%mod+Wqb(r-l+1))%mod;
        ll res=0;
        if(x<=mid) res=Wq(ls,l,mid,x,y);
        if(y>mid) res=(res+Wq(rs,mid+1,r,x,y))%mod;
        return res;
    }
    short main()
    {
        // freopen(".in","r",stdin),freopen(".out","w",stdout);
        int T=qr;
        k[1]=1,b[1]=0;
        while(T--)
        {
            n=qr,x=qr,y=qr;
            printf("%lld\n",Wq(1,1,n,x,y));
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. 魔法师

神秘题，数据更神秘。

由于赛时被 T2 卡了太久，一眼看出这题不太可做，于是打了 \(n^2\) 的 30pts 暴力和 20pts 无删的部分分，然后翻了翻大样例，一看全是 \(0\)，也没咋细研究，就把剩下不会的部分全输出 \(0\)，然后喜提 25pts，由于数据出锅打的暴力分只有 15pts，结合一下就成为初代数据最高分。

然后改来改去最后也就拿了该有的暴力分，正解仙姑。

D. 园艺

一眼可做，再一眼不可做，再再一眼可做。

根据样例得出一个假结论：最优解在整个过程非边界处最多拐一次。然后 5min 写出了式子，10min 打出代码。过一会发现暴力 \(d_i=1\) 和上面结论对不上，在大样例的信心加持下选择了相信假结论，然后就过了。

设 \(dis_i\) 为 \(i\) 距起点的距离，\(sum_i\) 为起点到 \(i\) 的路径上的点的距离和。

设 \(t\) 为枚举的拐点，以 \(t\lt k\) 举例，则答案为：

\[sum_t+sum_n+2dis_t\left(n-k\right)+sum_1-sum_t+2\left(dis_t+dis_n\right)\left(t-1\right) \]

\(t\gt k\) 同理，换一下位置就行。

过了之后尝试证明了一下结论，发现如果存在：

\[2dis_{t_1}\left(n-k\right)>2dis_{t_2}\left(k-t_1\right)+\left(3dis_{t_2}+2dis_{t_1}\right)\left(n-t_2\right)+\left(dis_{t_1}+2dis_{t_2}\right)\left(t_1-1\right) \]

那么会出现拐两次比拐一次优的情况。但是一眼左边一小点右边一大坨，本能告诉我结论是正确的的，然后水水的数据也是这样的，于是过了。

下午 int_R 送来一组 hack 数据：

5 3
100000 10 100 1000000

又研究了一下，发现如果满足：

\[dis_{t_1}\left(2t_2-2k-t_1+1\right)>dis_{t_2}\left(2k+3n-3t_2-2\right) \]

即可卡掉，看着很复杂，其实手造还是很容易卡掉的。

错误的满分代码（真的很短） 
#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 fi first
#define se second
const int Ratio=0;
const int N=2e6+5;
const int mod=1e9+7;
const int inf=1e9;
int n,k;
ll d[N];
ll ans9223372036854775807,dis[N],sum[N];
namespace Wisadel
{
    short main()
    {
        // freopen("cut2.in","r",stdin),freopen(".out","w",stdout);
        n=qr,k=qr;
        fo(i,1,n-1) d[i]=qr;
        fu(i,k-1,1) dis[i]=dis[i+1]+d[i],sum[i]=sum[i+1]+dis[i];
        fo(i,k+1,n) dis[i]=dis[i-1]+d[i-1],sum[i]=sum[i-1]+dis[i];
        fu(i,k-1,1) ans=min(ans,sum[i]+sum[n]+(n-k)*2*dis[i]+sum[1]-sum[i]+2*(dis[i]+dis[n])*(i-1));
        fo(i,k+1,n) ans=min(ans,sum[i]+sum[1]+(k-1)*2*dis[i]+sum[n]-sum[i]+2*(dis[i]+dis[1])*(n-i));
        printf("%lld\n",ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

末

Rank 1拿得挺意外的。本来卡 T2 1.5h 觉得自己跟昨天一样又寄寄了，结果神秘数据直接给我错解全放过了，挺牛的。

那么也反映一个问题，数据强的话又能打多少分呢？所以能过的题不抓住还是挺伤的，比如 T2。

T4 说实话开始猜结论时预期就拿个 50pts 左右，过了大样例给我震惊了，一时间以为把正解按出来了，最后倒计时结束时看到两个绿勾还是很高兴的。

就把这次当做一次激励吧，激励我继续冲击 Rank1 的助推剂，也希望能在这最后纯粹的 OI 时光里留下点什么拼搏的回忆。

Upd on 数据换源后：T3 起码该拿的拿到了，虽然是 Rank2，但起码知道了自己没挂分不是吗？

还有 %%% GGrun。

完结撒花~

标签：ch,ll,len,right,lx,CSP,模拟,left
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18401820

相关文章

  • CSP vp 记录
    CSP-S2019JX注：使用了IOI赛制。赛时：\(100+70+64+0+0=234\)，目测上了JX1=。补题：\(100+100+100+0+100=400\)。T1分数变动：\(73\to64\to73\to73\to100\)。首先判定月份是否合法，若不合法则可以保留个位或者把十位变成\(1\)（\(73\)分寄因：未考虑后者情况）。如果合法......
  • [csp-s 模拟2] 线段树
    记搜是真叽霸快啊#include<bits/stdc++.h>#definelcs(rt<<1)#definercs(rt<<1|1)#defineaxer-l+1usingnamespacestd;usingll=longlong;constintmod=1e9+7;llT,n,x,y;map<ll,ll>k,b;voiddfs(lln){ if(k[n])return; lln1=ceil(1.0......
  • CSP模拟2
    A.不相邻集合考虑值域上连续的段，可以发现连续的长度为\(x\)的段的贡献必定为\(\lceil{\frac{x}{2}}\rceil\)考虑并查集维护值域连续的段的大小，每次询问求出全部连续段的\(\lceil{\frac{size}{2}}\rceil\)之和即为答案合并操作：在值域上加入\(x\)，尝试合并\(x-1\)与\(x+1......
  • 【程序分享 2】分子动力学模拟 + 数据处理程序
    ​【2】分子动力学模拟+数据处理程序viewSq程序：可视化分子动力学（VMD）模块+ 分析X射线和中子结构因子freud程序:用于原子模拟数据的高通量分析HBCalculator程序：通过VMD可计算分子动力学模拟中氢键密度和强度的一维和二维分布DensityCalculator程序（1D&2D......
  • 【CSP】 202209-2 何以包邮？
    试题编号：202209-2试题名称：何以包邮？时间限制：1.0s内存限制：512.0MB70分DFS解法：#include<bits/stdc++.h>//包含所有标准库#defineN1000//定义常量N为1000#definelllonglong//定义ll为longlong类型的别名usingnamespacestd;llans=0x3f3f......
  • 20240906 模拟赛总结
    期望：100+70+4=174实际：100+70+4=174T1梦熊13连测的原题，刚好前几天订正过。。也就给我狗运到了，，观察性质发现，如果两个点所在直线与坐标轴的夹角越接近\(45^{\circ}\)就越优，转化为找到横坐标差的绝对值和纵坐标差的绝对值的差的最小值的两个点，可以坐标轴旋转，不过可以用更方便......
  • CSP 模拟 28
    T1喜剧的迷人之处在于将\(a\)分解质因数，容易找到满足\(ab\)为平方数的最小\(b\)，然后需要让\(b\)乘上一个平方数后在\([L,R]\)中，二分找即可。T2镜中的野兽\[\begin{aligned}&f(x)=\sum\cdots\sum[\gcd=1,\text{lcm}=x]\\&g(x)=\sum\cdots\sum[\gcd\midx,\text{lcm......
  • CF1307（模拟赛记录）
    比赛页面偶然发现一道做过的G；C的罚时：没开longlong，谨记。然后一个小时没想出E……E题面：在一年成功的牛奶生产后，FarmerJohn奖励他的奶牛们它们最喜欢的美味的草。在田里有\(n\)个单位的排成一行的草，每个单位的草有甜味\(s_i\)。FarmerJohn有\(m\)头奶牛，每只都......
  • CSP-2024 第一次
    A分解\(a\)之后可以轻松找到最小的\(b\)满足\((a,b)\)是好的，而其他的\(b\)一定是最小的\(b\)的完全平方数倍。B暴力大战（为啥\(d^3(m)\)甚至\(d^4(m)\)能轻松过1e9啊，赛时以为\(d(m)=\Theta(\sqrtm)\)，\(d^3(m)=\Theta(m\sqrtm)\)就没敢写，只写了\(O(m\log......
  • 洛谷 P5658 [CSP-S2019] 括号树
    洛谷P5658[CSP-S2019]括号树题意给定一棵树，每个点有一个括号(或)。定义\(s_i\)表示根节点到\(i\)每个点的括号组成的序列。求每个\(s_i\)中合法括号子串的个数\(f_i\)。思路定义\(g_i\)表示\(s_i\)中以\(i\)结尾的合法括号子串的个数。有\(f_i=f_{fa_......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99