牛客練習試合25

前言
私は料理が上手ですね.Tシャツに向かっていたのに
A
要求ans=Σni=1Σj|i 1 a n s=Σi=1 nΣj|i 1我々は奇跡的な銀殻を必要としないことに気づき,列挙主体を交換するだけで√nを行うことができる.

#include 
#include 
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

typedef long long LL;

void solve(LL n) {
    LL ans=0;
    for (LL i=1,j;i<=n;i=j+1) {
        j=n/(n/i);
        ans=(ans+(n/i)*(j-i+1));
    }
    printf("%lld
", ans);
}

int main(void) {
    int T; scanf("%d",&T);
    while (T--) {
        LL n; scanf("%lld",&n);
        solve(n);
    }
    return 0;
}

B
線分ツリー裸問題

#include 
#include 
#include 
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=200005;

int s[N<<2],ls[N<<2],rs[N<<2],a[N];

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void modify(int now,int tl,int tr,int x,int v) {
    if (tl==tr) {
        ls[now]=rs[now]=s[now]=1;
        return (void) (a[tl]=v);
    }
    int mid=(tl+tr)>>1;
    if (x<=mid) modify(now<<1,tl,mid,x,v);
    else modify(now<<1|1,mid+1,tr,x,v);
    ls[now]=ls[now<<1];
    if (ls[now]==(mid-tl+1)&&a[mid]1]) ls[now]+=ls[now<<1|1];
rs[now]=rs[now<<1|1];
if (rs[now]==(tr-mid)&&a[mid]1]) rs[now]+=rs[now<<1];
s[now]=std:: max(s[now<<1],s[now<<1|1]);
if (a[mid]1]) s[now]=std:: max(s[now],rs[now<<1]+ls[now<<1|1]);
}
int main(void) {
int n=read(),m=read();
rep(i,1,n) {
int x=read();
modify(1,1,n,i,x);
}
printf("%d", s[1]);
for (;m--;) {
int x=read(),y=read();
modify(1,1,n,x,y);
printf("%d", s[1]);
}
return 0;
}

C
各答えの前の係数は同じであることに気づいたので,O(t)が1波の係数を求めて対応する位置のaに乗じるだけでよい.

#include 
#include 
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)

typedef long long LL;
const int MOD=1000000007;
const int N=200005;

LL a[N],b[N],sum;
int n,m;

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

int main(void) {
    n=read(),m=read();
    rep(i,1,n) {
        a[i]=read();
        sum=(sum+a[i])%MOD;
    }
    LL tmp=1;
    rep(i,1,100000) {
        b[i]=(sum*tmp%MOD-b[i-1]+MOD)%MOD;
        tmp=tmp*(n-1)%MOD;
    }
    for (;m--;) {
        int x=read(),t=read();
        if (!t) printf("%lld
", a[x]);
        else printf("%lld
", (b[t]+((t&1)?(-1):(1))*a[x]+MOD)%MOD);
    }
    return 0;
}

D
私にはできませんでしたが、変なふるい+針で掃除する方法だと思います.
E
まず図がつながっていない肯定impossibleはいつimpossibleがあるかを考えて、橋が存在する時だけ、私たちはこの橋の辺に方向を定めて新しい図を強く連通してtarjanは橋を求めてそれから勝手にdfsを求めます

#include 
#include 
#include 
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=2000005;
const int E=2000005;

struct edge {int x,y,next;} e[E];
int ls[N],prt[N],edCnt=1;

void add_edge(int x,int y) {
    e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {y,x,ls[y]}; ls[y]=edCnt;
}

int dfn[N],low[N],vis[N];

int read() {
    int x=0,v=1; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
    return x*v;
}

void dfs(int now,int fa) {
    dfn[now]=low[now]=++dfn[0];
    for (int i=ls[now];i;i=e[i].next) {
        if (!dfn[e[i].y]) {
            dfs(e[i].y,now);
            low[now]=std:: min(low[now],low[e[i].y]);
        } else if (e[i].y!=fa) {
            low[now]=std:: min(low[now],dfn[e[i].y]);
        }
    }
}

void solve(int now) {
    vis[now]=1;
    for (int i=ls[now];i;i=e[i].next) {
        prt[i/2]=i&1;
        if (vis[e[i].y]) continue;
        solve(e[i].y);
    }
}

int main(void) {
    freopen("data.in","r",stdin);
    freopen("myp.out","w",stdout);
    int n=read(),m=read();
    rep(i,1,m) {
        int x=read(),y=read();
        add_edge(x,y);
    }
    dfs(1,-1);
    if (dfn[0]!=n) {
        puts("impossible");
        return 0;
    } int cnt=0;
    for (int i=2;i<=edCnt;i+=2) {
        if (low[e[i].x]!=low[e[i].y]) {
            cnt++;
        }
    }
    if (!cnt) {
        solve(1);
        rep(i,1,m) printf("%d", prt[i]);
    } else puts("impossible");
    return 0;
}

F
私にはできなかった