FR #1题解

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

建图跑最小费用最大流。分类讨论每种情况如何连边，费用怎么定。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define maxv 105

#define maxe 100500

#define inf 1000000000

using namespace std;

int n,m,a[maxv],b[maxv],c[maxv],d[maxv],s,t,fin[maxv],fout[maxv],g[maxv],dis[maxv],nume=,ans=,pree[maxv],prev[maxv];

bool vis[maxv];

queue <int> q;

struct edge

{

    int v,f,c,nxt;

}e[maxe];

void addedge(int u,int v,int f,int c)

{

    e[++nume].v=v;e[nume].nxt=g[u];

    e[nume].f=f;e[nume].c=c;g[u]=nume;

    e[++nume].v=u;e[nume].nxt=g[v];

    e[nume].f=;e[nume].c=-c;g[v]=nume;

}

bool spfa()

{

    for (int i=s;i<=t;i++) {vis[i]=false;dis[i]=inf;}

    dis[s]=;q.push(s);

    while (!q.empty())

    {

        int head=q.front();q.pop();

        for (int i=g[head];i;i=e[i].nxt)

        {

            int v=e[i].v;

            if ((e[i].f) && (dis[v]>dis[head]+e[i].c))

            {

                dis[v]=dis[head]+e[i].c;

                pree[v]=i;prev[v]=head;

                if (!vis[v]) {vis[v]=true;q.push(v);}

            }

        }

        vis[head]=false;

    }

    if (dis[t]==inf) return false;

    return true;

}

int dinic()

{

    int u=t,dt=inf;

    while (u!=s)

    {

        dt=min(dt,e[pree[u]].f);

        u=prev[u];

    }

    u=t;

    while (u!=s)

    {

        e[pree[u]].f-=dt;

        e[pree[u]^].f+=dt;

        u=prev[u];

    }

    return dis[t]*dt;

}

int main()

{

    scanf("%d%d",&n,&m);s=;t=n+;

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

    {

        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);

        fout[a[i]]+=d[i];fin[b[i]]+=d[i];

    }

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

    {

        if (fin[i]>fout[i]) addedge(s,i,fin[i]-fout[i],);

        else addedge(i,t,fout[i]-fin[i],);

    }

    addedge(n,,inf,);

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

    {

        if (d[i]>c[i])

        {

            addedge(a[i],b[i],inf,);

            addedge(b[i],a[i],d[i]-c[i],);

            addedge(b[i],a[i],c[i],);

            ans+=d[i]-c[i];

        }

        else

        {

            addedge(a[i],b[i],c[i]-d[i],);

            addedge(a[i],b[i],inf,);

            addedge(b[i],a[i],d[i],);

        }

    }

    while (spfa()) ans+=dinic();

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

    return ;

}

奇妙的数学题。

首先for i=2 -> n是肯定的。考虑如何在log^2n的时间内得到答案。

有一个log^3n的做法是显然的。对于一个新的i，我们枚举它所有的质因数，加到一个数组里，那么这是我们的答案就是对于每个质因数的答案和上一个的答案取max（每一个质因数的答案：若2出现i次，则找到2出现次数大于i次的最小的那个n）。然后我们二分答案，通过[n/p]+[n/p^2]+[n/p^3]+....算出答案。

考虑如何优化（神来之笔）。将n看成p进制的数akak-1ak-2....a1a0。然后考虑上面那个式子的答案就是Σai*(p^i-1)/(p-1)，且使上面那个式子刚好>=cnt。怎么确定数组a呢？直接贪心就好了！预处理后面关于ｐ的多项式，之后能取大就取大。这样一定是正确的（但是我不知道为什么）。。。。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000050

#define mod 1000000007

using namespace std;

long long n,k,prime[maxn/],tot=,mn[maxn],ans=,tab[maxn],kr=,num[maxn];

bool vis[maxn];

void get_table()

{

    mn[]=;

    for (long long i=;i<=maxn-;i++)

    {

        if (!vis[i]) {vis[i]=true;prime[++tot]=i;mn[i]=i;}

        for (long long j=;j<=tot && i*prime[j]<=maxn-;j++)

        {

            vis[i*prime[j]]=true;mn[i*prime[j]]=prime[j];

            if (!i%prime[j]) break;

        }

    }

}

long long ask(long long x,long long cnt)

{

    if (x==-) return ;

    long long lim=,ret=,ans=;tab[]=;

    while (tab[ret]<=cnt) tab[++ret]=tab[ret-]*x+1LL;

    ret--;

    for (long long i=ret;i>=;i--)

    {

        ans=ans*x+cnt/tab[i];

        cnt%=tab[i];

    }

    return ans*x;

}

int main()

{

    scanf("%lld%lld",&n,&k);

    get_table();

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

    {

        long long x=i,ret1=-,cnt=,rr;

        while (x!=)

        {

            if (mn[x]!=ret1) {ans=max(ans,ask(ret1,num[ret1]*k));ret1=mn[x];}

            num[mn[x]]++;

            rr=mn[x];x/=mn[x];

        }

        ans=max(ans,ask(ret1,num[rr]*k));cnt=;

        kr=(kr+ans)%mod;

    }

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

    return ;

}