本次模考共四题
说实话本次模考题目难度不大但需注意的细节很多
T1 小信数 <21031>
观察到该题的数都是以2为底的幂运算
所以这里将原算式转换为二进制的形式
如:2^6+2^5-2^3=1100000-1000
本题的核心就是对二进制数做减法运算
for(int i=a-c;i>=0;i--){
if(ans[i]=='1'){ //如果够减
ans[i]='0';
cnt--;
break;
}
else{ //如果不够减就向前一位借1
cnt++;
ans[i]='1';
}
}
(ans下标从0开始 表示该二进制的最高位 cnt表示1的个数其初始值为2）
T2 糖豆人派对 <21406>
该题的题目描述有些问题 
如果说d[i]为负数时应该向左走abs(d[i])步或向右走d[i]步
但这并不影响我们做题
如果暴力枚举0-r个位置我们只能得到Test1-Test12的60分
for(long long i=0;i<=r;i++){
long long tem=i;
for(int j=1;j<=n;j++){
tem+=d[j];
if(tem>r) tem=r;
else if(tem<0) tem=0;
}
if(ans==-1) ans=tem;
else{
if(ans!=tem){
cout<<-1;
return 0;
}
}
}
因为所以玩家的移动指令是相同的
所以我们只需模拟i=0和i=r两种情况即可
long long int st=0,ed=r;
for(int i=1;i<=n;i++){
st+=d[i];
if(st>r) st=r;
else if(st<0) st=0;
}
for(int i=1;i<=n;i++){
ed+=d[i];
if(ed>r) ed=r;
else if(ed<0) ed=0;
}
if(st==ed) cout<<st;
else cout<<-1;
T3 破译密码机 <21034>
因为n,m都是小于15的
所以该题我们可以考虑搜索 枚举每次折叠的长度
(考虑正负 正数表示从左边折到右边 负数表示右边折到左边）
总折叠长度的绝对值应该等与n-m
即
n-m=\sum_{i=0}^kabs(d[i])
(k表示折叠次数 d[i]表示每次折叠的长度）
接下来就是对每次折叠进行具体操作了
这里的下标处理有点麻烦 我就不展开细讲了
直接上dfs代码
void dfs(int x,int sum,int cnt){
if(sum>=x){
if(sum==x){
int tem[N],sym1=0,sym2=0;
memset(tem,0,sizeof(tem));
for(int i=1;i<=n;i++){
tem[i]=a[i];
}
int l=1,r=n;
for(int i=1;i<cnt;i++){
if(ans[i]>0){
for(int j=l;j<=ans[i]+l-1;j++){
tem[2*ans[i]+2*l-1-j]=tem[j]+tem[2*ans[i]+2*l-1-j];
tem[j]=0;
}
l+=ans[i];
}
else{
for(int j=r;j>=r+ans[i]+1;j--){
tem[2*r+2*ans[i]+1-j]=tem[j]+tem[2*r+2*ans[i]+1-j];
tem[j]=0;
}
r+=ans[i];
}
}
for(int i=l;i<=r;i++){
if(b[i-l+1]!=tem[i]){
sym1=1;
}
}
for(int i=r;i>=l;i--){
if(b[r-i+1]!=tem[i]){
sym2=1;
}
}
if(sym1==0||sym2==0) flag=1;
}
return ;
}
if(flag==1) return ;
for(int i=-x;i<=x;i++){
if(sum+abs(i)>x||i==0) continue;
ans[cnt]=i;
int now_sum=sum+abs(i);
dfs(x,now_sum,cnt+1);
}
}
因为我们没有考虑在收尾端折叠的情况
所以我们应将tem数组正序和逆序判断两遍
只要有一种情况符合即可
(以上代码中对tem下标变换有疑问的话可以发在讨论区）
T4 最优匹配 <19501>
这题其实是 编辑距离<14094>的优化版
在距离编辑中我们的dp是这样的
for(int i=1;i<=len_a;i++){
for(int j=1;j<=len_b;j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
}
}
}
如果dp不懂的话可以找下距离编辑的讲解
显然这题中1e6的平方肯定会
Time Limit Exceeded+Memory Limit Exceeded
那如何对空间和时间同时优化呢 其实很简单
对于空间
每一个dp[i][j]只与dp[i-1][j],dp[i][j-1]和dp[i-1][j-1]有关
所以我们可以开一个滚动数组
const int N=1e6+5;
int dp[2][N];
每行模拟结束后互换已处理位置和预处理的行标
对于时间
如果两个字符串的长度大于k 结果肯定是不能的
所以我们在枚举j时只需从i-k到i+k即可
int l=0,r=1;
for(int i=1;i<=len_a;i++){
for(int j=max(1,i-k);j<=min(len_b,i+k);j++){
if(a[i]==b[j]){
dp[r][j]=dp[l][j-1];
}
else{
dp[r][j]=min({dp[l][j],dp[r][j-1],dp[r][j-1]})+1;
}
}
swap(l,r);
}
最后只需判断dp[l][len_b]的值即可
(注意 dp的值应初始化为0x3f dp[0][0]的值为0）
总结
本次模考有两点细节值得注意和总结
T3枚举折叠长度后将数值相加的下标变化
T4滚动数组解决数组长度超限的问题
