难度跟第一天差不多,省选左右吧。

Problem A: 余数

题目描述:

题解:

拆开来

\sum _{i=1}^m n\%i =\sum _{i=1}^mn-\sum _{i=1}^m i* \left \lfloor \frac{n}{i} \right \rfloor

后面整除分块,完了。

注意什么东西都要模一下,会爆longlong!!!!!

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define Mod 1000000007
#define ll long long
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll n,m,ans;
il ll S(ll x)
{
    return (x*(x+1)/2)%Mod;
}
il ll calc()
{
    ll res=0;
    for(ll l=1,r;l<=m&&l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        res=(res+(S(r%Mod)-S((l-1)%Mod))*((n/l)%Mod)%Mod+Mod)%Mod;
    }
    return (res+Mod)%Mod;
}
int main()
{
    //freopen("A.txt","r",stdin);
    n=read(),m=read();
    ans=(n%Mod*(m%Mod)%Mod-calc()+Mod)%Mod;
    //cout<<calc<<endl;
    cout<<ans<<endl;
}

Problem B: 糖果

题目描述:

题解:

原题是CF798D。

我排序后爆搜+特判一些可以卡的点拿了80pts

结论还是挺难想的。

代码:

80pts暴力:

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define ll long long
#define int ll
//#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
char In[Max],*ss=In,*tt=In;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,sa,sb,m,v,flag,ans[Max];
struct node
{
    int a,b,id;
}e[Max];
il bool cmp(node x,node y)
{
    if(x.a!=y.a) return x.a>y.a;
    if(x.b!=y.b) return x.b>y.b;
    return x.id>y.id;
}
il bool cmp2(node x,node y)
{
    if(x.b!=y.b) return x.b>y.b;
    if(x.a!=y.a) return x.a>y.a;
    return x.id>y.id;
}
il bool check()
{
    int s1=0;
    for(int i=1;i<=m;i++) s1+=e[ans[i]].a;
    if(s1<=sa) return 0;
    s1=0;
    for(int i=1;i<=m;i++) s1+=e[ans[i]].b;
    if(s1<=sb) return 0;
    return 1;
}
il void print()
{
    cout<<m<<endl;
    for(int i=1;i<=m;i++) printf("%d ",e[ans[i]].id);
    puts("");
    //cout<<sa<<' '<<sb<<endl;
    exit(0);
}
il void dfs(int x,int tot)
{
    if(x==n+1) return;
    if(tot==m+1)
    {
        if(check()) print();
        return;
    }
    ans[tot]=x;
    dfs(x+1,tot+1);
    ans[tot]=0;
    dfs(x+1,tot);
}
signed main()
{
    //freopen("B.in","r",stdin);
    //freopen("B.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) e[i].a=read(),sa+=e[i].a,e[i].a*=2,e[i].id=i;
    for(int i=1;i<=n;i++) e[i].b=read(),sb+=e[i].b,e[i].b*=2;
    sort(e+1,e+1+n,cmp);
    for(int i=1;i<n;i++) if(e[i].a!=e[i+1].a) flag=1;
    m=(n/2)+1;
    if(!flag)
    {
        cout<<m<<endl;
        for(int i=1;i<=m;i++) printf("%d ",e[i].id);
        puts("");
        exit(0);
    }
    for(int i=1;i<=m;i++) ans[i]=i;
    if(check()) print();
    sort(e+1,e+1+n,cmp2);
    if(check()) print();
    sort(e+1,e+1+n,cmp);
    int s1=0,s2=0;
    for(int i=1;i<=m/2;i++) s1+=e[i].a,s2+=e[i].b;
    sort(e+1,e+1+n,cmp2);
    for(int i=1;i<=(m-(m/2));i++) s1+=e[i].a,s2+=e[i].b;
    if(s1>sa&&s2>sb)
    {
        cout<<m<<endl;
        for(int i=1;i<=m-(m/2);i++) printf("%d ",e[i].id);
        sort(e+1,e+1+n,cmp);
        for(int i=1;i<=m/2;i++) printf("%d ",e[i].id);
        puts("");
        exit(0);
    }
    for(int i=1;i<=m/2+1;i++) s1+=e[i].a,s2+=e[i].b;
    sort(e+1,e+1+n,cmp2);
    for(int i=1;i<=(m-(m/2)-1);i++) s1+=e[i].a,s2+=e[i].b;
    if(s1>sa&&s2>sb)
    {
        cout<<m<<endl;
        for(int i=1;i<=m-(m/2+1);i++) printf("%d ",e[i].id);
        sort(e+1,e+1+n,cmp);
        for(int i=1;i<=m/2+1;i++) printf("%d ",e[i].id);
        puts("");
        exit(0);
    }
    dfs(1,1);
    puts("-1");
}

满分做法:

#include <bits/stdc++.h>
#define il inline
#define Max 100005
#define ll long long
#define int ll
using namespace std;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int a,b,id;
}e[Max];
il bool cmp(node x,node y)
{
    if(x.a!=y.a) return x.a>y.a;
    return x.b>y.b;
}
int m,ans[Max];
il void print()
{
    cout<<m<<endl;
    for(int i=1;i<=m;i++) printf("%d ",e[ans[i]].id);
    puts("");
    //cout<<sa<<' '<<sb<<endl;
    exit(0);
}
int n,cnt;
signed main()
{
    n=read();m=n/2+1;
    for(int i=1;i<=n;i++) e[i].a=read(),e[i].a*=2,e[i].id=i;
    for(int i=1;i<=n;i++) e[i].b=read(),e[i].b*=2;
    sort(e+1,e+1+n,cmp);
    ans[++cnt]=1;
    if(n%2==0) ans[++cnt]=2;
    for(int i=cnt+1;i<=n;i+=2)
    {
        if(e[i].b>e[i+1].b) ans[++cnt]=i;
        else ans[++cnt]=i+1;
    }
    print();
}

Problem C: 虫子

题目描述:

题解:

实在是毒瘤。

我只写了50分做法,100分想出来了不会写也调不出来。

代码:

50pts:

#include <bits/stdc++.h>
#define il inline
#define Max 400005
#define ll long long
#define int long long
//#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
using namespace std;
char In[Max],*ss=In,*tt=In;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int t,nt;
}e[Max<<1];
int head[Max],d[Max],f[Max],sz[Max],w[Max],cnt[Max],tot=1,g[Max],n,m,ans,vst[Max];
il void add(int u,int v)
{
    e[++tot].t=v;
    e[tot].nt=head[u];
    head[u]=tot;
}
il void dfs(int u,int fa)
{
    //cout<<u<<endl;
    sz[u]=1,cnt[u]=1;
    d[u]=d[fa]+1;
    f[u]=fa;
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].t;
        if(v==fa||vst[i]) continue;
        //cout<<u<<' '<<v<<endl;
        dfs(v,u);
        cnt[u]+=sz[u]*sz[v]*2;
        sz[u]+=sz[v];
        //if(sz[v]>sz[wsn[u]]) wsn[u]=v;
    }
    g[u]=cnt[u]*w[u];
}
int opt;
signed main()
{
    n=read();
    for(int i=2;i<=n;i++)
    {
        int j=read();
        add(i,j),add(j,i);
    }
    for(int i=1;i<=n;i++) w[i]=read();
    dfs(1,0);
    for(int i=1;i<=n;i++) ans=ans+g[i];//,cout<<i<<' '<<g[i]<<" qwq\n";
    //cout<<ans<<endl;
    printf("%.10lf\n",1.0*ans/(1.0*n*n));
    m=read();
    while(m--)
    {
        opt=read();
        int u=read(),v=read();
        if(opt==1)
        {
            int t=v;
            if(d[u]<d[v]) while(f[t]!=u&&f[t]) t=f[t];
            if(f[t]==u) swap(u,v);
            for(int i=head[f[u]];i;i=e[i].nt)
            {
                if(e[i].t==u) vst[i]=vst[i^1]=1;
            }
            add(u,v),add(v,u);
            //cout<<u<<' '<<v<<endl;
            dfs(1,0);
            ans=0;
            for(int i=1;i<=n;i++) ans=ans+g[i];
            printf("%.10lf\n",1.0*ans/(1.0*n*n));
        }
        if(opt==2)
        {
            ans-=g[u];
            w[u]=v;
            g[u]=cnt[u]*w[u];
            ans+=g[u];
            //cout<<ans<<endl;
            printf("%.10lf\n",1.0*ans/(1.0*n*n));
        }
    }
}

100pts from Owen:

#include<bits/stdc++.h>
using namespace std;
typedef long long giant;
inline char nchar() {
    static const int bufl=1<<20;
    static char buf[bufl],*a,*b;
    return a==b && (b=(a=buf)+fread(buf,1,bufl,stdin),a==b)?EOF:*a++;
}
inline int read() {
    int x=0,f=1;
    char c=nchar();
    for (;!isdigit(c);c=nchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=nchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=1e5+1;
int fa[maxn],n,m;
giant ans=0,nn,a[maxn];
inline void print(giant x) {
    long double ret=(long double)x/nn;
    printf("%.12Lf\n",ret);
}
namespace lct {
    struct node {
        int ch[2],fa,size,vs;
        giant mtag,mul,w,as;
        // no makeroot, so no rev
    } t[maxn];
    inline bool rson(int x) {return t[t[x].fa].ch[1]==x;}
    inline bool isroot(int x) {return t[t[x].fa].ch[rson(x)]!=x;}
    inline void update(int x) {
        t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].vs+1;
        t[x].w=a[x]*(t[x].vs+1);
        t[x].as=t[t[x].ch[0]].as+t[t[x].ch[1]].as+t[x].w;
    }
    inline void tick(int x,giant mt) {
        t[x].mul+=mt*(t[x].vs+1);
        t[x].mtag+=mt;
    }
    inline void doit(int x) {
        if (t[x].mtag) {
            if (t[x].ch[0]) tick(t[x].ch[0],t[x].mtag);
            if (t[x].ch[1]) tick(t[x].ch[1],t[x].mtag);
            t[x].mtag=0;
        }
    }
    void down(int x) {
        if (!isroot(x)) down(t[x].fa);
        doit(x);
    }
    inline void rotate(int x) {
        int f=t[x].fa,d=rson(x),c=t[x].ch[d^1];
        if (!isroot(f)) t[t[f].fa].ch[rson(f)]=x;
        if (c) t[c].fa=f;
        t[x].fa=t[f].fa,t[f].fa=x,t[x].ch[d^1]=f,t[f].ch[d]=c;
        update(f),update(x);
    }
    inline void splay(int x) {
        down(x); // mtag
        while (!isroot(x)) isroot(t[x].fa)?rotate(x):(rson(x)==rson(t[x].fa)?(rotate(t[x].fa),rotate(x)):(rotate(x),rotate(x)));
    }
    inline void access(int x) {
        for (int last=0;x;x=t[last=x].fa) {
            splay(x);
            t[x].vs+=t[t[x].ch[1]].size-t[last].size;
            t[x].ch[1]=last;
            update(x);
        }
    }
    inline bool isanc(int x,int y) {
        access(y);
        splay(y);
        for (;!isroot(x);x=t[x].fa);
        return x==y;
    }
    inline void modfa(int x,int y) {
        assert(x!=y);

        if (isanc(x,y)) swap(x,y);

        int &f=fa[x]; // remember to change fa[x]=y
        access(f);
        splay(f);
        splay(x);
        int &sz=t[x].size;
        t[f].vs-=sz; // is this the real t[x].size? check it if error occurs
        tick(f,-sz); // change t[f].mtag ans mul
        update(f);
        ans-=t[f].as*sz*2;

        f=y;  // right?
        access(f);
        splay(f);
        t[x].fa=f;
        ans+=t[f].as*sz*2;
        tick(f,sz);
        t[f].vs+=sz;
        update(f);
    }

    inline void modval(int x,int y) {
        access(x);
        splay(x);
        ans+=(t[x].mul*2ll+1ll)*(y-a[x]);
        a[x]=y;
        update(x);
    }
}
namespace tree {
    vector<int> g[maxn];
    inline void add(int x,int y) {g[x].push_back(y);}
    void dfs(int x) {
        using namespace lct;
        int &vs=t[x].vs=0;
        giant tmp=1,&mul=t[x].mul=0; // calc ans
        for (const int &v:g[x]) {
            t[v].fa=x;
            dfs(v);
            vs+=t[v].size;
            mul+=tmp*t[v].size;
            tmp+=t[v].size;
        }
        ans+=mul*a[x]*2;
        t[x].size=vs+1;
        t[x].w=a[x]*(vs+1);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
#endif
    n=read(),nn=(giant)n*n;
    for (int i=2;i<=n;++i) tree::add(fa[i]=read(),i);
    for (int i=1;i<=n;++i) ans+=(a[i]=read()); // for (x,x)
    tree::dfs(1);
    print(ans);
    m=read();
    while (m--) {
        int o=read(),x=read(),y=read();
        if (o==1) lct::modfa(x,y); // fa[y]=x if x is anc of y else fa[x]=y; modify fa[] in it.
        if (o==2) lct::modval(x,y);  // modify a[] in it
        print(ans);
    }
    return 0;
}