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

2024暑假集训测试16

时间：2024-07-31 20:39:40浏览次数：14  
标签：10 16 int void Tp 2024 inline 集训 define

前言

image

真是一次比一次唐了。

被莫反害惨了属于是（其实完全是自己唐吧），T1 狂推莫反不止，一直想着怎么处理 \(999\) 的限制，最后推出来了复杂度是 \(999\sqrt n\) 的，过不去，继续唐我的高级分块套分块做法，比赛快结束了才发现正因为那个限制所以我直接枚举就行了，丫的最后少了个取模还挂了4pts，所以又被签到题爆刷了？！？！？！

好像打得唐的这几次都是因为 T1 死的，今天喵喵进来讲了学长们考 NOI 的经历告诉我们 T1 不能影响比赛以及心态的问题，每次都说下次不能这么挂了结果下次接着挂。

结果就是打完 T1 去调 T4 平衡树没调出来打暴力了，T2 没看（其实也是个签到题），T3 直接输出 \(0\)。

T1 黑客

签到题，直接枚举 \(i+j\)，这个最多到 \(999\)，对于每个 \(i+j\) 枚举每一对 \(\gcd(i,j)=1\)，其贡献为 \((i+j)\times \min(\lfloor\dfrac{n}{i}\rfloor,\lfloor\dfrac{m}{j}\rfloor)\)。

最后分 \(4\) 块容斥即可，\(ans=calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=5e6+10,P=1e9+7;
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 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);}
ll a,b,c,d;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll solve(ll n,ll m)
{
    ll ans=0;
    for(ll i=1;i<=min(999ll,n+m);i++)
    {
        for(ll x=max(1ll,i-m);x<=min(n,i-1);x++)
        {
            ll y=i-x;
            if(gcd(x,y)!=1) continue;
            (ans+=i*min(n/x,m/y)%P)%=P;
        }
    }
    return ans;
}
signed main()
{
    read(a),read(b),read(c),read(d);
    write((solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1)+P+P)%P);
}

T2 密码技术

也是个签到题，发现两个结论：

  • 行和列之间互不影响。
  • 若 \(i,j\) 可换，\(j,k\) 可换，有 \(i,k\) 可换。

以上结论主要原因是题目保证元素不重复，都很显然。

所以直接并查集维护即可，每个块的贡献为 \(size!\)，行和列答案乘起来即可。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=55,P=998244353;
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 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);}
ll n,s,f[N],sz[N],ans=1,a[N][N],jc[N];
ll find(ll x) {return f[x]==x?x:f[x]=find(f[x]);}
void merge(ll x,ll y)
{
    x=find(x),y=find(y);
    if(x==y) return ;
    f[y]=x;
    sz[x]+=sz[y];
    sz[y]=0;
}
signed main()
{
    read(n),read(s);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            read(a[i][j]);
    jc[0]=1;
    for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,jc[i]=jc[i-1]*i%P;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            bool flag=0;
            for(int k=1;k<=n;k++) 
                if(a[i][k]+a[j][k]>s)
                {
                    flag=1;
                    break;
                }
            if(!flag) merge(i,j);
        }
    for(int i=1;i<=n;i++)
        if(sz[i]) (ans*=jc[sz[i]])%=P;
    for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            bool flag=0;
            for(int k=1;k<=n;k++) 
                if(a[k][i]+a[k][j]>s)
                {
                    flag=1;
                    break;
                }
            if(!flag) merge(i,j);
        }
    for(int i=1;i<=n;i++)
        if(sz[i]) (ans*=jc[sz[i]])%=P;
    write(ans);
}

T3 修水管

注：下面所说的修理指该处为最靠前的爆炸点，而轮数的定义也和题面不同，这里指修理了多少个点，也就是说最终论述可以不为 \(r\)。

对于修理点 \(i\)，则点 \(1\sim i-1\) 均需满足以下条件之一：

  • 被修理过。
  • 没有爆炸且再也不会爆炸。

那么若去修理点 \(i\)，对应有以下两种情况：

  • 从本轮往后爆炸一次，对应被修理过。
  • 后面轮中再也不会爆炸。

根据上面的定义只有此处修理了 \(i\) 论述才加一，设当前论述为 \(j\)，后面最多还有 \(r-j\) 次修理的机会，在这些机会中若此时 \(i\) 爆炸了且没有修便会贡献一次 \(d_i\)，故此时 \(i\) 必须修理；而在此之前的 \(j\) 轮中 \(i\) 不是最靠前的，他炸了也没有贡献且不计入轮数，由此上述结论是成立的。

故此设 \(f_{i,j}\) 表示前 \(i\) 个点进行了 \(j\) 轮的概率，有 DP 式子：

\[f_{i-1,j-1}\times (1-(1-p_i)^{r-j+1})+f_{i,j}=f_{i-1,j}\times (1-p_i)^{r-j} \]

分别对标两种情况，定义 \(g_i\) 为修理 \(i\) 的概率，有：

\[g_{i}=\sum\limits_{j=1}^{r}f_{i-1,j-1}\times (1-(1-p_i)^{r-j+1}) \]

直接对标情况一，最后统计期望：

\[ans=\sum\limits_{i=1}^ng_id_i \]

点击查看代码 
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=260,M=320;
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 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);}
int T,n,r;
double p[N],d[N],f[N][N],g[N],ans;
double qpow(double a,int b)
{
    double ans=1;
    for(;b;b>>=1)
    {
        if(b&1) ans*=a;
        a*=a;
    }
    return ans;
}
signed main()
{
    read(T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        ans=0;
        read(n),read(r);
        for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i],&d[i]);
        f[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=min(i,r);j++)
            {
                f[i][j]+=f[i-1][j]*qpow(1.0-p[i],r-j);
                if(j!=0) 
                    f[i][j]+=f[i-1][j-1]*(1.0-qpow(1.0-p[i],r-j+1));
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=min(i,r);j++)
                g[i]+=f[i-1][j-1]*(1.0-qpow(1-p[i],r-j+1));
        for(int i=1;i<=n;i++) ans+=g[i]*d[i];
        printf("%.10lf\n",ans);
    } 
}

T4 货物搬运

有分块和平衡树套平衡树两种做法，赛时平衡树没调出来，目前大家都写得分块，又好写又好理解，赛后改分块了。

分块 + deque。 这个做法真的巨简单，但赛时打出来的虽然都写的分块但都没有用 deque，不过没有卡掉，思路是一致的，被大家爆切。

对于一个区间 \([l,r]\)，即将 \(r\) 移到 \(l\) 的位置，其余均向后错一位，可以用分块很好的维护，两边的散块直接暴力重构，复杂度是 \(O(\sqrt n)\) 的，中间的整块即上一个块的末尾成为本块的开头，可以每个块开一个 deque 单次 \(O(1)\) 修改，复杂度也是 \(O(\sqrt n)\)。时空复杂度均为 \(O(n+m\sqrt n)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long 
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e5+10,M=320;
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 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);}
int n,m,t,a[N],b[N],pos[N],cnt[M][N],last,sta[N],top;
deque<int>q[M];
int L(int x) {return (x-1)*t+1;}
int R(int x) {return x*t;}
void change(int l,int r)
{
    int x=pos[l],y=pos[r],sy;
    l-=L(x),r-=L(y);
    if(x==y)
    {
        sta[++top]=q[x][r];
        for(int i=l+1;i<=r;i++) sta[++top]=q[x][i-1];
        for(int i=r;i>=l;i--) q[x][i]=sta[top--];
        return ;
    }
    sy=q[y-1][q[y-1].size()-1];
    for(int i=x+1;i<=y-1;i++) 
    {
        int s=q[i-1].back();
        q[i].push_front(s);
        cnt[i][s]++;
    }
    for(int i=x+1;i<=y-1;i++)
    {
        int s=q[i].back();
        q[i].pop_back();
        cnt[i][s]--;
    }
    cnt[x][q[y][r]]++,cnt[y][q[y][r]]--;
    cnt[x][q[x].back()]--,cnt[y][sy]++;
    sta[++top]=q[y][r];
    for(int i=l+1;i<=R(x)-L(x);i++) sta[++top]=q[x][i-1];
    for(int i=R(x)-L(x);i>=l;i--) q[x][i]=sta[top--];
    sta[++top]=sy; 
    for(int i=1;i<=r;i++) sta[++top]=q[y][i-1];
    for(int i=r;i>=0;i--) q[y][i]=sta[top--];
}
int ask(int l,int r,int k)
{
    int x=pos[l],y=pos[r],ans=0;
    l-=L(x),r-=L(y);
    if(x==y)
    {
        for(int i=l;i<=r;i++) 
            if(q[x][i]==k) ans++;
        return ans;
    }
    for(int i=l;i<=R(x)-L(x);i++)
        if(q[x][i]==k) ans++;
    for(int i=x+1;i<=y-1;i++) ans+=cnt[i][k];
    for(int i=0;i<=r;i++) 
        if(q[y][i]==k) ans++;
    return ans;
}
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    read(m);
    t=sqrt(n);
    for(int i=1;i<=n;i++) pos[i]=(i-1)/t+1;
    for(int i=1;i<=pos[n];i++)
        for(int j=L(i);j<=R(i);j++)
        {
            q[i].push_back(a[j]);
            cnt[i][a[j]]++;
        }
    for(int i=1,op,l,r,k;i<=m;i++)
    {
        read(op),read(l),read(r);
        l=(l+last-1)%n+1,r=(r+last-1)%n+1;
        if(l>r) swap(l,r);
        if(op==1) change(l,r);
        if(op==2)
        {
            read(k); k=(k+last-1)%n+1;
            last=ask(l,r,k);
            write(last),puts("");
        }
    }
}

总结

该思考以下怎么应对这个 “T1 综合症了”，首先若感觉 T1 很难先看看下面的题看是不是被 swap 了，如果是直接看下面题就好了，否则仔细想一想，尤其不要想复杂，时刻告诉自己 T1 不会太难，像今天狂推莫反的行为就应该给自己一个嘴巴子；其次若很长时间想不出来赶紧往下做，把这题忘掉，最起码把下面简单一点的题切掉或把部分分拿全，再回来想，通常这时候头脑稍微清醒一点会有新的思路，至少会跳出思维误区。最后尤其不要着急，T1 做不出来确实唐但不是致命的，因为 T1 不会耽误下面的题从而满盘皆输才是。

附录

这次 rk 前三没给发零食（不关我的事）

rk1 是外校六年级小孩哥直接 AK 了，膜拜。

标签：10,16,int,void,Tp,2024,inline,集训,define
From： https://www.cnblogs.com/Charlieljk/p/18335419

相关文章

  • 从嘉手札<2024-7-31>
    倪海夏短解《易经》1、知其不可奈何，而安之若命。心若有所往，何惧道阻且长。无能为力的时候人总是会讲顺其自然，来敷衍自己的不作为和怯懦，来掩盖路上的坎坷荆棘。可事实上真正的顺其自然是竭尽所能之后对结果不强求，凡事有胜败，若是一味追求结果往往会堕入功利的陷阱，尽其力而不能至者......
  • 暑假集训CSP提高模拟12
    T1这题千万不要认为是莫反题枚举质因子\(x,y\)，\(x,y<=998\),对答案的贡献为\(min(\lfloor{\frac{B}{x}}\rfloor,\lfloor{\frac{D}{y}}\rfloor)\)，再容斥一下即可MD最后答案要取模啊点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.t......
  • 代码随想录训练第三十天|01背包理论基础、01背包、LeetCode416.分割等和子集
    文章目录01背包理论基础01背包二维dp数组01背包一维dp数组(滚动数组)416.分割等和子集思路01背包理论基础背包问题的理论基础重中之重是01背包，一定要理解透！leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。所以我先通过纯01背......
  • 实训日记day16
    web服务安装与部署web基本概念和常识web服务为⽤户提供的⼀种在互联⽹上浏览信息的服务，Web服务是动态的、可交互的、跨平台的和图形化的。Web服务为⽤户提供各种互联⽹服务，这些服务包括信息浏览服务，以及各种交互式服务，包括聊天、购物、学习等等内容。......
  • 『模拟赛』暑假集训CSP提高模拟12
    Rank正常偏下发挥吧。A.黑客签到题。题目中的关键点是只有\(x\)和\(y\)的和在区间\(\left[0,999\right]\)内才合法，因此我们只枚举和在这个范围内的两个值，寻找约分前的值即可，复杂度为\(\mathcal{O(999^2)}\)。点击查看代码#include<bits/stdc++.h>#definefo(x,......
  • 【2024最新版】超详细Python+Pycharm安装保姆级教程，Python+Pycharm环境配置和使用指南
    本文将从Python解释器安装到Pycharm专业版安装和配置汉化等使用都进行了详细介绍，希望能够帮助到大家。Python解释器&Pycharm安装包&Pycharm破姐插件我都打包好了。这份完整版的Python安装包已经上传至CSDN官方，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费获取......
  • Educational Codeforces Round 168 (Rated for Div. 2) (4/6)
    比赛链接:https://codeforces.com/contest/1997solve:ABCD开头:终于能上青名了,本来以为还得打个两三场,看来这暑假必须上蓝名了,不过这一场说实话感觉运气成分大一点,先稳住青名,最近感觉有点懒惰了,欠了好几场补题,牛客多校还有好多场qwq,得努力了A.StrongPassword思路:......
  • 暑假集训CSP提高模拟12
    暑假集训CSP提高模拟12\(T1\)P171.黑客\(40pts\)将式子进行二维差分。考虑枚举\(\frac{i+j}{\gcd(i,j)}=t\)，并统计它能对答案产生的贡献。令\(\gcd(i,j)=1\)，这样的话才会不重不漏。推式子，有\(\begin{aligned}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\fr......
  • 暑假集训CSP提高模拟 ∫[0,6] (x^2)/6 dx
    \[\text{暑假集训CSP提高模拟}\int^{6}_{0}\frac{x^{2}}{6}dx\]A.黑客显然这个题里只有\(999\)放在复杂度里是有可能对的，要么是\(999^{2}\)要么是\(999^{2}\log999\)，显然应该是前者.考虑枚举全部的最简分数，然后乘上去，算的时候直接算当前分母/分子是最简分式的几倍（注意上......
  • H7-TOOL自制Flash读写保护算法系列，为STM32H7全系列芯片制作读写使能和解除算法，支持在
    说明：很多IC厂家仅发布了内部Flash算法文件，并没有提供读写保护算法文件，也就是选项字节算法文件，需要我们制作。实际上当前已经发布的TOOL版本，已经自制很多了。但是依然有些厂家还没自制，所以陆续开始为这些厂家提供读写保护支持。最近好几个网友咨询H7系列芯片保护支持，马不停蹄，已......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99