牛客巅峰赛S1
第一场
B-魔法数字
思路：直接看样例，n=3,m=10,3首先可以变成4，2，9，然后4只能通过+1变成5，因为减1成3的话又回去了，平方的话变成16（**n最大不能超过m+m-n**，因为如果超过m+m-n的话要一直做减一操作变为m，那还不如直接一直加一变成m），所以只能加一，同理2可以变成1，9可以变成10，8结束，所以最受操作数是2，可以看出来这是一个广搜的过程，运用队列来实现，而用队列来实现的话通过哪个路径先到达m，哪个的操作次数就是最少，**同时要注意做减1操作的时候n不能小于0**，因为一旦成了负数就要进行平方操作，而一个数到达负数后再平方的次数一定比他是正数到他是负数平方后的数的次数多，所以不能减到负数。（粗体内容是剪枝）。
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
LL mod = 1e9+7;
const int INF = 1e5;
//const int inx = INT_MAX;
using namespace std;
// srand(time(NULL));
// m = rand() % 1000 + 1;
//定义i i(A) i+n i+n(B) i+n+n i+n+n(C)
//bitset<Max>s,q;
//int a[100],n;
void bfs(int n,int m,int dis[])
{
queue<int>q;
dis[n] = 0;
q.push(n);
while(!q.empty()){
int p = q.front();
q.pop();
if(p == m) break;
if(p+1 <= m && dis[p+1] == 0){
dis[p+1] = dis[p] + 1;
q.push(p+1);
}
if(p-1 > 0 && dis[p-1] == 0){
dis[p-1] = dis[p] + 1;
q.push(p-1);
}
if(p*p < (2*m-n) && dis[p*p] == 0){
dis[p*p] = dis[p] + 1;
q.push(p*p);
}
}
}
int main()
{
int n,m;
int dis[2005];
cin >> n >> m;
bfs(n,m,dis);
cout << dis[m];
return 0;
} 第三场
牛牛晾衣服：二分
class Solution {
public:
/**
* 计算最少要多少时间可以把所有的衣服全烘干
* @param n int整型 n件衣服
* @param a int整型vector n件衣服所含水量数组
* @param k int整型 烘***1分钟可以烘干的水量
* @return int整型
*/
int pd(vector<int> &a,int mid,int k,int n)
{
int i,sum = 0;
for(i = 0; i < n; i++){
if(a[i] > mid){
sum += (a[i]-mid - 1) / (k - 1) + 1;
}
}
if(sum <= mid) return 1;
else return 0;
}
int solve(int n, vector<int>& a, int k) {
// write code here
int i,mid,l,r,ans = 0;
for(i = 0; i < a.size(); i++){
if(a[i] > ans) ans = a[i];
}
if(k == 1) return ans;
l = 0,r = ans;
while(l <= r){
mid = (l + r) / 2;
if(pd(a,mid,k,n) == 1) r = mid - 1;
else l = mid + 1;
}
// cout << l;
return l;
}
}; 第四场
B题
思路：直接看例子，n=10时，n/i等于1的有10，9，8，7，6，等于2的有5，4，等于3的有3，等于5的有2，等于1的有10，可以看出来越靠近n的数向下区整答案相同的有很多，并且都大于根号n，而这些i也都小于等于根号n，所以我们在i<根号n的范围内枚举，我们还可以发现n/i等于1的上限是10(n/(i))，下限是6，也就是n/(i+1)+1,(上限-下限+1)*i就是n/x向下取整等于i的和。其他小于根号n的直接枚举1-最后一次下限即可。
#include <bits/stdc++.h>
#include <iostream>
#define LL long long
using namespace std;
int main()
{
LL n;
cin >> n;
int ans = 0,p;
p = 998244353;
LL sx,xx;
for(int i = 1; 1LL*i*i <= n; i++){
sx = n / i;
xx = n / (i+1) + 1;
ans = (ans % p + (sx - xx + 1) * i % p) % p;
}
cout << ans << xx << endl;
for(int i = 1; i < xx; i++){
ans = (ans % p + (n / i) % p) % p;
}
cout << ans;
return 0;
} 第五场：砖石场
A
思路:设这个数是y，xx=y,那么x%1000x%1000=y%1000,y%1000得到的是y的后三位数，所以我们只需要知道y的后三为是多少就行，而xx,我们如果知道x的后三位，xx的后三位也就是y的后三位也能知道，即y的后三位是多少与x的后三为前面的数无关，所有我们枚举i-1000即可。
class Solution {
public:
/**
*
@param x int整型
@return bool布尔型
*/
bool solve(int x) {
// write code here
for(int i = 1; i <= 1000; i++){
if(i * i % 1000 == x) return true;
}
return false;
}
}; B
1：题目要我们求移动字母的最大次数，并且移动的字母ai < a(i+k),很明显我们只要找到将数组分成k个数组，即a0,a(0+k),a(0+2k)...,a(1),a(1+k)...,a(k),a(2k)...
2：对于每个数组我们去判断这个数组中的每个元素前面有多少个比它小的数，这些数的个数就是当前这个数的可移动次数。
3: 为什么我们能保证一定可以移动那么多次呢，因为我们在移动当前这个数时，前面比它的数以前移动到了数组的前面去了，比如，afeagggb,k=2,拿出一个数组fagb,对于g，前面有fa比g小，变成gfab，然后对于b，a比它小，变成了gfba，g比b大，本以为不用移动，其实在移动b之前g已经移到比b小的数前面去了。
方法一：树状数组
class Solution {
public:
/**
*
@param s string字符串 s.size() <= 1e5
@param k int整型 k <= s.size()
@return int整型
*/
int tree[31];
int lowbit(int x){
return x & (-x);
}
void add(int x,int val){
while(x <= 27){
tree[x] += val;
x += lowbit(x);
}
}
int sum(int x){
int ans = 0;
while(x){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
int turn(string s, int k) {
// write code here
int ans = 0;
for(int i = 0; i < k; i++){
memset(tree,0,sizeof(tree));
for(int j = i; j < s.size(); j += k){
add(s[j] - 'a' + 1,1);
ans += sum(s[j] - 'a');
}
}
return ans;
}
}; 方法二：
思路：用一个数组去保存比当前数小的每个数出现的个数，最后累加起来就是比当前数小的个数。
class Solution {
public:
/**
*
* @param s string字符串 s.size() <= 1e5
* @param k int整型 k <= s.size()
* @return int整型
*/
int a[30];
int turn(string s, int k) {
// write code here
int ans = 0;
for(int i = 0; i < k; i++){
memset(a,0,sizeof(a));
for(int j = i; j < s.size(); j += k){
int t = s[j] - 'a';
a[t]++;
for(int p = 0; p < t; p++){
ans += a[p];
}
}
}
return ans;
}
}; 
