题目大意
给你一张n个点的无向图,求两对点间最短路的最长公共路径。
无重边,无自环
n<=1500
给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
点击了解详情↓
继续阅读
给你一个串s和一些单词,要求你把串分成k段,使每段所含单词数之和最大。
要求单个字母只能对应一个单词的开头,要求单个字母只能对应一个单词的开头,
如 串为:funk
单词为fun ,funk
你就只能选一个匹配数据范围 len(s)<=200 只有小写字母 k<=40数据范围 len(s)<=200 只有小写字母 k<=40
由于范围很小,各种hash暴力贪心花式kmp都能过,
f_{i,j}=max(f_{k,j-1}+tot)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=205;
const int M=11;
const int INF=0x3f3f3f3f;
char s[N],word[M][N],len[M];
int p,m,n,num;
int d[N],f[N][M<<2];
void dp()
{
//先处理出d数组
memset(d,INF,sizeof(d));
for(int i=1;i<=n;++i)
{
for(int j=1;j<=num;++j)
{
if(n-i+1<len[j]||d[i]<=len[j]) continue;
//如果过长或不优都不要
bool flag=false;
for(int k=0;k<len[j];++k)
if(s[i+k]!=word[j][k+1]) {flag=true;break;}//暴力匹配即可
//或者闲的无聊写个trie树把常数优化掉
if(flag) continue;
d[i]=i+len[j]-1;
}
// printf("d[%d]=%dn",i,d[i]);
}
//进行dp
for(int i=1;i<=n;++i)//首先枚举位置
for(int j=1;j<=m;++j)//其次枚举断了几处
{
int tot=0;
for(int k=i;k>=j;--k)//然后在哪里断的,反向转移保证tot合法
{
if(d[k]<=i) tot++;
f[i][j]=max(f[i][j],f[k-1][j-1]+tot);
}
}
}
int main()
{
scanf("%d%d",&p,&m);
for(int i=1;i<=p;i++) scanf("%s",s+1+20*(i-1));
n=strlen(s+1);
//首先这题的垃圾输入方式非常毒瘤
// printf("%s",s+1);//return 0;
scanf("%d",&num);
for(int i=1;i<=num;i++)
scanf("%s",word[i]+1),len[i]=strlen(word[i]+1);
//其次你读入每个单词
dp();
printf("%d",f[n][m]);
}
[图片无法显示]
给你一棵树,每个点有点权,让你支持③种操作
(1)点x值加y
(2)以点x为根的子树加y
(3)定义(u,v)为u和v的点权和。求∑(u,v) (u<v&&lca(u,c)=x)
123132
132
123
近期评论