A. 手机的生产
题目链接
http://uoj.ac/problem/113
思路
找规律可以发现，只有$表达式的话，fork()会产生3台手机，fork()$fork()会产生4台手机，fork()$fork()$fork会产生5台手机……依次类推。
那么我们可以用|把若干个连续的$块分割开，每个长度为 x 的$块会产生x−1个结果为0的表达式， 1 个结果为1的表达式，那么我们可以从右边往左边递推，假设共tot个$块，可以得到 f[i]=[i,tot] 段$块产生的手机个数，容易得到DP方程：
f[i]=(num[i]−1)f[i+1]+1,num[i]=第i段连续的$的长度
代码
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAXN 410000
#define MOD 998244353
using namespace std;
typedef long long int LL;
LL total=;
int ans[MAXN],n;
char s[MAXN],op[MAXN];
char ch[];
LL stack[MAXN];
int top=;
LL f[MAXN];
int main()
{
scanf("%d",&n);
if(n==)
{
cout<<<<endl;
return ;
}
for(int j=;j<n;j++)
{
scanf("%s",ch);
if(ch[]=='&')
op[j]='&';
else op[j]='|';
}
int h=,t=;
LL tmp=;
while(h<n&&t<n)
{
if(op[t]=='&') tmp++,t++;
else
{
h=t=t+;
stack[++top]=tmp;
tmp=;
}
}
stack[++top]=tmp;
f[top]=stack[top];
for(int i=top-;i>=;i--)
f[i]=(f[i+]*(stack[i]-)%MOD+)%MOD;
printf("%lld\n",f[]);
return ;
}
C. 谣言的传播
题目链接
http://uoj.ac/problem/115
思路
蒟蒻太弱，只会做40分的。。。。
前10分可以通过爆枚序列 b 的全排列得到。
之后30分可以枚举i的谣言终结者 b[i] ，然后求出 i 的影响系数，容易发现这就是一个二分图最小/最大权匹配问题，对于点i而言，将它的入点与所有的 j(j≠i) 的出点连边，边权为 j 作为b[i]的情况下 i <script type="math/tex" id="MathJax-Element-732">i</script>的影响系数，然后做费用流或KM，然后通过残余网络可以找出可行解。
代码
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n,a[];
namespace bruteforce
{
const int MAXN=;
int b[MAXN],ansmin[MAXN],ansmax[MAXN],minans=INF,maxans=-INF;
bool used[MAXN];
int sum=;
bool vis[MAXN];
void calc(int S,int x,int fa)
{
sum++;
if(b[S]==x) return;
if(!vis[a[x]])
{
vis[a[x]]=true;
calc(S,a[x],x);
}
}
void DFS(int pos)
{
if(pos>n)
{
sum=;
bool flag=true;
/*if(b[1]==4&&b[2]==1&&b[3]==5&&b[4]==3&&b[5]==2)
cout<<1<<endl;*/
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++) vis[j]=false;
//sum++;
vis[i]=true;
calc(i,i,);
}
if(!flag) return;
if(sum<minans)
{
minans=sum;
for(int i=;i<=n;i++)
ansmin[i]=b[i];
}
if(sum>maxans)
{
maxans=sum;
for(int i=;i<=n;i++)
ansmax[i]=b[i];
}
return;
}
for(int i=;i<=n;i++)
if(!used[i]&&i!=pos)
{
used[i]=true;
b[pos]=i;
DFS(pos+);
used[i]=false;
}
}
void solve()
{
DFS();
printf("%d\n",minans);
for(int i=;i<=n;i++)
printf("%d ",ansmin[i]);
printf("\n");
printf("%d\n",maxans);
for(int i=;i<=n;i++)
printf("%d ",ansmax[i]);
printf("\n");
}
}
namespace KM
{
const int MAXV=;
const int MAXE=;
int S=MAXV-,T=MAXV-;
struct edge
{
int u,v,w,cap,next;
}edges[MAXE*];
int head[MAXV],nCount=;
void AddEdge(int U,int V,int W,int C)
{
edges[++nCount].u=U;
edges[nCount].v=V;
edges[nCount].w=W;
edges[nCount].cap=C;
edges[nCount].next=head[U];
head[U]=nCount;
}
void add(int U,int V,int W,int C)
{
AddEdge(U,V,W,C);
AddEdge(V,U,-W,);
}
int q[MAXE*],dist[MAXV],pre[MAXV];
bool inQueue[MAXV];
bool SPFA_max()
{
memset(pre,-,sizeof(pre));
memset(dist,-INF,sizeof(dist));
memset(inQueue,false,sizeof(inQueue));
int h=,t=;
q[h]=S;
dist[S]=;
inQueue[S]=true;
while(h<t)
{
int u=q[h++];
inQueue[u]=false;
for(int p=head[u];p!=-;p=edges[p].next)
{
int v=edges[p].v;
if(dist[u]+edges[p].w>dist[v]&&edges[p].cap)
{
dist[v]=dist[u]+edges[p].w;
pre[v]=p;
if(!inQueue[v])
{
inQueue[v]=true;
q[t++]=v;
}
}
}
}
return pre[T]!=-;
}
int MCMF_max()
{
int cost=;
while(SPFA_max())
{
int flow=INF;
for(int p=pre[T];p!=-;p=pre[edges[p].u])
flow=min(flow,edges[p].cap);
for(int p=pre[T];p!=-;p=pre[edges[p].u])
{
edges[p].cap-=flow;
edges[p^].cap+=flow;
}
cost+=flow*dist[T];
}
return cost;
}
bool SPFA_min()
{
memset(pre,-,sizeof(pre));
memset(dist,INF,sizeof(dist));
memset(inQueue,false,sizeof(inQueue));
int h=,t=;
q[h]=S;
dist[S]=;
inQueue[S]=true;
while(h<t)
{
int u=q[h++];
inQueue[u]=false;
for(int p=head[u];p!=-;p=edges[p].next)
{
int v=edges[p].v;
if(dist[u]+edges[p].w<dist[v]&&edges[p].cap)
{
dist[v]=dist[u]+edges[p].w;
pre[v]=p;
if(!inQueue[v])
{
inQueue[v]=true;
q[t++]=v;
}
}
}
}
return pre[T]!=-;
}
int MCMF_min()
{
int cost=;
while(SPFA_min())
{
int flow=INF;
for(int p=pre[T];p!=-;p=pre[edges[p].u])
flow=min(flow,edges[p].cap);
for(int p=pre[T];p!=-;p=pre[edges[p].u])
{
edges[p].cap-=flow;
edges[p^].cap+=flow;
}
cost+=flow*dist[T];
}
return cost;
}
bool vis[MAXV];
int b[MAXV];
int sum=;
void calc(int S,int x,int fa)
{
sum++;
if(b[S]==x) return;
if(!vis[a[x]])
{
vis[a[x]]=true;
calc(S,a[x],x);
}
}
void solve_min()
{
memset(head,-,sizeof(head));
nCount=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) //让j作为b[i]
{
if(i==j) continue;
for(int k=;k<=n;k++)
vis[k]=false;
b[i]=j;
sum=;
vis[i]=true;
calc(i,i,);
add(i,j+n,sum,);
}
for(int i=;i<=n;i++)
add(S,i,,),add(i+n,T,,);
int ans=MCMF_min();
for(int i=;i<=nCount-*n;i+=)
if(!edges[i].cap)
b[edges[i].u]=edges[i].v-n;
printf("%d\n",ans);
for(int i=;i<=n;i++) printf("%d ",b[i]);
printf("\n");
}
void solve_max()
{
memset(head,-,sizeof(head));
nCount=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++) //让j作为b[i]
{
if(i==j) continue;
for(int k=;k<=n;k++)
vis[k]=false;
b[i]=j;
sum=;
vis[i]=true;
calc(i,i,);
add(i,j+n,sum,);
}
for(int i=;i<=n;i++)
add(S,i,,),add(i+n,T,,);
int ans=MCMF_max();
for(int i=;i<=nCount-*n;i+=)
if(!edges[i].cap)
b[edges[i].u]=edges[i].v-n;
printf("%d\n",ans);
for(int i=;i<=n;i++) printf("%d ",b[i]);
printf("\n");
}
void solve()
{
solve_min();
solve_max();
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
if(n<=)
{
using namespace bruteforce;
solve();
}
else
{
using namespace KM;
solve();
}
return ;
}
![UOJ 买卖最大化利润[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)