头像

阿巳




离线:1小时前


最近来访(12)
用户头像
李小涛
用户头像
7_48
用户头像
谁与我煮酒论天下
用户头像
ncust202103
用户头像
厚かましい
用户头像
swifties270
用户头像
五星市民欧某人
用户头像
yxc
用户头像
明朗编程
用户头像
仙女本人
用户头像
算法小爱

分享 复习提醒

阿巳
3小时前

11/30 再做一次赶牛入圈与最佳牛围栏
前缀和与差分,离散化的题目练习
12//02
trie树与并查集总结与练习
12/05
基础算法的练习(双指针,位运算)




阿巳
12小时前
//前缀和求矩阵的内容
for(int x1=1,x2=k;x2<=n;x2++,x1++)//保证x1,x2之间差为k
{
    for(int y1=1,y2=k;y2<=n;y2++,y1++)  
    {sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];

    }
}
一个区域的平均数最大为多少的二维版;
bool check(int mid)
{
for(int x1=1,x2=k;x2<=n;x2++,x1++)//保证x1,x2之间差大于等于k
{

    int minnum=0;

    for(int y1=1,y2=k;y2<=n;y2++,y1++)
    {minnum=min(minnum,sum[x1][y2]+sum[x2][y1]-sum[x1][y1],sum[x1][y2],sum[x2][y1]);//只是思路
    if(sum[x2][y2]-minnum>=mid)return true;

    }
}
return false ;
}





活动打卡代码 AcWing 102. 最佳牛围栏

阿巳
12小时前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int >pll;
vector<pll>v;
vector<int>lisan;
int sum[1005][1005];
int n,c;
int get(int x)
{
    int l=0;int r=lisan.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(lisan[mid]>=x)r=mid;
        else l=mid+1;
    }
    return r;
}
bool check(int mid)
{
    for(int x1=1,x2=1;x2<lisan.size();x2++)
    {while(lisan[x2]-lisan[x1]+1>mid)x1++;
    for(int y1=1,y2=1;y2<lisan.size();y2++)
    {
        while(lisan[y2]-lisan[y1]+1>mid)y1++;
       if(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]>=c )return true;
    }

    }

    return false ;
}

int main()
{

lisan.push_back(0);
cin>>c>>n;
while(n--)
{
int x,y;
cin>>x>>y;
v.push_back({x,y});
lisan.push_back(x);
lisan.push_back(y);
}
sort(lisan.begin(),lisan.end());
lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end());
for(int i=0;i<v.size();i++)
{
    int x=get(v[i].first);int y=get(v[i].second);
    sum[x][y]++;
}
for(int i=1;i<lisan.size();i++)
  for(int j=1;j<lisan.size();j++)
  sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
 int l=1;
 int r=1e4;
 while(l<r)
 {
     int mid=l+r>>1;
     if(check(mid))r=mid;
     else l=mid+1;
 }
 cout<<r;

 }
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 102. 最佳牛围栏

阿巳
1天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int >pll;
vector<pll>v;
vector<int>lisan;
int sum[1005][1005];
int n,c;
int get(int x)
{
    int l=0;int r=lisan.size()-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(lisan[mid]>=x)r=mid;
        else l=mid+1;
    }
    return r;
}
bool check(int mid)
{
    for(int x1=1,x2=1;x2<lisan.size();x2++)
    {while(lisan[x2]-lisan[x1]+1>mid)x1++;
    for(int y1=1,y2=1;y2<lisan.size();y2++)
    {
        while(lisan[y2]-lisan[y1]+1>mid)y1++;
       if(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]>=c )return true;
    }

    }

    return false ;
}

int main()
{

lisan.push_back(0);
cin>>c>>n;
while(n--)
{
int x,y;
cin>>x>>y;
v.push_back({x,y});
lisan.push_back(x);
lisan.push_back(y);
}
sort(lisan.begin(),lisan.end());
lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end());
for(int i=0;i<v.size();i++)
{
    int x=get(v[i].first);int y=get(v[i].second);
    sum[x][y]++;
}
for(int i=1;i<lisan.size();i++)
  for(int j=1;j<lisan.size();j++)
  sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
 int l=1;
 int r=1e4;
 while(l<r)
 {
     int mid=l+r>>1;
     if(check(mid))r=mid;
     else l=mid+1;
 }
 cout<<r;

 }
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



阿巳
1天前

题号68:查找漏的元素//

if(r<0)return 0;
while(l<r)
{
int mid=(l+r)>>1;
if(nums[mid]>mid)r=mid;//nums[mid]不可能小于mid,所以另一种情况就是nums[mid]==mid
else l=mid+1;          //所以这题二分的条件还可以是nums[mid]!=mid;
}
if(nums[r]==r)return r+1;
return r;

题目:14   不改变数组查找重复的元素要o(1)的空间(即不用hash表)那用二分
int cnt=0;
int mid=(l+r)>>1;
int i=0;
for(auto x:nums)cnt+=x<=mid&&x>=l;
if(cnt>mid-l+1)r=mid;
else l=mid+1;
return r;

而最佳牛围栏那道题二分的是这个数(mid)作为最优解可不可以,而不是对数组二分,二分的实质是分界性。

double l=1;
double r=1e5
while(r-l>1e-5)//因为要取到答案要求保留的位数的再后两位
{double mid=(l+r)/2;//因为不是int型所以不能用>>1;
if(check(mid))r=mid;
else l=mid+1;
}
//然后就是写最重要的check函数了
double check(double mid)
{for(int i=1;i<=n;i++)
{
    sum[i]=sum[i-1]+(cow[i]-mid);
}
double minnum=0;
for(int i=0,j=k;j<=n;i++,j++)//这样就满足了j与minnum代表的长度的差值一定大于等于k
    {minnum={minnum,sum[i]};
    if(sum[j]-minum>=0)return true;
    }
    return false ;
}

屏幕截图 2021-11-27 165448.png


//而防线这道题用的分界性是在只有一个奇数的情况下其他都是偶数那必有一段的总和为偶数一段的总和为奇数

struct defe
{
    int s,e,d;
}a[N];
int n,t;



int getsum(int x)//因为开不了那么大的数组所以可以用一个变量多次计算
{int sum=0;
    for(int i=0;i<n;i++)
    {if(x>=a[i].s)//判断条件别少
        sum+=(min(a[i].e,x)-a[i].s)/a[i].d+1;//加一是加上s这个数
    }
    return sum;
}



bool check(int l,int mid)
{
    return (getsum(mid)-getsum(l-1))&1;
}

int maxe=0;
for(int i=0;i<n;i++)
{
    cin>>a[i].s>>a[i].e>>a[i].d;
    maxe=max(maxe,a[i].e);//找到最大的e作为r的初始值


}
int l=0;
int r=maxe;
if(!(getsum(maxe)&1))cout<<"There's no weakness."<<endl;
 else 
{ while(l<r)
{
int mid=r+l>>1;
if(check(l,mid))r=mid;
else l=mid+1;
}
cout<<r<<" "<<getsum(r)-getsum(r-1)<<endl;
}
}
}








阿巳
1天前
如何找出一个数组中长度大于等于k的区间的和的最大值,这样的方法在题目(最佳牛圈)中可用
int minnum=0;maxnum=0;
for(int i=0,j=k;j<=n;i++,j++)//n为数组长度;num[N]为要求的数组的前缀和且num[0]=0;
{
    minnum=min(minnum,num[i]);//这样找到的minnum一定是小于满足j-i+1>=k的
    maxnum=max((num[j]-minnum),maxnum);
}


分享 二分

阿巳
3天前
二分(两个版本)第一个是可以找到第一个等于x的元素,第二个是可以找到最后一个等于x的元素
但不局限于此第一个可以看作找到某个条件的最左端,第二个就是最右端
#### C++ 代码


void find(int x)
 {int l=0;
 int r=N;
 while(l<r)
 {
     int mid=r+l>>1;
    if(a[mid]>=x)r=mid;
    else l=mid+1;
 }

 }
 void find (int x)
 {
     int l=0;
     int r=N;
     while(l<r)
     {
       int mid=r+l+1>>1;
       if(a[mid]<=x)l=mid;
       else r=mid-1;
     }
 } 




阿巳
3天前

题目描述

给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。

请找出数组中任意一个重复的数,但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。
blablabla

算法1

(暴力枚举) $O(n)$

时间复杂度

参考文献

C++ 代码

class Solution {
public:

    int duplicateInArray(vector<int>& nums) 
    {int a[nums.size()];
    memset(a,0,sizeof a);
    for(int i=0;i<nums.size();i++)
    {if(!a[nums[i]])
    {
        a[nums[i]]=1;//未重复出现的赋值为1

    }
    else return nums[i];


    }

    }
};

算法2

(二分) $O(nlogn)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:

    int duplicateInArray(vector<int>& nums) 
    {int l=1;int r=nums.size()-1;

    while(l<r)
    {int mid=r+l>>1;
    int cnt=0;//每一次都要重新查找所以cnt要重新赋值为0;
    for(auto x:nums)cnt+=x>=l&&x<=mid;//计算[l,mid]的数的个数
        if(cnt>mid-l+1)//如果大于区间的长度说明[l,mid]该区间有重复的数
        r=mid;
        else l=mid+1;
    }
    return r;//找到该数
    }
};


活动打卡代码 AcWing 240. 食物链

阿巳
3天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int p[N],d[N];



int find(int x)//并查集+路径压缩
{
    if(p[x]!=x)
    {int t=find(p[x]);
    d[x]+=d[p[x]];
    p[x]=t;//不太懂
      }
    return p[x];//记得是返回祖宗结点的值
}

int main()
{int n, m;
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++)
{p[i]=i;
}

while(m--)
{
 int c;
    int a,b;
 cin>>c;
    cin>>a;
   cin>>b;
   if(a>n||b>n) 
   {ans++;
   continue;
   }
   else
   {int px=find(a);int py=find(b);
 if(c==1)
 { 
         if(px==py&&(d[a]-d[b])%3){ans++;}//a是否吃b或者a吃的吃b
      else  if(px!=py)
      { p[find(a)]=find(b);
       d[px]=d[b]-d[a];
      }


    }
    else if(c==2)
    {
    if(find(a)==find(b)&&(d[a]-d[b]-1)%3)
    {ans++;

    }
  else if(py!=px)//只检查b是否吃a
        {
            p[px]=py;
         d[px]=d[b]-d[a]+1;
     }

    }

}

}
cout<<ans;



}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 840. 模拟散列表

阿巳
3天前
//这里填你的代码^^
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int null=0x3f3f3f3f;
int  h[N],ne[2*N],e[2*N],idx;
void add(int x)
{   int k=((x%N)+N)%N;
    e[idx]=x;ne[idx]=h[k];h[k]=idx++;
}
int find(int x)
{ int k=((x%N)+N)%N;
    for(int i=h[k];i!=-1;i=ne[i] )
    {
        if(e[i]==x)
        return true;
    }
    return false;
}

int main()
{memset(h,-1,sizeof h);
    int n;
    cin>>n;
    while(n--)
    {
        char c;
        cin>>c;
        int x;
        cin>>x;
        if(c=='I')
        {
          add(x);
        }
        else 
        {
            if(find(x))
            {
                cout<<"Yes"<<endl;
            }
            else 
            cout<<"No"<<endl;
        }
    }




}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~