女生做网站编辑,室内设计公司排名前十强及作品,外国网站服务器,网站邮箱怎么做的题意 你有一个长度为 $n$ 的模板串#xff08;由 $0-9$ 这 $10$ 个数字和通配符 $.$ 组成#xff09;#xff0c;还有 $m$ 个匹配串#xff08;只由 $0-9$ 这 $10$ 个数字组成#xff09;#xff0c;每个匹配串有一个魔力值 $v_i$。你要把模板串的每个 $.$ 都换成一个数字…题意 你有一个长度为 $n$ 的模板串由 $0-9$ 这 $10$ 个数字和通配符 $.$ 组成还有 $m$ 个匹配串只由 $0-9$ 这 $10$ 个数字组成每个匹配串有一个魔力值 $v_i$。你要把模板串的每个 $.$ 都换成一个数字使得模板串的魔力值最大。模板串的魔力值定义为模板串中每出现一次任意一个匹配串 $s_i$字符串的魔力就 $\times v_i$。最终魔力值开 $c$ 次方根$c$ 为模板串中出现的匹配串的总数。 $1\le n,m,s\le 1501,\space 1\le v_i\le 10^9$ 题解 王·能过就行·子健 显然只要三个 $10^9$ 大小的数乘起来就爆 $long\space long$ 了即 $\prod v_i$ 会很大而高精度开根既难写又爆复杂度光乘法就爆时间了所以不能直接按题目的公式求。 如果你没学过数学比如我可以把所有 $v_i$ 各自开 $c$ 次方根再相乘但即使开 $long\space double$ 也会爆精度不过可以拿 $80$ 分。 如果你学过数学应该记得高一数学必修 $1$ 中有一章讲了关于 $log$ 的各种性质其中有两条是 $$\log_a{MN} \log_a{M}\log_a{N}$$ $$\log_a{N}^k k\times \log_a{N}$$ 其中 $a$ 可以是任意实底数。 第一条式子中的 $MN$ 可以拓展成任意多个乘数等号右边就会得到一堆 $log$ 值相加。简单地说就是因为幂值相乘等于指数相加比如 $2^4$ 变成 $2^5$ 次方值乘了 $2$但指数只加了 $1$。 具体证明可以去翻书。 把两个公式组合一下就可以推这题的公式 $$ans \sqrt[c]{v_1\times v_2\times ...\times v_k} (v_1\times v_2\times ...\times v_k)^{\frac{1}{c}}$$ 两边同时取以一个实数 $a$ 为底的对数得到 $$\log_a{ans} \log_a{(v_1\times v_2\times ...\times v_k)^{\frac{1}{c}}}$$ $$\log_a{ans} \frac{1}{c}\times \log_a{(v_1\times v_2\times ...\times v_k)}$$ $$\log_a{ans} \frac{1}{c}(\log_a{v_1}\log_a{v_2}...\log_a{v_k})$$ 因为这题只需要你求方案所以你只要确保不同方案之间的相对魔力值即可不用维护具体的 $ans$ 值所以可以把 $ans$ 取 $log$$log$ 的底数 $a$ 也可以随便取大部分人应该都取的是自然对数 $e$。 不难发现等号右边变成了一个类似于平均数的东西仔细观察即可发现把所有匹配串的魔力值 $v_i$ 取 $ln$ 后你要使出现的所有匹配串的 $v_i$ 的平均数最大。 平均数最大这种东西就是套路的01分数规划…… 具体做法就是二分平均数 $x$然后把所有匹配串的 $a_i$ 都减去 $x$问题就变成了如何使 $v_i$ 之和最大。在所有模板串组成的 AC 自动机上 $dp$ 即可。 AC 自动机上 $dp$ 的状态就是 $f_{i,j}$ 表示确定模板串的前 $i$ 位按模板串的前 $i$ 位跑 AC 自动机到达的点的编号为 $j$ 时模板串的魔力值最大是多少。 然后判断一下模板串的第 $i$ 位是不是通配符就行了是的话就可以往任意儿子转移不是的话就要沿对应的字符边转移。 时间复杂度 $O(10ns\log{\frac{\ln v_{max}}{eps}})$。 这他吗什么复杂度怎么跑过的……能过就行了 1 #includebits/stdc.h2 #define N 15053 #define inf 1e994 #define eps 1e-65 using namespace std;6 inline int read(){7 int x0; bool f1; char cgetchar();8 for(;!isdigit(c);cgetchar()) if(c-) f0;9 for(; isdigit(c);cgetchar()) x(x3)(x1)(c^0);10 if(f) return x;11 return 0;12 }13 int n,m;14 char T[N];15 namespace AC{16 int cnt,ch[N][12],sum[N]; double val[N];17 inline void ins(char *s,double v){18 int u0,lenstrlen(s),c;19 for(int i0;ilen;i){20 cs[i]-0;21 if(!ch[u][c]) ch[u][c]cnt;22 uch[u][c];23 }24 sum[u], val[u]v;25 }26 int que[N],l,r,fail[N];27 void BuildAC(){28 fail[0]-1, que[lr1]0;29 while(lr){30 int uque[l];31 for(int i0;i10;i)32 if(!ch[u][i]) ch[u][i]ch[fail[u]][i];33 else fail[ch[u][i]]ch[fail[u]][i], que[r]ch[u][i];34 }35 for(int i2;ir;i){36 sum[que[i]]sum[fail[que[i]]];37 val[que[i]]val[fail[que[i]]];38 //coutque[i] fail[que[i]] sum[que[i]] val[que[i]]endl;39 }40 }41 42 double f[N][N]; int g[N][N][2]; char ansStr[N];43 double DP(double x){44 //coutxendl;45 for(int j0;jcnt;j) val[j]-sum[j]*x;46 for(int i0;in;i)47 for(int j0;jcnt;j)48 f[i][j]-inf;49 f[0][0]0;50 for(int i0;in;i){51 for(int j0;jcnt;j){52 if(f[i][j]-inf) continue;53 if(T[i].){54 for(int k0;k10;k){55 int _jch[j][k];56 if(f[i1][_j]f[i][j]val[_j]){57 f[i1][_j]f[i][j]val[_j];58 }59 }60 }61 else{62 int kT[i]-0, _jch[j][k];63 if(f[i1][_j]f[i][j]val[_j]) f[i1][_j]f[i][j]val[_j];64 }65 }66 }67 for(int i0;icnt;i) val[i]sum[i]*x;68 int ans0;69 for(int j1;jcnt;j) if(f[n][j]f[n][ans]) ansj;70 //coutf[n][ans]endl;71 return f[n][ans];72 }73 void _DP(double x){74 for(int j0;jcnt;j) val[j]-sum[j]*x;75 for(int i0;in;i)76 for(int j0;jcnt;j)77 f[i][j]-inf;78 f[0][0]0;79 for(int i0;in;i){80 for(int j0;jcnt;j){81 if(f[i][j]-inf) continue;82 if(T[i].){83 for(int k0;k10;k){84 int _jch[j][k];85 if(f[i1][_j]f[i][j]val[_j]){86 f[i1][_j]f[i][j]val[_j],87 g[i1][_j][0]j, g[i1][_j][1]k;88 }89 }90 }91 else{92 int kT[i]-0, _jch[j][k];93 if(f[i1][_j]f[i][j]val[_j])94 f[i1][_j]f[i][j]val[_j],95 g[i1][_j][0]j, g[i1][_j][1]k;96 }97 }98 }99 for(int i0;icnt;i) val[i]sum[i]*x;
100 int ans0;
101 for(int j1;jcnt;j) if(f[n][j]f[n][ans]) ansj;
102 for(int in;i0;--i){
103 ansStr[i-1]g[i][ans][1]0;
104 ansg[i][ans][0];
105 }
106 }
107 }
108 using namespace AC;
109 int main(){
110 //freopen(1.in,r,stdin);
111 //freopen(1.out,w,stdout);
112 nread(), mread(); scanf(%s,T);
113 char S[N]; double V;
114 for(int i1;im;i){
115 scanf(%s%lf,S,V);
116 ins(S,log(V));
117 }
118 BuildAC();
119 double l0, rlog(1e91), mid, ans0;
120 while(r-leps){
121 mid(lr)/2;
122 if(DP(mid)0) ansmid, lmid;
123 else rmid;
124 }
125 //coutansendl;
126 _DP(ans);
127 printf(%s\n,ansStr);
128 return 0;
129 } Viev Code 总结 1. 这类题不能直接 $dp$ 求最大平均数。因为求最大平均数这种问题除了分数规划外即二分答案只能在某些情况下用贪心比如从大到小取。 若不能贪心我们不能把上述 $dp$ 的值直接记为最大平均数 或者同时记一个最小的匹配数量。考虑平均数这个东西的本质对于到达同一状态的两种情况可能一种情况匹配的数少平均数也更小但把两种情况同时加入一个新数这种情况的新平均数就可能比另一种情况的新平均数大了。比如两个数集 $\{10\}$ 和 $\{9,9,9,14\}$前者的平均数是 $10$后者的平均数是 $10.25$但把两个数集同时加入一个数 $11$前者的平均数变成了 $10.5$后者的平均数变成了 $10.4$。所以如果用 $dp$ 求最大平均数必须再开一维状态记匹配的串数即要求多少个数的平均数但匹配的串数可能很多再开一维状态的话时空复杂度都不能承受。所以只能分数规划。 2. 这道题告诉我们一定要学好数学这门文化课否则会被数学杀。转载于:https://www.cnblogs.com/scx2015noip-as-php/p/bjoi2019d1t1.html
