牛客小白月赛34 部分题解
比赛链接
@TOC
A.dd爱科学1.0(DP)
题目
链接：https://ac.nowcoder.com/acm/contest/11211/A 来源：牛客网 题目描述 大科学家dddd最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成，dddd经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的dddd开始着手修改白菜的基因序列，dddd每次修改基因序列的任意位需要的代价是11，dddd想知道，修改白菜的基因序列使其高附加值达到最高，所需要的最小代价的是多少。 输入描述: 第一行一个正整数n(1≤n≤1000000) 第二行一个长度为n的字符串，表示所给白菜的基因序列 保证给出字符串中有且仅有大写英文字母 输出描述: 输出一行，表示最小代价 示例1 输入 复制 5 ACEBF 输出 复制 1 说明 改成ACEEF或者ACEFF，都只用改动一个字符，所需代价最小为1
思路:
最长上升(非严格)子序列,DP做法复杂度O(n*26),因为值域只是'A'~'Z'所以速度比贪心快;
f[i]表示以s[i]结尾最长的上升序列;
last[k]表示上个s[i]==(k+'A')的i位置;
code:DP
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int f[1000010];
string t;
int last[28];
int main()
{
cin>>n;
cin>>t;
s=" ";
s+=t;
int ans=0;
for(int i=1;i<s.size();i++)
{
int k=s[i]-'A';
f[i]=1;
for(int j=0;j<=k;j++)
{
f[i]=max(f[i],f[last[j]]+1);
}
last[k]=i;
ans=max(f[i],ans);
}
cout<<n-ans<<'\n';
return 0;
} code:贪心,二分
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e6+10;
string s;
char q[N];
int tt;
int main()
{
cin>>n;
cin>>s;
int ans=0;
q[tt++]=s[0];
for(int i=1;i<s.size();i++)
{
if(s[i]>=q[tt-1])q[tt++]=s[i];
else *upper_bound(q,q+tt,s[i])=s[i];//严格用up 非严格用low
ans=max(ans,tt);
}
cout<<n-ans<<'\n';
return 0;
} B.dd爱探险(状态压缩DP)
题目
链接：https://ac.nowcoder.com/acm/contest/11211/B 来源：牛客网 题目描述 星际中有nn个空间站，任意两个空间站间可以相互跳跃，由空间站xx跳跃到空间站yy所需要的代价为P[x][y]P[x][y],注意不保证p[x][y]=p[y][x]p[x][y]=p[y][x]，dddd可以任意选择出发的空间站，并通过恰好n-1n−1次跳跃把所有空间站跳完，并且dddd必须选择22次跳跃，其中一次跳跃中进行重力加速，另一次跳跃中进行反重力加速，重力加速会导致当前跳跃代价变为00，反重力加速会导致当前跳跃代价翻倍(乘22)，问跳完所有空间站所需要最小代价 输入描述: 第一行一个数n(3≤n≤16) 接下来n行每行n个数，第x行第y个数表示p[x][y](0≤p[x][y]≤100000) 输出描述: 一个数,表示最小代价 示例1 输入 复制 3 0 2 1 2 0 1 3 1 0 输出 复制 2 说明 1->2重力加速 2->3反重力加速 代价0+1*2=2
思路:
思路来源于lyd老师的<<算法进阶指南>>中的最短Hamilton路径
空间站最多有16个
用二进制压缩成1个大小为2的16次方的数表示16个空间站;
状态表示:
f[ i ][ j ][ 0~3 ] i 表示对应2进制某位为1表示该空间站访问过,j表示当前在访问第j个空间站; 0表示没使用 重力/反重力加速, 1表示先使用重力加速,消耗代价为0 2表示先试用非重力加速,消耗代价*2 3表示使用完了加速 消耗0或 *2代价
状态转移
对应状态f[i][j][x]:
先忽略x的改变,
对于状态i在第j位,状态i^(1<<j)在第k位;
且第j位不等于第k位;
f[i^(1<<j)][k][x]--->f[i][j][x]
对于x
0->0代价不变
0->1代价为0
0->2代价*2
1->1代价不变
1->3代价*2
2->2代价不变
2->3代价为0
3->3代价不变初始化
因为dd可以选择任意的地点出发, 所以for(int i=0;i<n;i++)f[1<<i][i][0]=0; 其他都为正无穷
答案
因为dd最后可以在任意地点 所以for(int i=0;i<n;i++)ans=min(ans,f[(1<<n)-1][i][3]);
code:
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<16;
int p[20][20];
int n;
int ans;
int f[M][N][4];
//状态表示:f[i][j][]:i在二进制下是1表示当前位置跳过,j表示现在在哪,0表示没有重力加速,1,2表示用了,3表示全用了
//
signed main()
{
cin>>n;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cin>>p[i][j];
memset(f,0x3f,sizeof f);
for(int i=0;i<n;i++)f[1<<i][i][0]=0;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
if(i>>j&1)
{
for(int k=0;k<n;k++)
{
if(i^(1<<j)>>k&1)
{
int t=i^(1<<j);
f[i][j][0]=min(f[t][k][0]+p[k][j],f[i][j][0]);
f[i][j][1]=min(f[i][j][1],min(f[t][k][0],f[t][k][1]+p[k][j]));
f[i][j][2]=min(f[t][k][0]+2*p[k][j],min(f[t][k][2]+p[k][j],f[i][j][2]));
f[i][j][3]=min(f[i][j][3],min(f[t][k][2],f[t][k][3]+p[k][j]));
f[i][j][3]=min(f[i][j][3],f[t][k][1]+2*p[k][j]);
}
}
}
}
}
int ans=1e9;
for(int i=0;i<n;i++)ans=min(ans,f[(1<<n)-1][i][3]);
cout<<ans<<'\n';
return 0;
} C.dd爱科学2.0(DP)
题目
链接：https://ac.nowcoder.com/acm/contest/11211/C 来源：牛客网 题目描述 大科学家dddd最近在研究转基因白菜，白菜的基因序列由一串大写英文字母构成，dddd经过严谨的推理证明发现，只有当白菜的基因序列呈按位非递减形式时，这株白菜的高附加值将达到最高，于是优秀的dddd开始着手修改白菜的基因序列，dddd每次可以选择基因序列的一位进行修改，每次当她把一个字母xx修改成yy时，会产生|x-y|∣x−y∣(即xx与yy的ASCIIASCII码差值的绝对值)的改动偏移量，dddd希望，修改白菜的基因序列使其高附加值达到最高，并且基因序列的改动偏移量总和最小，她想知道最小的改动偏移量总和是多少。 输入描述: 第一行一个正整数n(1≤n≤1000000) 第二行一个长度为n的字符串，表示所给白菜的基因序列 保证给出字符串中有且仅有大写英文字母 输出描述: 输出一行，表示最小改动偏移量总和 示例1 输入 复制 5 AEEBC 输出 复制 5 说明 改成AEEEE或ACCCC偏移量总和最小 改成AEEEE，偏移量总和为|B-E|+|C-E|=3+2=5 改成ACCCC，偏移量总和为|E-C|+|E-C|+|B-C|=2+2+1=5 所以最小偏移量总和为5
思路
状态表示:f[ i ][ j ]表示前i个字符最后一个变为 ( j +'A' ) 的最小代价;
状态转移:min( f[ i - 1 ][ 0 ~ j ] ) ---> f[ i ][ j ]
初始化:f[ 0 ][ 0 ]为0,其他都为负无穷;
答案:f[ n ][ 0 ~ 25 ]把最后一个字符改为'A'~'Z'中的最小值;
code
#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e6+10;
char s[N];
int f[N][26];
signed main()
{
cin>>n>>s+1;
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
{
int k=s[i]-'A';
int x=2e9;
for(int j=0;j<26;j++)
{
x=min(x,f[i-1][j]);
f[i][j]=abs(k-j)+x;//min(f[i-1][0~j])-->f[i][j]
}
}
int ans=1e9;
for(int i=0;i<26;++i)ans=min(ans,f[n][i]);
cout<<ans<<'\n';
return 0;
} D.dd爱矩阵(优先队列,贪心)
题目
链接：https://ac.nowcoder.com/acm/contest/11211/D
来源：牛客网
题目描述
给一个n*nn∗n的矩阵，每行各选一个数字，把选出来的n个数字相加，一共有n^{n}n
n
种可行答案，你只要输出前nn大就行了
输入描述:
第一行一个数正整数n(1≤n≤500)，表示矩阵大小
接下来n行，每行n个数描述矩阵，矩阵中数字取值范围在[1,500000]内
输出描述:
一行，n个数，输出前n大的结果
示例1
输入
复制
5
6 6 4 4 5
5 6 8 5 7
6 1 6 9 4
4 8 8 1 5
9 2 3 9 3
输出
复制
40 40 40 40 40思路
老题了,紫书蓝书里面都讲过,
洛谷P1631简单版本,P1392正常版本;
先看简单版本:
假设我们现在只需要合并2个数组,求最小的n个和,设n为4,那么有16种组合方式,
先把a数组排序(只对a排序,b不需要);
| a1+b1 |a2+b1 |a3+b1 |a4+b1 |
|--|--|--|--|
| a1+b2 | a2+b2 | a3+b2|a4+b2 |
| a1+b3 | a2+b3 | a3+b3|a4+b3 |
| a1+b4 | a2+b4 | a3+b4|a4+b4 |
第一列都是a数组中的最小值加上b,那么16个数中的最小值就在第一列中.
假设最小的是a1+b3,那么下次最小值就在
a1+b1
a1+b2
a2+b3
a1+b44个数中选
再重复上面步骤,
我们可以先将4个数丢入优先队列,就可以快速找到最小值,丢入的时候我们需要维护a的下标 ,可以发现,每次a的下标都会+1,而b的下标不变;
经过n次操作,可以取出n个最小值,很明显是单调递增的.
正常版本就是把n个最小值当成a数组继续与其他数组合并;
code
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N],b[N],c[N];
typedef pair<int,int>pii;
signed main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n,greater<int>());
for(int j=1;j<n;j++)
{
priority_queue<pii,vector<pii>>q;
for(int i=0;i<n;i++)
{
cin>>b[i];
q.push({b[i]+a[0],0});
}
for(int i=0;i<n;i++)
{
auto t=q.top();;
q.pop();
c[i]=t.first;
q.push({t.first-a[t.second]+a[t.second+1],t.second+1});
}
memcpy(a,c,4*n);
}
for(int i=0;i<n;i++)cout<<a[i]<<" \n"[i==n-1];
return 0;
} E.dd爱旋转(水题)
题目
链接：https://ac.nowcoder.com/acm/contest/11211/E
来源：牛客网
题目描述
【题目描述】
读入一个n*nn∗n的矩阵，对于一个矩阵有以下两种操作
11:顺时针旋180°180°
22:关于行镜像
如
\left[ \begin{matrix} 1 & 2 \\ 3 & 4\\ \end{matrix} \right][
1
3
2
4
]变成\left[ \begin{matrix} 3 & 4 \\ 1 & 2\\ \end{matrix} \right][
3
1
4
2
]
给出qq个操作，输出操作完的矩阵
输入描述:
第一行一个数n(1≤n≤1000)，表示矩阵大小
接下来n行，每行n个数，描述矩阵，其中数字范围为[1,2000]
一下来一行一个数q(1≤q≤100000)，表示询问次数
接下来q行，每行一个数x(x=1或x=2)，描述每次询问
输出描述:
n行，每行n个数，描述操作后的矩阵
示例1
输入
复制
2
1 2
3 4
1
1
输出
复制
4 3
2 1
示例2
输入
复制
2
1 2
3 4
1
2
输出
复制
3 4
1 2思路:
大概模拟下,
操作1:关于行和列镜像
操作2:对行镜像
所以只需要记录下对行和列的操作次数就可以了,是奇数就输出的时候镜像处理;
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
int r=0,c=0;
int q;
cin>>q;
while(q--)
{
int x;
cin>>x;
r^=1;
if(x&1)c^=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<g[r?n-i+1:i][c?n-j+1:j]<<" \n"[j==n];
}
}
return 0;
} F.dd爱框框(双指针)
题目
链接：https://ac.nowcoder.com/acm/contest/11211/F 来源：牛客网 题目描述 读入n，xn，x,给出nn个数a[1],a[2],……,a[n]a[1],a[2],……,a[n],求最小的区间[l,r][l,r]，使a[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥x，若存在相同长度区间，输出ll最小的那个 输入描述: 第一行两个数，n(1≤n≤10000000),x(1≤x≤10000) 第二行n个数a[i](1≤a[i]≤1000) 输出描述: 输出符合条件l,r(保证有解) 示例1 输入 复制 10 20 1 1 6 10 9 3 3 5 3 7 输出 复制 3 5
思路:
其实有点像单调队列?
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,m;
int a[N];
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//不关就炸
cin>>n;
cin>>m;
for(int i=1;i<=n;i++)cin>>a[i];
int sum=0;
int ansl=1,ansr=n;
int l=1,r=0;
while(l<=n)
{
while(r<=n&&sum<m)
{
sum+=a[++r];
}
if(r>n)break;
if(r-l<ansr-ansl)
{
ansr=r;
ansl=l;
}
sum-=a[l++];
}
cout<<ansl<<" "<<ansr<<'\n';
return 0;
} 
