【HHHOJ】NOIP2018 模拟赛（二十四）解题报告

点此进入比赛

得分： \(100+60+100\)（挺好的，涨了一波\(Rating\)）

排名： \(Rank\ 1\)

\(Rating\)：\(+115\)

\(T1\)：【HHHOJ13】金（点此看题面）

原题： 【洛谷2152】[SDOI2009] SuperGCD

将这道题的题意一转化，其实就是给你两个数，让你判断这两个是否互质。

而\(x\)与\(y\)互质和\(gcd(x,y)=1\)是一个意思。

所以只要求出\(gcd(x,y)\)即可。

为了避免使用高精，我们可以写\(Python\)，代码如下：

def gcd(n,m):#定义函数，以供递归调用

    if m==0:

        return n#如果m=0，返回n

    else:

        return gcd(m,n%m)#否则返回gcd(m,n%m)

T=(int)(input())#读入数据组数

while T:

    st=input().split()#在一行里读入两个数

    n=(int)(st[0])#用n存储第一个数

    m=(int)(st[1])#用m存储第二个数

    if gcd(n,m)==1:

        print("Yes")#如果gcd(n,m)=1，输出Yes

    else:

        print("No")#否则输出No

    T-=1#将数据组数减1

\(T2\)：【HHHOJ14】斯诺（点此看题面）

这题刚看完真的是非常懵，因此写了个大力分类讨论，交上去得了\(60\)分。

但其实看完题解后这题还是很水的。

首先，有一个基本事实：革命的区间数量\(=\)总区间数量\(\frac {n(n+1)}2-\)不革命的区间数量。

而不革命的区间其实只有三种：\(0\)的数量大于区间一半、\(1\)的数量大于区间一半、\(2\)的数量大于区间一半。

我们可以考虑把大于区间一半的数看成\(1\)，小于一半的数看成\(-1\)，那么我们要求的就是值\(>0\)的区间个数。

如果用\(sum_i\)表示\(\sum_{x=1}^ia_x\)，则就是要求有多少个\(j\le i\)满足\(sum_i>sum_j\)。

于是我们可以开一个数组\(tot_i\)表示满足\(sum_x=i\)的\(x\)的数量。

那么我们要求的就是\(\sum_{i=-n}^{sum_x-1}tot_i\)，这显然可以用前缀和+树状数组维护（虽然\(O(nlogn)\)，但是由于树状数组常数巨小，所以某些奆老依然能卡过）。

不过，其实我们完全没必要这么麻烦。

可以发现，当你查询了\(tot_i\)之后，只会查询与其相邻的一位（\(tot_{i-1}\)或\(tot_{i+1}\)），因此直接\(O(1)\)更新即可。

这样一来，总复杂度就是\(O(n)\)的。

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define uint unsigned int

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define abs(x) ((x)<0?-(x):(x))

#define INF 1e9

#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))

#define ten(x) (((x)<<3)+((x)<<1))

#define N 5000000

using namespace std;

int n,a[N+5];LL ans;

class FIO

{

	private:

		#define Fsize 100000

		#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)

		#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))

		int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];

	public:

		FIO() {FinNow=FinEnd=Fin;}

		inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}

		inline void read_digit(int &x) {while(!isdigit(x=tc()));x&=15;}

		inline void write(LL x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}

		inline void end() {fwrite(Fout,1,FoutSize,stdout);}

}F;

class Class_Solver//求解

{

	private:

		LL tot[(N<<1)+5];

	public:

		inline LL Operate(int v)//操作

		{

			register LL sum=1;memset(tot,0,sizeof(tot));//注意清空

			for(register int i=tot[N]=1,x=N;i<=n;++i)

			{

				if(a[i]^v) sum-=tot[x]+tot[x-1],++tot[--x],ans-=sum,sum+=tot[x];//对于a[i]不等于v的情况，将x减1

				else ++tot[++x],ans-=sum,sum+=tot[x];//对于a[i]等于v的情况，将x加1

			}

		}

}Solver;

int main()

{

    register int i;

    for(F.read(n),i=1,ans=1LL*n*(n+1)>>1;i<=n;++i) F.read_digit(a[i]);//读入，初始化ans为n(n+1)/2

    Solver.Operate(0),Solver.Operate(1),Solver.Operate(2);//枚举大于区间一半的数的个数

    return F.write(ans),F.end(),0;

}

\(T3\)：【HHHOJ15】赤（点此看题面）

原题： 【CF739E】Gosha is hunting

做到这题真的感觉人品爆表了。

几周前学 \(WQS\)二分 时上网搜例题，第一个搜到的就是这题，没想到居然还会在模拟赛中出现！

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define uint unsigned int

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define abs(x) ((x)<0?-(x):(x))

#define INF 1e9

#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))

#define ten(x) (((x)<<3)+((x)<<1))

#define N 100000

#define eps 1e-12

using namespace std;

int n,A,B;double s1[N+5],s2[N+5];

class Class_WQS//WQS二分套WQS二分

{

    private:

        double C1,C2,f[N+5];int g1[N+5],g2[N+5];//用f[i]表示到第i只猫为止捕捉到的猫总数的最大期望值，并用g1[i]表示此时使用的干脆面个数，用g2[i]表示此时使用的豆干个数

        inline void check()//DP转移

        {

            for(register int i=1;i<=n;++i)

            {

                f[i]=f[i-1],g1[i]=g1[i-1],g2[i]=g2[i-1];//什么都不使用

                if(f[i-1]+(s1[i]-C1)-f[i]>eps) f[i]=f[i-1]+(s1[i]-C1),g1[i]=g1[i-1]+1,g2[i]=g2[i-1];//使用干脆面

                if(f[i-1]+(s2[i]-C2)-f[i]>eps) f[i]=f[i-1]+(s2[i]-C2),g1[i]=g1[i-1],g2[i]=g2[i-1]+1;//使用豆干

                if(f[i-1]+(s1[i]+s2[i]-C1-C2-s1[i]*s2[i])-f[i]>eps) f[i]=f[i-1]+(s1[i]+s2[i]-C1-C2-s1[i]*s2[i]),g1[i]=g1[i-1]+1,g2[i]=g2[i-1]+1;//同时使用干脆面和豆干

 			}

 		}

 		inline void GetRes()//第二层二分，二分C2

 		{

            register double l=0.0,r=1.0;

            for(C2=(l+r)/2;r-l>eps;C2=(l+r)/2)

            {

                if(check(),!(g2[n]^B)) return;//找到符合条件的C2，就可以return了

                g2[n]>B?l=C2:r=C2;//如果选得物品数量偏多，将l更新为C2，否则将r更新为C2

            }

        }

    public:

        inline double GetAns()//第一层二分，二分C1

        {

            register double l=0.0,r=1.0;

            for(C1=(l+r)/2;r-l>eps;C1=(l+r)/2)

            {

                if(GetRes(),!(g1[n]^A)) break;//找到符合条件的C1，就可以break了

                g1[n]>A?l=C1:r=C1;//如果选得物品数量偏多，将l更新为C1，否则将r更新为C1

            }

            return f[n]+A*C1+B*C2;//返回答案

        }

}WQS;

int main()

{

    register int i;

	scanf("%d%d%d",&n,&A,&B);

    for(i=1;i<=n;++i) scanf("%lf",&s1[i]);

    for(i=1;i<=n;++i) scanf("%lf",&s2[i]);

    return printf("%.10lf\n",WQS.GetAns()),0;

}

巴特西

【HHHOJ】NOIP2018 模拟赛（二十四）解题报告

\(T1\)：【HHHOJ13】金（点此看题面）

\(T2\)：【HHHOJ14】斯诺（点此看题面）

\(T3\)：【HHHOJ15】赤（点此看题面）

最新文章

热门文章

巴特西

【HHHOJ】NOIP2018 模拟赛（二十四） 解题报告

\(T1\)：【HHHOJ13】金（点此看题面）

\(T2\)：【HHHOJ14】斯诺（点此看题面）

\(T3\)：【HHHOJ15】赤（点此看题面）

最新文章

热门文章

【HHHOJ】NOIP2018 模拟赛（二十四）解题报告