CodeChef Starters 151 (Div.2) A~D

codechef是真敢给分，上把刚注册，这把就div2了，再加上一周没打过还是有点不适应的，好在最后还是能够顺利上分
今天的封面是P3R的设置菜单 我抠出来做我自己的游戏主页了（

A - Convert string

题意

在01串里面可以翻转k次，问从1到n有多少个k有机会使01串所有元素相同

思路

暴力遍历求解即可，一开始下标打错了wa了一发

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;void solve()
{int n;scanf("%d",&n);string s;cin>>s;int one=0,zero=0;for(int i=0;i<n;i++){if(s[i]=='1'){one++;}else{zero++;}}int cnt=0;for(int k=1;k<=n;k++){//全变1if(k>=zero and (k-zero)%2==0){
//            printf("%d ",k);cnt++;continue;}//全变0if(k>=one and (k-one)%2==0){
//            printf("%d ",k);cnt++;continue;}}
//    printf("\n");printf("%d\n",cnt);
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

B - Ball Game

题意

好多小球冲家，速度各不相同，中间撞上了就会融合成一个速度取最大值的新小球，问最后一共有多少个小球到终点

思路

所谓的融合其实就是大球吃小球，维护个pq然后大小比较无效化就行

代码

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <cctype>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLL;
#define qwq ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define tcase      \LL t = read(); \while (t--)LL read()
{LL sum = 0, fl = 1;int ch = getchar();for (; !isdigit(ch); ch = getchar())if (ch == '-')fl = -1;for (; isdigit(ch); ch = getchar())sum = sum * 10 + ch - '0';return sum * fl;
}
const int N = 1e6 + 10;
struct node
{LL d, v;bool operator<(const node &T) const{return d < T.d;}
} a[N];struct node2
{LL x, y;bool operator<(const node2 &T) const{return x * T.y < T.x * y;}
};void solve()
{LL n = read();for (int i = 1; i <= n;i++)a[i].d = read();for (int i = 1; i <= n;i++)a[i].v = read();sort(a + 1, a + 1 + n);priority_queue<node2> pq;for (int i = 1; i <= n;i++){node2 nowt = {a[i].d,a[i].v};while(pq.size()&&nowt<pq.top())pq.pop();pq.push(nowt);}printf("%lld\n", pq.size());
}int main()
{tcasesolve();return 0;
}

C - Sequence Search

题意

$X_1=0;$
$X_2=A;$
$X_3=B;$
$X_i=X_{i-1}+X_{i-2}=X_{i-3};$
一直A和B，求数组中第k小的数

思路

简单枚举一下很容易可以发现规律

0,A,B,A+B,2B,A+2B,3B,A+3B,4B,A+4B,5B,A+5B,6B,A+6B,7B,A+7B,8B,A+8B,9B,A+9B,10B,A+10B,11B,A+11B,12B,A+12B,13B,A+13B,14B

然后现在还要排序，很容易想到比较时一个很重要的印象因素就是A是B的几倍，然后再枚举下找下规律就行了

0,B,A,2B,A+B,3B,A+2B,4B,A+3B,5B       A/B==1
0,B,2B,A,3B,A+B,4B    A/B==2

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;//0,A,B,A+B,2B,A+2B,3B,A+3B,4B,A+4B,5B,A+5B,6B,A+6B,7B,A+7B,8B,A+8B,9B,A+9B,10B,A+10B,11B,A+11B,12B,A+12B,13B,A+13B,14B,A+14B,15B,A+15B,16B,A+16B,17B,A+17B,18B,A+18B,19B,A+19B,20B,A+20B,21B,A+21B,22B,A+22B,23B,A+23B,24B,A+24B,25B,A+25B,26B,A+26B,27B,A+27B,28B,A+28B,29B,A+29B,30B,A+30B,31B,A+31B,32B,A+32B,33B,A+33B,34B,A+34B,35B,A+35B,36B,A+36B,37B,A+37B,38B,A+38B,39B,A+39B,40B,A+40B,41B,A+41B,42B,A+42B,43B,A+43B,44B,A+44B,45B,A+45B,46B,A+46B,47B,A+47B,48B,A+48B,49B,A+49B,50B,A+50B,51B,A+51B,52B,A+52B,53B,A+53B,54B,A+54B,55B,A+55B,56B,A+56B,57B,A+57B,58B,A+58B,59B,A+59B,60B,A+60B,61B,A+61B,62B,A+62B,63B,A+63B,64B,A+64B,65B,A+65B,66B,A+66B,67B,A+67B,68B,A+68B,69B,A+69B,70B,A+70B,71B,A+71B,72B,A+72B,73B,A+73B,74B,A+74
//0,B,A,2B,A+B,3B,A+2B,4B,A+3B,5B       A/B==1
//0,B,2B,A,3B,A+B,4B    A/B==2
void solve()
{ll A,B,K;scanf("%lld%lld%lld",&A,&B,&K);int time=A/B;int start=3+time;if(K==start-1){printf("%lld\n",A);return ;}if(K==1){printf("%lld\n",0);return ;}if(K<start){printf("%lld\n",(K-1)*B);return ;}K-=start;K++;if(K%2==1){printf("%lld\n",((K+1)/2+time)*B);return ;}else{printf("%lld\n",(K/2)*B+A);return ;}
}int main()
{int T=1;scanf("%d",&T);while(T--){solve();}return 0;
}

D - Shooting (Easy)

题意

射飞镖，以一个点为中心点，距离为得分，求两个人在每个点作为中心点情况得分的差值

思路

前缀和维护即可

代码

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <cctype>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLL;
#define qwq ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define tcase      \LL t = read(); \while (t--)LL read()
{LL sum = 0, fl = 1;int ch = getchar();for (; !isdigit(ch); ch = getchar())if (ch == '-')fl = -1;for (; isdigit(ch); ch = getchar())sum = sum * 10 + ch - '0';return sum * fl;
}
const int N = 1e6 + 10;
LL d[N];
LL s1[N], s2[N];void solve()
{LL sum1 = 0, sum2 = 0;LL n = read(),m = read();n = m;for (int i = 1; i <= m;i++)d[i] = read();for (int i = 1; i <= m;i++){s1[i] = s1[i - 1] + 1;s2[i] = s2[i - 1] + 1;if(d[i]==1){s1[i]++;sum1 += i - 1;}else if(d[i]==2){s2[i]++;sum2 += i - 1;}else if(d[i]==3){s1[i]++;s2[i]++;sum1 += i - 1;sum2 += i - 1;}// printf("%lld %lld\n", s1[i], s2[i]);}//printf("%lld %lld\n", s1[m], s2[m]);printf("%lld ", llabs(sum1 - sum2));// printf("de %lld %lld\n", sum1, sum2);for (int i = 2; i <= m;i++){sum1 += s1[i - 1];sum1 -= s1[m] - s1[i - 1];// printf("add:%lld sub:%lld\n", s1[i - 1], s1[m] - s1[i - 1]);sum2 += s2[i - 1];sum2 -= s2[m] - s2[i - 1];// printf("add:%lld sub:%lld\n", s2[i - 1], s2[m] - s2[i - 1]);printf("%lld ", llabs(sum1 - sum2));// printf("de %lld %lld\n", sum1 , sum2);}printf("\n");
}int main()
{tcasesolve();return 0;
}