A
题意：dddd
思路：
先将数组输入并按升序排好序，同时处理得到数组中的最小值 mn 和最大值 mx，以及每项元素的总和。之后分别考虑操作k次后数组中的最小值和最大值的取值
（范围初始化错了，会出问题）
以下都是闭区间
考虑最小值，最小值的范围必须在 mn 到 sum/n之间，
考虑最大值，范围必须在 sum/n + 1 到 mx之间 或者 sum/n + 1 到 mx 之间
二分的核心思想 ：
将枚举的mid 待入原来的数组中模拟所需要的操作次数
例如数据
4 1
1 1 4 2
先输入数组 1 1 4 2 ，之后排序得 1 1 2 4 其中mx=4 ，mn=1，sum=8;
再从[ mn, sum/n ]即[ 1, 2 ]区间中枚举最小值的取值，将最小值变为1需要0次操作，变为2需要 1 + 1 = 2次操作 得 最小值 vl （value left）取 1
从[2 , 4]中枚举最大值取值，将最大值变为4需要0次操作，变为3需要1次操作 最大值 vr
（value right） 取 3
得最大减最小为vr - vl = 3 - 1 = 2
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define ll long long
const int N = 5e5 + 10, M = 2 * N;
using namespace std;
ll a[N];//存放数组
ll n, k;
bool chek1(ll mid)
{
ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] >= mid)break;
ans += mid - a[i];
}
return ans <= k;
}
bool chek2(ll mid)
{
ll ans = 0;
for (int i = n; i >= 1; i--)
{
if (a[i] <= mid)break;
ans += a[i] - mid;
}
return ans <= k;
}
int main()
{
cin >> n >> k;//输入数组长度n，操作次数k
ll mn = 1e9, mx = 0, sum = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
mn = min(mn,a[i]);//筛选出最大值最小值
mx = max(mx, a[i]);
sum+=a[i];//顺便求和
}
sort(a + 1, a + 1 + n);//排序函数，复杂度n*log(n)
ll l = mn, r = sum/n;//注意二分边界的初始化取值
while (l < r)//二分枚举最小值
{
ll mid = (l + r +1)>> 1;
if (chek1(mid))
l = mid;
else
r = mid - 1;
}
ll lv = l;//记录最小值
if (sum % n == 0) l = sum / n;
else l = sum / n + 1;
r = mx;
while (l < r)//二分枚举最大值
{
ll mid = l + r >> 1;
if (chek2(mid))
r = mid;
else
l = mid + 1;
}
ll rv = r;//记录最大值
cout << rv - lv;//输出极差
return 0;
}J
题意：
给定最开始前两项数字，后面的数字每一个都等于前面两项之和，（即 a [ i ] = a[ i - 1] + a[ i - 2 ]
和斐波那契数列一样），要求输出第 k 项数字是否为3的倍数
思路：
只需要关注每一项对于3的余数即可，有一个余数定理 （a+b)%p == (a%p+b%p)%p
即两数之和对 p 的余数等于两数分别对 p 的余数之和，
将最初的两项转换成对3的余数，而后按照余数之和递推下一项，由于对3的余数只有0 1 2 三个 ，显然会出现循环的数列
例如
项数： 1 2 3 4 5 6 7 8 9 10
数值： 0 1 1 2 0 2 2 1 0 1
从第九项出现循环，
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define ll long long
using namespace std;
int main()
{
int n; cin >> n;
while (n--)
{
ll a, b, k;
cin >> a >> b >> k;
vector<ll> t(2);//声明一个动态数组t并初始化大小为2
t[0] = a % 3, t[1] = b % 3;
int m, n;
m = t[0], n = t[1];//保留t[0] t[1]的值
while (1)
{
//(m+n)%3 是下一个数对三的余数，(m+n+n)%3是下下个数对三的余数
//两者和最开始的t[0], t[1]相等说明出现了循环
if ((m + n) % 3 == t[0] && (m + n + n) % 3 == t[1])
break;
else//不相等说明需要继续演算
{
t.push_back((m + n) % 3),
t.push_back((n + n + m) % 3);
m = (m + n) % 3;//将新的数放入m
n = (n + m) % 3;//更新n
}
}
ll sz = t.size();//得到循环节的大小
ll d = k % sz;//计算目标对于循环节大小的余数
if (d == 0) d = sz;//特判，余数为零说明目标对三的余数等于循环节最后一个数字
//动态数组下标从 0 开始，需要减 1
if (t[d - 1] == 0)cout << "Yes\n";
else cout << "No\n";
}
return 0;
}I
题意：
有一个数列 A 长度为 n (1 <= n <= 10) , A[ i ] 表示第i个数，要求输出满足 A[ i ] != i 的排列个数
思路：
直接套用错排公式 a[ i ] = ( i - 1 ) * ( a[ i - 1 ] + a[ i - 2 ] )
项数： 1 2 3 4 5 6
数值： 0 1 2 9 44 265
错排公式推导：
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define ll long long
const int N = 2e5 + 10, M = 2 * N;
using namespace std;
const int mod = 918;
int main()
{
ll n; cin >> n;
ll a[100]={0};
a[1] = 0, a[2] = 1;
for (int i = 3; i <= n; i++)
a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
cout << a[n] % mod;
return 0;
}