A
solution:
每次只能在尾部操作，所以题目非常简单，只需要找到每个位置不相同的字符，长度不相同可以选择删除长的字符串，也可以选择添加短的字符串
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n,m,cnt = 0;
string s1,s2;
cin>>n>>m;
cin>>s1>>s2;
int minn = min(n , m);
for(int i=0;i<minn;i++)
{
if(s1[i] != s2[i]){
cnt++;
}
}
cout<<cnt + abs(n - m)<<endl;
return 0;
}B
solution:
第一次遇到三分的题目，，，
给你n个点，在x轴上找一点，求出该点到所有点的最大距离的最小值。
在x轴，没法证明这些点是单调的，二分不好做，用三分来找峰值
多写几个三分再来加点讲解
std
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
double a[maxn],b[maxn];
int n;
bool check(double mid)
{
double x = -10000.0,y = 10000.0;
for(int i=1;i<=n;i++)
{
if(fabs(b[i]) > mid)
return 0;
double z = sqrt(mid*mid - b[i]*b[i]);
if(a[i] - z > x)
x = a[i] - z;
if(a[i] + z < y)
y = a[i] + z;
}
return x - 1e-8 <= y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i],&b[i]);
double l = 0,r = 20000;
while(l <= r)
{
double mid = (l+r)/2;
if(check(mid))
r = mid - 1e-8;
else
l = mid + 1e-8;
}
printf("%.6lf\n",l);
return 0;
}C
solution:no solution，不大不小的模拟写哭了
D
solution:
一开始写成了搜索，写完测了几组样例有点不对，长记性了，还是先模拟模拟再写
其实只需要找到一个临界点，当选择闪现比每单位走1m的情况坏的时候，就不能再使用闪现
举个例子 ：
牛可乐在-27，牛妹在5
第一次移动，牛可乐选择闪现到-3
第二次移动，牛可乐选择闪现到-3^(1/3)
第三次移动，如果接着使用闪现，永远无法到达正半轴，如果移动多个1m到达了正半轴，当前的点的三分之一次方无法到达一个比它大的数字上，所以一旦不使用闪现，接下来一定是一直以1m/s的方式移动
所以我们只要贪心的考虑每次移动的好坏
如果闪现的距离大于等于1m，且缩短距离就是用闪现
否则计算两人间的距离，累加到答案里，break
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
const double esp = 1e-8;
int main()
{
int t;
cin>>t;
while(t--)
{
int a,b;
scanf("%d %d",&a,&b);
double ans = 0;
double x = a,y = b;
double pi = 1.0/3.0;
while(1)
{
double z;
if(x < 0)
z = -pow(-x,pi);
else
z = pow(x,pi);
if(fabs(z - y) + 1.0 < fabs(x - y))
ans += 1.0,x = z;
else{
ans += fabs(x - y);
break ;
}
}
printf("%.9lf\n",ans);
}
return 0;
}E
solution:
没怎么学过博弈的算法，就找了找规律，考虑临界点，即必赢点或者必输点，
n = 奇数，先手必赢(先手每次只取1张牌)，不再考虑奇数
n = 2，先手必输
n = 4，先手必输 所以结论是n为偶数先手必输？
n = 6，先手拿两张牌，n = 4，后手必输
n = 8，先手必输
n =10，先手拿2张牌，n = 8，后手必输
n =12，先手拿4张牌，n = 8，后手必输
n =14，先手拿6张牌，n = 8，后手必输
n =16，先手必输
规律出来了~
当n = 2的次幂，先手必输，否则先手必赢
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n;
int flag = 0;
cin>>n;
for(ll i=2;i<=1e18;){
if(n < i){
break ;
}
if(n == i){
flag = 1;
break ;
}
i = i*2;
}
if(flag){
printf("Alice\n");
}else{
printf("Bob\n");
}
return 0;
}F
solution:
想必大家题目都理解的有点模糊，题目准确的说给你的x是每次RJ的时候会连续说几个“你能不能行啊”。然后给出你区间[l,r]，让你输出这个区间所有可能的情况
这么一想是不是简单点了？由于有多次查询，我们只能预处理好前缀和
dp[i][0]表示说了i句话，且当前RJ了
dp[i][1]表示说了i句话，且当前AC了
状态转移方程：
dp[i][1] = dp[i-1][0] + dp[i-1][1]
dp[i][0] = dp[i-x][1]
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const int maxn = 1000005;
ll dp[maxn][2];
int main()
{
int t,x,l,r;
scanf("%d",&x);
for(int i=1;i<=x;i++){
dp[i][0] = 1;
}
dp[x][1] = 1;
for(int i=x + 1;i<=maxn;i++){
dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod;
dp[i][1] = (dp[i-x][0] )%mod;
}
for(int i=1;i<=maxn;i++){
dp[i][0] = (dp[i][0] + dp[i][1] + dp[i-1][0])%mod;
}
scanf("%d",&t);
while(t--){
scanf("%d %d",&l,&r);
printf("%lld\n",(dp[r][0] - dp[l-1][0] +mod)%mod);
}
return 0;
}G
solution:
这道题真的是一道很好的bfs题
由于僵尸会在一个长为k的矩形中不断移动，但是每次移动都是有规律的，循环周期为2×(k-1),即每次移动，他们都会到达一个固定的位置，那么我们可以在bfs的向量里面添加时间这一向量，每次judge是否和僵尸的位置冲突，不断地bfs，直到队列为空或者走到终点结束
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 505;
int n,m,p,k;
char str[maxn],s[maxn][maxn];
int t[maxn][maxn][22];
ll vis[maxn][maxn][22];
int dx[] ={0 , 0 , -1 , 1};
int dy[] ={-1, 1 , 0 , 0};
struct node{
int x,y,z;
};
void init()
{
for(int i=1;i<=p;i++){
int x,y;
scanf("%d %d %s",&x,&y,str);
if(str[0] == 'R'){
for(int i=0;i<=k;i++)t[x][y+i][i]=1;
for(int i=k+1;i<2*k;i++)t[x][y+k-i+k][i]=1;
}
if(str[0] == 'U'){
for(int i=0;i<=k;i++)t[x-i][y][i]=1;
for(int i=k+1;i<2*k;i++)t[x-k+i-k][y][i]=1;
}
if(str[0] == 'D'){
for(int i=0;i<=k;i++)t[x+i][y][i]=1;
for(int i=k+1;i<2*k;i++)t[x+k-i+k][y][i]=1;
}
if(str[0] == 'L'){
for(int i=0;i<=k;i++)t[x][y-i][i]=1;
for(int i=k+1;i<2*k;i++)t[x][y-k+i-k][i]=1;
}
}
}
int solve(int x,int y,int z){
if(x < 1 || x > n || y < 1 || y > m || s[x][y] == '&' || t[x][y][z] == 1){
return 1;
}
return 0;
}
int main()
{
int x,y,z,sx,sy,tx,ty;
scanf("%d %d %d %d",&n,&m,&p,&k);k--;
for(int i=1;i<=n;i++){
scanf("%s",s[i] + 1);
for(int j=1;j<=m;j++){
if(s[i][j] == 'L'){sx = i, sy = j;}
if(s[i][j] == 'A'){tx = i, ty = j;}
for(int q=0;q<2*k;q++)
vis[i][j][q] = 1e18;
}
}
init();
vis[sx][sy][0] = 0;
queue<node> q;
q.push(node{sx,sy,0});
while(!q.empty())
{
node now = q.front();q.pop();
x = now.x,y = now.y,z = now.z;
for(int i=0;i<4;i++){
int xx = x + dx[i];
int yy = y + dy[i];
int zz = (z + 1)%(2*k);
if(solve(x,y,z)){
continue ;
}
if(vis[xx][yy][zz] > vis[x][y][z] + 1){
vis[xx][yy][zz] = vis[x][y][z] + 1;
q.push(node{xx,yy,zz});
}
}
}
ll ans = 1e18;
for(int i=0;i<2*k;i++){
ans = min(ans , vis[tx][ty][i]);
}
if(ans >= 1e18){
printf("Oh no\n");
}else{
printf("%lld\n",ans);
}
return 0;
}
H
solution:
从进制转换的角度不难发现，字符串是26进制,而其hash值为10进制，那么就很简单了，先将字符串S的hash值k算出来，因为S′与其取模相同且 字典序最小,那么 k′=k+mod，然后将其转换为26进制输出
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
string s;
int mod ;
while(cin>>s>>mod)
{
int cnt = 0;
for(int i=0;i<6;i++){
cnt = cnt*26 + (s[i] - 'a');
}
cnt += mod;
for(int i=5;i>=0;i--)
{
s[i] = 'a' + (cnt%26);
cnt /= 26;
}
if(cnt){
cout<<"-1"<<endl;
}else{
cout<<s<<endl;
}
}
return 0;
}I
solution:
只有一个坑，就是可能会存在并列的人数
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[20];
int main()
{
int n , m ,cnt = 0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans = a[9];
sort(a+1,a+1+n);
int pre = a[n-2];
if(ans >= pre){
printf("Yes\n");
return 0;
}
if(ans*10 - 8*m >= 0){
printf("Yes\n");
return 0;
}
printf("No\n");
return 0;
}J
solution:
球的内接正n多边形边长等于 2rsin(180/n),这里记得将180换成pai
std：
#include
using namespace std;
#define ll long long
int main()
{
int n,r;
int x,y;
cin>>n>>r>>x>>y;
int l = min(x,y);
int rr = max(x,y);
int z = min(rr-l , n-rr+l);
double rrr = (double)r;
double esp = acos(-1.0);
double cnt = (2.000000*rrr)*(sin(esp/((double)n)));
double ans = cnt*((double)z);
printf("%.6lf\n",ans);
return 0;
}
京公网安备 11010502036488号