首页 > 其他分享 >NOIP A层联测9 & CSP模拟52

NOIP A层联测9 & CSP模拟52

时间：2023-10-11 17:14:35浏览次数：39  
标签：NOIP int register 52 MAXN 联测 INF include dis

我的评价是三道傻逼题和一道牛逼题。

T4 上厕所时想了个奇怪东西打了一个半个小时 170 行结果剩 10 分钟发现假了，最后 \(k=1\) 都没来得及写就直接交了暴力。没想到 HZOJ 过了 50pts，喜了。但是 Accoders 上只过了 35pts，恼了。

T1 长春花

\(b^2\bmod p=(b\bmod p)^2\bmod p\)，所以可以先枚举 \(b\in [0,p-1]\) 求出所有可能的 \(b^2\bmod p\)。观察大样例发现 \(f(x)\) 不会很大，所以直接枚举 \(x\)，再从小到大枚举 \(a\)，每次检查 \((x-a^2)\bmod p\) 是否是可能的 \(b^2\bmod p\)，时间复杂度大概 \(O(p)\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
int p,ans;bool vis[MAXN];
int main()
{
#ifdef ONLINE_JUDGE
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>p;
    for(register long long b=0;b<p;++b) vis[b*b%p]=true;
    for(register int x=0;x<p;++x)
    {
        for(register long long a=0;a<p;++a)
        {
            ans=max(ans,(int)a);
            if(vis[(x-a*a%p+p)%p]) break;
        }
    }
    cout<<ans<<'\n';return 0;
}

T2 紫罗兰

枚举边，bfs 搜索包含这条边的最小环的个数（不是找最小环中包含这条边的个数，而是“包含这条边”作为前提条件，然后最小环的个数）。

就相当于去掉当前枚举的这条边，有多少条最短路径可以从 \(x\) 到 \(y\)。之后对于所有枚举的边中最小的“包含这条边的最小环”就是全局的最小环，统计一下即可。一个 \(x\) 元环在枚举边时每条边都计算了一次，所以要除以 \(x\)。时间复杂度 \(O(m(n+m))\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=3e3+10,MAXM=6e3+10,INF=1e9+7;
int n,m,to[MAXM<<1],nxt[MAXM<<1],head[MAXN],cnt;
int x[MAXM],y[MAXM],s,t,cur,dis[MAXN],d[MAXN],MIN=INF,ans[MAXN];
inline void add(int x,int y)
{
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt;return ;
}
inline void bfs()
{
    for(register int i=1;i<=n;++i) dis[i]=d[i]=0;
    dis[s]=d[s]=1;queue <int> q;q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();if(x==t||dis[x]>MIN) break;
        for(register int i=head[x];i;i=nxt[i])
        {
            if(i==cur*2-1||i==cur*2) continue;
            int y=to[i];
            if(!dis[y])
            {
                dis[y]=dis[x]+1,d[y]+=d[x];
                q.push(y);
            }
            else if(dis[y]==dis[x]+1) d[y]+=d[x];
        }
    }
    if(dis[t]) MIN=min(MIN,dis[t]),ans[dis[t]]+=d[t];return ;
}
int main()
{
#ifdef ONLINE_JUDGE
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n>>m;
    for(register int i=1;i<=m;++i)
        cin>>x[i]>>y[i],add(x[i],y[i]),add(y[i],x[i]);
    for(register int i=1;i<=m;++i)
        s=x[i],t=y[i],cur=i,bfs();
    for(register int i=3;i<=n;++i)
        if(ans[i]){cout<<ans[i]/i<<'\n';return 0;}
    cout<<"0\n";return 0;
}

T3 天竺葵

\(c_{i+1}>b_i\times c_i,b_i\geq 1\) 可知 \(c_{i+1}\times b_{i+1}>c_i\times b_i\)。

那么就可以直接借鉴最长上升子序列 \(O(n\log n)\) 的做法，维护出当前最长的子序列，每次在 \(c_j\times b_j\) 中找到第一个大于等于 \(a_i\) 的位置 \(k\)，判断一下若 \(a_i\) 小于 \(c_k\) 则将 \(c_k\gets a_i\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
int n,b[MAXN],tot;long long a[MAXN],f[MAXN];
int main()
{
#ifdef ONLINE_JUDGE
    freopen("C.in","r",stdin);
    freopen("C.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) cin>>a[i];
    for(register int i=1;i<=n;++i) cin>>b[i];
    for(register int i=1;i<=n;++i)
    {
        if(a[i]>f[tot]) ++tot,f[tot]=a[i]*b[tot];
        else
        {
            int k=lower_bound(f+1,f+1+tot,a[i])-f;
            if(a[i]*b[k]<f[k]) f[k]=a[i]*b[k];
        }
    }
    cout<<tot<<'\n';return 0;
}

T4 风信子

带修超级钢琴。

考虑用 \((l1,r1,l2,r2,x,y)\) 表示 \(\max\limits_{x\in[l1,r1],y\in[l2,r2]} a_x-a_y\)。发现当 \(l1=l2\leq r1=r2\) 或者 \(l1\leq r1<l2\leq r2\) 这两种情况比较好计算。\(x,y\) 是根据 \(l1,r1,l2,r2\) 确定的。

对于第一种情况用线段树维护，合并时答案为左儿子答案，右儿子答案，左儿子最大值减右儿子最小值，三者中的最大值，这是显然的，也是好维护的。第二种情况就是左区间最大值减右区间最小值，更容易了。

参考超级钢琴，我们使用一个堆来每次取出当前最优。处理完以后，我们要将剩下的部分分割成上面两种情况。

对于第一种情况，可以分割成：

\((l,x-1,l,x-1),(l,x-1,x,r),(x,x,x,x),(x,x,x+1,y-1),(x,x,y+1,r),(x+1,r,x+1,r)\)，这样考虑了所有情况，注意如果 \(x=y\) 就没有 \((x,x,x,x)\) 了，其他的注意一下使区间左端点不大于右端点就行。

对于第二种情况，可以分割成：

\((l1,x-1,l2,r2),(x,x,l2,y-1),(x,x,y+1,r2),(x+1,r1,l2,r2)\)，同样注意一下左端点不大于右端点。

这样每次可以快速求出当前最优，而 \(\sum k\leq 3\times 10^5\) 所以复杂度有保证，为 \(O(n\log n+(\sum k)(\log n+\log(\sum k)))\)。

线段树上要维护最大值，最小值，最大的 \(a_x-a_y\)，最大值的位置，最小值的位置，\(x\) 和 \(y\)。区间加就是最大值和最小值加，别的不变。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int MAXN=1e5+10,INF=1e9+7;
int n,m,a[MAXN];
namespace seg
{
    struct tree{int MAX,MIN,num,maxn,minn,ansx,ansy;}t[MAXN<<2];int add[MAXN<<2];
    inline void push_up(tree &p,tree ls,tree rs)
    {
        p.MAX=max(ls.MAX,rs.MAX);
        p.MIN=min(ls.MIN,rs.MIN);
        p.maxn=(ls.MAX>rs.MAX)?ls.maxn:rs.maxn;
        p.minn=(ls.MIN<rs.MIN)?ls.minn:rs.minn;
        p.num=max(max(ls.num,rs.num),ls.MAX-rs.MIN);
        if(p.num==ls.num) p.ansx=ls.ansx,p.ansy=ls.ansy;
        else if(p.num==rs.num) p.ansx=rs.ansx,p.ansy=rs.ansy;
        else p.ansx=ls.maxn,p.ansy=rs.minn;return ;
    }
    inline void build(int l,int r,int p)
    {
        if(l==r){t[p]={a[l],a[l],0,l,l,l,l};return ;}
        int mid=(l+r)>>1;
        build(l,mid,p<<1),build(mid+1,r,p<<1|1);
        push_up(t[p],t[p<<1],t[p<<1|1]);
        return ;
    }
    inline void spread(int p)
    {
        if(!add[p]) return ;
        t[p<<1].MAX+=add[p],t[p<<1|1].MAX+=add[p];
        t[p<<1].MIN+=add[p],t[p<<1|1].MIN+=add[p];
        add[p<<1]+=add[p],add[p<<1|1]+=add[p];
        add[p]=0;return ;
    }
    inline void change(int l,int r,int p,int x,int y,int z)
    {
        if(x<=l&&y>=r){t[p].MAX+=z,t[p].MIN+=z,add[p]+=z;return ;}
        int mid=(l+r)>>1;spread(p);
        if(x<=mid) change(l,mid,p<<1,x,y,z);
        if(y>mid) change(mid+1,r,p<<1|1,x,y,z);
        push_up(t[p],t[p<<1],t[p<<1|1]);return ;
    }
    inline tree query(int l,int r,int p,int x,int y)
    {
        if(x<=l&&y>=r) return t[p];
        int mid=(l+r)>>1;spread(p);
        tree a={-INF,INF,-INF},b={-INF,INF,-INF},ans;
        if(x<=mid) a=query(l,mid,p<<1,x,y);
        if(y>mid) b=query(mid+1,r,p<<1|1,x,y);
        push_up(ans,a,b);return ans;
    }
};
inline int A(int x,int l=1,int r=n,int p=1)
{
    if(l==r) return seg::t[p].MAX;
    int mid=(l+r)>>1;seg::spread(p);
    return (x<=mid)?A(x,l,mid,p<<1):A(x,mid+1,r,p<<1|1);
}
struct node
{
    int l1,r1,l2,r2,x,y;
    node(int l1,int r1,int l2,int r2):l1(l1),r1(r1),l2(l2),r2(r2)
    {
        if(l1==l2)
        {
            seg::tree P=seg::query(1,n,1,l1,r1);
            x=P.ansx,y=P.ansy;
        }
        else
        {
            seg::tree P1=seg::query(1,n,1,l1,r1);
            seg::tree P2=seg::query(1,n,1,l2,r2);
            x=P1.maxn,y=P2.minn;
        }
    };
    friend bool operator <(const node &x,const node &y){return A(x.x)-A(x.y)<A(y.x)-A(y.y);}
};
signed main()
{
#ifdef ONLINE_JUDGE
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
#endif
    cin>>n>>m;
    for(register int i=1;i<=n;++i) cin>>a[i];
    seg::build(1,n,1);
    while(m--)
    {
        int opt,l,r,x,ans=0;cin>>opt>>l>>r>>x;
        if(opt==1) seg::change(1,n,1,l,r,x);
        if(opt==2)
        {
            priority_queue <node> q;
            q.push(node(l,r,l,r));
            while(x--)
            {
                node P=q.top();q.pop();
                ans+=A(P.x)-A(P.y);
                if(P.l1==P.l2)
                {
                    int l=P.l1,r=P.r1,x=P.x,y=P.y;
                    if(l!=x) q.push(node(l,x-1,l,x-1));
                    if(l!=x) q.push(node(l,x-1,x,r));
                    if(x!=y) q.push(node(x,x,x,x));
                    if(x<y-1) q.push(node(x,x,x+1,y-1));
                    if(y!=r) q.push(node(x,x,y+1,r));
                    if(x!=r) q.push(node(x+1,r,x+1,r));
                }
                else
                {
                    int l1=P.l1,r1=P.r1,l2=P.l2,r2=P.r2,x=P.x,y=P.y;
                    if(l1!=x) q.push(node(l1,x-1,l2,r2));
                    if(l2!=y) q.push(node(x,x,l2,y-1));
                    if(y!=r2) q.push(node(x,x,y+1,r2));
                    if(x!=r1) q.push(node(x+1,r1,l2,r2));
                }
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

标签：NOIP,int,register,52,MAXN,联测,INF,include,dis
From： https://www.cnblogs.com/int-R/p/NOIP-A-9.html

相关文章

  • CSP/NOIP 2020,2021,2022
    CSP-S2020儒略历可以发现不管是缺的\(10\)天还是什么特殊规定，前面的天数都比较少，直接暴力模拟前头就行。可以直接暴力模拟\(3\times10^6\)天，然后接下来考虑如果要连着跳\(k\)天，首先如果\(k\le400\)就暴力跳\(k\)次，否则我们先跳若干步到\(1\)月\(1\)日。然后可......
  • CSP模拟50联测12 T2 赌神
    CSP模拟50联测12T2赌神题面与数据规模Ps:超链接为衡水中学OJ。思路\(subtask2\)：由于\(x_i\)较小，考虑dp。假设一开始球的颜色为红和蓝，设\(dp[i][j]\)为剩\(i\)个红球，\(j\)个蓝球时可获得的最大筹码数。如果不同球掉落所获得的筹码不同，那么肯定会掉落最少筹码的那一......
  • 正如ioi2023noip二十连游寄
    day1抽象场。T1是诈骗题，剩下三题都是撒币概率期望。赛事没有人过t3t4。毫无意义。T2想不到可以把相似的状态归在一起。从\(O(2^{3n})\)到\(O({\begin{pmatrix}n+m\\n\end{pmatrix}}^3)\)，很难想到。不过foi的时候甚至听说过拆分数复杂度的题。day2信心场。但是我没有信......
  • P1540 [NOIP2010 提高组] 机器翻译
    传送门题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；......
  • CSP模拟51联测13 B.狗
    CSP模拟51联测13B.狗目录CSP模拟51联测13B.狗题目大意题目描述输入格式输出格式样例样例1inputoutput思路题目大意题目描述小G养了很多狗。小G一共有\(n\timesn\)条狗，在一个矩阵上。小G想让狗狗交朋友，一条狗狗最多只能交一个朋友，不必所有狗狗都有朋友。但是狗狗交朋友......
  • [NOIP2011 提高组] 铺地毯
    题目描述为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有\(n\)张地毯，编号从\(1\)到\(n\)。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设......
  • LY1376 [ 20231008 NOIP 模拟赛 T0 ] 递增路径
    题意\(A\),\(B\)两人轮流在一张图上移动一个点。要求这次移动的边权必须大于上次的。\(A\)希望游戏进行的轮数多，\(B\)希望游戏进行的轮数少。对于每个\(s=1,2,...,n\)作为起点，若双方都采用最优策略，游戏会进行多少轮。Sol考虑将所有边按照从大到小的顺序排序。每......
  • NOIPTG联合权值
    P1351[NOIP2014提高组]联合权值我们对于每个点计算它的子结点的\(\sumw,\maxw\)。如图，发现贡献有三类：直接计算。需要剔除自己这个点，对于sum直接减去即可，对于max维护一个次大值，发现这个点是最大值用次大值代替。枚举子节点，然后直接利用子节点的\(\sum,\max\)信......
  • Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）
    EducationalCodeforcesRound152(Div.2)D.ArrayPainting//思路：双指针找连续正数段//若段中出现2，则更新两头的0的情况，若为涂色则改为true//若无2，则优先更新左侧0，若左0已经为true，则更新右侧0//数组开头结尾特判#defineintlonglong#defineldlongdoubleusingnam......
  • LY1380 [ 20231009 NOIP 模拟赛 T1 ] AK 神
    题意给定长度为\(n\)的序列\(S\)。\(A\)，\(B\)两人轮流取连续\(k\)个数，保证\(n\equiv1\pmodk\)。\(A\)使最终数字更小，\(B\)使最终数字更大。问取到数的和。Sol直接考虑每次选哪些数，怎么选显然是不好做的。不难发现\(n\equiv1\pmodk\)的条件。题面提示我们......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99