首页 > 其他分享 >暑假集训csp提高模拟11

暑假集训csp提高模拟11

时间：2024-07-29 19:52:18浏览次数：15  
标签：11 int long 集训 FILE ans using csp define

赛时 rank 9 ,T1 100,T2 100,T3 0,T4 0

update: 赛后T1被hack了,成了99，死因没有记忆化

挂成了rank 10

我又要挂分了。

T3 暴力挂了？

话说jjdw和k8啥时候回来。

T1 Fate

签到题，最短路板子。

考虑一个点\(a\)，其最短路前驱节点为\(b\),前驱结点组成的集合为\(B\),其次短路的前驱节点为\(c\)，组成的集合为\(C\)

那么考虑对于每一个\(c\)，看看其是否与\(B\)中的节点有且仅有一条边相连，若有，则答案数加上c的最短路路径数。

记搜一下

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
#include<sys/timeb.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
#define pii pair<int,int>
#define mk make_pair
const int N = 2e5 + 10,mod = 1e9 + 7;
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){edge[++cnt] = {v,head[u]};head[u] = cnt;}
priority_queue<pii,vector<pii>,greater<pii> > q;
bitset<N> vis;
unordered_set<int> pre[N];
int dist[N],num[N];
int n,s,t,m,mn;
inline void dijkstra(int s){
    vis.reset();
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;num[s] = 1;
    queue<int> q;q.push(s);vis[s] = true;
    while(q.size()){
        int x = q.front();q.pop();vis[x] = false;
        for(int i = head[x]; i;i = edge[i].next){
            int y = edge[i].to;
            if(dist[y] > dist[x] + 1){
                dist[y] = dist[x] + 1;
                num[y] = num[x] % mod;
                unordered_set<int> ().swap(pre[y]);
                pre[y].insert(x);
                if(!vis[y]){
                    vis[y] = true;
                    q.push(y);
                }
            }
            else if(dist[y] == dist[x] + 1) num[y] = (num[y] + num[x]) % mod,pre[y].insert(x);
        }
    }
}
int ans = 0;
int mp[N];
int dfs(int x){
    if(vis[x]) return mp[x];
    vis[x] = true;
    int ans = 0;
    for(int i = head[x]; i;i = edge[i].next){
        int y = edge[i].to;
        if(pre[x].find(y) != pre[x].end()) continue;
        if(dist[y] == dist[x]) ans = (0ll + ans + num[y]) % mod;
    }
    for(auto i : pre[x]) ans = (ans + dfs(i)) % mod;
    return mp[x] = ans;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    for(int i = 1,u,v;i <= m; ++i){
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    dijkstra(s);;
    cout<<dfs(t)<<'\n';
}

T2 EVA

[ABC274F] Fishing

贪心。

考虑枚举任意一点为起点，看看其在t时最多可以抓住多少。

用优先队列存一条鱼可以被抓住的起始时间，不能被抓住的终止时间。

然后pop就行

所以这也配蓝？

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
const int N = 2e3 + 10;
const db eps = 1e-9;
struct node{int x,v,w;}a[N];
#define mk make_pair
int n,s,sum;
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>s;
    for(int i = 1;i <= n; ++i) cin>>a[i].w>>a[i].x>>a[i].v;
    sort(a+1,a+1+n,[](node x,node y){return x.x < y.x;});
    int ans = 0;
    for(int i = 1;i <= n; ++i){
        __gnu_pbds::priority_queue<pair<db,int>,greater<pair<db,int> > > add;
        __gnu_pbds::priority_queue<pair<db,int>,greater<pair<db,int> > > del;
        // cerr<<i<<":\n";
        int res = a[i].w;//算上自己
        for(int j = 1;j <= n; ++j){
            if(i == j) continue;
            if(j < i){
                if(a[j].v <= a[i].v && a[j].x != a[i].x) continue;//在后面还无法超过
                else if(a[j].v == a[i].v && a[j].x == a[i].x){res += a[j].w;continue;}//在一起
                else if(a[j].v < a[i].v && a[j].x < a[i].x) continue;
                else if(a[j].v < a[i].v && a[j].x == a[i].x){
                    db reach = 1.0 * (a[i].x - a[j].x)/(a[j].v - a[i].v);
                    add.push(mk(reach,j));
                    del.push(mk(reach,j));
                    continue;
                }
                db reach = 1.0 * (a[i].x - a[j].x)/(a[j].v - a[i].v);//可以捉到
                db de = 1.0 * (a[i].x + s - a[j].x)/(a[j].v - a[i].v);//最后可以捉到的时间
                add.push(mk(reach,j)),del.push(mk(de,j));
            }
            if(j > i){
                if(a[j].v >= a[i].v && a[i].x + s < a[j].x) continue;//无法捉到
                else if(a[j].v == a[i].v && a[i].x + s >= a[j].x){res += a[j].w;continue;}//一直可以捉到
                if(a[i].v > a[j].v){
                    db reach = 1.0 * (a[j].x - a[i].x - s)/(a[i].v - a[j].v);
                    db de = 1.0 * (a[j].x - a[i].x) / (a[i].v - a[j].v);
                    add.push(mk(reach,j));
                    del.push(mk(de,j));
                }
                else{
                    db reach = 0.0;
                    db de = 1.0 * (a[i].x + s - a[j].x)/(a[j].v - a[i].v);
                    add.push(mk(max(reach,0.0),j));
                    del.push(mk(de,j));
                }
            }
        }
        ans = max(ans,res);
        while(add.size()){
            db now = add.top().first;res += a[add.top().second].w;
            add.pop();
            while(del.size() && del.top().first + eps < now){
                res -= a[del.top().second].w;
                del.pop();
            }
            ans = max(ans,res);
        }
    }
    cout<<ans<<'\n';
}

T3 嘉然登场

[ARC148E] ≥ K

来自int_R的思路

考虑将所有的数分为两种\(<\frac{k}{2}\)的，\(\le\frac{k}{2}\)的。

将一个\(<\frac{k}{2}\)的数\(a_i\)放在第一个\(\le k-a_i\)上。

从大到小放所有\(\le\frac{k}{2}\)的数\(a_i\)，放到一个数就把放在它上面的数也放了。

放第一类数\(a_i\le\frac{k}{2}\)的数会使得可以放的位置+1，放第二类数会使得可以放的位置-1。

除以重复元素出现次数的阶乘。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
const int N = 2e5 + 10,mod = 998244353;
int n,k,a[N],cnt[N];
inline ll power(ll a,ll b,ll mod){
    ll res = 1;
    for(; b;b >>= 1,a = a * a % mod)
        if(b&1) res = res * a % mod;
    return res;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    sort(a+1,a+1+n);
    if(a[n] + a[1] < k) return cout<<0<<'\n',0;
    for(int i = 1;i <= n && a[i] <= (k-1)/2; ++i){
        ++cnt[lower_bound(a+1,a+1+n,k-a[i])-a];
    }
    ll ans = 1,pos_num = 1,total = 1;
    for(int i = n;i && a[i] > (k-1)/2; --i){
        ans = ans * pos_num % mod,++pos_num;
        for(int j = 1;j <= cnt[i];++j)
            ans = ans * pos_num % mod,--pos_num;
    }
    for(int i = 1,j = 1;i <= n; i = j){
        while(a[j] == a[i]) ++j;
        for(int k = 1;k <= j-i; ++k) total = total * k % mod;
    }
    cout<<ans * power(total,mod-2,mod)%mod;
}

T4 Clannad

P9340 [JOISC 2023 Day3] Tourism

赛时想了一个bitset的做法，但是莫名WA了。

套路题

考虑如何计算点集。我们用数据结构标记一下所有被查询的点走到某一个特殊点所经过的边，统计被标记的边的数量。

我们钦定这个特殊点为1，记\(LCA = lca\{c_i\}(i\in [l,r])\)，多出来的答案就是\(dep_{LCA}-dep_1\)

考虑如何统计答案。

离线，按r排序，以时间为值进行覆盖。统计\(LCA\)子树内值\(\ge l\)的数的个数。

但是如果只覆盖到\(LCA\)的话不太好处理，那么我们直接覆盖到1，反正多出来的部分会被减去。

用一个BIT统计值域，ODT区间赋值。

其实还有bitset和回滚莫队的做法，但我不会……

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
const int N = 1e5 + 10;
int n,m,q,a[N],st[18][N],ans[N];;
struct Query{int l,r,id;}Q[N];
struct EDGE{int to,next;}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){edge[++cnt] = {v,head[u]};head[u] = cnt;}
namespace TCS{
    int fa[N],dep[N],top[N],siz[N],son[N],dfn[N],tot;
    void dfs1(int x){
        siz[x] = 1;
        dep[x] = dep[fa[x]] + 1;
        for(int i = head[x]; i;i = edge[i].next){
            int y = edge[i].to;
            if(y == fa[x]) continue;
            fa[y] = x;dfs1(y);
            siz[x] += siz[y];
            if(siz[son[x]] < siz[y]) son[x] = y;
        }
    }
    void dfs2(int x,int t){
        top[x] = t;
        dfn[x] = ++tot;
        if(son[x]) dfs2(son[x],t);else return;
        for(int i = head[x]; i;i = edge[i].next){
            int y = edge[i].to;
            if(y == son[x] || y == fa[x]) continue;
            dfs2(y,y);
        }
    }
    inline int LCA(int x,int y){
        int fx = top[x],fy = top[y];
        while(fx != fy){
            if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);
            x = fa[fx];
            fx = top[x];
        }
        if(dep[x] > dep[y]) swap(x,y);
        return x;
    }
}using namespace TCS;
class BIT{
private:
    int tree[N];
    #define lowbit(x) (x&(-x))
public:
    int mx;
    inline void update(int pos,int val){
        for(int i = pos;i <= mx;i += lowbit(i)) tree[i] += val;
    }
    inline int query(int pos){
        int res = 0;
        for(int i = pos; i;i -= lowbit(i)) res += tree[i];
        return res;
    }
}T;
class ODT{
private:
    struct node{
        int l,r;mutable int val;
        inline bool operator < (const node &a) const {return l < a.l;}
        node (int L = 0,int R = 0,int Val = 0) : l(L),r(R),val(Val){}
    };
    #define sit set<node>::iterator
public:
    set<node> s;
    inline sit split(int pos){
        sit it = s.lower_bound(node(pos));
        if(it != s.end() && it->l == pos) return it;
        --it;
        int l = it->l,r = it->r,val = it->val;
        s.erase(it);
        s.insert(node(l,pos-1,val));
        return s.insert(node(pos,r,val)).first;
    }
    inline void assign(int l,int r,int val){
        sit it2 = split(r + 1),it1 = split(l);
        for(sit it = it1;it != it2; ++it) T.update(m-it->val+1,-(it->r-it->l+1));
        s.erase(it1,it2);
        s.insert(node(l,r,val));
        T.update(m-val+1,r-l+1);
    }
    inline void insert(int l,int r,int val){s.insert(node(l,r,val));}
}Tree;
inline void update(int x,int val){
    while(x){
        Tree.assign(dfn[top[x]],dfn[x],val);
        x = fa[top[x]];
    }
}
inline void pre(){
    int t = log2(m)+1;
    for(int i = 1;i <= m; ++i) st[0][i] = a[i];
    for(int j = 1;j <= t; ++j){
        for(int i = 1;i + (1<<j) - 1 <= m; ++i){
            st[j][i] = LCA(st[j-1][i],st[j-1][i+(1<<(j-1))]);
        }
    }
}
inline int query(int l,int r){
    int k = log2(r-l+1);
    return LCA(st[k][l],st[k][r-(1<<k)+1]);
}
vector<int> vec[N];
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>m>>q;Tree.insert(1,n,0);T.mx = m;
    for(int i = 1,u,v;i < n; ++i) cin>>u>>v,add(u,v),add(v,u);
    for(int i = 1;i <= m; ++i) cin>>a[i];
    dfs1(1);dfs2(1,1);pre();
    for(int i = 1;i <= q; ++i){
        cin>>Q[i].l>>Q[i].r;Q[i].id = i;
        vec[Q[i].r].push_back(i);
        ans[i] = -dep[query(Q[i].l,Q[i].r)] + dep[1];
    }
    for(int i = 1;i <= m; ++i){
        update(a[i],i);
        for(int j : vec[i]) ans[j] += T.query(m-Q[j].l+1);
    }
    for(int i = 1;i <= q; ++i) cout<<ans[i]<<'\n';
}

标签：11,int,long,集训,FILE,ans,using,csp,define
From： https://www.cnblogs.com/hzoi-Cu/p/18330832

相关文章

  • 2024夏中山集训第1周
    【NOIP模拟一】20240729比赛有点唐，C没开ll挂50，D挂了一点部分分。C注意到答案是s除以区间gcd。裴蜀定理推广D像这样建图，跑全源最短路。在这张图上有\(1\to2\to3\to4\to5\)和\(7\to8\to9\to3\to10\to11\)两条路径。把路径上的点看作车上的点，每个点本身看作......
  • 暑假集训CSP提高模拟11
    A.Fate求次短路方案数.这题有点小水了，好像之前做过.具体的方案显然是DP，考虑枚举当前每一个路径长度，假如比最短路更优则覆盖最短路，之前的最短路用来覆盖次短路.否则如果比次短路更优，则直接覆盖次短路.方案数的话考虑一样的方法维护，只是在遇到相等的路径长时使方案数加一即可.......
  • 暑假集训CSP提高模拟11
    暑假集训CSP提高模拟11组题人：@KafuuChinocpp\(T1\)P152.Fate\(24pts\)强化版：HDU1688Sightseeing设\(dis_{i,0/1}\)表示从\(s\)到\(i\)的最短路/次短路长度，\(f_{i,0/1}\)表示从\(s\)到\(i\)的最短路/次短路条数。\(dijkstra\)过程中按照路径长度与......
  • 『模拟赛』暑假集训CSP提高模拟11
    Rank昨天积攒的rp生效了！A.Fate签到题。次短路计数，感觉做过类似的，不过这里次短路定义为最短路长度+1，赛时把自环想成环了，原谅我犯唐。还是用dijkstra，我们这次开两个dis数组存最短路和次短路长度，然后两个cnt数组存二者的个数，稍微想想就能想到一共的四种可能：更新后......
  • 【C++11】C++11新纪元：深入探索右值引用与移动语义
    ......
  • CSP11
    CSP11T1暴力#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#definelllonglong#defineullunsignedlonglong#definelid(rt<<1)#definerid(rt<<1|1)//#defineendl'\n'//#d......
  • 都是全志T113处理器，“-i”和“-S3”有什么区别？
    自9个月前，创龙科技“1片含税就79元”的全志T113-i双核[email protected]的工业核心板(SOM-TLT113)推出之后，不少嵌入式软硬件工程师、用户都咨询我们，究竟T113-i和T113-S3这两款处理器有什么区别？不同后缀型号的处理器，哪个更适合工业场景？今天，创龙科技就为大家深度揭秘，详细讲解......
  • spellman电源维修XRM50P50X3839 NY11788
    电源维修的常见故障包括：无法开机、电源烧、短路、输出偏小、电源不通电、电源风扇不转，无输出，缺项，输出过高，电源烧毁，灯不亮，不动作等故障维修。Spellman的专有高压技术，再加上MT电路，导致了一个紧凑和轻量级的模块，是理想的OEM应用布置来获得的高压输出，而较低的电压单元则采用稳健......
  • GLSL教程 第11章：性能优化和调试
    目录11.1GLSL着色器的性能考量11.1.1减少计算复杂度避免不必要的计算使用适当的数据类型优化数学操作11.1.2减少内存访问减少纹理采样次数使用纹理缓存11.1.3优化数据传输减少数据传输量批处理（Batching）11.1.4使用高级渲染技术LevelofDetail(LOD)延迟渲染......
  • 911、基于51单片机的温度报警（上下限，LCD）
    完整资料或代做滴滴我（有偿）目录一、设计功能二、proteus仿真三、原理图四、程序源码五、资料包括一、设计功能温度报警系统1、实时显示当前温度2、对上下限进行设定，通过按键设置3、温度高于上限或低于下限显示屏有相应提示，蜂鸣器响二、proteus仿真三......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99