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

多校A层冲刺NOIP2024模拟赛07

时间：2024-10-15 20:23:37浏览次数：6  
标签：07 int rep 多校 long st using NOIP2024 define

rank 7，T1 100pts，T2 0pts，T3 70pts，T4 16pts

accoder上rank31，同分

限速（speed）

签，糖。

打的\(O(m\log V)\)的。

考虑分类讨论，有两种情况。

  1. 最大值是由最小的转化过来的，那么就是看边权\(\le k\)的是否可以构成一颗最大生成树，时间复杂度\(O(m\log m)\)

  2. 最大值是由更大的减下来的，发现如果小的可以，那么大的也可以，答案具有单调性，考虑二分答案。假设当前二分到的答案为\(mid\)，那么\(check(mid)\)表示可否使用边权\(\le mid\)的构成一个生成树。但这个生成树必须强制将边权\(\le mid\)的最大的边加入进去，剩下的跑最小生成树，然后记录该生成树需要的边，如果有边权\(>k\)，那么答案\(+=边权-k\)

最后答案取min，时间复杂度\(O(m\log m + m\log V)\)

然而事实是只需要求最小生成树和边权\(\le k\)构成的最大生成树即可

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(#x".in","r",stdin)
#define outfile(x) freopen(#x".out","w",stdout)
#define errfile(x) freopen(#x".err","w",stderr)
#define ansfile(x) freopen(#x".ans","w",stdout)
#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),*OutFile = outfile(out);
    // FILE *ErrFile = errfile(err);
#else
    FILE *Infile = infile(speed),*OutFile = outfile(speed);
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define int long long
const int N = 2e5 + 10,M = 2e5 + 10,inf = 0x3f3f3f3f3f3f3f3f;
int fa[N],n,m,k,ans = inf;
struct node{
    int u,v,w;
    bool operator < (node x) const{return w < x.w;}
}e[M];
int get_fa(int x){return x==fa[x]?x:fa[x] = get_fa(fa[x]);}
bitset<N> vis;
inline bool check1(int mid){
    rep(i,1,n,1) fa[i] = i;
    rep(i,1,m,1) vis[i] = false;
    int pos = upper_bound(e+1,e+1+m,node{0,0,mid}) - e - 1;
    drep(i,pos,1,1){
        int fx = get_fa(e[i].u),fy = get_fa(e[i].v);
        if(fx == fy) continue;
        fa[fx] = fy;
        vis[i] = true;
    }
    rep(i,2,n,1) if(get_fa(i) != get_fa(i-1)) return false;
    return true;
}
inline void get_ans1(int l,int r){
    bool flag = check1(k);
    int pos = upper_bound(e+1,e+1+m,node{0,0,k}) - e - 1,res = inf;
    if(!flag) return;
    drep(i,pos,1,1){if(vis[i]){res = e[i].w;break;}}
    ans = min(ans,abs(res-k));
}
inline bool check2(int mid){
    rep(i,1,n,1) fa[i] = i;
    rep(i,1,m,1) vis[i] = false;
    int pos = upper_bound(e+1,e+1+m,node{0,0,mid}) - e - 1;
    int fx = get_fa(e[pos].u),fy = get_fa(e[pos].v);
    if(fx != fy) fa[fx] = fy,vis[pos] = true;
    rep(i,1,pos-1,1){
        int fx = get_fa(e[i].u),fy = get_fa(e[i].v);
        if(fx == fy) continue;
        fa[fx] = fy;
        vis[i] = true;
    }
    rep(i,2,n,1) if(get_fa(i) != get_fa(i-1)) return false;
    return true;
}
inline void get_ans2(int l,int r){
    if(l > r) return;
    int res = -inf;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check2(mid)) res = mid,r = mid - 1;
        else l = mid + 1;
    }
    int emm = 0;
    int pos = upper_bound(e+1,e+1+m,node{0,0,res}) - e - 1;
    if(res == -inf) emm = inf;
    if(res != -inf) check2(res);
    drep(i,pos,1,1){
        if(e[i].w <= k) break;
        if(!vis[i]) continue;
        emm += abs(k-e[i].w);
    }
    ans = min(ans,emm);
}
inline void solve(){
    cin>>n>>m>>k;
    rep(i,1,m,1) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+1+m,[](node x,node y){return x.w < y.w;});
    get_ans1(0,k);get_ans2(k+1,e[m].w);
    cout<<ans<<'\n';
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

酒鬼 （drunkard）

赛时题没看懂，部分分不会打。

大力分讨加大模拟，牛魔题。

考虑到合法状态与\(p_i+q_i\)的奇偶性有关，如果\(p_i+q_i\)的奇偶性不同，那么就是无解。而且相邻的时刻移动距离不能超过它们的时间差。

但是发现当\(p_i=1\)时不用保证奇偶性一致，因为是从1开始的。但是要保证时刻小于最晚移动时间。

然后用一个\(map/set\)记录一下每个时间对应的值，模拟就完了。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(#x".in","r",stdin)
#define outfile(x) freopen(#x".out","w",stdout)
#define errfile(x) freopen(#x".err","w",stderr)
#define ansfile(x) freopen(#x".ans","w",stdout)
#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),*OutFile = outfile(out);
    // FILE *ErrFile = errfile(err);
#else
    FILE *Infile = infile(drunkard),*OutFile = outfile(drunkard);
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int inf = 0x3f3f3f3f;
int n,m,nmn = 0,nmx = inf;
bool flag = true;
#define pii pair<int,int>
#define mk make_pair
map<ll,pii> mp;
inline bool check(pii p1,pii p2){
    if(abs(p2.first - p1.first) > p2.second - p1.second) return false;
    if(p1.first != 1 && p1.second <= nmn) return false;
    if(p2.first != 1) nmx = min(nmx,p2.second - p2.first + 1);
    if(p1.first == 1 && p1.second <= nmx){
        if((abs(p2.first - p1.first)&1) != ((p2.second-p1.second)&1))
            nmn = max(nmn,p1.second + 1);
        return true;
    }
    if((abs(p2.first - p1.first)&1) != ((p2.second - p1.second)&1)) return false;
    return true;
}
inline void solve(){
    cin>>n>>m;
    mp[0] = mk(1,0);
    rep(test,1,m,1){
        string op;cin>>op;
        if(op[1] == 'l'){
            int p,q;cin>>p>>q;
            if(!flag) continue;
            auto it = mp.find(q);
            if(it != mp.end()){
                if(it->second.first != p) flag = false;
                continue;
            }
            it = mp.lower_bound(q);
            if(it != mp.end() && !check(mk(p,q),it->second)){flag = false;continue;}
            it--;
            if(!check(it->second,mk(p,q))) {flag = false;continue;}
            mp[q] = mk(p,q);
        }
        if(op[1] == 'i'){
            if(!flag){cout<<"bad\n";continue;}
            cout<<nmn<<'\n';
        }
        if(op[1] == 'a'){
            if(!flag){cout<<"bad\n";continue;}
            if(nmx == inf) cout<<"inf\n";
            else cout<<nmx<<'\n';
        }
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

距离（distance）

赛时打的\(O(n^2\log^2 n)\)。

有一个性质\(a+b = min(a,b)+max(a,b)\)，所以\(\min(∣a_x−a_y∣, ∣b_x − b_y∣)=|a_x-a_y|+|b_x-b_y|-\max(|a_x-a_y|,|b_x-b_y|)\)。然后发现后面的就是切比雪夫距离，转成曼哈顿距离，就变成了\(|p_x-p_y|+|q_x-q_y|\)，其中\(p_x=\frac{a_x+b_x}{2},q_x=\frac{a_x-b_x}{2}\)

然后就变成了维护\(\sum\limits_{x\in Subtree_u}\sum\limits_{y\in Subtree_u}|a_x-a_y|+|b_x-b_y|-|p_x-p_y|-|q_x-q_y|\)，分开维护，用线段树维护，拆绝对值，考虑到\(ans_x=ans_{ls}+ans_{rs}+sum_{ls}\times val_{rs}-sum_{rs}\times val_{ls}\)，其中\(ls/rs\)表示\(x\)的左/右儿子，\(val_x\)表示\(x\)和，\(sum_x\)表示\(x\)数的数量，这个线段树合并即可维护。

发现\(p,q\)有\(/2\)不好维护，考虑先乘二，然后乘上\(inv(2)\)即可。

最后答案要乘上二，因为反过来还有一个。

时间复杂度\(O(n\log n)\)

fhq_treap也可以维护，也是\(O(n\log n)\)的。

DSU On Tree也可以，但DSU On Tree比较慢，是\(O(n\log^2 n)\)。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(#x".in","r",stdin)
#define outfile(x) freopen(#x".out","w",stdout)
#define errfile(x) freopen(#x".err","w",stderr)
#define ansfile(x) freopen(#x".ans","w",stdout)
#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),*OutFile = outfile(out);
    // FILE *ErrFile = errfile(err);
#else
    FILE *Infile = infile(distance),*OutFile = outfile(distance);
    //FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define eb emplace_back
#define All(x) x.begin(),x.end()
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;
        char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
    inline void write(char x){pc(x);}
    template<class T,class... Args>
    inline void write(T x,Args... argc){write(x);write(argc...);}
}using namespace IO;
const int N = 5e5 + 10,mod = 1e9 + 7;
int n,a[5][N],ans[N],np,rt[N];
vector<int> e[N],num[5];
struct Segment_Tree{
    struct segment_tree{
        int lc,rc,val,sum,ans;
        #define lc(x) tree[x].lc
        #define rc(x) tree[x].rc
        #define val(x) tree[x].val
        #define sum(x) tree[x].sum
        #define ans(x) tree[x].ans
    }tree[N*25];
    int tot = 0;
    inline void P(int k){
        sum(k) = sum(lc(k)) + sum(rc(k));
        val(k) = (val(lc(k)) + val(rc(k)))%mod;
    }
    void I(int &k,int l,int r,int pos,int val){
        if(!k) k = ++tot,lc(k) = rc(k) = val(k) = sum(k) = ans(k) = 0;
        if(l == r) return sum(k)++,val(k) = (val(k) + num[np][val])%mod,void();
        int mid = (l + r) >> 1;
        if(pos <= mid) I(lc(k),l,mid,pos,val);
        else I(rc(k),mid+1,r,pos,val);
        P(k);
    }
    void Merge(int &x,int y){
        if(!x) return x = y,void();
        if(!y) return;
        sum(x) += sum(y);
        val(x) = (val(x) + val(y))%mod;
        Merge(lc(x),lc(y));Merge(rc(x),rc(y));
        ans(x) = (0ll + ans(lc(x)) + ans(rc(x)) + 1ll*val(rc(x))*sum(lc(x))%mod - 1ll*val(lc(x))*sum(rc(x))%mod + mod)%mod;
    }
}T;
inline void pre(int p){
    num[p].eb(INT_MIN);
    rep(i,1,n,1) num[p].eb(a[p][i]);
    sort(All(num[p]));
    num[p].erase(unique(All(num[p])),num[p].end());
    rep(i,1,n,1) a[p][i] = lower_bound(All(num[p]),a[p][i]) - num[p].begin();
}
void dfs(int x,int f){
    T.I(rt[x],1,n,a[np][x],a[np][x]);
    for(int y:e[x]){
        if(y == f) continue;
        dfs(y,x);
        T.Merge(rt[x],rt[y]);
    }
    ans[x] = (ans[x] + T.ans(rt[x]))%mod;
}
inline void solve(){
    read(n);
    rep(i,2,n,1){int u,v;read(u,v);e[u].eb(v);e[v].eb(u);}
    rep(i,1,n,1) read(a[1][i],a[2][i]),a[3][i] = a[1][i]+a[2][i],a[4][i] = a[1][i] - a[2][i];
    rep(i,1,4,1) pre(i);
    drep(i,4,1,1){
        rep(j,1,n,1) rt[j] = 0;
        T.tot = 0,np = i;dfs(1,0);
        if(i == 3) rep(j,1,n,1) ans[j] = (-500000004ll*ans[j]%mod+mod)%mod;
    }
    rep(i,1,n,1) write(ans[i]*2%mod,'\n');
}
signed main(){solve();}

update:给神卡常卡过了，学习了一个快速取模的Barrett约减。

团队选拔（selection）

赛时打的特殊性质，但好像正解也是线段树合并。

\(n\le 10\quad O(3^n)\)搜索即可。

\(\forall i\in [1,n]\quad a_i=1\)，打表可以找出规律，\(O(n)\)

好难不会。

点此查看代码 
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(#x".in","r",stdin)
#define outfile(x) freopen(#x".out","w",stdout)
#define errfile(x) freopen(#x".err","w",stderr)
#define ansfile(x) freopen(#x".ans","w",stdout)
#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),*OutFile = outfile(out);
    // FILE *ErrFile = errfile(err);
#else
    FILE *Infile = infile(selection),*OutFile = outfile(selection);
    //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,mod = 998244353;
int st[18][N],n,a[N],lg[N];
inline void st_pre(){
    lg[1] = 0;
    rep(i,2,n,1) lg[i] = lg[i>>1]+1;
    int t = lg[n];
    rep(i,1,n,1) st[0][i] = a[i];
    rep(j,1,t,1) rep(i,1,n-(1<<j)+1,1){
        st[j][i] = __gcd(st[j-1][i],st[j-1][i+(1<<(j-1))]);
    }
}
inline int Q(int l,int r){
    int k = lg[r-l+1];
    return __gcd(st[k][l],st[k][r-(1<<k)+1]);
}
namespace S1{
    int b[N],ans = 0,vis[N],f[N],k[N];
    inline void get_ans(){
        int gcd = 0;
        bool flag = false;
        set<int> st;
        rep(i,1,n,1) k[i] = 0;
        rep(i,1,n,1){
            if(b[i] == 1)gcd = a[i],flag = true,k[i]++;
            if(!b[i] && vis[i]) st.insert(a[i]),k[i]++;
            if(b[i] != 1 && flag) gcd = __gcd(gcd,a[i]),k[i]++;
            if(b[i] == -1){st.insert(gcd);flag = false;}
        }
        if(st.size() < 2) rep(i,1,n,1) f[i] += k[i];
    }
    void dfs(int now,bool flag){
        if(now == n+1){
            if(!flag) return;
            else get_ans();
            return;
        }
        b[now] = 0;vis[now] = false;
        dfs(now+1,flag);
        b[now] = flag?1:-1;
        dfs(now+1,flag^1);
        if(flag) b[now] = 0,vis[now] = true,dfs(now+1,true);
    }
    inline void solve(){
        dfs(1,true);
        rep(i,1,n,1) cout<<f[i]<<' ';
    }
}
namespace S2{
    int f[N],g[N],ans[N];
    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(){
        f[1] = g[1] = 1;
        f[2] = 1,g[2] = 3;
        rep(i,3,n,1) 
            f[i] = (f[i-1]+f[i-2])%mod,
            g[i] = (g[i-1]+g[i-2])%mod;
        ans[1] = 1ll*f[n]*g[n]%mod;
        rep(i,2,ceil(n/2.0),1)
            ans[i] = (ans[i-1]+1ll*f[n-(2*(i-1))]*g[n-(2*(i-1))]%mod)%mod;
        rep(i,n/2+1,n,1) ans[i] = ans[n-i+1];
        rep(i,1,n,1) cout<<ans[i]<<' ';
    }  
} 
inline void solve(){
    cin>>n; rep(i,1,n,1) cin>>a[i];
    // st_pre();
    int tot = 0;
    rep(i,1,n,1) if(a[i] == 1) tot++;
    if(tot == n) return S2::solve(),void();
    return S1::solve(),void();
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    solve();
}

挂个官解和std

image

image

image

点此查看代码 
#include<bits/stdc++.h>
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
	char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=998244353,maxn=100005;
struct sode{int l,r,v;}st[maxn],bl[maxn];
struct node{int l,r,x,v;}A[maxn*30],B[maxn*30];
struct Seg{int l,r,v;}seg[2][maxn];
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
inline int dqm(int x) {return x<0?x+mod:x;}
inline int qm(int x) {return x>=mod?x-mod:x;} 
inline int cmp(const node &A,const node &B){
	return A.v==B.v?A.x<B.x:A.v<B.v;
}
inline int ctp(const node &A,const node &B) {
	return A.v==B.v?A.x>B.x:A.v<B.v;
}
int n,a[maxn],top,sa,sb,lp,sz[2],ans,pre[maxn];
int l[maxn*3],r[maxn*3],tag[maxn*3],d[maxn*3];
inline void pushup(int i) {d[i]=qm(d[i<<1]+d[i<<1|1]);}
inline void pushr(int i,int v) {
	tag[i]=v;d[i]=1ll*(r[i]-l[i]+1)*v%mod;
}
inline void pushdown(int i) {
	if(tag[i]==-1) return;pushr(i<<1,tag[i]);
	pushr(i<<1|1,tag[i]);tag[i]=-1;
}
void bud(int x,int y,int i) {
	l[i]=x,r[i]=y,tag[i]=-1;if(x==y) return;
	int mid=x+y>>1;bud(x,mid,i<<1),bud(mid+1,y,i<<1|1);
}
void chg(int x,int y,int v,int i) {
	if(x<=l[i]&&y>=r[i]) {pushr(i,v);return;}
	int mid=l[i]+r[i]>>1;pushdown(i);
	if(x<=mid) chg(x,y,v,i<<1);
	if(y>mid) chg(x,y,v,i<<1|1);pushup(i);
}
int qry(int x,int y,int i) {
	if(x<=l[i]&&y>=r[i]) return d[i];
	int mid=l[i]+r[i]>>1;pushdown(i);
	return qm((x<=mid?qry(x,y,i<<1):0)+(y>mid?qry(x,y,i<<1|1):0));
}
inline void ins(int l,int r,int v,int o) {
	if(r>n)r=n;if(l<1)l=1;if(l>r) return;
	seg[o][++sz[o]]=(Seg){l,r,v};
}
inline void calc(int l,int r,int v) {
	pre[l]=qm(pre[l]+v),pre[r+1]=dqm(pre[r+1]-v);
} 
inline void solve(int L,int R) {
	int lst=0,v=0;sz[0]=sz[1]=0;
	for(int i=L;i<=R;++i) {
		chg(lst,A[i].x-1,v,1);
		ins(lst+1,A[i].x,qm(v+1),0);
		lst=A[i].x;
		v=qm(v+qry(A[i].l-1,A[i].r-1,1));
		v=qm(v+A[i].r-A[i].l+1);
	}  
	chg(lst,n,v,1);
	ins(lst+1,n+1,qm(v+1),0);
	lst=n+1,v=0;int rp=lp;
	while(lp<=sb&&B[lp].v==A[L].v) ++lp;
	for(int i=rp;i<lp;++i) {
		chg(B[i].x+1,lst,v,1);
		ins(B[i].x,lst-1,qm(v+1),1);
		lst=B[i].x;
		v=qm(v+qry(B[i].l+1,B[i].r+1,1));
		v=qm(v+B[i].r-B[i].l+1);
	}  
	chg(1,lst,v,1);ans=qm(ans+v);
	ins(0,lst-1,qm(v+1),1);
	std::reverse(seg[1],seg[1]+sz[1]+1);
	int x,y;x=0,y=0;
	while(x<=sz[0]&&y<=sz[1]) {
		calc(max(seg[0][x].l,seg[1][y].l),min(seg[0][x].r,seg[1][y].r),dqm(1ll*seg[0][x].v*seg[1][y].v%mod-1));
		if(seg[0][x].r<seg[1][y].r) ++x;
		else if(seg[0][x].r>seg[1][y].r) ++y;
		else if(seg[0][x].r==seg[1][y].r) ++y,++x;
	}
}
int main() {
	freopen("selection.in", "r", stdin);
	freopen("selection.out", "w", stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=top;++j) 
			st[j].v=gcd(st[j].v,a[i]);
		st[++top]=(sode){i,i,a[i]};
		int tot=0,x=i,y=i;
		for(int j=top-1;j>=0;--j) {
			if(st[j].v!=st[j+1].v) {
				bl[++tot].l=x,bl[tot].r=y;
				bl[tot].v=st[j+1].v;
				x=st[j].l,y=st[j].r;
			}else x=st[j].l;
		}
		top=0;
		while(tot) st[++top]=bl[tot--];
		for(int j=1;j<=top;++j) 
			A[++sa]=(node){st[j].l,st[j].r,i,st[j].v};
	}
	top=0;
	for(int i=n;i;i--) {
		for(int j=1;j<=top;++j) 
			st[j].v=gcd(st[j].v,a[i]);
		st[++top]=(sode){i,i,a[i]};
		int tot=0,x=i,y=i;
		for(int j=top-1;j>=0;--j) 
			if(st[j].v!=st[j+1].v) {
				bl[++tot].l=x,bl[tot].r=y;
				bl[tot].v=st[j+1].v;
				x=st[j].l,y=st[j].r;
			} else y=st[j].r;
		top=0;
		while(tot) st[++top]=bl[tot--];
		for(int j=1;j<=top;++j) 
			B[++sb]=(node){st[j].l,st[j].r,i,st[j].v};
	}
	std::sort(A+1,A+sa+1,cmp);std::sort(B+1,B+sb+1,ctp);
	int L=1;lp=1;
	bud(0,n+1,1);
	for(int i=2;i<=sa+1;++i) 
		if(A[i].v!=A[i-1].v) 
			solve(L,i-1),L=i;
	for(int i=1;i<=n;i++)pre[i]=qm(pre[i-1]+pre[i]);
	for(int i=1;i<=n;i++)printf("%d ",dqm(ans-pre[i]));
	return 0;
}

标签：07,int,rep,多校,long,st,using,NOIP2024,define
From： https://www.cnblogs.com/hzoi-Cu/p/18468355

相关文章

  • NOIP2024集训Day52 图论
    NOIP2024集训Day52图论A.[CF1253F]CheapRobot先用Dijkstra求出每个点离他最近的关键点的距离，设点\(u\)的距离为\(dis_u\)。设\(u\)的容量为\(x_u\)，那么一定满足\(c-dis_u\gex_u\gedis_u\)，因为它一定要能够从最近的关键点走过来，再走回最近的关键点。那么如......
  • GZ073 网络系统管理赛项赛题第5套A模块
    2023****年全国职业院校技能大赛网络系统管理赛项模块A：网络构建（样题10）目录任务描述…3任务清单…3（一）基础配置…3（二）有线网络配置…3（三）无线网络配置…5（四）出口网络配置…7附录1：拓扑图…8附录2：地址规划表…9任务描述CII集团公司业务不断发展壮大，为适应IT......
  • 多校A层冲刺NOIP2024模拟赛07
    多校A层冲刺NOIP2024模拟赛07\(T1\)A.限速（speed）\(40pts\)设最终保留的边的权值构成的集合为\(S\)。那么其贡献为\(\begin{cases}k-\max\limits_{x\inS}\{x\}&\max\limits_{x\inS}\{x\}\lek\\\sum\limits_{x\inS}[x>k]\times(x-k)&\max......
  • [ABC062C]/[ARC074A] Chocolate Bar 题解
    神秘分讨题（？总共\(4\)中情况。第一种：三个竖的并列：ans=min(ans,(h%3>0)*w);。第二种：三个横的并列：ans=min(ans,(w%3>0)*h);。第三种：一个横的矩形，然后是两个竖着的。For(i,1,h){ intfst=i*w; intscd=(w/2)*(h-i); intthd=(w%2>0)*(h-i)+(w/2)*(h-i); ans=min(ans......
  • DLT645-2007 协议快速入门
    @目录DLT645-2007协议快速入门1.什么是DLT645-2007协议2.帧格式2.1帧起始符2.2地址域2.3控制码3.4数据长度3.5数据域2.6校验码CS2.7结束符2.8传输事项3.报文解析4.代码实例5.报文解析工具DLT645-2007协议快速入门1.什么是DLT645-2007协议DLT645目前主要使用......
  • 统计数字（2007年NOIP全国联赛提高组）
    题目描述某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。输入格式每组输入数据包含n+1行；第一行是整数n，表示自然数的个数；第2~n+1行，每行一个自......
  • 2024牛客暑期多校训练营4 - J. Zero （究极卡常）
    \(O(N^2)\)AC。输入后预处理?数量的前缀和。双层循环找所有的区间\([l,r]\)使区间内没有\(0\)，找到以后直接用逆元+快速幂求\(\frac{(r-l+1)^k}{2^{sum_{r}-sum_{l-1}}}\)，最后累加和。因为数据过水，这样已经能AC了。#include<cstdio>usingnamespacestd;constint......
  • NOIP2024集训Day49 图论
    NOIP2024集训Day49图论A.[BZOJ2348中山市选2011]杀人游戏最优决策一定是我们找到一个点，使它能够尽可能到达更多的点，然后我们会发现必须询问的人缩点后就是入度为\(0\)的点。如果剩下了一个人，那么这个人是可以被推出来的。即：入度为\(0\)的点是一定要被询问的，如果存在一......
  • NOIP2024集训Day50 图论
    NOIP2024集训Day50图论A.[JSOI2012]越狱老虎桥先边双缩点，建出边双生成树。在不额外加边的情况下，割掉树边会使子树内部断开；在加入边的情况下，若加入一条\(1-u\)的边，则形成了一个\(1-u\)的环，环无法通过割一条边断开；而连接树上两个节点\((u,v)\)的情况，把图展开后发......
  • 云电脑玩赛博朋克2077必备三个条件，以ToDesk为例
    云电脑近期成为不少用户玩游戏的首选，尤其是面对像《赛博朋克2077》这样硬件要求高的游戏时，价格实惠且性能极高的云电脑，简直是游戏玩家的福音。市面上虽说有众多云电脑可供我们选择，但小编试用过这么多后还是最推荐ToDesk的云电脑。覆盖的系统够全面，3060和4070配置足够玩游戏，而且......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99