【题解】2020牛客寒假算法基础集训营第五场
A. 模板
题目看起来是编辑距离的模板题，其实就是一个很简单的题目，贪心地考虑问题。先考虑两个字符串相同的部分，显然，只要把原字符串和新字符串不同的字符修改就行了；对于两个字符串后面不同的部分，如果原字符串比较长，就全部删掉；如果原字符串比较短，就对照第二个字符串添加字符。所以，只要按照两个字符串较大的长度进行遍历，比较两个字符串不同的字符有几个就可以了。如果一个字符串比较短，那么它后面的部分可以看成\0，同样可以参与字符串比较。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
char str[2][MAXN];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
scanf("%s%s", str[0], str[1]);
int len = max(n, m);
int cnt = 0;
for (int i = 0; i < len; i++)
{
if (str[0][i] != str[1][i])
{
cnt++;
}
}
printf("%d\n", cnt);
return 0;
} B. 牛牛战队的比赛地
题目要求最大距离最小，很容易想到使用二分或者三分的方法去做。
这题使用三分会比较简单，二分会比较麻烦。
#include <bits/stdc++.h>
using namespace std;
struct p{
int x,y;
}a[100005];
int n;
double check(double x)
{
double max=0;
for (int i=1;i<=n;i++)
{
double tmp=sqrt(a[i].y*a[i].y+(a[i].x-x)*(a[i].x-x));
if (tmp>max) max=tmp;
}
return max;
}
double tsearch(double left,double right){
int i;
double mid,midmid;
for(i=0;i<100;i++){
mid=left+(right-left)/2;
midmid=mid+(right-mid)/2;
if(check(mid)>check(midmid)) //极大值求法
left=mid;
else
right=midmid;
}
return mid;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
double max=tsearch(-10000,10000);
printf("%.4lf\n",check(max));
return 0;
} EX：大家可以思考一下，二分怎么做呢
C. C语言IDE
不大不小的模拟，由于题目的情况不是很多，因此只需要匹配){}的组合即可，这样的组合最外层一定是函数，通过括号匹配，里面的do for while 等均直接被匹配消除~
一开始自己还想出结构体内的，后来发现太复杂了，就出了弱化版本~
#include <bits/stdc++.h>
using namespace std;
string source;
void replaceAll(string &s, string oldstr, string newstr)
{
for (string::size_type pos = 0; pos != string::npos; pos += newstr.length())
if ((pos = s.find(oldstr, pos)) != string::npos) s.replace(pos, oldstr.length(), newstr);
else break;
}
struct functions{
string inClass, name, outputType;
vector<string> inputType;
functions(string inClass = "", string name = "", string outputType = "void", vector<string> inputType = vector<string>(0))
:inClass(inClass), name(name), outputType(outputType), inputType(inputType) {}
};
vector<functions> funs;
void solve(string &s)
{
replaceAll(s, "/*", " /* ");
replaceAll(s, "*/", " */ ");
replaceAll(s, "//", " // ");
replaceAll(s, "(", " ( ");
replaceAll(s, ")", " ) ");
replaceAll(s, "{", " { ");
replaceAll(s, "}", " } ");
replaceAll(s, "=", " = ");
replaceAll(s, "\"", " \" ");
replaceAll(s, "'", " ' ");
replaceAll(s, ";", " ; ");
replaceAll(s, ",", " , ");
replaceAll(s, "+ = ", "+=");
replaceAll(s, "- = ", "-=");
replaceAll(s, "* = ", "*=");
replaceAll(s, "/ = ", "/=");
replaceAll(s, "^ = ", "^=");
replaceAll(s, "| = ", "|=");
replaceAll(s, "& = ", "&=");
replaceAll(s, ":", " : ");
replaceAll(s, " : : ", "::");
//ע���滻������ע��
vector<string> tokens; string now = "";
for (int i = 0; s[i]; i++)
{
if (s[i] == ' ' || s[i] == '\t' || s[i] == '\r' || s[i] == '\n' || s[i] == '\0')
{
if (now != "")
{
if (now == ":" && tokens.back() == ")")
{
string tmpnow = "";
for (int j = i + 1; s[j]; j++)
{
if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0')
{
if (tmpnow == "{")
{
now = "{";
i = j - 1;
break;
}
tmpnow = "";
}
else tmpnow += s[j];
}
continue;
}
if (now == "const")
{
now = "";
continue;
}
if (now == "//")
{
for (int j = i; s[j]; j++)
{
if (s[j] == '\n')
{
i = j - 1;
break;
}
}
now = "";
continue;
}
if (now == "/*")
{
int num = 1;
string tmpnow = "";
for (int j = i + 1; s[j]; j++)
{
if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0')
{
if (tmpnow == "/*") num++;
if (tmpnow == "*/")
{
num--;
if (num == 0)
{
i = j - 1;
break;
}
}
tmpnow = "";
}
else tmpnow += s[j];
}
now = "";
continue;
}
//cout << now << s[i];
tokens.push_back(now);
now = "";
}
//else cout << s[i];
}
else now += s[i];
}
int cnt = 0;
string nowNamespace = "";
for (int i = 1; i < (int)tokens.size(); i++)
{
if ((tokens[i] == "struct" || tokens[i] == "class") && tokens[i + 2] == "{")
{
cnt = 0;
nowNamespace = tokens[i + 1];
i += 2;
}
functions tmp(nowNamespace);
if (tokens[i] == "{" && tokens[i - 1] == ")")
{
int num = 1;
for (int j = i - 2; j >= 0; j--)
{
if (tokens[j] == ")") num++;
if (tokens[j] == "(")
{
num--;
if (num == 0)
{
tmp.name = tokens[j - 1];
tmp.outputType = "";
for (int k = j - 2; k >= 0; k--)
if (tokens[k] != "}" && tokens[k] != "}" && tokens[k] != ";" &&
tokens[k].back() != ':' && tokens[k] != "inline" &&
tokens[k] != "static" && tokens[k][0] != '#' &&
tokens[k].back() != '\"' && tokens[k].back() != '>')
tmp.outputType = tmp.outputType == "" ? tokens[k] : tokens[k] + " " + tmp.outputType;
else break;
int last = i - 2;
for (int k = i - 2; k >= j; k--)
{
if (tokens[k] == "(" || tokens[k] == ",")
{
string tt = "";
for (int t = k + 1; t < last; t++)
tt = tt == "" ? tokens[t] : tt + " " + tokens[t];
if (tt != "") tmp.inputType.push_back(tt);
last = k - 1;
}
if (tokens[k] == "=" || tokens[k] == ")") last = k - 1;
}
reverse(tmp.inputType.begin(), tmp.inputType.end());
break;
}
}
}
funs.push_back(tmp);
num = 1;
for (int j = i + 1; j < (int)tokens.size(); j++)
{
if (tokens[j] == "{") num++;
if (tokens[j] == "}")
{
num--;
if (num == 0)
{
i = j;
//cout << tmp.outputType << " " << tmp.name << " ";
//cout << j << endl;
break;
}
}
}
continue;
}
if (nowNamespace != "")
{
//cout << i << " " << nowNamespace << " " << cnt << endl;
if (tokens[i] == "{") cnt++;
if (tokens[i] == "}")
{
cnt--;
if (!cnt) nowNamespace = "";
}
}
}
}
int main()
{
char ch;
while ((ch = getchar()) != EOF)
source += ch;
solve(source);
for (auto & i: funs)
{
if (i.outputType != "") cout << i.outputType << " ";
if (i.inClass != "") cout << i.inClass << "::";
cout << i.name << "(";
for (int j = 0; j < (int)i.inputType.size(); j++)
cout << i.inputType[j] << (j == (int)i.inputType.size() - 1 ? ")" : ",");
if ((int)i.inputType.size() == 0) cout << ")";
cout << endl;
}
return 0;
} D. 牛牛与牛妹的约会
贪心。比较直接走和闪现哪一个可以走的更快，选择更快的方法去走即可。
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
const double eps = 1e-8;
int main()
{
int T; cin>>T;
while(T--){
int a, b; scanf("%d%d", &a, &b);
double ans = 0;
double ca = a, cb = b;
double p = 1.0/3.0;
while(1){
double na;
if(ca < 0) na = -pow(-ca,p);
else na = pow(ca, p);
if(abs(na-cb)+1.0 < abs(ca-cb)) ans += 1.0, ca = na;
else {
ans += abs(ca-cb); break;
}
}
printf("%.9f\n", ans);
}
} E. Enjoy the game
找规律可以发现，当张数是的时候输出
Alice，否则输出Bob。
如果不是，先手直接拿等同于其二进制最低位的数量的张数，后手将无力还击~
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n;
scanf("%lld", &n);
long long tmp = 2;
for (int i = 1; i <= 60; i++)
{
if (tmp == n)
{
printf("Alice\n");
return 0;
}
tmp = tmp * 2;
}
printf("Bob\n");
return 0;
} F. 碎碎念
考虑到了第句话时候，这种状态可能由两种状态转移而来。
- 直接一发AC，从第
句话直接到达第
句。
- 如果
,可以由一发RJ从
句到达第i句。 构造
，
表示到了第
表示到了第i句话，是由
（前面一发是WA是AC无关紧要）
(
易确定边界条件 ;
;
由于有次查询 ，查询数目较多，我们可以线性时间内预处理前
项和即前缀和，然后用第
项减去第
项即可。
#include <bits/stdc++.h>
#define MAXN 100005
const int P = 1e9+7;
using namespace std;
typedef long long ll;
int dp[MAXN][4]={0};
int l,r;
int main() {
int q,k;
scanf("%d%d",&k,&q);
dp[0][0]=1;
for(int i=1;i<MAXN;i++)
{
dp[i][0]=(dp[i-1][0]+dp[i-1][1])%P;
if(i>=k)
{
dp[i][1]=dp[i-k][0];
}
}
dp[0][3]=1;
for(int i=1;i<MAXN;i++)
{
dp[i][3]=((dp[i][0]+dp[i][1])%P+dp[i][2])%P;
// printf("%d ",dp[i][3]);
dp[i][3]+=dp[i-1][3];
dp[i][3]%=P;
}
for(int i=0;i<q;i++)
{
scanf("%d%d",&l,&r);
ll ans=dp[r][3]-dp[l-1][3];
printf("%lld\n",((ans%P+P)%P));
}
return 0;
} G. 街机争霸
因为所有僵尸的行走长度是一样的，所以周期长度应该为，所以在普通的bfs基础上加上一维表示时间，从当前位置
和时间
去更新
周围位置时间
的
数组，并且加入队列，直到到达终点或者队列为空，即可求出最佳答案。
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define P pair<int,int>
using namespace std;
const int maxn = 505;
int n, m, p, k;
int dstx, dsty;
char mp[maxn][maxn];
int zmb[maxn][maxn][20];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int dz[2] = {-1, 1};
int vis[maxn][maxn][20][2];
struct node{
int x, y, z, ud;
};
queue<node> q;
void init(){
cin>>n>>m>>p>>k;
memset(vis, -1, sizeof vis);
assert(n <= 500 & n >= 3 && m >= 3 && m <= 500 && p <= 50 && p >= 0 && k <= 10 && k >= 2);
for(int i = 0; i < n; ++i) {
scanf("%s", mp[i]);
for(int j = 0; j < m; ++j){
if(mp[i][j] == 'A') dstx = i, dsty = j;
else if(mp[i][j] == 'L'){
q.push((node){i,j,0,0}); vis[i][j][0][0] = 0;
}
}
}
for(int i = 0; i < p; ++i){
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
zmb[x][y][0] = 1;
int dst;
char cmd[10]; scanf("%s", cmd);
if(cmd[0] == 'U') dst = 0;
else if(cmd[0] == 'D') dst = 1;
else if(cmd[0] == 'L') dst = 2;
else if(cmd[0] == 'R') dst = 3;
for(int i = 1; i < k; ++i){
x = x + dx[dst]; y = y + dy[dst];
zmb[x][y][i] = 1;
}
}
// for(int t = 0; t < k; ++t){
// cout<<endl;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout<<zmb[i][j][t]<<" ";cout<<endl;
// }
// }
}
bool ok(int x, int y, int z){//board && 障碍 && zombie
if(x < 0 || x >= n) return 0;
if(y < 0 || y >= m) return 0;
if(mp[x][y] == '&') return 0;
if(zmb[x][y][z]) return 0;
return 1;
}
void sol(){
int ans = -1;
while(q.size()){
node temp = q.front(); q.pop();
int x = temp.x, y = temp.y, z = temp.z;
//cout<<"x:"<<x<<" y:"<<y<<" z:"<<z<<endl;
if(x == dstx && y == dsty){
ans = vis[x][y][z][temp.ud]; break;
}
int xx, yy, zz, dst = temp.ud;
if(z == 0 || z == k-1) dst ^= 1;
for(int i = 0; i < 4; ++i){
xx = x + dx[i];
yy = y + dy[i];
zz = z + dz[dst];
if(ok(xx, yy, zz) && vis[xx][yy][zz][dst] == -1){
vis[xx][yy][zz][dst] = vis[x][y][z][temp.ud]+1;
q.push((node){xx,yy,zz,dst});
}
}
}
if(ans == -1) cout<<"Oh no"<<endl;
else cout<<ans<<endl;
}
int main()
{
init();
sol();
} H. hash
观察给的哈希函数可以轻松看出，这个哈希函数就仅仅是把一个只由小写字符组成的字符串当成了一个26进制的数，不取模的情况下，任意小写字符串和自然数是一一对应的。因此，只要把给的字符串转换成对应的26进制整数，加上模数后转换回字符串，一定可以得到一个最小字典序大于原串的字符串。只要这个新字符串长度为6即是满足要求的字符串。
#include <iostream>
using namespace std;
const int LEN = 6;
int mod;
char str[15];
int main()
{
#ifndef ONLINE_JUDGE
freopen("hash.in", "r", stdin);
freopen("hash.out", "w", stdout);
#endif
while (scanf("%s%d", str, &mod) != EOF)
{
long long res = 0;
for (int i = 0; i < LEN; i++)
{
res = res * 26 + str[i] - 'a';
}
res += mod;
for (int i = LEN - 1; i >= 0; i--)
{
str[i] = res % 26 + 'a';
res /= 26;
}
if (res)
{
puts("-1");
}
else
{
printf("%s\n", str);
}
}
return 0;
} I. I题是个签到题
签到题。判断是否大于等于，或者排过序以后是否大于等于
即可。
#include <bits/stdc++.h>
using namespace std;
pair<int,int> problems[15];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
int curcnt = 0;
for (int i = 1; i <= n; i++)
{
int t;
scanf("%d", &t);
problems[i] = {i, t};
if (i == 9) curcnt = t;
}
int tmp;
if (m % 5 != 0) tmp = (int)(m * 0.8) + 1;
else tmp = m / 5 * 4;
sort(problems + 1, problems + n + 1, [](const pair<int, int> a, const pair<int, int> b) -> bool{
return a.second > b.second;
});
if (curcnt >= tmp || curcnt >= problems[3].second) printf("Yes\n");
else printf("No\n");
return 0;
}
J. 牛牛战队的秀场
先求一条边的边长。如图，边形对应的
，边长就是
。
再求i到j最短经过几条边：
最后答案就是
#include <bit/stdc++.h>
using namespace std;
const double PI = acos(-1);
int main()
{
int n;
double r;
scanf("%d%lf", &n, &r);
int i, j;
scanf("%d%d", &i, &j);
i--, j--;
double dis = min((i - j + n) % n, (j - i + n) % n);
double deg = PI / n;
double len = r * sin(deg) * 2;
printf("%lf\n", len * dis);
return 0;
}
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42975793
中移(苏州)软件技术有限公司工作强度 29人发布