超级码力反场赛 9月26日 日常周赛 题解

1.折纸

显然每对折一次，以中间的一个凹痕为中心，两边对称翻转。
$ep:0\to 001\to (001)0(011)$

class Solution {
public:/*** @param n: The folding times* @return: the 01 string*/string getString(int n) {string x="0",ans="0";for(int i=0;i<n-1;i++){string re=x;reverse(re.begin(),re.end());for(int j=0;j<re.size();j++) if(re[j]=='0') re[j]='1';else re[j]='0';ans=x+"0"+re;x=ans;}return ans;}
}sol;

2.字符串的不同排列

用$next\_permutation$函数即可实现全排列。

class Solution {
public:/*** @param str: A string* @return: all permutations*/vector<string> stringPermutation(string &a) {// write your code heresort(a.begin(),a.end());vector<string>ans;do{ans.push_back(a);}while(next_permutation(a.begin(),a.end()));return ans;}
};

3.硬币排成线

区间$dp$模板题。

令$dp[i][j]$表示区间$[i,j]$先手与后手价值之差的最大值。

容易得到状态转移方程：

$dp[i][j]=max(val[i]-dp[i+1][j],val[j]-dp[i][j-1])$

因为先手取了一个后，后手面临的情况就相当于先手。

初始化：$dp[i][i]=val[i]$

然后跑区间$dp$即可，注意$for$循环的顺序。

$i$逆序，$j$顺序，这可以从状态转移看出来。

class Solution {
public:/*** @param values: a vector of integers* @return: a boolean which equals to true if the first player will win*/bool firstWillWin(vector<int> &a) {// write your code hereint n = a.size();if (n <= 2) return 1;vector<vector<int>> dp;dp.resize(n, vector<int>(n));for (int i = 0; i < n; i++)dp[i][i] = a[i];for(int i=n-2;~i;i--)for(int j=i+1;j<n;j++)dp[i][j]=max(a[i]-dp[i+1][j],a[j]-dp[i][j-1]);return dp[0][n-1] > 0;}
};

4.K步编辑

$dp+Trie$优化。
该题是对于最短编辑距离的加强版，
原版是给定两个两字符串，求将一个字符串通过这三种操作变成目标字符串的最小操作数，可以用$dp$做。
令$dp[i][j]$表示字符串$S$前$i$个字符串和字符串$T$前$j$个字符的最小操作数。

可以得到状态转移方程:
$\{\begin{array}{l}dp[i][j]=dp[i-1][j-1](S[i]=T[j])\\ dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1,(S[i]\ne T[j])\end{array}$

对于本题，因为字符串有多种，若每个都进行$dp$，会进行很多重复的操作，所以考虑用$Trie$处理字符串集合，将原来$dp$的一维换成字典树的前缀，第一维通过在字典树中进行$dfs$实现，然后第二维进行转移。

初始化：$dp[i]=i$，表示的是字典树的$root$与目标字符串的前$i$个字符的最小操作数。

进行$dfs$的时候，用两个数组$nt[],dp[]$分别储存更新后的前缀，和原来的前缀。
每次都需要初始化$nt[0]=dp[0]+1$，表示当前的前缀与目标字符串的前$0$个字符最小操作数等于上一个前缀的操作数+1。

#define pb push_back
class Solution {
public:struct Tree{Tree(){for(int i=0;i<26;i++) son[i]=NULL;ok=0;}Tree * son[26];bool ok;string str;void add(Tree *rt,string &s){Tree * p=rt;for(int i=0;i<s.size();i++){if(p->son[s[i]-'a']==NULL){p->son[s[i]-'a'] = new Tree();}p=p->son[s[i]-'a'];}p->ok=1;p->str=s;}}T; void dfs(Tree *p,vector<string>&ans,string &b,vector<int>&dp,int k){int n=b.size();if(p->ok&&dp[n]<=k) ans.pb(p->str);vector<int>nt(n+1,0);for(int i=0;i<26;i++){if(p->son[i]!=NULL){nt[0]=dp[0]+1;for(int j=1;j<=n;j++){if(b[j-1]-'a'==i)	nt[j]=min(dp[j-1],min(nt[j-1],dp[j])+1);else  nt[j]=min({dp[j-1],nt[j-1],dp[j]})+1;}dfs(p->son[i],ans,b,nt,k);}}}vector<string> kDistance(vector<string> &a, string &b, int k) {vector<string>ans;Tree *rt= new Tree();for(int i=0;i<a.size();i++){T.add(rt,a[i]); }int n=b.size();vector<int>dp(n+1,0);for(int i=0;i<=n;i++) dp[i]=i; dfs(rt,ans,b,dp,k);return ans;}
}sol;