个人网站建设的花费,win8安装wordpress500,深圳市建设股份有限公司,wordpress 评论到微博写在前面的话#xff1a;心可以冷#xff0c;但手不能停 第一题#xff1a;C. Flexible String 题目大意#xff1a;给一个aaa字符串和bbb字符串和数字kkk#xff0c;首先设置一个计数器cntcntcnt,其中可以对aaa字符串做以下操作#xff1a;替换aaa中的一个字母xxx#…写在前面的话心可以冷但手不能停 第一题C. Flexible String 题目大意给一个aaa字符串和bbb字符串和数字kkk首先设置一个计数器cntcntcnt,其中可以对aaa字符串做以下操作替换aaa中的一个字母xxx将字母xxx加入到集合QQQ如果这个字母已经在集合QQQ中了则cntcntcnt不动否则cntcntcnt记s[l,r]s[l,r]s[l,r]为在[l,r][l,r][l,r]区间中aaa和bbb的字母全相等。达到的目标为在cnt≤kcnt \leq kcnt≤k的情况下让s[l,r]s[l,r]s[l,r]的数量最大。 解题思路 这个题可以这样想对于任意一个a[i]≠b[i]a[i] \neq b[i]a[i]b[i]可以将这个位置记作一个断点被断点隔开的若干个区间可以用这样的形式来表达s[l,r]s[l,r]s[l,r]的数量:len∗(len1)/2len*(len1)/2len∗(len1)/2,其中len为区间内的字母数量。我们注意到如果将某个满足a[i]≠b[i]a[i] \neq b[i]a[i]b[i]的字母加入到集合QQQ中则区间可能被连上注意可能断点是由两个字母组成的。这样的话考虑k最大可能为101010则可以用数位dpdpdp或者dfsdfsdfs等来枚举所有可能性。枚举出一种可能性之后只要用O(n)O(n)O(n)判断即可大概是10810^8108这样的级别那么这里的枚举状态可以用这种形式表达
for(int i0;i1024;i)注意由于我把集合中的字母用mapmapmap映射所以所有字母不能映射到000否则wronganswerontest3wrong\space answer \space on\space test3wrong answer on test3 代码
#includeiostream
#includecstdio
#includevector
#includestack
#includemap
using namespace std;
typedef long long ll;
const int length 1e5 5;
char a[length];
char b[length];
ll max(ll a, ll b)
{if (a b)return a;else return b;
}
ll solve(int i, mapchar, int mp,int n,int k)
{vectorint flag(20, 0);int q 0;for (int j 1; j 10; j){if (i(1 j)){flag[j] 1;q;}}if(qk)return 0;int s 0;ll res 0;while (s n){int tmp s;while (a[s] b[s]||flag[mp[a[s]]]1){s;if (s n)break;}int len s - tmp;res res (ll)(len 1)*len / 2;s;}return res;}
int main(void)
{int t;scanf_s(%d, t);for (int i 0; i t; i){int n;int k;scanf_s(%d%d, n, k);getchar();//收\nscanf_s(%s, a,sizeof(a));getchar();//收\nscanf_s(%s, b,sizeof(b));getchar();mapchar,int mp;int cnt 0;for (int i 0; i n; i){if (a[i] ! b[i]){if (mp[a[i]] 0){mp[a[i]] cnt;}}}if (cnt k){ll tmp (ll)n*(n 1) / 2;printf(%lld\n, tmp);continue;}vectorll dp(1500, 0);ll ans -1;for (int i 0; i 1024; i){ll asolve(i*2, mp,n,k);ans max(ans, a);}printf(%lld\n, ans);}
}第2题D. Flexible String Revisit 这个题比较有意思 题目大意 给一个由0和1组成的两个字符串对字符串a可以做以下操作可以任选一个数字对其进行反转问达到两个字符串第一次相等所需要的操作次数期望。 解题思路 参考文章 代码
#includeiostream
#includecstdio
#includevector
using namespace std;
typedef long long ll;
int mod 998244353;
const int length 1e6 5;
int f[length][2];
int dp[length];
char a[length];
char b[length];
int ksm(int k)
{int tmp mod-2;int base k;int ans 1;while (tmp){if (tmp % 2 1){ans (ll)ans*base%mod;}base (ll)base*base%mod;tmp tmp 1;}return ans;
}
int solve(int n, int k)
{f[n][0] 1;f[n][1] 1;for (int i n-1; i 0; i--){int now ((ll)1 - (ll)(n - i)*f[i 1][1]%mod *ksm(n) % mod mod) % mod;f[i][0] ((ll)1 (ll)(f[i1][0])*(n-i)%mod*ksm(n) % mod) % mod*ksm(now)%mod;f[i][1] (ll)i*ksm(n) % mod*ksm(now) % mod;}dp[0] f[0][0];for (int i 1; i k; i){dp[i] (ll)((ll)dp[i - 1] * f[i][1] % mod f[i][0]) % mod;}return dp[k];
}
int main(void)
{int t;scanf_s(%d, t);for (int i 0; i t; i){int n;scanf_s(%d, n);int k 0;getchar();scanf_s(%s, a,sizeof(a));//a.push_back(t);getchar();scanf_s(%s, b, sizeof(b));getchar();for (int i 0; i n; i){if (a[i] ! b[i])k;}int a1solve(n, k);printf(%d\n, a1);}
}
