前排碎碎念
昨天下午劳逸逸逸结合了一下。有朋自远方来那就带她出去玩，再加上晚上大大大暴雨，所以昨天没学什么东西，因而小结空了一天。
但今天转念一想觉得还是浅写一下叭，那就写两天的！
7.18的内容：
上午看了一下二分（实际上是前一天晚上在oi-wiki上面随便翻开结果发现第一次交WA了，所以决定好好看一下）紧接着中午看了wiki的数论基础（噫，总不能是发量给的自信叭），晚上回去看了最短路（dijkstra和floyd）
二分做了这几个题：https://www.luogu.com.cn/problem/P1873，https://www.luogu.com.cn/problem/P2440以及https://www.luogu.com.cn/problem/P2678
砍树：https://www.luogu.com.cn/problem/P1873
根据高度进行二分，注意左闭右开r初始值应+1。
第一次WA是因为二分的l和r当成所有树木的最矮和最高了。
AC：
点击查看代码
#include<iostream>
using namespace std;
int a[1000005];
int n,m;
bool chk(int x){
long long tt=0;
for(int i=1;i<=n;i++){
if(a[i]>x)tt+=a[i]-x;
}
if(tt>=m)return true;
else return false;
}
int find(){
long long l=1,r=1000000001,ck;
while(l+1<r){
int mid=(l+r)/2;
ck=chk(mid);
if(ck==1){
l=mid;
}
else{
r=mid;
}
}
return l;
}
int main(){
cin>>n>>m;
long long ans;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ans=find();
cout<<ans<<endl;
return 0;
}
木材加工：https://www.luogu.com.cn/problem/P2440
和砍树基本上是一样的题目。
点击查看代码
#include<iostream>
using namespace std;
int n,k,l;
int a[100005];
bool chk(int x){
long long tt=0;
for(int i=1;i<=n;i++){
tt+=a[i]/x;
}
if(tt>=k)return true;
else return false;
}
int find(){
long long l=1,r=100000001,ck;
while(l+1<r){
long long mid=(l+r)/2;
ck=chk(mid);
if(ck==1)l=mid;
else r=mid;
}
if(chk(l)==0)return 0;
return l;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cout<<find()<<endl;
return 0;
}
跳石头：https://www.luogu.com.cn/problem/P2678
啊这个我一开始以为不会是二分（这也太不像了吧），后来发现是对距离进行二分，看需要移走的石头块数是否符合要求。
关于这个移走块数也不是简单的这个石头和前一个的间距是否小于距离，因为移走第二块石头的同时第三块石头与前一块石头的距离也增大了，也不是移走之后的下一个距离增大，因为如果最后一个石头与岸距离过近的话总不能把岸移走叭（那就愚公移山好了喵）。
所以选择再额外设置一个变量nw表示现在在哪块石头上面，然后比较a[i]与a[nw]的距离是否满足跳跃要求。
代码如下：
点击查看代码
#include<iostream>
using namespace std;
int k,n,m;
int a[50005];
bool chk(int x){
int tt=0,nw=0;
for(int i=1;i<=n+1;i++){
if(a[i]-a[nw]>=x)nw=i;
else tt++;
}
if(tt>m)return false;
else return true;
}
long long find(){
int l=1,r=1000000001,ck;
while(l+1<r){
int mid=(l+r)/2;
ck=chk(mid);
if(ck==1)l=mid;
else r=mid;
}
return l;
}
int main(){
cin>>k>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[n+1]=k;
cout<<find()<<endl;
return 0;
}
数论基础：https://oi-wiki.org//math/number-theory/basic/
因为感觉没有什么对口的题目所以就随便翻了翻，发现两个很好玩的题目做了一下
又是毕业季②：https://www.luogu.com.cn/problem/P1414
分别统计每个数的因数，然后从大到小找能满足人数要求的最大的因数。
WA在了统计因数上面。
第一次WA是因为只加上了i*i<=n的因数，第二次WA是把1和它本身加了两遍。
还因为注释没删干净WA了一次
最后AC代码如下：
点击查看代码
#include<iostream>
#include<cstdio>
using namespace std;
int a[1000005];
int main(){
int n,inf;
cin>>n;
for(int i=1;i<=n;i++){
cin>>inf;
//cout<<"这个是"<<inf<<" ";
int j;
for(j=1;j*j<inf;j++){
if(inf%j==0){
a[j]++;
a[inf/j]++;// cout<<j<<" "<<inf/j<<" ";
}
}
if(j*j==inf){
a[j]++;
//cout<<j<<" ";
}
}//cout<<endl;
// for(int i=1;i<=6;i++){
// cout<<i<<" "<<a[i]<<endl;
// }
int nw=1000000;
for(int i=1;i<=n;i++){
while(a[nw]<i){
nw--;
}
cout<<nw<<endl;
}
return 0;
}
找筷子：https://www.luogu.com.cn/problem/P1469
是个异或题。因为0与任何数的亦或者都是它本身，a与a的异或值为0，所以把所有数都异或在一起最后剩下的就是单独的啦。
AC代码如下：
include
using namespace std;
int main(){
int ans=0,n,a;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
ans^=a;
}
cout<<ans<<endl;
return 0;
}
7.19的list
是想赖床的一天呢（可恶今天洛谷签到又是大凶！！！！！！！连着凶了好几天了，怀疑是被改了，暴躁捶luogu）
素数
上午看了会儿素数：https://oi-wiki.org//math/number-theory/prime/
嗯...然后在看到反素数的时候钢笔没墨水惹，太可恶哩o(>﹏<)o
主要就是如何判断一个数是不是素数啦，最简单最暴力的是从2到sqrt(n)一个一个的进行尝试，除此之外还有Fermat和Miller-Rabin素性测试。
以及反素数，在值尽可能小的情况下因数个数最多。
河南萌新联赛：https://ac.nowcoder.com/acm/contest/61657
萌新联赛一点都不萌新！！！就跟小白联赛一点都不小白一样！！！（气鼓鼓）
一直在T!!!!!我真的哭哭(இдஇ; )
上来先把题目看了看，感觉A和I很可做（为什么没发现D呢，因为发现C挺...之后没看D和E，以为这仨应该是差不多的或者依次递进的）
于是就开始做I（因为觉得A好像代码量挺大的）
最一开始想的简单了些，没有注意到位数不能改变，发现样例不过之后写了一个查找位数和一的个数然后从小到大依次把一摆放到位，最后再加上最高位的1的程序，样例过了但是WA了...
看了眼榜，发现D过的很多，觉得D可能是签到题，于是便开了D，一发AC
点击查看代码
#include<iostream>
using namespace std;
int main(){
long long n,m,tt=0,a,flag=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a;
tt+=a;
if(tt>=m){
cout<<"YES"<<endl;
flag=1;
break;
}
}
if(flag==0){
cout<<"NO"<<endl;
}
return 0;
}
又看了眼G，发现是昨天上午学的二分，果断交了。
AC代码如下：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=62856445
紧接着回去看E（因为我特别相信不会很难，毕竟是萌新联赛），改了下快读（毕竟是要输入多个数据），又T了
然后去开A...
当时的思路也是比较的朴实，每次倒水模拟水的流动，唯一的优化就是对小麦的量做了一个前缀和的处理，果不其然也T了（坐牢开始！）
在坐牢的时候想到了之前在前缀和的时候看到了一个新奇的点子，就是打标签，但是...由于边界的处理和打上标签之后忘记用前缀和滚一边了所以样例一直没有过
再继续修改A，紧接着继续T...
时间到了晚上，从A开始补题（嗯！只要补了A和K就是ＡＫ了比赛对叭(≧▽≦)/
A的思路是，在浇水之前就计算这个格子能流多远，流的距离是从第一个格子开始计算流的长度，每次往后添加一个格子，分往后延长了一个平地还是升高了一块两种情况进行讨论。
AC代码如下：
运用了一下队列思想，ll和rr是分别计算往前流的和被截断的多少。WA了一次是因为...十年OI一场空，_______见祖宗
点击查看代码
#include<iostream>
using namespace std;
long long a[100005];//每格小麦的个数
long long b[100005];//前缀和
long long c[100005];//土地的高度是否变化
long long d[100005];//最远流到的距离
int main(){
long long n,q,k;
cin>>n>>q>>k;
cin>>a[1];
b[1]=a[1];
for(int i=2;i<=n;i++){
cin>>a[i];
b[i]=b[i-1]+a[i];
}
/*
for(int i=1;i<=n;i++){
cout<<i<<" "<<a[i]<<" "<<b[i]<<endl;
}
*/
for(int i=1;i<=n;i++){
cin>>c[i];
}
for(int i=n;i>=1;i--){
c[i]-=c[i-1];
}
c[1]=0;
/*
for(int i=1;i<=n;i++){
cout<<c[i]<<" ";
}
*/
long long ll=0,rr=0,x=0,y=k;
for(int i=1;i<=n;i++){
if(c[i]==0){
ll++;
x++;
if(x==k){
ll=rr+k;
y=k;
}
if(ll-rr>y)rr++;
}
if(c[i]>0){
y+=(k-1);
ll++;
x=1;
}
d[i]=ll-rr;
}
int p;
for(int i=1;i<=q;i++){
cin>>p;
if(p-d[p]>=0)cout<<b[p]-b[p-d[p]]<<endl;
else cout<<b[p]<<endl;
}
return 0;
}
既然A有了那么距离AK就差Ｋ了，旁边的香香姐姐过了K所以我就大胆尝试。发现其实K真的真的很简单，自己当时没有找对递推的式子（虽然题目给了，但是我居然下意识忽略了递推，选择了计算每个单项的结果），于是当时就没有写这个题（血亏），另外感觉榜有点歪，毕竟这个题只是看着吓人了一点。
计算0的个数实际上就是计算10的个数也就是计算2和5的个数，取比较少的就可以。
朴实的写一下，不用gcd之类的就AC啦。
代码如下：
点击查看代码
#include<iostream>
using namespace std;
int qwq[5000005][3];
long long qe(int x){
int res=0;
while(x!=0){
if(x%2==0){
res++;
x/=2;
}
else break;
}
return res;
}
long long qw(int x){
int res=0;
while(x!=0){
if(x%5==0){
res++;
x/=5;
}
else break;
}
return res;
}
int main(){
int n;
cin>>n;
int a,b,c,d,te=0,tw=0;
for(int i=1;i<=n;i++){
c=0,d=0;
a=4*i-2;b=i+1;
//cout<<a<<" "<<b<<endl;
c+=qe(a);
c-=qe(b);
//cout<<qe(a)<<" "<<qe(b)<<endl;
qwq[i][1]=qwq[i-1][1]+c;
d+=qw(a);
d-=qw(b);
//cout<<qw(a)<<" "<<qw(b)<<endl;
qwq[i][2]=qwq[i-1][2]+d;
te+=qwq[i][1];
tw+=qwq[i][2];
//cout<<i<<" "<<qwq[i][1]<<" "<<qwq[i][2]<<endl;
}
long long mi;
if(te<tw)mi=te;
else mi=tw;
cout<<mi<<endl;
return 0;
}
最后回去补E，在打标签的基础上滚一边前缀和，愉快AC
点击查看代码
#include<iostream>
using namespace std;
int a[1000005];
int main(){
int n,x,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(x==0)continue;
if(i<x){
a[1]++;
}
else a[i-x]++;
a[i]--;
a[i+1]++;
if(i+x<n)a[i+x+1]--;
}
for(int i=1;i<=n;i++){
a[i]+=a[i-1];
//cout<<i<<" "<<a[i]<<endl;
if(a[i]>0)ans++;
}
cout<<ans<<endl;
return 0;
}