首页 > 其他分享 >【比赛】2022NOIP A层联测27

【比赛】2022NOIP A层联测27

时间：2022-11-13 21:37:51浏览次数：60  
标签：27 int res 2022NOIP ch 联测 include dp WR

A. 天平

image

点击查看代码 
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
int n,a[WR];
int ans;
int read(){
    int s=0,w=1;    
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int gcd(int x,int y){
    if(!y) return x;
    return gcd(y,x%y);
}
bool check(){
    for(int i=1;i<=n;i++){
        if(a[i]%ans) return false;
    }
    return true;
}
signed main(){
    freopen("weights.in","r",stdin);
    freopen("weights.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    int g=a[1];
    for(int i=2;i<=n;i++) g=gcd(g,a[i]);
    for(int i=1;i<=n;i++) a[i]/=g;
    sort(a+1,a+1+n);
    if(a[1]==1) printf("1\n");
    else{
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(gcd(a[i],a[j])==1){
                    printf("2\n");
                    fclose(stdin);
                    fclose(stdout);
                    return 0;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=j+1;k<=n;k++){
                    if(gcd(gcd(a[i],a[j]),a[k])==1){
                        printf("3\n");
                        fclose(stdin);
                        fclose(stdout);
                        return 0;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=j+1;k<=n;k++){
                    for(int l=k+1;l<=n;l++){
                        if(gcd(gcd(a[i],a[j]),gcd(a[k],a[l]))==1){
                            printf("4\n");
                            fclose(stdin);
                            fclose(stdout);
                            return 0;
                        }
                    }
                }
            }
        }
        int minn=a[n];
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                minn=min(minn,gcd(a[i],a[j]));
            }
        }
        for(int i=2;i<=n;i++){
            ans=minn;
            if(check()){
                printf("%lld\n",i);
                return 0;
            }
            int tmp=minn;
            minn=a[n];
            for(int j=1;j<=n;j++) minn=min(minn,gcd(tmp,a[j]));
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

B. 支配数据

image

但是由于我写的乱搞做法因此

点击查看代码 
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
struct Segment{
    int l,r,minval;
}seg[WR<<2];
struct SegmentTree{
    int lson,rson,minval,val,lzy;
}tree[WR*15];
int n,k;
int tot=1;
int a[WR];
int read(){
    int s=0,w=1;    
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
void pushup(int k){
    tree[k].val=tree[tree[k].lson].val+tree[tree[k].rson].val;
    tree[k].minval=min(tree[tree[k].lson].minval,tree[tree[k].rson].minval);
}
void pushdown(int k,int l,int r){
    if(!tree[k].lson) tree[k].lson=++tot;
    if(!tree[k].rson) tree[k].rson=++tot;
    tree[tree[k].lson].lzy=tree[tree[k].rson].lzy=tree[k].lzy;
    tree[tree[k].lson].minval=tree[tree[k].rson].minval=tree[k].lzy;
    int mid=(l+r)>>1;
    tree[tree[k].lson].val=mid-l+1;
    tree[tree[k].rson].val=r-mid;
    tree[k].lzy=0;
}
void build(int k,int l,int r){
    seg[k].l=l,seg[k].r=r,seg[k].minval=INF;
    if(l==r){
        seg[k].minval=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    seg[k].minval=min(seg[k<<1].minval,seg[k<<1|1].minval);
}
void modify(int &k,int l,int r,int L,int R,int val){
    if(k==0) k=++tot;
    if(l>=L&&r<=R){
        tree[k].minval=tree[k].lzy=val;
        tree[k].val=r-l+1;
        return;
    }
    if(tree[k].lzy) pushdown(k,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) modify(tree[k].lson,l,mid,L,R,val);
    if(R>mid) modify(tree[k].rson,mid+1,r,L,R,val);
    pushup(k);
}
int query(int k,int l,int r){
    if(seg[k].l>=l&&seg[k].r<=r){
        return seg[k].minval;
    }
    int mid=(seg[k].l+seg[k].r)>>1,res=INF;
    if(l<=mid) res=min(res,query(k<<1,l,r));
    if(r>mid) res=min(res,query(k<<1|1,l,r));
    return res;
}
void trans(int l,int r,int &L,int &R){
    if(r-l>=n){
        L=1,R=2*n;
        return;
    }
    l%=n,r%=n;
    if(l==0) l=n;
    if(r==0) r=n;
    if(l<=r){L=l,R=r;return;}
    else{L=l,R=n+r;return;}
}
int ask(int k,int l,int r,int L,int R){
    // cerr<<k<<" "<<l<<" "<<r<<endl;
    if(L<=l&&r<=R){
        if(k==0){
            int tmpl,tmpr;
            trans(max(L,l),min(R,r),tmpl,tmpr);
            return query(1,tmpl,tmpr);
        }
        if(tree[k].val==r-l+1) return tree[k].minval;
        int mid=(l+r)>>1,res=INF;
        if(L<=mid) res=min(res,ask(tree[k].lson,l,mid,L,R));
        if(R>mid) res=min(res,ask(tree[k].rson,mid+1,r,L,R));
        return res;
    }
    if(tree[k].lzy) pushdown(k,l,r);
    int res=INF,mid=(l+r)>>1;
    if(L<=mid){
        if(!tree[k].lson){
            int tmpl,tmpr;
            trans(max(L,l),min(R,mid),tmpl,tmpr);
            res=min(res,query(1,tmpl,tmpr));
        }else res=min(res,ask(tree[k].lson,l,mid,L,R));
    }
    if(R>mid){
        if(!tree[k].rson){
            int tmpl,tmpr;
            trans(max(L,mid+1),min(R,r),tmpl,tmpr);
            res=min(res,query(1,tmpl,tmpr));
        }else res=min(res,ask(tree[k].rson,mid+1,r,L,R));
    }
    return res;
}
signed main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=a[i+n]=read();
    build(1,1,n<<1);
    tree[1].minval=seg[1].minval;
    int Q=read(),root=1;
    while(Q--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            int val=read();
            modify(root,1,n*k,l,r,val);
        }else printf("%lld\n",ask(1,1,n*k,l,r));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

C. 信息学的尽头

image
image

点击查看代码 
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,mod=1e9+7,INF=9e18;
struct Edge{
    int pre,to,val;
}edge[WR<<1];
int n;
int head[WR],tot;
bool vis[WR];
int ans[WR];
int read(){
    int s=0,w=1;    
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
void add(int u,int v,int val){
    edge[++tot].pre=head[u];
    edge[tot].to=v;
    edge[tot].val=val;
    head[u]=tot;
}
int rng[WR],w[WR],st,cnt,len;
bool dfs1(int u,int root){
    vis[u]=true;
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to,val=edge[i].val;
        if(v==root) continue;
        if(vis[v]){
            st=v;
            rng[++cnt]=u;
            w[cnt]=val;
            len+=val;
            return true;
        }
        if(dfs1(v,u)){
            rng[++cnt]=u;
            w[cnt]=val;
            len+=val;
            if(u==st) return false;
            else return true;
        }
    }
    vis[u]=false;
    return false;
}
int sum[WR],sze[WR];
void dfs2(int u,int root){
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to,val=edge[i].val;
        if(vis[v]||v==root) continue;
        dfs2(v,u);
        sum[u]+=sum[v]+sze[v]*val;
        sze[u]+=sze[v];
    }
    sze[u]++;
}
void dfs3(int u,int root){
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to,val=edge[i].val;
        if(vis[v]||v==root) continue;
        ans[v]=ans[u]+(n-sze[v])*val-sze[v]*val;
        dfs3(v,u);
    }
}
int pre[WR],rec[WR];
signed main(){
    freopen("end.in","r",stdin);
    freopen("end.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        int u=read(),v=read(),val=read();
        add(u,v,val);add(v,u,val);
    }
    dfs1(1,0);
    for(int i=1;i<=(cnt<<1);i++) rng[i+cnt]=rng[i],w[i+cnt]=w[i],pre[i]=pre[i-1]+w[i];
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=cnt;i++) vis[rng[i]]=true;
    for(int i=1;i<=cnt;i++) dfs2(rng[i],0);
    int res=0;
    for(int i=cnt;i>1;i--){
        res+=w[i+1];
        rec[rng[i]]=res;
    }
    int tmp=0;
    for(int i=1;i<=cnt;i++) tmp+=sum[rng[i]]+min(len-rec[rng[i]],rec[rng[i]])*sze[rng[i]];
    for(int i=2;i<=cnt+1;i++){
        if(rec[rng[i]]<=len-rec[rng[i]]){
            st=i;break;
        }
    }
    res=0;
    for(int i=st;i<=cnt+1;i++) res+=sze[rng[i]];
    for(int i=cnt+1;i<=(cnt<<1);i++){
        if(i!=cnt+1){
            tmp+=res*w[i];
            tmp-=(n-res)*w[i];
            res+=sze[rng[i]];
            while(st<=i&&pre[i]-pre[st]>=len-pre[i]+pre[st]){
                tmp-=(pre[i]-pre[st])*sze[rng[st]];
                res-=sze[rng[st]];
                tmp+=(len-pre[i]+pre[st])*sze[rng[st]];
                st++;
            }
        }
        ans[rng[i]]=tmp;
    }
    for(int i=1;i<=cnt;i++) dfs3(rng[i],0);
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

D. 球对称薛定谔方程

请跳转这里

点击查看代码 
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=310,INF=9e18;
int read(){
    int s=0,w=1;    
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int K,n,mod;
int dp[WR][WR][WR];
signed main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    n=read(),K=read(),mod=read();
    dp[0][1][0]=1;
    for(int i=0;i<=n;i++){
        for(int j=1;j<=K;j++){
            for(int k=i;k>=0;k--){
                if(k) dp[i][j][k-1]=(dp[i][j][k-1]+dp[i][j][k])%mod;
                dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k]*(k+1)%mod)%mod;
            }
            dp[i][j+1][i]=(dp[i][j+1][i]+dp[i][j][0])%mod;
        }
    }
    printf("%lld\n",dp[n+1][K][0]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

标签：27,int,res,2022NOIP,ch,联测,include,dp,WR
From： https://www.cnblogs.com/WintersRain/p/16887005.html

相关文章

  • (AtCoder Beginner Contest 277)E(分层图+最短路 or bfs搜两种状态）
    E-CrystalSwitches题目大意：给你n个点,m条边，连接成一个无向图，每个边最初有一个状态（0or1）表示是否能够通过，同时给k个开关位于k的顶点上，每次点击开关会使得所有路的状......
  • CF1027E Inverse Coloring
    考场上没敲出来（其实想到就挺好写的捏组数据手动模拟一下：\(\begin{bmatrix}1&0&1&1&1&0&1\\1&0&1&1&1&0&1\\0&1&0&0&0&1&0\\1&0&1&1&1&0&1\\0&1&0&0&0&1&0\\0......
  • ABC277E 题解
    前言题目传送门！更好的阅读体验？非常套路的分层图，纪念赛时切掉了。思路我们以样例来解释。首先，这是最基础的图。我们把图分成两层：第一层是原本\(w=1\)的路可以通......
  • ABC277D 题解
    前言题目传送门！或许更好的阅读体验？比较简单的模拟。思路首先把\(a_i\)排序。每次往后一直跑，如果不能再取了，就停下。但是这样做是\(O(n^2)\)的。我们需要优化。......
  • 2022NOIP A层联测26 乘筛积 放进去 最长路径 生成树的传说
    T1[转化枚举角度]给出长度是n的a序列，和长度是m的b序列，给出Q组询问\([p,q]\),求\(\sum_{p*i+q*j=C}^{}ai*bj\)。（n,m,C,q<=3e5）考场上来想枚举，对于\(max(p,q)>=\sqrt{C}\),......
  • AtCoder Beginner Contest 277 D Takahashi's Solitaire
    Takahashi'sSolitaire双指针&&尺取先排个序，然后把数组扩展到\(2\timesn\)，为了处理循环的情况然后双指针跑一下，限定\(r\)扩展的条件为：当前数字等于前一个或者......
  • AtCoder Beginner Contest 277 F Sorting a Matrix
    SortingaMatrix拓扑序首先可以明确无论怎么交换行列，原本在同一行或者同一列的元素，还是会处于同一行或者同一列条件一每行每行地看，如果能满足从小到大的条件，说明第......
  • AtCoder Beginner Contest 277 E Crystal Switches
    CrystalSwitches分层图+\(01bfs\)按钮的操作就是走分层图的边因此就构建两张图，然后将特殊点加一个双向边\(01bfs\)跑一下就行#include<iostream>#include<cstd......
  • 已知：3的a平方加一次方+3的a平方减一次方=270，求a？
    END......
  • AtCoder Beginner Contest 277 题解
    掉大分力（悲A-^{-1}直接模拟。#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false)#defineTIEcin.tie(0),cout.tie(0)#defineintlonglongusing......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99