首页 > 其他分享 >NOIP A层联测5

NOIP A层联测5

时间：2023-10-04 19:02:45浏览次数：41  
标签：bel NOIP int long MAXN 联测 theta include

T1 漂亮大厨(cook)

教主的魔法+高橋君=漂亮大厨。

先求出每次询问有多少个数小于等于 \(y\)，再统计答案。

区间加，区间查小于等于某个数个数，考虑分块，块内再维护一个有序序列。

区间加：散块直接加，暴力排序重构有序序列；整块打标记。

区间小于等于某个数个数：散块暴力累加；整块在有序序列中二分查找快速统计。

这一部分时间复杂度 \(O(q\sqrt n\log n)\)，有神秘做法可以做到 \(O(q\sqrt n)\)，但据说实用性不大。

这时问题变为给定若干个 \(n,m\)，求 \(\sum\limits_{i=0}^{m} \dbinom{n}{i}\)。为方便，记 \(C(n,m)=\dbinom{n}{m},S(n,m)=\sum\limits_{i=0}^{m} C(n,i)\)。

我们知道 \(C(n,m)=C(n-1,m-1)+C(n-1,m)\)，那么：

\[S(n,m)=C(n-1,0)+\sum\limits_{i=1}^{m} C(n-1,i-1)+C(n-1,i)=2S(n-1,m)-C(n-1,m) \]

变形得到：

\[S(n-1,m)=\dfrac{S(n,m)+C(n-1,m)}{2} \]

\[S(n+1,m)=2S(n,m)-C(n,m) \]

同时又有：

\[S(n,m-1)=S(n,m)-C(n,m) \]

\[S(n,m+1)=S(n,m)+C(n,m+1) \]

所以发现 \(n,m\) 可以 \(O(1)\) 加减 \(1\)，用莫队维护，初始时 \(S(0,0)=1\)，时间复杂度 \(O(q\sqrt W)\)，\(W\) 为值域，最大为 \(max_x\times q+max_{a_i}=10^7+5\times 10^5\)，数据过水，没超过 \(10^5\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN=1e5+10,MAX=1e7+5e5+10,MOD=998244353;
int n,m,a[MAXN],len,bel[MAXN],b[MAXN],e[MAXN],p[MAXN],add[MAXN],cnt;
namespace mo
{
    int t,N,len,bel[MAX],ANS[MAXN];
    long long P[MAX],inv[MAX],ans=1;
    struct node{int n,m,pos;}p[MAXN];
    inline bool cmp(node x,node y)
    {
        if(bel[x.n]!=bel[y.n]) return x.n<y.n;
        return (bel[x.n]&1)?x.m<y.m:x.m>y.m;
    }
    inline long long C(int n,int m)
    {
        if(n<m) return 0;
        return P[n]*inv[m]%MOD*inv[n-m]%MOD;
    }
    inline long long ksm(long long a,int b)
    {
        long long ans=1;
        while(b)
        {
            if(b&1) ans=ans*a%MOD;
            a=a*a%MOD,b>>=1;
        }
        return ans;
    }
    inline void work()
    {
        t=::cnt;
        for(register int i=1;i<=t;++i)
            N=max(N,p[i].n);
        len=N/sqrt(t);
        for(register int i=1;i<=N;++i) bel[i]=(i-1)/len+1;
        sort(p+1,p+t+1,cmp);
        P[0]=1;for(register int i=1;i<=N;++i) P[i]=P[i-1]*i%MOD;
        inv[N]=ksm(P[N],MOD-2);for(register int i=N-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;
        for(register int i=1,n=0,m=0;i<=t;++i)
        {
            while(n<p[i].n) ans=(ans*2-C(n,m))%MOD,++n;
            while(m>p[i].m) ans=(ans-C(n,m))%MOD,--m;
            while(n>p[i].n) ans=(ans+C(n-1,m))%MOD*499122177%MOD,--n;
            while(m<p[i].m) ans=(ans+C(n,m+1))%MOD,++m;
            ans=(ans+MOD)%MOD;ANS[p[i].pos]=ans;
        }
        for(register int i=1;i<=t;++i) cout<<ANS[i]<<'\n';
        return ;
    }
};
int main()
{
#ifdef ONLINE_JUDGE
    freopen("cook.in","r",stdin);
    freopen("cook.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n>>m;len=sqrt(n);
    for(register int i=1;i<=n;++i)
        cin>>a[i],p[i]=a[i],bel[i]=(i-1)/len+1;
    for(register int i=1;i<=bel[n];++i)
    {
        b[i]=(i-1)*len+1,e[i]=min(i*len,n);
        sort(p+b[i],p+e[i]+1);
    }
    while(m--)
    {
        int opt,l,r,x,y,k;cin>>opt>>l>>r;
        if(opt==1)
        {
            cin>>x;
            if(bel[l]==bel[r])
            {
                for(register int i=l;i<=r;++i) a[i]+=x;
                for(register int i=b[bel[l]];i<=e[bel[l]];++i) p[i]=a[i];
                sort(p+b[bel[l]],p+e[bel[l]]+1);continue;
            }
            for(register int i=l;i<=e[bel[l]];++i) a[i]+=x;
            for(register int i=b[bel[l]];i<=e[bel[l]];++i) p[i]=a[i];
            sort(p+b[bel[l]],p+e[bel[l]]+1);
            for(register int i=b[bel[r]];i<=r;++i) a[i]+=x;
            for(register int i=b[bel[r]];i<=e[bel[r]];++i) p[i]=a[i];
            sort(p+b[bel[r]],p+e[bel[r]]+1);
            for(register int i=bel[l]+1;i<bel[r];++i) add[i]+=x;
        }
        else
        {
            cin>>y>>k;int ans=0,ANS=0;
            if(bel[l]==bel[r])
            {
                for(register int i=l;i<=r;++i)
                    if(a[i]+add[bel[l]]<=y) ++ans;
            }
            else
            {
                for(register int i=l;i<=e[bel[l]];++i)
                    if(a[i]+add[bel[l]]<=y) ++ans;
                for(register int i=b[bel[r]];i<=r;++i)
                    if(a[i]+add[bel[r]]<=y) ++ans;
                for(register int i=bel[l]+1;i<bel[r];++i)
                    ans+=upper_bound(p+b[i],p+e[i]+1,y-add[i])-(p+b[i]);
            }
            ++cnt;mo::p[cnt]={ans,min(ans,k),cnt};
        }
    }
    mo::work();return 0;
}

考场想不到莫队求 \(S(n,m)\)，让我对莫队有更深理解了。

T2 吃树(eat)

我是\(\huge\text{常数大}\)师。

与题解做法不同。当联通块大小 \(k\) 确定，对于一个点 \(x\)，它每个儿子的子树中剩下未归到连通块中的点都将与 \(x\) 同属一个连通块。具体的，包含 \(x\) 的联通块大小一定大于等于 \(1+\sum\limits_{y\in son(x)} (siz_y \bmod k)\)，所以若存在一个 \(x\) 使这个数大于 \(k\) 则不合法。

则先 dfs 一遍，然后枚举 \(k,k\mid n\)，\(O(n)\) 判断是否合法。没必要递归写，会被卡常。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN=1e6+10;
int n,to[MAXN<<1],nxt[MAXN<<1],head[MAXN],cnt,siz[MAXN],fa[MAXN],ans;
inline void add(int x,int y)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt;return ;
}
void dfs(int x)
{
    siz[x]=1;
    for(register int i=head[x];i;i=nxt[i])
    {
        int y=to[i];if(y==fa[x]) continue;
        fa[y]=x,dfs(y);siz[x]+=siz[y];
    }
    return ;
}
int main()
{
#ifdef ONLINE_JUDGE
    freopen("eat.in","r",stdin);
    freopen("eat.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n;
    for(register int i=1;i<n;++i)
    {
        int x,y;cin>>x>>y;
        add(x,y),add(y,x);
    }
    dfs(1);
    for(register int k=1;k<=n;++k)
    {
        if(!(n%k))
        {
            for(register int x=1;x<=n;++x)
            {
                int sum=1;
                for(register int i=head[x];i;i=nxt[i])
                {
                    int y=to[i];if(y==fa[x]) continue;
                    sum+=siz[y]%k;
                }
                if(sum>k) break;
                if(x==n) ++ans;
            }
        }
    }
    cout<<ans<<'\n';return 0;
}

赛时写递归主要是担心 \(y\) 不合法那么 \(y\) 的子树中未归到连通块中的点不等于 \(siz_y\bmod k\)，所以每次重新 dfs 了，后来发现多此一举，只要存在一个不合法结果都是一样的。

T3 飞翔的胖鸟(fly)

whk 题，现学导数。一篇导数的博客。

求 \(\min\limits_{\theta\in (0,\frac{\Pi}{2}]} f(\theta)=\dfrac{ah}{\sin\theta} + b\theta\)。直接求导。

[图片来源(https://www.cnblogs.com/wanghai0666/p/11770162.html)]

\[f'(\theta)=b-\dfrac{ah \cos \theta}{\sin^2 \theta} \]

为避免精度问题设 \(x=\cos x\)，由 \(\sin^2 x+\cos ^2 x=1\)，将 \(\sin^2 x\) 替换为 \(1-x^2\)，则：

\[f'(x)=b-\dfrac{ahx}{1-x^2}=b-x^2b-ahx=bx^2+ahx-b \]

求极值，所以使 \(f'(x)=0\)。特判 \(b=0\)，解二元一次方程，\(\theta=\arccos x\)，将 \(\theta\) 带回函数求出答案。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;
const int MOD=19260817;
int typ,T,h,a,b,H,A,B;long long ans,P=1;
inline void Read(){
    long long x=1ll*h*H,y=1ll*a*A,z=1ll*b*B;
    h=(H^(y+z))%1000+1;
    a=(A^(x+z))%1000+1;
    b=(B^(x+y))%100000+1;
}
inline long double f(long double th){return (long double)a*h/sin(th)+b*th;}
int main()
{
#ifdef ONLINE_JUDGE
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>typ>>T;
    if(typ) cin>>h>>a>>b>>H>>A>>B;
    for(register int i=1;i<=T;++i)
    {
        if(!typ) cin>>h>>a>>b;
        else Read();P=P*11514%MOD;
        long long A=b,B=a*h,C=-b;
        double x=A?(sqrt(B*B-4*A*C)-B)/(A<<1):0;
        if(!typ) cout<<fixed<<setprecision(4)<<f(acos(x))<<'\n';
        else
        {
            long long now=floor(f(acos(x))*10000);
            ans+=now%MOD*P%MOD;
        }
    }
    if(typ) cout<<ans%MOD<<'\n';
    return 0;
}

不会导数是真的。

T4 漂亮轰炸(bomb)

没改完，先咕。

标签：bel,NOIP,int,long,MAXN,联测,theta,include
From： https://www.cnblogs.com/int-R/p/NOIP-A-5.html

相关文章

  • P1025 [NOIP2001 提高组] 数的划分 题解
    题目传送门本题共有两种方法，分别是递归深搜和动态规划方法一：递归深搜Solution从小到大一一枚举每一个划分的数，。只要找到一种方案就记录，具体细节代码中有注释。Code#include<bits/stdc++.h>usingnamespacestd;intn,k,ans;voiddfs(intstart,intstep,intsum){......
  • P1054 [NOIP2005 提高组] 等价表达式
    P1054[NOIP2005提高组]等价表达式这个题在计算表达式时可能会出现高次方，比如在某一数据中就出现了2^7^10也就是\(2^{70}\)自然溢出会寄，所以要取模自然溢出\(80\)分ullquick_pow(ullx,ullp){ ullres=1; while(p) { if(p&1)res*=x; p>>=1;......
  • NOIP2022 比赛
    Day\(2^2+3^2+4^2\)。HNOI2016序列的加强版。我去年怎么这么菜啊，虽然现在也是就是了。\[\sum\limits_{[l,r]\in[L,R]}\left(\max\limits_{i\in[l,r]}a_i\right)\left(\max\limits_{i\in[l,r]}b_i\right)\]考虑离线，对右端点\(r\)扫描线，对每个左端点\(l\)维护\(S_l=\le......
  • NOIP2023 国庆集训 A 组 Day7
    T1思路:因为只有三个串故枚举其中一个为调换的串，再枚举k验证即可。T2思路:正着不好做，考虑反着做。这样就不会覆盖之前的。赛时没想到这个常见套路，正难则反。T3事实上只有一种情况，故只需倒着枚举遇到a统计答案。使用一个变量sum来记录遇到下一个a的次数如果枚举到b,sum+=1。......
  • 【题解】洛谷 P1003 [NOIP2011 提高组] 铺地毯
    原题链接解题思路如果直接按照题意开一个二维数组来模拟每个点最上面的地毯编号，会发现所占空间最坏情况下约为(2*105)2*4B=4*1010*4B=1.6*1011B≈149GB，程序完全无法运行。但实际上没有必要将每一个点的信息记录下来，只需要记录每一块地毯能覆盖哪些点，再依次判断哪那些地毯可以......
  • 我个人今年csp/noip赛前复习列表：
    Part1、图论：1*、3种tarjan2、dij算法：暴力写法和heap优化3*、Prim算法：暴力与heap优化4、Floyd算法+矩阵5、直径求法（dp+dfs）与性质6、树的重心（dp求法）7*、差分约束系统建模方式8*、二分图相关问题9*、Dinic算法板子（骗分）10、基环树的一些常见写法（估计不会考）Part2、数据结构：......
  • P5015 [NOIP2018 普及组] 标题统计
    题目描述传送门凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。输入格式输入文件只有一行，一个字符串\(s\)。输出格式输出文件只有一行，包含一个整数，即作......
  • P3956 [NOIP2017 普及组] 棋盘
    传送门P3956[NOIP2017普及组]棋盘不清楚曾师为什么把这个神奇的题目放在搜索\(search\)专栏，反正我用\(dijkstra\)水过去了，虽然\(dijkstra\)严格来说也是一种能够解决一般性最短路问题的算法。然后考虑这道题的建图。这道题来看首先是去除魔法的部分，一般地，任意一个点只......
  • P1514 [NOIP2010 提高组] 引水入城
    link搜索。首先先用\(dfs\)判断一下对于每一个点来说对应的可以覆盖的\(L,R\).假设题目一定存在一个解，所以一定会有该点覆盖的区间连续。设该区间为\(L,R\)，若不是每一个点均会被覆盖，那么题目不会存在任何一个解。判断是否有解：跑一遍\(dfs\)，记录每一个点被\(dfs......
  • P1037 [NOIP2002 普及组] 产生数
    P1037[NOIP2002普及组]产生数解法1：利用floyd寻找每位数字可变化的点点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;strings;intd[20][20];intf[25];intnum[150];intmain(){ cin>>s; intn=s.length(); intq; ci......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99