网站收录查询主要由哪几个网站,设计院项目管理系统,教育 wordpress模板,dw旅游网站模板下载题目大意
有一个键盘#xff0c;上面有 n 1 n1 n1个按键#xff0c;按下按键 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n会打印出字符串 S i S_i Si#xff0c;按下按键 n 1 n1 n1会删掉结尾的 K K K个字符#xff0c;如果不足 K K K个字符则全部删完#xff0c;问打印出 S …题目大意
有一个键盘上面有 n 1 n1 n1个按键按下按键 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n会打印出字符串 S i S_i Si按下按键 n 1 n1 n1会删掉结尾的 K K K个字符如果不足 K K K个字符则全部删完问打印出 S S S最少要按多少次。
有 T T T组数据。 1 ≤ T ≤ 100 , 10 ≤ n ≤ 5 × 1 0 3 , 1 ≤ ∑ K ≤ 2 × 1 0 3 1\leq T\leq 100,10\leq n\leq 5\times 10^3,1\leq \sum K\leq 2\times 10^3 1≤T≤100,10≤n≤5×103,1≤∑K≤2×103 1 ≤ ∑ ( ∑ ∣ S i ∣ ) ≤ 1 0 6 , 1 ≤ ∑ ∣ S ∣ ≤ 5 × 1 0 3 1\leq \sum(\sum|S_i|)\leq 10^6,1\leq \sum |S|\leq 5\times 10^3 1≤∑(∑∣Si∣)≤106,1≤∑∣S∣≤5×103
时间限制 2000 m s 2000ms 2000ms空间限制 512 M B 512MB 512MB。 题解
考虑 D P DP DP设 f i f_i fi表示打出前 i i i个字符需要的最小操作次数。那我们要求的就是打出 S S S的第 i i i个字符到第 j j j个字符需要的最小操作次数。
先考虑如何得到 S S S中 [ i , j ] [i,j] [i,j]这一段。我们选择一个前 j − i 1 j-i1 j−i1个字符与 S S S的 [ i , j ] [i,j] [i,j]中的字符相同的 S p S_p Sp然后将 S p S_p Sp打出并删到只剩下 S S S的 [ i , j ] [i,j] [i,j]这部分即可。我们可以建一棵字典树每次加入一个 S i S_i Si时更新从根节点到达路径上每个点的最小操作次数。为了求这里的最小操作次数我们还需要求出删除若干个字符所需要的最小操作次数这个可以用一个类似“同余”的最短路来求出用 dijkstra \text{dijkstra} dijkstra可以 O ( K 2 ) O(K^2) O(K2)解决连边是 O ( k 2 ) O(k^2) O(k2)的求最短路是 O ( K log K ) O(K\log K) O(KlogK)的。
得到了带到每个位置的最小操作次数之后枚举每个 i i i然后在字典树上按 S S S从 i i i往后枚举设枚举到 j j j则用 f i f_i fi来更新 f j f_j fj。 D P DP DP的时间复杂度为 O ( ∣ S ∣ 2 ) O(|S|^2) O(∣S∣2)。
总时间复杂度为 O ( ∑ ( ∑ ∣ S i ∣ ∣ S ∣ 2 K 2 ) ) O(\sum(\sum |S_i||S|^2K^2)) O(∑(∑∣Si∣∣S∣2K2))。
可以参考代码帮助理解。
code
#includebits/stdc.h
using namespace std;
const int N5000,M1000000,K2000;
int T,n,k,s1,now,bg[N5],len[N5],z[K5],vs[K5],cm[K5];
int tot;
char s[N5],t[M5],ss[M5];
long long dis[K5],to[M5],f[N5];
struct node{int x;long long dis;bool operator(const node ax)const{return disax.dis;}
};
vectorpairint,intg[K5];
priority_queuenodeq;
struct trie{int a[26];
}w[M5];
void pt(){int lenstrlen(ss1);for(int i1;ilen;i){t[now]ss[i];}
}
void init(){for(int i0;ik;i){z[i]1e9;vs[i]cm[i]0;g[i].clear();}for(int i1;in;i){len[i]bg[i1]-bg[i];z[len[i]%k]min(z[len[i]%k],len[i]);vs[len[i]%k]1;}for(int i1;in;i){if(z[len[i]%k]!len[i]) continue;if(!vs[len[i]%k]) continue;vs[len[i]%k]0;for(int j0;jk;j){g[(jlen[i])%k].push_back({j,1(jlen[i])/k});}}for(int i0;ik;i) dis[i]1e16;dis[0]dis[k]0;q.push((node){0,0});while(!q.empty()){int uq.top().x;q.pop();if(cm[u]) continue;cm[u]1;for(auto p:g[u]){int vp.first,wp.second;if(dis[u]wdis[v]){dis[v]dis[u]w;q.push((node){v,dis[v]});}}}
}
void pt(int tw){int q,vq1;for(int i1;ilen[tw];i){qt[bg[tw]i-1]-a;if(!w[vq].a[q]){w[vq].a[q]tot;to[tot]1e16;}vqw[vq].a[q];to[vq]min(to[vq],1ll(len[tw]-i)/kdis[(len[tw]-i)%k]);}
}
void solve(int tw){int q,vq1;for(int itw1;is1;i){qs[i]-a;if(!w[vq].a[q]) return;vqw[vq].a[q];f[i]min(f[i],f[tw]to[vq]);}
}
int main()
{
// freopen(keyboard.in,r,stdin);
// freopen(keyboard.out,w,stdout);scanf(%d,T);while(T--){scanf(%d%d,n,k);now0;for(int i1;in;i){scanf(%s,ss1);bg[i]now1;pt();}bg[n1]now1;scanf(%s,s1);s1strlen(s1);init();tot1;for(int i1;in;i) pt(i);for(int i0;is1;i) f[i]1e16;f[0]0;for(int i0;is1;i) solve(i);if(f[s1]1e16) printf(-1\n);else printf(%lld\n,f[s1]);for(int i1;itot;i){for(int j0;j26;j) w[i].a[j]0;}}return 0;
}
