不怕噩夢
題面
蚊子最近經常做噩夢，然后就會被嚇醒，這可不好，，
瘋子一直在發愁，然后突然有一天，他發現蚊子其實就是害怕某些事，
如果那些事出現在她的夢里，就會害怕，
我們可以假定那個害怕的事其實是一個字串，而她做的夢其實也是一個字串，
她可以一個晚上一直做夢，所以夢這個字串會很長，如果其中包含了她所害怕的事情，那么她這天晚上就會害怕，
當然一個害怕的事也可能在這天晚上被她夢到很多遍，當然每個晚上也可能有很多種害怕的事都被夢到，
每個害怕的事都有一定的權值，
而這天晚上如果夢到了某件事，那么這件事所產生的黑暗效果等于這件事的權值乘以這個害怕的事在夢字串里的開始位置，
如果同樣的事夢到了很多遍，那么就重復上面的操作很多遍，
當天晚上的黑暗效果總和等于當天所有害怕的事產生的黑暗效果累加到一起，
現在瘋子想知道蚊子這些天來噩夢的黑暗效果總和是多少，
輸入格式
第\(1\)行兩個整數\(N,M\)代表一共有\(N\)天夢和\(M\)個害怕的事，
第\(2\)行到第\(M+1\)行，每行一個字串\(t_i\),代表第\(i\)個害怕的事
第\(M+2\)行到第\(2M+2\)行，每行一個整數\(a_i\).代表第\(i\)個害怕的事權值
第\(2M+3\)行到第\(N+2M+3\)行，每行一個字串\(s_i\)，代表第\(i\)天的夢，
輸出格式
$SUM $
\(SUM=N\)天里黑暗效果的總和，
我們保證每天的黑暗效果都小于\(\texttt{maxlongint}\);
樣例
\(\texttt{input\#1}\)
2 2
abc
def
1
2
abcdef
defabc
\(\texttt{output\#1}\)
15
資料范圍與提示
【樣例解釋】
\(1 * 1 + 2 * 4 + 1 * 4 + 2 * 1 = 15\)
對于資料的把握和時間復雜度的估計是成敗的關鍵，
如果出現一個夢是:ab
而害怕的事有a,b,ab，那么a,b,ab都需要參與計算..
【資料范圍】
對于$30 % $的資料
\(N,M \leqslant 50\)
對于所有的資料
\(N<=200.M<=200. length(s_i)<=200.length(t_i)<=200.a_i<=10.\)
題解
str1.find(str2,qwq)是從str1的qwq位置開始找str2找到的話回傳str2在str1中的從qwq位置開始第一次出現的位置，模擬即可，
\(Code\)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
typedef long long ll;
ll ans,n,m;
std::string sss[201];
struct aaa {
std::string name;
ll w;
}a[201];
inline void read(ll &T) {
ll x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
inline void calc(int a,int b) {
ans+=a*b;
}
int main() {
read(n),read(m);
for(int i=1;i<=m;++i) {
std::cin>>a[i].name;
}
for(int i=1;i<=m;++i) {
read(a[i].w);
}
for(int i=1;i<=n;++i) {
std::cin>>sss[i];
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
int x=0;
while(1) {
x=sss[i].find(a[j].name,x);
if(x==-1) break;
else calc(x+1,a[j].w);
x++;
}
}
}
std::cout<<ans<<'\n';
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/93377.html
標籤：C++
上一篇：Vue專案樹形控制元件node-click事件控制臺報錯Invalid handler for event "node-click": got undefined
下一篇：【CSP-S膜你考】那23個路口