头像

阿罗




离线:8天前


最近来访(9)
用户头像
这道题有点难耶
用户头像
2850g
用户头像
codingxiaobai
用户头像
cccwl
用户头像
撒野_9
用户头像
名字长才会有人跟着念
用户头像
wanghai673
用户头像
喵喵喵喵子


阿罗
3个月前
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N],s[N];

int main()
{
    cin>>n;
    for (int j = 0; j < n; j ++ ) cin>>a[j];

    int res=0;  //定义答案

    for (int i = 0,j=0; i < n; i ++ )
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j++]]--;
        }

        res=max(res,i-j+1);
    }

    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

阿罗
3个月前
#include<iostream>

using namespace std;

const int N = 1010;

int n,m,q;
int a[N][N],b[N][N];

//二维差分操作
void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    //输入前缀和数组
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);
    //用差分操作,构造出a数组,“+”出来
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i,j,i,j,a[i][j]);
    //二维差分操作      
    while (q -- ){
        int x1, y1, x2, y2,c;
        scanf("%d%d%d%d%d",&x1, &y1, &x2, &y2,&c);
        insert(x1,y1,x2,y2,c);
    }

    //将差分数组更新成差分操作后的前缀和数组
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];

    //输出被操作过的a数组,即前缀和数组    
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ )
            printf("%d ",b[i][j]);
        puts("");
    }



    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

阿罗
3个月前
#include <iostream>

using namespace std;

int main()
{
  double x,l,r;
  cin >> x;

  if(x<=1&&x>=0) l=0,r = 1;
  else if(x<0&&x>=-1) l=-1,r=0;
  else if(x<0) l=x,r=0;
  else l=0,r=x;
  while(r-l > 1e-8)     //保留四位小数1e-6;保留五位小数1e-7;保留六位小数1e-8
  {
    double mid = (l + r) / 2;
    if(mid * mid * mid >= x) r = mid;
    else l=mid;
  }

  printf("%lf\n",l);

  return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

阿罗
3个月前
#include <iostream>

using namespace std;
const int N=1e5+10;

//typedef long long   ll;

int n;
int q[N];
int temp[N];
long long count=0;

void merge_sort(int q[],int l,int r){
    if(l>=r) return;            //递归出口

    //取中点
    int mid=l+r>>1;


    //递归处理左右两边
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);

    //归并
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) temp[k++]=q[i++];
        else temp[k++]=q[j++],count+=mid-i+1;
    }
    while(i<=mid) temp[k++]=q[i++];
    while(j<=r) temp[k++]=q[j++];


    for(int i=l,j=0;i<=r;j++,i++) q[i]=temp[j];
}


int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    merge_sort(q,0,n-1);
    printf("%lld",count);
    return 0;
}








活动打卡代码 AcWing 786. 第k个数

阿罗
6个月前
//题目意思:输出第k个数 快速选择算法时间复杂度0(n)
//快排算法时间复杂度O(nlogn)

//第k个数下标为k-1,第k小数意味着升序排列
#include<iostream>

using namespace std;

const int N=1e5+10;

int n,k;
int q[N];   //q[N]为全局变量,这里其实可以不用传参

int quick_sort(int l,int r,int k)//c++中局部变量和全局变量重名,会优先使用局部变量
{
    if(l>=r) return q[l];       ////k保证在l到k里面,只有一个数时直接输出

    int x=q[(l + r) >> 1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }

    if(k<=(j-l+1)) return quick_sort(l,j,k);
    else return quick_sort(j+1,r,k-(j-l+1));

}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);

    cout<<quick_sort(0,n-1,k)<<endl;

    return 0;
}






活动打卡代码 AcWing 830. 单调栈

阿罗
6个月前
//边输入数据,边排除掉都比x小,但下标更远的数据
#include<iostream>

using namespace std;

const int N=1e5+10;

int n;
int stk[N],tt;  //全局变量默认是0

//
int main()
{
  ios::sync_with_stdio(false);

  cin >> n;
  for(int i=0;i<n;i++)
  {
    int x;
    cin >> x;
    while(tt && stk[tt] >= x) tt--;
    if(tt) cout<<stk[tt]<<' ';
    else cout <<-1<<' ';

    stk[++tt]=x;
  }
  return 0;
}



阿罗
6个月前

截屏2022-03-13 21.06.04.png

为啥提交可以通过,调试过程中输出全是0;(代码和yxc的一样,而且没有边界问题)



活动打卡代码 AcWing 797. 差分

阿罗
6个月前
#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];   //a前缀数组,b差分数组

void insert(int l, int r, int c)
{
  b[l] += c;
  b[r+1] -= c;
}

int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

  for(int i = 1; i <= n; i++) insert(i, i, a[i]);

  while (m --)
  {
    int l, r, c;
    scanf("%d%d%d",&l, &r, &c);
    insert(l , r, c);
  }

  for(int i = 1; i <= n; i ++) b[i] += b[i-1];

  for(int i = 1; i <= n; i ++) printf("%d ", b[i]);

  return 0;
}




活动打卡代码 AcWing 796. 子矩阵的和

阿罗
6个月前
#include<iostream>

//using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];  

int main()
{
    //输入二维数组
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    //求前缀和
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

    //算部分和
    while(q --)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
        printf("%d\n",s[x2][y2]-s[x1 - 1][y2]-s[x2][y1 - 1]+s[x1 - 1][y1 - 1]);
    }

    return 0;
}



活动打卡代码 AcWing 795. 前缀和

阿罗
6个月前
#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int a[N],s[N];    //前缀和用数组存,查找的时间复杂度为O(1)

int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);      //数组初始化

    for(int i = 1; i <= n; i ++) s[i]=s[i-1]+a[i];       //前缀和初始化

    while(m --)
    {
        int l, r;
        scanf("%d%d", &l,&r);
        printf("%d\n", s[r]-s[l-1]);                     //区间和的计算
    }

    return 0;
}