首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛21

多校A层冲刺NOIP2024模拟赛21

时间:2024-11-12 21:31:43浏览次数:1  
标签:dist 21 int rep 多校 long freopen using NOIP2024

以为150要垫底了,没想到还有高手。

送信卒

签,没一会就写完但因为交的太晚被猫娘抢了首A。恼火

简要题意

给一个\(n\times m(n,m\le 100)\)的网格图,左右走的代价为\(1\),上下走的代价为\(k\),求最小的\(k\),使得\((sx,sy)\)到\((tx,ty)\)的代价恰好为\(s(s\le 10^5)\)。数据保证有解。

solution

目前有\(O(n+m)\log m\log s\)的std解法和\(O(n^4)\)的反向爆标解法,但因为跑得慢,所以不说了。

发现当\(k\)越大时,最短路越大,所以考虑二分\(k\),如果最短路\(\ge s\),则记录即可,注意一下精度问题吧,因为卡错解的时候不小心吧\(O(n^4)\)的精度卡了。

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    // FILE *InFile = stdin,*OutFile = stdout;
    FILE *InFile = freopen("msg.in","r",stdin),*OutFile = freopen("msg.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long  long;
using db = double;using ldb = long double;
const int N = 1e5 + 10,RN = 110;
const db eps = 1e-7;
template<size_t N,size_t M>
struct Graph{
    struct EDGE{int to,n;db w;}e[M];
    int h[N],cnt;
    inline void add(int u,int v,db w){e[++cnt] = {v,h[u],w};h[u] = cnt;}
    inline void Add(int u,int v,db w){add(u,v,w);add(v,u,w);}
#define repe(i,x,y,g) for(int i = g.h[x],y = g.e[i].to;i;i = g.e[i].n,y = g.e[i].to)
};Graph<N,N*5> g;
int n,m,sx,sy,tx,ty,st,ed,a[RN][RN];
db s,dist[N];
bitset<N> vis;
vector<int> up;
inline int gp(int x,int y){return (x-1)*m+y;}
inline void dijkstra(int s){
    rep(i,1,gp(n,m),1) dist[i] = INT_MAX,vis[i] = false;
    priority_queue<pair<db,int>,vector<pair<db,int> >,greater<pair<db,int> > > q;
    dist[s] = 0;q.push(make_pair(dist[s],s));
    while(q.size()){
        int x = q.top().second;q.pop();
        if(vis[x]) continue;vis[x] = true;
        repe(i,x,y,g){
            if(dist[y] > dist[x] + g.e[i].w){
                dist[y] = dist[x]+g.e[i].w;
                q.push(make_pair(dist[y],y));
            }
        }
    }
}
inline bool check(db mid){
    for(auto i:up) g.e[i].w = mid;
    dijkstra(st);
    return dist[ed] >= s + eps;
}
inline void solve(){
    cin>>n>>m>>sx>>sy>>tx>>ty;
    st = gp(sx,sy),ed = gp(tx,ty);
    rep(i,1,n,1) rep(j,1,m,1) cin>>a[i][j];
    cin>>s;
    auto pd = [&](int x,int y){
        return 1 <= x && x <= n && 1 <= y && y <= m && a[x][y] == 0;
    };
    rep(i,1,n,1) rep(j,1,m,1){
        if(a[i][j]) continue;
        if(pd(i,j-1)){
            // cerr<<i<<' '<<j<<'\n';
            g.Add(gp(i,j),gp(i,j-1),1);
        }
        if(pd(i-1,j)){
            // cerr<<i<<' '<<j<<'\n';
            g.Add(gp(i,j),gp(i-1,j),0),
            up.push_back(g.cnt),up.push_back(g.cnt-1);
        }
    }
    // cerr<<check(0.667)<<'\n';
    // exit(0);
    db l = 0,r = s,ans = 0;
    while(l + eps <= r){
        db mid = (l + r)/2;
        if(check(mid)) ans = mid,r = mid;
        else l = mid;
    }
    cout<<fixed<<setprecision(3)<<ans<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

共轭树图

赛时推出结论来了不会打\(dp\)我是SB

简要题意

太长了不写了

solution

发现满足上述条件的\(G\)是可生成的时,当且仅当:把\(G\)中的边画在原树上,形成的两条路径要么无交,要么为包含关系。

考虑设\(f_{x,i}\)表示以\(x\)为根的子树,而且\(x\)只被允许和它的第\(i\)个祖先在\(G\)中连边时,子树的方案数。有

\[f_{x,i}=\prod\sum_{j=1}^if_{y,i-j+2} \]

发现后面的柿子用前缀和优化即可做到\(O(n^2)\)。

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    // FILE *InFile = stdin,*OutFile = stdout;
    FILE *InFile = freopen("reflection.in","r",stdin),*OutFile = freopen("reflection.out","w",stdout);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define eb emplace_back
constexpr int N = 3e3 + 10,mod = 998244353;
int n,f[N][N];
vector<int> e[N];
void dfs(int x,int fa){
    for(int y:e[x]) if(y ^ fa) dfs(y,x);
    rep(i,1,n,1){
        f[x][i] = 1;
        for(int y:e[x]) if(y ^ fa) f[x][i] = 1ll*f[x][i]*f[y][i+1]%mod;
    }
    rep(i,3,n+1,1) f[x][i] = (f[x][i] + f[x][i-1])%mod;
}
inline void solve(){
    cin>>n;
    rep(i,1,n-1,1){int u,v;cin>>u>>v;e[u].eb(v);e[v].eb(u);}
    dfs(n,0);cout<<f[n][1];
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

摸鱼军训

简要题意

给定一个长度为\(n(n\le 5\times10^5)\)的排列,有\(q(q\le 5\times 10^5)\)次询问,每次给定\(k,x(k,x\le 5\times 10^5)\),求\(k\)轮冒泡排序后\(x\)所在的位置。

solution

记\(r_x\)表示在\(x\)前中比\(x\)大的数的个数。

如果\(r_x\ge k\),那么\(x\)会去到\(i-k\)的位置,反之,那么剩下的就会填入剩余的空位中。

先求出\(r\)数组后,将询问离线,然后就转化成了单点取反,区间求和,求第\(k\)个\(0/1\)的位置的数据结构,这就是个线段树,最后一个操作线段树上二分即可。

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    // FILE *InFile = stdin,*OutFile = stdout;
    FILE *InFile = freopen("bubble.in","r",stdin),*OutFile = freopen("bubble.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
struct Segment_Tree{
    struct segment_tree{
        int l,r,val;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define val(x) tree[x].val
    }tree[N<<2];
    inline void pushup(int k){val(k) = val(k<<1)+val(k<<1|1);}
    void build(int k,int l,int r){
        l(k) = l,r(k) = r;
        if(l == r) return val(k) = 0,void();
        int mid = (l + r) >> 1;
        build(k<<1,l,mid);build(k<<1|1,mid+1,r);
        pushup(k);
    }
    void upd(int k,int pos,int val = 1){
        if(l(k) == r(k)) return val(k) = 1,void();
        int mid = (l(k) + r(k)) >> 1;
        if(pos <= mid) upd(k<<1,pos,val);else upd(k<<1|1,pos,val);
        pushup(k);
    }
    int qryk(int k,int p){
        if(l(k) == r(k)) return l(k);
        int ls = k<<1;
        if(p - val(ls) <= 0) return qryk(k<<1,p);
        else return qryk(k<<1|1,p-val(ls));
    }
    int qrys(int k,int l,int r){
        if(l <= l(k) && r(k) <= r) return val(k);
        int mid = (l(k) + r(k)) >> 1,res = 0;
        if(l <= mid) res += qrys(k<<1,l,r);
        if(r > mid) res += qrys(k<<1|1,l,r);
        return res;
    }
}T;
struct BIT{
    int mx,tree[N];
    inline int lb(int x){return (x&(-x));}
    inline void upd(int pos,int val){rep(i,pos,mx,lb(i)) tree[i] += val;}
    inline int qry(int pos){int res = 0;drep(i,pos,1,lb(i)) res += tree[i];return res;}
}bit;
struct Q{int k,x,id;}q[N];
int n,m,pos[N],ans[N],a[N],num[N];
inline void solve(){
    cin>>n;T.build(1,1,n);bit.mx = n;
    rep(i,1,n,1) cin>>a[i],pos[a[i]] = i;
    rep(i,1,n,1) bit.upd(a[i],1),num[i] = i - bit.qry(a[i]);
    cin>>m;rep(i,1,m,1) cin>>q[i].k>>q[i].x,q[i].id = i;
    sort(q+1,q+1+m,[](Q x,Q y){return x.x > y.x;});
    int now = n;
    rep(i,1,m,1){
        while(now > q[i].x) T.upd(1,pos[now]),now--;
        if(num[pos[q[i].x]] >= q[i].k) ans[q[i].id] = pos[q[i].x] - q[i].k;
        else{
            if(q[i].k > T.tree[1].val) ans[q[i].id] = q[i].x;
            else ans[q[i].id] = T.qryk(1,q[i].k) - q[i].k;
        }
    }
    rep(i,1,m,1) cout<<ans[i]<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

神奇园艺师

不会。

本来想写鲜花的但是电脑死了,都没了,不写了。

p

image
image

标签:dist,21,int,rep,多校,long,freopen,using,NOIP2024
From: https://www.cnblogs.com/hzoi-Cu/p/18542691

相关文章

  • 『模拟赛』多校A层冲刺NOIP2024模拟赛21
    Rank别样的,不好评价,烂完了A.送信卒签,我是唐氏。为什么呢题目没给最短路的定义,我赛时觉得最短路就是最短路径,于是直接bfs一遍随便加个check就做完了。当然过得那遍按我的思路来说是错的,然后我也发现了这一点,然后就改了,然后就WA了。总结:错误思路的错解是正确思路......
  • 多校A层冲刺NOIP2024模拟赛21
    多校A层冲刺NOIP2024模拟赛21\(T1\)A.送信卒\(90pts/100pts\)部分分\(90pts\)设最后的可能的最短路中左右共移动了\(d\)次,上下共移动了\(x\)次。则等价于求\(\min\{x_{i}k+d_{i}\}=s\)的解,观察到\(d\in[0,\min(\left\lceil\frac{nm}{2}\right\rce......
  • 打卡信奥刷题(221)用C++信奥P1740[普及组/提高] Diamond A&B(1)
    DiamondA&B(1)题目背景由于本题较难,将本题拆做两题,分别为diamondA以及diamondB。本题为DiamondA。题目描述教主上电视了!这个消息绝对是一个爆炸性的新闻。一经传开,大街上瞬间就没人了(都回家看电视去了),商店打烊,工厂停业。大家都把电视机的音量开到最大,教主的声音......
  • 21天教你学会PCIe专栏(5)--事务层(Transaction Layer)
    目录第5天:事务层(TransactionLayer)课程目标课程内容1.事务层概述2.事务类型3.请求和响应机制4.事务层的配置和管理5.实际应用示例课后练习结语第5天:事务层(TransactionLayer)课程目标理解PCIe事务层的基本概念和功能掌握事务类型及其工作原理了解请求和响应......
  • HDU - 4821 String
    给定字符串\(S\)。求有多少长\(M\timesL\)的子串,使得将其划分成\(M\)个长度为\(L\)的字符串\(S_1,S_2,\dotsS_M\)互不相同。\(1\leM\timesL\le|S|\le10^5\)。从\(0\)起下标。显然这些字符串的起始位置在模\(L\)意义下相同。不妨枚举这个值\(r\in[......
  • NOIP2024模拟赛#18 总结
    头要炸了。T1题面很好懂,手玩了一下发现答案最小是\((m-1)\timesn\)。可能会多出来一个长度为\(k\)的部分,会发现如果多出来一个长度为\(k\)的部分且合法,那么单个串\(1\simk\)位与\(n-k+1\simn\)位一定相同,\(k+1\simn\)位与\(1\simn-k\)一定相同。Hash判一下即......
  • 『模拟赛』NOIP2024加赛4
    Rank给我唐完了,又名,【MX-S5】梦熊NOIP2024模拟赛1。A.王国边缘好像简单倍增就做完了。由于昨天T5在我脑海中留下了挥之不去的印象,今天一上来看到这题就发现是一个内向基环树森林。然后被硬控硬控硬控,最后一个小点加一点优化就能过没调出来,挂30pts,菜菜菜菜菜。注......
  • comp9021 olygons Python
    Assignment2,Trimester3,2024Generalmatter1.1.Aims.Thepurposeoftheassignmentisto:designandimplementaninterfacebasedonthedesiredbehaviourofanapplicationprogram;practicetheuseofPythonsyntax;developproblemsolvingsk......
  • CVE-2021-21311
    CVE-2021-21311今天要记录的是ssrf,cve编号为CVE-2021-21311Adminer是一个PHP编写的开源数据库管理工具,支持MySQL、MariaDB、PostgreSQL、SQLite、MSSQL、Oracle、Elasticsearch、MongoDB等数据库。在其4.0.0到4.7.9版本之间,连接ElasticSearch和ClickHouse数据库时存在一处......
  • 代码随想录算法训练营第二十二天| leetcode77. 组合、leetcode216.组合总和III、leetc
    1leetcode77.组合题目链接:77.组合-力扣(LeetCode)文章链接:代码随想录视频链接:带你学透回溯算法-组合问题(对应力扣题目:77.组合)|回溯法精讲!_哔哩哔哩_bilibili思路:开始想循环,感觉行不通,然后看了视频,就嗯理解了一些感觉跟递归的思路确实差不多1.1回溯三部曲回溯的方法首......