首页 > 其他分享 >csp-s模拟10

csp-s模拟10

时间:2024-10-08 17:48:48浏览次数:6  
标签:pre 10 suf int res vis using csp 模拟

rank 31,垫底了,T1 0pts,T2 18pts,T3 0pts,T4 50pts

状态有点不好,策略有问题,T4是可以切的,但是不知道为什么弃了。T1不会线性基寄。T3 奇怪结论题,T2 结论题。

在猜结论上还是不行。

T1 欧几里得的噩梦

用到了线性基线性无关的性质,将两个数连边,把环去掉,并查集判断即可。

统计答案用快速幂和线性基可以异或出的数的个数的性质即可。

点此查看代码
#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)
#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 = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("Euclid.in"),*OutFile = outfile("Euclid.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
int fa[N],n,m,siz[N];
inline int get_fa(int x){while(x != fa[x]) x = fa[x] = fa[fa[x]];return x;}
vector<int> p;
inline int power(int a,int b,int mod){
    int res = 1;
    for(;b;b>>=1,a = 1ll*a*a%mod) if(b&1) res = 1ll*res*a%mod;
    return res;
}
inline void solve(){
    cin>>n>>m;
    rep(i,1,m+1,1) fa[i] = i,siz[i] = 1;
    rep(i,1,n,1){
        int op;cin>>op;
        if(op == 1){
            int x,y = m+1;cin>>x;
            int fx = get_fa(x),fy = get_fa(y);
            if(fx == fy) continue;
            fa[fx] = fy;siz[fy] += siz[fx];
            p.emplace_back(i);
        }
        else{
            int x,y;cin>>x>>y;
            int fx = get_fa(x),fy = get_fa(y);
            if(fx == fy) continue;
            fa[fx] = fy;siz[fy] += siz[fx];
            p.emplace_back(i);
        }
    }
    int ans = 1;
    rep(i,1,m+1,1) if(get_fa(i) == i) ans = 1ll*ans*power(2,siz[i]-1,1e9+7)%(int)(1e9+7);
    cout<<ans<<' '<<p.size()<<'\n';
    for(auto i:p) cout<<i<<' ';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

T2 清扫

[AGC010C] Cleaning

先特判掉点数为2的情况,然后以一个至少连接了两个节点的点为根。

考虑一个点处的石子被去掉有两种方式

  1. 被它的子树消去
  2. 被它的子树和另一个地方的消去
    image

比如\(5\)处的石子,可能是被\(2,6\)消走了一部分,也可能是被\(2,1\)消走了一部分。

那么每个节点需要上传的就是它还需要几个点来与其相连,记为\(f\)。

对于叶子节点,\(f_x=a_x\)

对于非叶子节点,先令其的\(f_x = \sum\limits_{y\in son_x}f_y\),另记\(mx = \max\limits_{y\in son_x} f_y\)

然后分讨,如果\(mx\)占了一半以上,那么记\(p = f_x-mx\)
反之,那么\(p = \frac{f_x}{2}\)

如果所有的点都向别的子树连还不够将\(x\)处的节点消去或者将所有的点都向该子树连还是不能删去\(x\),直接无解。

最后\(f_x = 2\times a_x - f_x\)

为什么是这个?假设连向外面子树的个数为\(out\),连向自身的为\(in\),有\(in+out = a_x\),又有\(2\times in+out = f_x\)
联立就有\(out = 2\times a_x - f_x\)

点此查看代码
#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)
#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 = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
#define eb emplace_back
int n,a[N];
vector<int> edge[N];
inline void add(int u,int v){edge[u].eb(v);}
int fa[N];
ll f[N];
bool flag = false;
void dfs(int x){
    if(edge[x].size() == 1) return f[x] = a[x],void();
    ll p,mx = 0;
    for(int y:edge[x]){
        if(y == fa[x]) continue;
        fa[y] = x;dfs(y);f[x] += f[y];mx = max(mx,f[y]); 
    }
    if(mx > f[x] - mx) p = f[x] - mx;
    else p = f[x]/2;
    if(f[x] < a[x] || f[x] - a[x] > p) cout<<"NO\n",exit(0);
    f[x] = 2ll*a[x] - f[x];
}
inline void solve(){
    cin>>n;rep(i,1,n,1)cin>>a[i];
    if(n == 2){
        if(a[1] != a[2]) cout<<"NO\n";
        else cout<<"YES\n";
        return;
    }
    rep(i,2,n,1){int u,v;cin>>u>>v;add(u,v),add(v,u);}
    rep(i,1,n,1) if(edge[i].size() > 1)dfs(i),cout<<(f[i]?"NO\n":"YES\n"),assert(!f[i]&&!flag),exit(0);
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

T3 购物

结论题。

考虑先将\(a\)升序排列,记\(sum_i = \sum_{j=1}^i a_i\)。

枚举\(i\),如果没有加上第\(i\)个数,那么最大的值为\(sum_{i-1}\),若加上第\(i\)个数,那么中间就会多出\(sum_{i-1}\sim \left\lfloor\frac{a_i}{2}\right\rfloor\)的空缺,直接加上即可。

点此查看代码
#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)
#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 = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("buy.in"),*OutFile = outfile("buy.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
int n,a[N];
inline void solve(){
    cin>>n; rep(i,1,n,1) cin>>a[i];
    sort(a+1,a+1+n);
    ll s = 0,m = 0;
    rep(i,1,n,1){
        if((a[i]+1)/2 > s) m -= (a[i]+1)/2-s-1;
        s += a[i];
    }
    cout<<m+s<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

T4 ants

原题permu,回滚莫队,用链表模拟的并查集。

考虑将每段的最右段的点的左指针指向该段最左端,最左端的点的右指针指向该段最右段。

然后四种情况分讨即可,删除操作记录一下,逆序处理即可。

点此查看代码
#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)
#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 = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = infile("ants.in"),*OutFile = outfile("ants.out");
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10;
int n,m,L[N],R[N],pos[N],len,a[N],out[N];
struct node{int id,l,r;}q[N];
struct Change{int op,val,lef,rgh;};
int pre[N],suf[N],rpre[N],rsuf[N];
bitset<N> vis;
inline void Add(int x,int &res){
    vis[x] = true;
    if(vis[x-1] && vis[x+1]){
        suf[pre[x-1]] = suf[x+1];pre[suf[x+1]] = pre[x-1];
        res = max(suf[x+1] - pre[x-1] + 1,res);
    }
    if(vis[x-1] && !vis[x+1]){
        pre[x] = pre[x-1],suf[pre[x-1]] = x;
        res = max(x - pre[x - 1] + 1,res);
    }
    if(!vis[x-1] && vis[x+1]){
        suf[x] = suf[x+1],pre[suf[x+1]] = x;
        res = max(suf[x+1] - x + 1,res);
    }
    if(!vis[x-1] && !vis[x+1]) pre[x] = suf[x] = x;
}
inline void solve(){
    cin>>n>>m;rep(i,1,n,1) cin>>a[i];
    rep(i,1,m,1) cin>>q[i].l>>q[i].r,q[i].id = i;
    len = sqrt(n);rep(i,1,len,1) L[i] = R[i-1]+1,R[i] = i*len;
    if(R[len] < n) len++,L[len] = R[len-1] + 1,R[len] = n;
    rep(i,1,len,1) rep(j,L[i],R[i],1) pos[j] = i;
    sort(q+1,q+1+m,[](node x,node y){return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l;});
    int l,r,res = 0,i = 1;
    rep(now,1,len,1){
        rep(i,1,n,1) pre[i] = suf[i] = vis[i] = 0;
        r = R[now],res = 0;
        int ql = q[i].l,qr = q[i].r,id = q[i].id;
        while(pos[ql] == now){
            if(qr - ql < len){
                bitset<N> vis;
                rep(i,ql,qr,1) vis[a[i]] = true;
                int lastpos = 0,res = 0,ans = 0;
                while(vis._Find_next(lastpos) != vis.size()){
                    int pos = vis._Find_next(lastpos);
                    if(!lastpos) res = 1;
                    else if(lastpos && pos - lastpos == 1) res++;
                    else if(lastpos && pos - lastpos > 1) res = 1;
                    lastpos = pos;
                    ans = max(ans,res);
                }
                out[id] = ans;
                i++;ql = q[i].l,qr = q[i].r,id = q[i].id;
                continue;
            }
            
            l = R[now] + 1;
            while(r < qr) Add(a[++r],res);
            int rres = res;vector<Change> que;
            while(l > ql){
                l--;int x = a[l];vis[x] = true;Change p;p.val = x;
                if(vis[x-1] && vis[x+1]){
                    suf[pre[x-1]] = suf[x+1];pre[suf[x+1]] = pre[x-1];
                    p.op = 1;p.lef = pre[x-1],p.rgh = suf[x+1];
                    res = max(suf[x+1] - pre[x-1] + 1,res);
                }
                if(vis[x-1] && !vis[x+1]){
                    pre[x] = pre[x-1],suf[pre[x-1]] = x;
                    p.op = 2;p.lef = x,p.rgh = pre[x-1];
                    res = max(x - pre[x - 1] + 1,res);
                }
                if(!vis[x-1] && vis[x+1]){
                    suf[x] = suf[x+1],pre[suf[x+1]] = x;
                    p.op = 3;p.lef = x,p.rgh = suf[x+1];
                    res = max(suf[x+1] - x + 1,res);
                }
                if(!vis[x-1] && !vis[x+1]){
                    pre[x] = suf[x] = x;
                    p.op = 4; res = max(res,1);
                }
                que.push_back(p);
            }
            out[id] = res;
            res = rres;l = R[now] + 1;
            while(que.size()){
                auto p = que.back();que.pop_back(); vis[p.val] = false;
                if(p.op == 1) suf[p.lef] = p.val - 1,pre[p.rgh] = p.val + 1;
                if(p.op == 2) suf[p.rgh] = p.val - 1;
                if(p.op == 3) pre[p.rgh] = p.val + 1;
                if(p.op == 4) suf[p.val] = pre[p.val] = 0;
            }
            i++;ql = q[i].l,qr = q[i].r,id = q[i].id;
        }
    }
    rep(i,1,m,1) cout<<out[i]<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

标签:pre,10,suf,int,res,vis,using,csp,模拟
From: https://www.cnblogs.com/hzoi-Cu/p/18452209

相关文章

  • Linux csplit命令
    csplit命令在Linux中用于将文件分割成多个部分,基于指定的模式或固定数量的行。与split命令不同,csplit允许更复杂的分割条件,例如基于正则表达式匹配或特定字符的出现次数。基本语法csplit[选项]文件名模式文件名:要分割的文件。模式:分割文件的依据,可以是正则表达式或数字。......
  • P10641 BZOJ3252 攻略
    题目链接简要题意给定一个有\(n\)个结点的树,树有点权且点权为正整数。现选取\(k\)条从根结点出发到叶子结点的简单路径,求这些路径的并集上所有结点的点权之和的最大值。主要算法贪心,树链剖分,(线段树合并)思路一个显然的贪心,每次选一点点权和最大的链,再讲这条链清为0。正......
  • 【1024程序猿节】IT人#摸鱼计划#,多重奖励等你来拿!
    10月摸鱼计划如期而至,全新上线3款活动任务,还有多重奖励等你来拿!【活动时间】发文时间:2024年10月8日—2024年10月31日【活动任务】以下任务福利可同享!!同时,我们为大家整理了容易被百度收录的关键词,当你写作的时候,可以直接选择热点且擅长的关键词进行博文创作。 直达热点关键词库>>任......
  • Day1 备战CCF-CSP练习
    Day1201403-1问题描述有$N$个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数($a$和$-a$为一对相反数)。输入格式第一行包含一个正整数$N$。$(1≤N≤500)$。第二行为$N$个用单个空格隔开的非零整数,每个数的绝对值不超过$1000$,保证这些整数各......
  • 2024年10月8日大盘行情
    2024年5月中旬开始,大盘一直下跌,每天的交易额缩减到5000亿左右,人气低迷。2024年9月20日左右,出台了一系列提振经济和股市的政策,十一假期前的一周,大盘快速拉升,一周时间走完了半年的行情。很多人担心节后第一天会下杀,节前清空了仓位。节后第一天几乎涨停开盘,然后盘中下杀,最终收盘有所......
  • mfc100u.dll丢失找不到,win10电脑mfc100u.dll缺失的解决方法
    Mfc100u.dll是MicrosoftVisualStudio2010的一个重要动态链接库文件,主要用于支持基于MicrosoftFoundationClasses(MFC)的应用程序运行。当在Windows10系统中遇到“找不到Mfc100u.dll”或“Mfc100u.dll丢失”等错误提示时,意味着某些应用程序可能无法正常启动或运行。本文......
  • P1072 「NOIP2009TG」Hankson 的趣味题
    一个简单的想法就是枚举\(x\)然后判断,由题意可知\(x\)一定是\(b_1\)的因数。考虑较难的情况,当\(b_1\)较大不能直接枚举\(x\)该怎么做。因为\(\operatorname{lcm}(x,b_0)=b_1\),所以\(\dfrac{b_1}{b_0}\)的每种质因子,其在\(x\)中的数量和在\(b_1\)中的数量肯定是......
  • 不用工具直接从微软官网下载Win10正式版ISO镜像的技巧
    不用工具直接从微软官网下载Win10正式版ISO镜像的技巧发表于2018年12月25日23:21:24由MS酋长我们在重装Win10系统时需要用到ISO镜像,并且微软官网也有专门的“下载Windows10”页面,但问题是,你打开该页面后会发现,微软并没有直接提供Win10ISO镜像下载,而是提供了《微软Windows10......
  • 『模拟赛』CSP-S模拟10
    Rank没学线性基输麻了,A.欧几里得的噩梦线性基,输麻了。B.清扫思维题,差点签了。(感觉其实不是很难啊,没有紫的水平)一个叶子结点和另一个叶子结点的最短路径一定经过它的父节点。根据这一性质可以让整棵树的合法性拆分成每个节点的合法性。考虑如何判断每个节点的合法性。......
  • 10 月 8 日 A 股市场惊现暴涨行情!你看懂了吗?
    2024年10月8日,这一天注定将被载入A股市场的史册!创业板指全天大涨17.25%,沪深两市成交额超3.45万亿,再创历史新高!市场全天大幅高开回落后再度走高,创业板指更是续创历史单日最大涨幅。如此惊人的行情,究竟是怎么回事呢?让我们一起来深入分析。一、市场数据详情沪深两市成......