3.20 - 4.2
C. Pull Your Luck
题目真的好长（……）
简单理解下题意，我们有0~n-1一共n个人，当前指针指向第p个人，我们可以对转盘施加最大f、最小1的力，让转盘转动\(\sum_{i=1}^{k}i\)（序号增加），让我们判断是否能让指针最后指向0。
一开始的想法是模拟，即一个一个转，复杂度大概是O(m)的级别，是我们发现m的范围到了1e9，很明显这个方法会超时。
那我们就要思考有什么简化方法了。
在这里有一个小思想是如果一个数的范围很大的话，那我们可能可以找规律，即存在周期。
我们如果把转动的过程理解为加法然后取余，那么题目条件就是x加上一个数对n取余后结果为0。那么我们就会得到
如果我们把\(i=i+2n\)代入，最终会得到和\(i\)一样的结果，也就是说我们加的时候结果的周期是\(2n\)。
这个思路的参考文章
C. Pull Your Luck - onlyblues - 博客园 (cnblogs.com)
所以我们只需要把枚举次数上限设定在\(min(2n,f)\)，然后从1开始逐个枚举看是否能满足上式就可以了。
这样我们就可以把复杂度降到O(n)的级别，就可以解决问题了。
代码很简单就不给了（）
C. Sum on Subarrays
一道构造的题目。
简单翻译下题意，我们输出一个序列由-1000~1000间的n个数字组成，满足其子序列求和后为正数的个数为m，为负数的个数为n-m（也即是不存在求和后为0的子序列）
我们可以注意到题目对n的限制范围非常小，最多只有30。这个条件对于我们来说非常重要。当我们将一个数设为1000时，只要它后面的负数都相对较小，那我们可以认为包括它的所有子序列一定是正的子序列。
对于构造的题目，有一个很重要的思想就是要按顺序（从前往后或从后往前），一项一项来处理，尽可能让相同的数字排列在一起的同时让后处理的项不会影响到先处理的项。只是一个个人的小总结，瓦塔西还非常菜QAQ
那么延续我们上面的想法，如果从头开始处理，若将第1个数设为1000，那么我们就会得到n个正子序列，同理，如果将第二个也设为1000，我们就会得到n-1个正子序列……则让前i个数为1000，我们就会得到\(\sum_{j=n-i+1}^nj\)个正序列。
似乎解决了一部分问题，但仍然存在问题。如果当前需要的子序列无法被上述式子所覆盖，那又该怎么办呢？我们可以很明显看出，如果将m减去它所能减去最大的和式，结果一定比剩下未设置数的项的个数要小。由此可以推得，我们把第一项设为\(1+2(k-1)\)，其后项为\(-2\)，就可以得到k个正项序列。
代码也很简单，注意判断最后剩下k的个数是否为0，为0就不用再设置项了。
G1. Subsequence Addition
将数组排序，如果之前数字的和比当前数字小，那么就无法获得，easy和hard version思想一样
C. Unlucky Numbers
算是数位dp（？），我还不太了解。
题意：找到给定数范围内的一个数，使得这个数中最大的数字和最小的数字的差值最小。
易知这个差值的范围只有0-9，我们可以尝试去枚举差值反推回数字。同时，由于有范围的限制，我们在反推构造数字的时候应该让其尽可能地接近我们范围内最大的数，然后通过检验它是否大于等于最小的数来判断当前枚举的值是否符合要求，符合要求就输出。
其他的细节看代码注释。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=5010;
#define endl "\n"
//要开unsigned long long 不然会在枚举的时候爆掉……
ll a,b;
ll read(){
ll i=0,j=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') j=-1;
ch=getchar();
}
while(isdigit(ch)){
i=i*10+ch-'0';
ch=getchar();
}
return i*j;
}
ll find(int gap){
ll ans=0;
ll tmp=b,len=0;
//计算一下最大值的位数方便后续枚举
while(tmp) len++,tmp/=10;
for(int i=0;i<10;i++){//枚举当前的最小数字
if(i+gap>=10) break;
ll now=0;
for(int j=1;j<=len;j++){//一位位处理，从高位开始
for(int k=i+gap;k>=i;k--){//保证差值gap，每一位数字控制在i~i+gap间
//从大到小枚举，保证当前位是可取范围内最大的
ll t=now*10+k;//可以保证每一位之前的位都符合要求
for(int p=j+1;p<=len;p++){
//将当前位之后的位都置为i，方便检验是否符合要求
t=t*10+i;
}
if(t<=b){
//符合要求就把当前位存起来
now=now*10+k;
break;
//后面当前位更小的都不用检测了，把数字控制在满足条件的情况下尽可能大
}
}
}
ans=max(ans,now);//找到小于等于最大值的范围内最大的数
}
return ans;
}
int main(){
int T=read();
while(T--){
a=read(),b=read();
for(int i=0;i<10;i++){//要找到差值最小的数，从小的差值开始枚举
ll tmp=find(i);
if(tmp>=a){//符合就输出，保证此时是差值最小的
cout<<tmp<<endl;
break;
}
}
}
return 0;
}
一点碎碎念：当时比赛时间紧急第一眼还以为跟lucky number的思路差不多，结果当然没过（我太菜了），现在来想想，对于一个数的差值，我们我们可以很容易地让其增加（这就是lucky number能用暴力的原因）但要其减小就需要改变更多。
B. Points on Plane
当时纠结了好久呜呜QAQ
翻译下题意，给我们n个棋子，要求将这些棋子布置在棋盘上使得这些棋子相对原点的欧几里得距离的最大值最小。
看到最大值最小化我们就可以想二分了，但是我当时纠结了好久不知道要怎么判断当前距离是否符合要求，遂去看了题解。
我们如果尝试动手画一下不同距离最大值满足要求的点的形状就可以发现一些规律了：对于一个相对原点欧氏距离最大为\(k\)的点集，其所包含点的个数为\((k+1)^2\)。由此我们就可以去二分啦，或者我们也可以直接通过对n开根号后上取整来求答案。
A. Two Towers
这题其实蛮简单的，但我一开始一直想着把怎么通过一个个看来判断出结果，代码写得很冗长。后来去看了题解发现可以把两个合并来找断点，非常巧妙，就记录一下。
将第二个转置后和第一个拼接在一起，逐个看，如果存在超过一个左右相邻的两个相同的情况，那么就不满足。
杨辉三角形
从0开始冲刺蓝桥杯了呜呜
题意：给出一个数要我们找出它在杨辉三角中出现的位置。
首先让我来先介绍一下杨辉三角的性质：对于第n行的第m个，它的数值可通过组合数求出来，等于\(C_{n-1}^m\)。这个性质将会在我们后续解题中得到利用。相对应的，杨辉三角的左右对称性也可以从组合数中看出。
接下来让来看题目。
首先，由于对称性，我们在看三角形的时候只用考虑左半边（在右半边出现的数一定会在左半边更先出现）。那么接下来该怎么想呢？我们会发现对于这半个杨辉三角的每个斜边上的元素，它的m都是相同的，每个斜边开始的元素等于\(C_{2m}^m\)，并且是单调递增的。我们自己大概算一下就会发现，当m等于16时， 这条斜边起始的数值就已经远远大于我们n的范围了，所以我们可以尝试枚举k来找到我们需要的元素n。
再然后，由于对于n来说，k越大时它出现的越前，所以我们要从大到小枚举k。
枚举完k后，对于一斜行的数，它具有单调性，我们可以用二分来查找是否存在我们所需要的数。
关于这个方法的正确性在下方视频里证明了，在此不过多赘述（我懒——）
题目思路到此就梳理完毕了，在书写代码的时候还有一些细节需要注意，详情写在代码的注释里了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e7;
//懒得思考数据全开ll防爆
ll n;
// C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
ll c(int a,int b){
ll res=1;
for(int i=a,j=1;j<=b;i--,j++){
res=res*i/j;
if(res>n) return res;
//这里也在防爆，如果当前数已经比n大了，那么我们再增加也没有意义，
//因为我们实际只想判断是否与n相等
}
return res;
}
bool check(int k){
ll l=k*2-1,r=max(n,l)+1;
//二分模板
//范围左端是由之前的斜边开始位置所确定，右端保证了有解
while(l+1<r){
int mid=l+r>>1;
if(c(mid,k)>=n) r=mid;
//因为要找到第一个大于等于n的数出现的地方，所以这里判断为≥
else l=mid;
}
//关于答案是取l还是取r当时调了很久，二分还是不太熟练啊啊啊啊啊（……）
if(c(r,k)!=n) return false;
//从之前的组合数可以推到，当取得数目为k的时候，实际上是当前行的第k+1个数
//杨辉三角第n行有n个元素，前n行元素等差数列求和
cout<<r*(r+1)/2+k+1<<endl;
return true;
}
int main(){
cin>>n;
for(int i=16;;i--){
if(check(i)) break;
}
return 0;
}