Solution
T1 制作徽章
原题链接
简要思路
按照题目模拟即可，注意一定要认真对比样例，一定要认真对比样例，一定要认真对比样例！！！（警钟撅烂）
完整代码
#include<bits/stdc++.h>
using namespace std;
signed main(){
int n;
cin>>n;
for(int i=1;i<=6*n+3;i++){
if(i==1||i==6*n+3){
for(int j=1;j<=10*n+3;j++)
cout<<'#';
cout<<endl;
}
else if(i-1<=n){
for(int j=1;j<=10*n+3;j++){
if(j==1||j==10*n+3)cout<<'#';
else cout<<'.';
}
cout<<endl;
}
else if(i<=6*n+3-n-1){
if(i!=1+n+4*n+1){
for(int k=1;k<=10*n+3;k++){
if(k==1||k==10*n+3||k==2+2*n)cout<<'#';
else cout<<'.';
}
}
else{
for(int j=1;j<=10*n+3;j++){
if(j!=1&&j!=10*n+3&&(j<=2*n+1||j>10*n+3-1-2*n))cout<<'.';
else cout<<'#';
}
}
cout<<endl;
}
else if(i>=6*n+3-n-1){
for(int j=1;j<=10*n+3;j++){
if(j==1||j==10*n+3)cout<<'#';
else cout<<'.';
}
cout<<endl;
}
}
return 0;
}
T2 买苹果
原题链接
简要思路
- 首先枚举得到实际需要买多少个苹果，记为 \(m\)。
- 然后我们将 \(c3\) 对 \(3 × c1\) 取最小值，将 \(c5\) 对 \(5 × c1\) 取最小值，以防止出现捆绑购买比单买更贵的情况。
- 最后枚举买了多少组五个一组的，剩下的苹果尽量买三个一组的，再剩下的只能单买。
完整代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c1,c3,c5;
signed main(){
cin>>n>>c1>>c3>>c5;
int m=0;
while(m+m/5*2+(m%5)/3<n){//枚举需要的苹果的数量
m++;
}
c3=min(c3,c1*3);
c5=min(c5,c1*5);//取 min
int ans=m*c1;
for(int i=0;i<=m;i++){//枚举买了几个 5 个一组的
int surplus=max(m-5*i,1ll*0);//surplus 代表当前除去 5 个一组选的苹果数后所剩余的苹果的数量
ans=min(ans,i*c5+surplus/3*c3+min(surplus%3*c1,c3));//更新所花钱数，维护 ans，使其最小
}
cout<<ans<<endl;
return 0;
}
优化
-
优化一
利用二分答案或直接计算的方法来求 \(m\) 的值。 -
优化二
求出买 \(15\) 个苹果的最优价格，将 \(m\) 个苹果中超出 \(30\) 部分都 \(15\) 个一组购买，直到 \(m \leq 30\)。
T3 写文章
原题链接
简要思路
-
暴力
暴力将文章展开，查询时直接得到那个位置的字符即可。
注意字符串从0开始，从0开始，从0开始！！！（警钟撅烂） -
优化正解
- 可以不把文章展开，每次询问时在文章中遍历，找到查询的位置对应的位置，如果是字符则直接输出，是单词则再算出查询位置对应该单词的哪个字符即可。
- 针对 \(T=0\) 的情况，文章仅由单词组成。设文章中第 \(i\) 个单词的编号为 \(a_i\)。我们求出 \(length(s_{a_i})\) 的前缀和数组 \(p_i\)，即为文章中第 \(i\) 个单词的最后一个字符的位置。询问时，我们可以在 \(p\) 数组上二分得到查询位置对应的单词，然后算出对应哪个字符即可。
- 将非单词的字符也传化理解为一个长度为 \(1\) 的单词，然后结合 \(1\),\(2\) 中优化，就可以得出时间复杂度为 \(O(q log(C + T))\) 的正解
完整代码
- 暴力
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
string s[100005];
int lens[100005];
char a[50000006];
int len;
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>s[i];
lens[i]=s[i].length();
}
char cc=getchar();
while(1){
char c=getchar();
if(c=='\n')break;
if(c=='['){
int x;
cin>>x;
for(int i=0;i<lens[x];i++)
a[++len]=s[x][i];
}
else if(c==']')continue;
else a[++len]=c;
}
while(q--){
int x;
cin>>x;
if(x>len)cout<<'!';
else cout<<a[x];
}
return 0;
}
- 正解
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,q;
string s[MAXN];//常用单词
string t;//文章
int cnt;//现在有 cnt 个单词（把字符看成单词）
int id[MAXN];//第 i 个单词对应的编号
long long pre[MAXN];//前缀和，pre[i] 代表第 i 个单词的最后一个字符在整个字符串中的位置
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=1;i<=26;i++)s[n+i]='a'+i-1;//把 a~z 的每个字符都转化为单词，加到 s 数组的后面
cin>>t;
int len=t.size();//在外面计算好，防止 TLE
int now=0;//用来计算中括号内的数字
for(int i=0;i<len;i++){
if('a'<=t[i]&&t[i]<='z')//字符
id[++cnt]=t[i]-'a'+1+n;//转化
else {
if(t[i]=='[')
now=0;//清零
else if(t[i]==']')
id[++cnt]=now;//记录下来编号
else now=now*10+t[i]-'0';//维护 now 的值
}
}
for(int i=1;i<=cnt;i++)//计算每个单词的前缀和
pre[i]=pre[i-1]+s[id[i]].size();
string ans;//答案字符串
for(int i=1;i<=q;i++){
long long x;
cin>>x;
int p=lower_bound(pre+1,pre+cnt+1,x)-pre;//寻找第一个大于等于的单词
if(p>cnt)ans+='!';//不合法
else ans+=s[id[p]][x-pre[p-1]-1];//答案加上
}
cout<<ans<<endl;
return 0;
}
T4 电车
原题链接
简要思路
-
暴力
Floyd 或 BFS。 -
正解
不会/kel
完整代码
咕咕。
今日习题
戳 这里。
今日总结
-
模拟题一定要将自己的输出和题目给的样例输出仔细比较对比。
-
从小样例入手，一点一点思考，直至正解。
-
学会上厕所（大雾