A.
建图跑最小费用最大流。分类讨论每种情况如何连边，费用怎么定。
#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=1,ans=0,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=0;e[nume].c=-c;g[v]=nume; } bool spfa() { for (int i=s;i<=t;i++) {vis[i]=false;dis[i]=inf;} dis[s]=0;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]^1].f+=dt; u=prev[u]; } return dis[t]*dt; } int main() { scanf("%d%d",&n,&m);s=0;t=n+1; for (int i=1;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=1;i<=n;i++) { if (fin[i]>fout[i]) addedge(s,i,fin[i]-fout[i],0); else addedge(i,t,fout[i]-fin[i],0); } addedge(n,1,inf,0); for (int i=1;i<=m;i++) { if (d[i]>c[i]) { addedge(a[i],b[i],inf,2); addedge(b[i],a[i],d[i]-c[i],0); addedge(b[i],a[i],c[i],1); ans+=d[i]-c[i]; } else { addedge(a[i],b[i],c[i]-d[i],1); addedge(a[i],b[i],inf,2); addedge(b[i],a[i],d[i],1); } } while (spfa()) ans+=dinic(); printf("%d ",ans); return 0; }
B.
奇妙的数学题。
首先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/5],tot=0,mn[maxn],ans=0,tab[maxn],kr=0,num[maxn]; bool vis[maxn]; void get_table() { mn[1]=1; for (long long i=2;i<=maxn-50;i++) { if (!vis[i]) {vis[i]=true;prime[++tot]=i;mn[i]=i;} for (long long j=1;j<=tot && i*prime[j]<=maxn-50;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==-1) return 0; long long lim=1,ret=1,ans=0;tab[1]=1; while (tab[ret]<=cnt) tab[++ret]=tab[ret-1]*x+1LL; ret--; for (long long i=ret;i>=1;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=2;i<=n;i++) { long long x=i,ret1=-1,cnt=0,rr; while (x!=1) { 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=1; kr=(kr+ans)%mod; } printf("%lld ",kr); return 0; }
Ｃ.
杜教筛神题。。。感觉先要学一学杜教筛的东西再来看。就没写啦。