建设网站怎么查明细,黑糖 wordpress 主题,徐州建设工程交易网招标公告最新,做房地产网站广告销售http://codeforces.com/contest/814/problem/C 【题意】 给定一个长度为n的字符串s#xff0c;一共有q个查询#xff0c;每个查询给出一个数字m和一个字符ch#xff0c;你的操作是可以改变字符串中的某些字母#xff0c;最多改变m个#xff0c;问操作后只包含字符ch的连续…http://codeforces.com/contest/814/problem/C 【题意】 给定一个长度为n的字符串s一共有q个查询每个查询给出一个数字m和一个字符ch你的操作是可以改变字符串中的某些字母最多改变m个问操作后只包含字符ch的连续子序列最长是多少 【思路】 方法一 有这么一类问题需要在给的一组数据中找到不大于某一个上限的“最优连续子序列” 于是就有了这样一种方法找这个子序列的过程很像毛毛虫爬行方式比较流行的叫法是“尺取法”。 有关尺取的练习 http://blog.csdn.net/acmer_sly/article/details/59524223 http://acm.hdu.edu.cn/showproblem.php?pid5328 尺取是线性的所以总的时间复杂度是O(qn). 方法二dp,对每个字母预处理时间复杂度是O(26n^2)。 【Accepted】 1 #include iostream2 #include stdio.h3 #include cmath4 #include vector5 #include algorithm6 #include set7 #include map8 #include queue9 #include deque
10 #include stack
11 #include string
12 #include bitset
13 #include ctime
14 #includealgorithm
15 #includecstring
16 using namespace std;
17 typedef long long ll;
18 const int maxn1502;
19 int n,q,m;
20 char s[maxn];
21 char ch[5];
22
23
24 int solve(char c)
25 {
26 //双指针
27 int l0,r0;
28 int ans0;
29 int cnt0;
30 while(lnrn)
31 {
32 //右端点不断往后扫直到不能再向右
33 while(rn (s[r]c||cntm))
34 {
35 if(s[r]!c)
36 {
37 cnt;
38 }
39 r;
40 }
41 //记下当前l下的解
42 ansmax(ans,r-l);
43 while(lr s[l]c)
44 {
45 l;
46 }
47 //找到第一个使cnt-1的l,r才能继续向右更新
48 l;
49 cnt--;
50 }
51 return ans;
52 }
53 int main()
54 {
55 while(~scanf(%d,n))
56 {
57 scanf(%s,s);
58 scanf(%d,q);
59 for(int i0;iq;i)
60 {
61 scanf(%d%s,m,ch);
62 int anssolve(ch[0]);
63 printf(%d\n,ans);
64 }
65 }
66 return 0;
67 } 尺取 1 #include iostream2 #include stdio.h3 #include cmath4 #include vector5 #include algorithm6 #include set7 #include map8 #include queue9 #include deque
10 #include stack
11 #include string
12 #include bitset
13 #include ctime
14 #includealgorithm
15 #includecstring
16 using namespace std;
17 typedef long long ll;
18 int n,q,m;
19 const int maxn1502;
20 char s[maxn];
21 int dp[maxn][27];
22 char ch[5];
23 void Init()
24 {
25 memset(dp,-1,sizeof(dp));
26 for(int c0;c26;c)
27 {
28 for(int i0;in;i)
29 {
30 int num0;
31 for(int ki;k0;k--)
32 {
33 if(s[k](char)(ca))
34 {
35 num;
36 }
37 //替换i-k1-num个字母达到的子段长度是i-k1,枚举所有的子段不断更新找到最大值共n^2个子段。
38 dp[i-k1-num][c]max(dp[i-k1-num][c],i-k1);
39 }
40 }
41 }
42 }
43 int main()
44 {
45 while(~scanf(%d,n))
46 {
47 scanf(%s,s);
48 Init();
49 scanf(%d,q);
50 for(int i0;iq;i)
51 {
52 scanf(%d%s,m,ch);
53 if(dp[m][ch[0]-a]-1)
54 {
55 printf(%d\n,n);
56 }
57 else
58 {
59 printf(%d\n,dp[m][ch[0]-a]);
60 }
61 }
62 }
63 return 0;
64 } dp 转载于:https://www.cnblogs.com/itcsl/p/6963357.html
