Acwing.第126场周赛
比赛链接
之前忘记整理上传了，不能有遗留问题
A.蜗牛爬井
蜗牛在 n米深的井底往上爬，每天清晨到傍晚向上爬 5米，夜间又滑下来 4米，请问像这样从某天清晨开始，第几天爬到井口？
输入格式
一个正整数 n。
输出格式
一个整数，表示爬到井口的天数。
思路：
就是一个比较简答的模拟，我们对这个过程进行一个比较简单的模拟就好了
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
int ans=0;
int x=0;
cin>>n;
while(true){
x+=5;
ans++;
if(x>=n){
break;
}
x-=4;
}
cout<<ans<<endl;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
B.替换字符
给定一个长度为 n的字符串 s和一个长度为 m的字符串 t。
字符串 s和 t均由小写字母组成，字符串 s的长度不超过字符串 t的长度。
我们希望字符串 s成为字符串 t 的子串。为此，你可以进行任意次（也可以不进行）字符替换操作。
每次操作可以任选字符串 s中的一个字符并将其替换为 ?。
? 可以视为等于任何其它字符。
请你计算，为了使得字符串 s成为字符串 t的子串，所需进行的最少操作次数，并提供一种具体操作方案。
例如，如果 s为 abd，t为 abcd，那么我们可以进行一次操作，将 s中的第 3个字符替换为 ?，替换后 s变为 ab?，可以与字符串 t 的子串 abc 匹配。
输入格式
第一行包含两个整数 n,m。
第二行包含一个长度为 n 的由小写字母构成的字符串 s。
第三行包含一个长度为 m 的由小写字母构成的字符串 t。
输出格式
首先，输出一行，一个整数 k，表示所需的最少操作次数。
如果 k=0，则输出到此为止，不要输出多余空行。
如果 k≠0，则还需再输出一行 k 个整数，其中第 i 个整数表示第 i 个操作所替换字符的位置编号。s 中字符的位置从左到右依次编号为 1∼n。
如果方案不唯一，输出任意合理方案均可。
思路：
根据原题给的数据范围，我们发现其实模拟是可以解决这个问题的，所以我们可以想着用模拟来解决这个问题，这里我没有给出数据范围，大家可以去上面链接自行查看
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N];
void solve(){
int n,m;
cin>>n>>m;
string s1,s2;
cin>>s1>>s2;
std::vector<int> v;
if(s2.find(s1)!=-1){
cout<<0<<endl;
return ;
}
int k=0x3f3f3f3f;
for(int i=0;i<=m-n;i++){
string s3="";
int ans=0;
for(int j=0;j<n;j++){
if(s1[j]!=s2[j+i]){
ans++;
}
}
k=min(k,ans);
}
cout<<k<<endl;
for(int i=0;i<=m-n;i++){
string s3="";
int ans=0;
for(int j=0;j<n;j++){
if(s1[j]!=s2[j+i]){
ans++;
}
}
if(ans==k){
for(int j=0;j<n;j++){
if(s1[j]!=s2[j+i]){
cout<<j+1<<" ";
}
}
break;
}
}
cout<<endl;
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
扩展字符串
题目链接
这个题面大家还是去看看原题吧
思路：
这个题当时我没有做出来，因为写了一半发现自己的概率论作业没有写呢，赛后看题解发现是一个比较简单的递归题
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, MAXN = 1e18 + 1;
int siz[N];
string s1 = "DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQB";
string s2 = "DKER EPH VOS GOLNJ UKLMH QHNGLNJ A";
string s3 = "AB CPH VOS FSQVB DLMM VOS QHNG A";
string s4 = "AB";
char dfs(int n, int k) {
if (n == 0)
return s1[k - 1];
if (k <= (int)s2.size())
return s2[k - 1];
else if (k <= (int)s2.size() + siz[n - 1])
return dfs(n - 1, k - s2.size());
else if (k <= (int)s2.size() + siz[n - 1] + s3.size())
return s3[k - s2.size() - siz[n - 1] - 1];
else if (k <= (int)s2.size() + siz[n - 1] + s3.size() + siz[n - 1])
return dfs(n - 1, k - s2.size() - siz[n - 1] - s3.size());
return s4[k - s2.size() - siz[n - 1] - s3.size() - siz[n - 1] - 1];
}
signed main(void) {
int t;
cin >> t;
siz[0] = s1.size();
for (int i = 1; i < N; i++) {
int now = siz[i - 1] * 2 + s2.size() + s3.size() + s4.size();
siz[i] = min(MAXN, now);
}
while (t--) {
int n, k;
cin >> n >> k;
if (siz[n] < k) {
cout << ".";
continue;
}
cout << dfs(n, k);
}
return 0;
}
代码2：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
const LL INF = 2e18;
LL len[N];
string s = "DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQB";
string a = "DKER EPH VOS GOLNJ UKLMH QHNGLNJ A";
string b = "AB CPH VOS FSQVB DLMM VOS QHNG A";
string c = "AB";
char f(int n, LL k)
{
if (k > len[n]) return '.';
if (n == 0) return s[k - 1];
if (k <= a.size()) return a[k - 1];
k -= a.size();
if (k <= len[n - 1]) return f(n - 1, k);
k -= len[n - 1];
if (k <= b.size()) return b[k - 1];
k -= b.size();
if (k <= len[n - 1]) return f(n - 1, k);
k -= len[n - 1];
return c[k - 1];
}
int main()
{
len[0] = s.size();
for (int i = 1; i < N; i ++ )
{
len[i] = len[i - 1] * 2 + a.size() + b.size() + c.size();
len[i] = min(len[i], INF);
}
int Q;
scanf("%d", &Q);
while (Q -- )
{
int n;
LL k;
cin >> n >> k;
cout << f(n, k);
}
return 0;
}