首页 > 其他分享 >Noip优质模拟赛口胡题解

Noip优质模拟赛口胡题解

时间：2023-07-16 16:56:01浏览次数：46  
标签：连边 Noip int 题解 long 赛口 include dp

HDU 5719

题意概括：

第一行输入t表示输入数据,每组数据第一行n，表示对1—n进行排序。接下来输入n个数b[n]表示排列中第i个数之前的最小值为b[i]。第三行n个数c[n]，表示排列中第i个数之前的最大值为c[i]。

解题思路：

递推,排除掉6种不可能的情况,1、b[i]>b[i-1] 2、c[i]<c[i-1] 3、b[i]>c[i] 4、c[1]!=b[1] 5、b[i],c[i] < 1 || > n 6、c[i]>c[i-1] &&b[i]<b[i-1]两个条件同时满足时。然后递推,如果当前产生的新的 b[i]或者 c[i] 那么dp[i] = dp[i-1] ，如果当前 b[i-1] = b[i] && c[i-1] = c[i] ，那么我们可以在 [b[i],c[i]]中任选一个数,但是由于谷堆是互不相同的,所以每次我们的选项都会变少,弄个计数器计算一下当前已经选了多少种,减掉之后答案即为 dp[i] = dp[i-1]*(c[i]-b[i]+1-num)

官方题解：

 具体实现

考虑使用数组存储（当然直接用一个ans从头到尾递推也是可以的）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353;
typedef long long LL;
typedef unsigned long long ULL;
int b[N],c[N],n;
LL dp[N];
int main()
{
    //freopen("perm.in","r",stdin);
    //freopen("perm.out","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        int flag=1;
        cin>>n;
        cin>>b[1];
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&b[i]);
            if(b[i]>b[i-1]||b[i]<1||b[i]>n)
                flag=0;
        }
        cin>>c[1];
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&c[i]);
            if(c[i]<c[i-1]||c[i]<1||c[i]>n||c[i]<b[i])
                flag=0;
            if(c[i]>c[i-1]&&b[i]<b[i-1])
                flag=0;
        }
        if(b[1]!=c[1])
            flag=0;
        if(flag==0)
        {
            cout<<0<<endl;
            continue;
        }
        else
        {
            
            int num=1;
            dp[1]=1;
            for(int i=2;i<=n;i++)
            {
                if(b[i]==b[i-1]&&c[i]==c[i-1])
                    dp[i]=dp[i-1]*(c[i]-b[i]+1-num)%mod;
                else if((b[i]==b[i-1]&&c[i]>c[i-1])||(b[i]<b[i-1]&&c[i]==c[i-1]))
                    dp[i]=dp[i-1];
                num++;
            }
            printf("%lld\n",dp[n]);
        }
    }
    return 0;
}

 

HDU 5807

解题思路

直接枚举当前三个人的状态以及下一步状态时间复杂度O(n^6)，考虑优化，本来是三个人同时走向下一个城市，现在给这三个同步的操作定一个顺序，那么每个合法任务应该是007,008,009,007,008,009,……,007,008,009
dp[i][j][k][0]表示当前三人分别在i,j,k城市，且下一步该i走的方法数；
dp[i][j][k][1]表示当前三人分别在i,j,k城市，且下一步该j走的方法数；
dp[i][j][k][2]表示当前三人分别在i,j,k城市，且下一步该k走的方法数；
那么dp[i][j][k][0]的后继状态就是dp[ii][j][k][1]（ii为i的出边对应的另一端点），dp[i][j][k][1]的后继状态就是dp[i][jj][k][2]（jj为j的出边对应的另一端点），dp[i][j][k][2]的后继状态就是dp[i][j][kk][0]（kk为k的出边对应的另一端点）,进而我们就可以由dp[0]->dp[1]，dp[1]->dp[2]，dp[2]->dp[0]得到所有状态的方法数，初始化的时候如果i,j,k满足条件则令dp[i][j][k][0]=1，否则令dp[i][j][k]=0，注意最后由dp[2]->dp[0]的时候需要判断这个dp[i][j][k][0]是否满足条件，求出dp数组后对于每次查询，如果三个特工初始位置是a,b,c的话，那么答案就是dp[a][b][c][0]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=55,mod=998244353;
int T,n,m,K,q,w[N];
ll dp[N][N][N][5];
vector<int>G[N];
void dfs()
{
    for(int i=n;i>=1;--i)
     for(int j=n;j>=1;--j)
      for(int k=n;k>=1;--k)
            {
                dp[i][j][k][0]=1;
                for(auto x:G[i]) dp[i][j][k][0]=(dp[x][j][k][2]+dp[i][j][k][0])%mod;
                for(auto x:G[j]) dp[i][j][k][1]=(dp[i][x][k][0]+dp[i][j][k][1])%mod;
                for(auto x:G[k]) dp[i][j][k][2]=(dp[i][j][x][1]+dp[i][j][k][2])%mod;
                if(abs(w[i]-w[j])>K||abs(w[i]-w[k])>K||abs(w[k]-w[j])>K) 
                    dp[i][j][k][0]=0;
            }
}
int main()
{
    //freopen("task.in","r",stdin);
    //freopen("task.out","w",stdout);
    cin>>T;
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&K,&q);
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        for(int i=0;i<N;i++)
            G[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
        }
        memset(dp,0,sizeof(dp));
        dfs();
        for(int i=1;i<=q;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            printf("%lld\n",dp[a][b][c][0]);
        }
    }
    return 0;
}

HDU 5597

证明

 证明出自Sept

链接 2023.07.16 高质量 NOIP 模拟赛题解 - CSP_Sept - 博客园 (cnblogs.com)

#include<bits/stdc++.h>
using namespace std;
#define ll __int64
int main()
{
    ll n, x;
    while(~scanf("%I64d%I64d", &n, &x))
    {
        x = n+x+1;
        ll ans=x;
        for(ll i=2; i*i<=x; i++)
        {
            if(x%i==0) 
            {
                ans=ans/i*(i-1);
                while(x%i==0) x/=i;
            }
        }
        if(x>1) ans=ans/x*(x-1);
        printf("%I64d\n", ans);
    }
    return 0;
}

HDU 5669

解题思路：

分析：（官方题解）

首先考虑暴力,显然可以直接每次O(n^2)

​的连边,最后跑一次分层图最短路就行了.

然后我们考虑优化一下这个连边的过程 ,因为都是区间上的操作,所以能够很明显的想到利用线段树来维护整个图,

连边时候找到对应区间,把线段树的节点之间连边.这样可以大大缩减边的规模,然后再跑分层图最短路就可以了.

但是这样建图,每一次加边都要在O(logn)个线段树节点上加边,虽然跑的非常快,但是复杂度仍然是不科学的.

为了解决边的规模的问题,开两棵线段树,连边时候可以新建一个中间节点,在对应区间的节点和中间节点之间连边

进一步缩减了边的规模,强行下降一个数量级

最后跑一下分层图最短路就行了

复杂度O(mlog^2n)

什么你会线段树但是不会分层图最短路?安利JLOI2011飞行路线.

因为边的数目还是相对比较多的,所以不能使用SPFA,而要使用Heap-Dijkstra来做最短路,

但是不排除某些厉害的选手有特殊的SPFA姿势可以做或者普通 SPFA写的比较优美就不小心跑过去了...

 

注：出题人的题解写的很详细了，然后JLOI2011飞行路线是BZOJ2763 直接去做就好了

      然后我的建图刚开始不太完善，跑了600+ms，然后后来完善了一下，按线段树节点建图（这就是题解）

     不过每个线段树的节点不需要和它的区域内所有的点连边，只需要按照线段树的结构，连它的左右儿子就行了

#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <string>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef pair<int,int>pii;
typedef long long LL;
const int N=6e5+5;
const int mod=1e9+7;
int n,m,s,k,t,cnt,idl[N<<1],idr[N<<1];
bool vis[N][11];
LL d[N][11];
vector<pii>edg[N];
void buildl(int rt,int l,int r)
{
    idl[rt]=++cnt;
    if(l==r)return ;
    int m=l+r>>1;
    buildl(rt<<1,l,m);
    buildl(rt<<1|1,m+1,r);
    edg[idl[rt<<1]].push_back(make_pair(idl[rt],0));
    edg[idl[rt<<1|1]].push_back(make_pair(idl[rt],0));
}
void buildr(int rt,int l,int r)
{
    idr[rt]=++cnt;
    if(l==r)return ;
    int m=l+r>>1;
    buildr(rt<<1,l,m);
    buildr(rt<<1|1,m+1,r);
    edg[idr[rt]].push_back(make_pair(idr[rt<<1],0));
    edg[idr[rt]].push_back(make_pair(idr[rt<<1|1],0));
}
void pre(int rt,int l,int r)
{
    if(l==r)
    {
        edg[l].push_back(make_pair(idl[rt],0));
        edg[idr[rt]].push_back(make_pair(l,0));
        return;
    }
    int m=l+r>>1;
    pre(rt<<1,l,m);
    pre(rt<<1|1,m+1,r);
}
void addl(int rt,int l,int r,int L,int R,int w){
    if(L<=l&&r<=R){
        edg[idl[rt]].push_back(make_pair(cnt,w));
        return;
    }
    int mid=(l+r)/2;
    if(L<=mid)addl(rt*2,l,mid,L,R,w);
    if(R>mid)addl(rt*2+1,mid+1,r,L,R,w);
}
void addr(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        edg[cnt].push_back(make_pair(idr[rt],0));
        return;
    }
    int mid=(l+r)/2;
    if(L<=mid)addr(rt*2,l,mid,L,R);
    if(R>mid)addr(rt*2+1,mid+1,r,L,R);
}
struct man{
    int v;
    int c;
    LL w;
    bool operator<(const man &e)const{
        return w>e.w;
    }
};
priority_queue<man>q;
void dij(int s){
    memset(d,-1,sizeof d);memset(vis,0,sizeof vis);
    d[s][0]=0;
    q.push(man{s,0,0});
    while(!q.empty()){
        int u=q.top().v,c=q.top().c;q.pop();
        if(vis[u][c])continue;
        vis[u][c]=1;
        for(int i=0;i<edg[u].size();++i){
            int v=edg[u][i].first,w=edg[u][i].second;
            if(!vis[v][c]&&(d[v][c]==-1||d[v][c]>d[u][c]+w)){
                d[v][c]=d[u][c]+w;
                q.push(man{v,c,d[v][c]});
            }
            if(c<k){
                if(!vis[v][c+1]&&(d[v][c+1]==-1||d[v][c+1]>d[u][c])){
                    d[v][c+1]=d[u][c];
                    q.push(man{v,c+1,d[v][c+1]});
                }
            }
        }
    }
}
int main()
{
    int x,y,w,l,r;
    int T;
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<N;i++)edg[i].clear();
        scanf("%d%d%d",&n,&m,&k);
        cnt=n;
        buildl(1,1,n);
        buildr(1,1,n);
        pre(1,1,n);
        while(m--)
        {
            ++cnt;
            scanf("%d%d%d%d%d",&x,&y,&l,&r,&w);
            addl(1,1,n,x,y,w);
            addr(1,1,n,l,r);
            cnt++;           //此处要注意
            addl(1,1,n,l,r,w);
            addr(1,1,n,x,y);
        }
        dij(1);
        LL ans=1000000000000;
        for(int i=0;i<=k;i++)ans=min(ans,d[n][i]);
        if(ans!=-1)printf("%lld\n",ans);
        else puts("CreationAugust is a sb!");
    }
    return 0;
}

 

标签：连边,Noip,int,题解,long,赛口,include,dp
From： https://www.cnblogs.com/mingloch/p/17558074.html

相关文章

  • 2023.07.16 高质量 NOIP 模拟赛题解
    HDU5719Arrange【模拟】给定数列\(B_n,C_n\)，求出满足\[B_i=\min_{j=1}^i\{A_j\},\quadC_i=\max_{j=1}^i\{A_j\}\]的排列\(A\)的数量。维护每个位置可能的数字数量，然后乘法原理即可。代码：http://acm.hdu.edu.cn/viewcode.php?rid=38654445。HDU5807KeepInTouch......
  • HHHOJ #1247. 「NOIP 2023 模拟赛 20230715 A」1 题解--zhengjun
    法老找来的题，说是找了三道其他模拟赛的T4拼成T1~T3，另外搞了道T4。思维好题，但是放在T1有点搞心态，但是还好大样例够强，400没挂。然而T3大样例输出错了，浪费了我0.5h，差评。首先发现向左走之后向右走是一定不优的，所以最短路的情况只能先向右再向左。考虑枚举起点\(s......
  • 题解 P2839【[国家集训队] middle】
    Problem一个长度为\(n\)的序列\(a\)，设其排过序之后为\(b\)，其中位数定义为\(b_{n/2}\)，其中\(a,b\)从\(0\)开始标号，除法下取整。给你一个长度为\(n\)的序列\(s\)。回答\(Q\)个这样的询问：\(s\)的左端点在\([a,b]\)之间，右端点在\([c,d]\)之间的子区间中，最大的中......
  • 你省（福建）省队集训 Day5 T1 题解
    简要题意有两个正整数\(a<b\le10^9\)，给出\(\dfrac{a}{b}\)的小数点后\(19\)位，要求还原\(a,b\)，保证有解。solution一个科技：\(\texttt{Stern-Brocottree}(SBT)\)，可以参考这个博客学习。先给出\(O(n)\)找的代码：......
  • 云斗杯 T2 派蒙是最好的伙伴！ 题解
    云斗杯T2题解赛时脑抽了只打了60pts暴力xwx。题目描述给定两个长度为\(n\)的\(01\)序列\({a_n}\)和\({b_n}\)，与另一个矩阵\({c_{n,n}}\)。矩阵\({c_{n,n}}\)的生成规则如下：\[c_{i,j}=a_i\timesb_j\]现给定一个数\(k\)，求在矩阵\(c_{n,n}\)内，有多少个......
  • freee Programming Contest 2023（AtCoder Beginner Contest 310）题解
    点我看题A-OrderSomethingElse直接比较\(P\)和\(Q+min(D_i)\)，输出较小值即可。点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#defi......
  • AJAX请求，响应头有set-cookie但浏览器不能写入cookie问题解决！
    开幕雷击：AJAX就不是干这个ajax只有向服务器发送请求时带上cookie的功能可选。不存在ajax向服务器get的时候带回来cookie的功能。解决把AJAX代码改成原始的js代码来完成需求：正确的jsdocument.addEventListener('DOMContentLoaded',function(){document.querySelector('......
  • CF339 题解
    CF339题解这套题虽然是div2，但是具有一定的价值，这套题作为典型的div2题目，全套5道题都几乎用暴力方法解决，但是为什么这样是对的？令人深思。A红题，把个位数提出来再排序就好了。#include<bits/stdc++.h>usingnamespacestd;constintN=105;chars[N];intn,num[N],tot=0......
  • P1891 疯狂 LCM 题解
    一、题目描述：$T$ 组数据，每组数据给定$n$，求$\sum_{i=1}^{n}lcm(i,n)$数据范围：$1\leT\le3\times10^5，1\len\le1\times10^6$。 二、解题思路：个人觉得思维难度不大，只是要记住一个结论：$\sum_{d\midn}d=\frac{\varphi(n)\timesn}{2}$这个公式对......
  • VMware17无法连接USB设备的问题解决方案
    前言【前言都是废话，可以直接看解决方案】事情是这样的，最近在做IMX6ULL的开发，刚开始就遇到了这个拦路虎问题，我使用的闪迪的TF卡32GB的，搭配绿联的读卡器使用。在windows以及物理机装的archlinux都能正常识别并进行挂载，离谱的就是在虚拟机上识别不了。虚拟机版本：VMwareWorkstati......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99