济南day3

连续几天都有点炸

预计的分拿不到，调整好心态，考试的时候多想一下，think twice，code once

唉，什么情况啊

题解链接

0+0+0

T1读错题输出反了

n*m%2判断是否==1

40分暴力忘记取mod了，全炸了gg

70分暴力输出了中间变量，然后主席树写成了区间第k小，gg

建立10颗线段树维护前k大，因为k<=10

总结：以后认真点.....多推一下样例，合理分配时间，多思考

做完之后检查，最后几分钟不调新程序

下午

题解链接

我可能只能口头ac了，考完后都能说出正解，就是写不来，也许不吃饭就考不好？？？？，我好菜啊

10+20+10

没状态，笔记本不好用，其实T2和T3是都可以切的，但是做了T1，虽然最后想出来了，没写不出来，不值。

T1 找环dfs瞎搞找错了，做了2h，后边没法做了

#include<cstdio>

#include<vector>

#include<cstring>

using namespace std;

const int maxn = ;

struct node{

    int v,next;

}edge[maxn*];

int head[maxn*];

const int mod =1e9+;int num;

inline void add_edge(int u,int v) {

    edge[++num].v=v;edge[num].next=head[u];head[u]=num;

}

inline int read() {

    int x=,f=;

    char c=getchar();

    while(c<''||c>'') {if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<='')x=x*+c-'',c=getchar();

    return x*f;

}

bool vis[maxn*];

int n,m;bool flag=;

int dfs(int u,int f) {

    int cnt=;

    vis[u]=;

    for(int i=head[u];i;i=edge[i].next) {

        int v=edge[i].v;

        if(v==f)continue;

        if(vis[v])flag=;

        else cnt=(cnt+dfs(v,u))%mod;

    }

    return cnt%mod;

}

int rd[maxn];

int main () {

    n=read();m=read();

    for(int i=;i<=m;++i) {

        int a=read(),b=read();

        add_edge(a,b);add_edge(b,a);

    }

    long long ans=;

    for(int i=;i<=n;++i) {

        if(!vis[i]){

            flag=;

            int qqq=dfs(i,)%mod;

            if(!flag)ans=(ans%mod*qqq%mod)%mod;

            else ans=(ans<<)%mod;

        }

    }

    printf("%lld\n",ans);

}

T2 想出来了正解，没时间写了，暴力写炸

#include<cmath>

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long LL;

LL n,ans,cnt;

LL a[],k;

int main() {

//    freopen("endless.in","r",stdin);

//    freopen("endless.out","w",stdout);

    cin>>n>>k;

    LL x=n;

    while(x) {

        a[++cnt]=x%k;

        x/=k;

    }

    if(cnt%==) ans=pow(k,cnt/);

    else {

        for(int i=cnt;i>=1;i--) {

            if(a[i]>0&&i%2==0) {

                ans+=pow(k,i/2);

                break;

            }

            if(a[i]==&&i%) continue;

            ans+=a[i]*pow(k,i/);

            if(i==&&a[i]>) ans++;

        }

    }

    cout<<ans<<endl;

    return ;

}

T3 想出来了正解，没写，暴力写炸

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

#define maxn 200007

#define LL long long

int n,K;

int num=;

int val[maxn<<],pos[maxn<<],fa[maxn<<];

int clo[maxn<<],cle[maxn<<],lason[maxn<<],tot=;

struct node{

    int v,next;

}edge[maxn<<];

int head[maxn<<];

LL dis[maxn<<],tree[maxn<<],tag[maxn<<],ans=;//I64d见祖宗

void add_edge(int u,int v){

  edge[++num].v=v;edge[num].next=head[u];head[u]=num;

}

void dfs(int rt) {

    clo[rt]=++tot;cle[tot]=rt;

    for(int i=head[rt];i;i=edge[i].next) {

        if(edge[i].v==fa[rt]) continue;

        fa[edge[i].v]=rt;dis[edge[i].v]=dis[rt]+(LL)val[edge[i].v];

        dfs(edge[i].v);

    }

    lason[rt]=tot;

}

void merge(int l,int r,int rt) {

    tree[rt]=tree[rt<<];pos[rt]=pos[rt<<];

    if(tree[rt] < tree[rt<<|]) tree[rt]=tree[rt<<|],pos[rt]=pos[rt<<|];

    return ;

}

void pushdown(int rt) {

    if(!tag[rt]) return ;

    tag[rt<<]+=tag[rt];tag[rt<<|]+=tag[rt];

    tree[rt<<]-=tag[rt];tree[rt<<|]-=tag[rt];

    tag[rt]=;return ;

}

void build(int l,int r,int rt) {

    if(l==r) {

        tree[rt]=dis[cle[r]];

        pos[rt]=cle[r];return ;

    }

    int mid=(l+r)>>;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

    merge(l,r,rt);

}

void update(int l,int r,int rt,int ll,int rr,int c) {

    if(ll<=l&& r<=rr) {

        tree[rt]-=(LL)c;tag[rt]+=(LL)c;return ;

    }

    pushdown(rt);

    int mid=(l+r)>>;

    if(ll<=mid) update(l,mid,rt<<,ll,rr,c);

    if(rr>mid) update(mid+,r,rt<<|,ll,rr,c);

    merge(l,r,rt);

}

int main() {

    //freopen("tour.in","r",stdin);

    //freopen("tour.out","w",stdout);

    int u,v,now;

    scanf("%d%d",&n,&K);

    for(int i=;i<=n;i++) scanf("%d",val+i);

    for(int i=;i<n;i++)

        scanf("%d%d",&u,&v),add_edge(u,v),add_edge(v,u);

    dis[]=val[];

    dfs();

    build(,n,);

    while(K--) {

        if(!tree[]) break;

        ans+=tree[];now=pos[];

        while(val[now]) {

            update(,n,,clo[now],lason[now],val[now]);val[now]=;now=fa[now];

        }

    }

    printf("%lld\n",ans);

    return ;

}

巴特西

济南day3

最新文章

热门文章