A. Split it!
题意
给定一个为的字符串和一个数
然后为是否存在个非空字符串使得
$R(abcd) = dcba$
首先不管我们每一个字符串取多少 即然他要求是非空字串 那么 前面k个字符就一定要和最后k个字符是要相反的才有可能存在
我们可以这样来想 举一个例子
$k=2$
于是乎我们可以取
这样就刚好符合条件
那么我们继续去缩小每一个的取值范围
当我们取到的时候 无论就已经可以确定可以符合条件了
因为第一个刚好等于最后一个 第二个刚好等于倒数第二个 因此中间的是什么就已经不必要了
所以我们就可以推出来
只要前面k个字符和最后k个字符是相反的就有可能存在了
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
char s[N];
void solve(){
int n , k;
scanf("%d%d", &n , &k);
getchar();
for(int i = 1 ; i <= n ; ++i)
scanf("%c" , &s[i]);
if(k * 2 >= n){
cout<<"NO"<<endl;
return ;
}
for(int i = 1 ; i <= k ; ++i){
if(s[i] != s[n - i + 1]){
cout<<"NO"<<endl;
return ;
}
}
cout<<"YES"<<endl;
}
int main(void){
int T;
scanf("%d" , &T);
while(T--)
solve();
return 0;
} B. Max and Mex
题意
给出个数字组成一个序列 和
次操作 每次操作选择序列中最大的数字a和序列中所缺的最小非负整数b 然后将
插入 序列中 然后求在
次操作之后 序列中有多少个不同的数字
比如0 1 3 4 序列中最大的数字就是4 所缺的最小非负整数是2 然后就将3插入序列 这个时候序列中就有
四个不同的数字
如果直接的去暴力 很明显会超时 所以我们先研究一下这个
就比如上面这个例子 不管操作多少次 我们都无法将最小的负整数增大 也就是說不管怎么弄 序列的数字都不会加一
那么我们再看什么情况会加一 如果上面那个例子没有3 也就是算出来的小于最大的数字 然后可以加上去
还有一个就是最小整数大于最大整数 就比如这个序列
最小负整数是5 最大的整数是 4 算出一个5 然后将5插入 如果再操作就再插入一个6
这样操作几次就插入几个
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e9 + 7;
const int INF = 0x3f3f3f3f;
map<int ,int >mp;
int findmin(int d){
for(int i = 0 ; i <= d ; ++i){
if(!mp[i]) return i;
}
}
void solve(){
int n , k , maxn = -1 , minn = 0 , x;
int sum = 0;
mp.clear();
scanf("%d%d" , &n , &k);
for(int i = 1 ; i <= n ; ++i){
scanf("%d" , &x);
if(x > maxn) maxn = x;
if(!mp[x]){
sum += 1;
}
mp[x] = 1;
if(x == minn){
while(mp.count(minn)) minn++;
}
}
for(int i = 1 ; i <= k ; ++i){
x = ceil( ((double)maxn + minn) / 2.0);
if(x > maxn){
sum += k;
break;
}
if(maxn == minn || mp[x]) break;
if(x > maxn) maxn = x;
if(x == minn){
while(mp[minn]) minn++;
}
sum++;
mp[x] = 1;
}
printf("%d\n" , sum);
}
int main(void){
int T ;
scanf("%d" , &T);
while(T--)
solve();
return 0;
} C. Diamond Miner
题意
有个矿工和
个矿 矿工在
轴上 矿在
轴上 一个矿工挖一个矿 一个矿也只能挖一个矿工 然后求出矿工和对应的矿的距离 求距离的综合的最小值
小的挖
小的就好了
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
double a[N] , b[N];
bool cmp(double a , double b){
return abs(a) < abs(b);
}
void solve(){
int n ;
scanf("%d" , &n);
double x , y;
int cnt1 = 0 , cnt2 = 0;
for(int i = 1 ; i <= n * 2 ; ++i){
scanf("%lf%lf" , &x , &y);
if(x == 0){
a[++cnt1] = y;
}
else{
b[++cnt2] = x;
}
}
sort(a + 1 , a + 1 + cnt1 , cmp);
sort(b + 1 , b + 1 + cnt2 , cmp);
double ans = 0;
for(int i = 1 ; i <= n ; ++i){
ans += (sqrt(a[i] * a[i] + b[i] * b[i]));
}
printf("%.12lf\n" , ans);
}
int main(void){
int T;
scanf("%d" , &T);
while(T--)
solve();
return 0;
} D. Let's Go Hiking
题意
给定一个 个点 在一条直线上 然后每一个点都有一个值 a和b进行博弈 a线选一个点 然后b再选一个点 a和b都只能在相邻的点上移动 并且a只能向小于自己所在的点的反向移动 b只能向大于自己所在的点移动 谁先不能移动就算谁落败 求所有a能够获胜的点的个数
直接拿一个样例来说 1 2 5 4 3 有且只有 a选择第三个点的时候 也就是值为5的这个点 a是必胜的
因为当a选择5的时候 b的选择就是 1 2 4 3
如果b选择2和4 那么a就向另一个方向走 比如 b选择2 那么a就向4 走
流程就是 5->4 2->5 4->3这个时候轮到b了但是b无法移动
然后如果选择1或者3 那那么比如1
流程就是 5->2 这个时候b就无法移动了 也就是说当a选择第三个点的时候 a是必胜的
很明显 我们就可以看到 如果a只能走左右两边的一边 那是必输无疑的 只要b堵住他就可以了
如果有一条路比另一条路长 那么b只要选择长的一条就好了 然后在最远的偶数位置等着他 a就必胜 因为左右两边相同时 如果a向没有b的一个方向走 因为a先行动 那么一定也是a最先动不了 b只要待在最远的地方就好了
由此我们就可以发现 a唯一的获胜方式就是 有两条路 并且b只能面向a走来 最后b走不了 因此 就可以得到 唯一的获胜条件就是两条路的长度相同且为奇数
然后我们还要排除一种情况 就是存在另一条道路的长度和这两条的长度相同 这样b也是只要无脑选另一条就因为 因为a先走 所以长度相同时还是b获胜
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
int l[N] , r[N];
int a[N];
void solve(){
int n ;
scanf("%d" , &n);
int maxn = -1;
for(int i = 1 ; i <= n ; ++i){
scanf("%d" , &a[i]);
}
l[1] = r[n] = 1;
for(int i = 2 ; i <= n ; ++i){
if(a[i] > a[i - 1]){
l[i] = l[i - 1] + 1;
}
else l[i] = 1;
}
for(int i = n - 1; i >= 1 ; --i){
if(a[i] > a[i + 1]){
r[i] = r[i + 1] + 1;
}
else r[i] = 1;
}
int top = -1;
int cnt = 0;
for(int i = 1 ; i <= n ; ++i){
// cout<<r[i]<<" ";
if(l[i] > maxn || r[i] > maxn){
top = i;
cnt = 1;
maxn = max(l[i] , r[i]);
}
else if(l[i] == maxn || r[i] == maxn){
cnt++;
}
}
if(cnt > 1){
cout<<"0"<<endl;
return ;
}
int shortlen = (maxn == l[top]) ? r[top] : l[top];
if(maxn & 1 && shortlen == maxn) cout<<"1"<<endl;
else cout<<"0"<<endl;
}
int main(void){
solve();
return 0;
} 
京公网安备 11010502036488号