头像

抱元守一




离线:7天前



#include<iostream>
using namespace std;
const int N=100010;
int a[N],s[N];
int res = 1;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int i=1,j=1;
    s[a[j]]++;
    while(j<=n)
    {

        if(s[a[j]] > 1) {
            s[a[i]]--; i++;

        }
        else {
            if(j-i+1 > res) res = j-i+1;
            j++,s[a[j]]++;

        }

    }
    printf("%d",res);
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

挑战模式,第二次提交成功,第一次搞反了n,m时间紧迫没来得及调试

#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int b[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);

    int i=1,j=1;
    while(i<=n && j<=m)
    {
        if(a[i]!=b[j]) j++;
        else i++,j++;
    }
    if(i==n+1) printf("Yes");
    else printf("No");
    return 0;
}




很开心,写完直接提交就AC了!~

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];

int main()
{
    int n,m,x;
    scanf("%d%d%d",&n,&m,&x);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    int i=n-1;
    int j=0;
    while(i>=0 && j<n)
    {
        if(a[i]+b[j]>x) i--;
        else if(a[i]+b[j]<x) j++;
        else {printf("%d %d",i,j);break;}
    }
    return 0;
}


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

#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int d[N][N];
//S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
void insert(int x1,int y1,int x2,int y2,int c)
{
    d[x1][y1]+=c;    //(x1,y1)右方及下方的点受到影响
    d[x2+1][y1]-=c;  //排除y1列超过x2行的影响
    d[x1][y2+1]-=c;  //排除x1行超过y2列的影响
    d[x2+1][y2+1]+=c;//保持不变


}
int main()
{
    int n,m,q,tmp;
    scanf("%d%d%d",&n,&m,&q);
    //首先直接建立二维差分数组
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&tmp);
            insert(i,j,i,j,tmp);
        }
    //更新二维差分数组 
    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++)
        {
            a[i][j]=a[i-1][j]+ a[i][j-1] -a[i-1][j-1] +d[i][j];
        }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",a[i][j]);
        printf("\n");
    }

    return 0;
}



众所周知,唐老师特别喜欢挑战难度很高的电子游戏,有一天他挑战了一款回合对战游戏,唐老师的阵地有N个哨塔,编号由1到N,且初始时每个哨塔有自己的血量,游戏开始后,敌军会对唐老师的阵地发起M轮进攻,每轮进攻都会对一些哨塔产生等量的伤害。且满足第i轮进攻会对编号Li到Ri的哨塔造成等量伤害Di,M轮进攻结束后,唐老师需要快速对血量最低的K座哨塔进行修补,若存在与第K座哨塔相同血量仍需要输出,输出的哨塔编号个数可能多余K个,由于哨塔特别多,所以请帮忙设计程序帮助唐老师快速的找出需要修补的哨塔的编号,输出编号按从小到大顺序。

输入格式:
第一行包含两个三整数N,M,K。
第二行包含N个正整数,表示编号1到N哨塔的血量。
接下来M行,每行包含三个整数L,R,D,表示一轮进攻对编号L到R的哨塔造成了D点伤害。
输出格式:
共一行,包含K个正整数,以空格分隔,表示需要修补的哨塔编号。

数据范围:
1≤N,M≤100000,
1≤L≤R≤N,
1≤K≤N,
1≤D≤1000,
1≤哨塔血量≤21亿,且M轮进攻后不存在哨塔血量小于等于0的情况。

输入样例:
7 3 6
500 500 500 500 500 500 500
1 7 100
2 3 50
3 5 200
输出样例:
1 2 3 4 5 6 7

#include<iostream>
using namespace std;
const int N = 100010;

typedef struct Tower
{
    int idx;
    int hp;
}tower;

tower a[N];
int d[N];
bool ans[N];

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

int part(tower q[],int l,int r,int k)
{
    if(l == r) return q[l].hp;
    int key = q[l+r>>1].hp;
    int i=l-1,j=r+1;
    while (i < j)
    {
        do i++; while(q[i].hp<key);
        do j--; while(q[j].hp>key);
        if (i < j)
            swap(q[i],q[j]);
    }
    int llen = j-l+1;
    if( k<=llen)
        part(q,l,j,k);
    else
        part(q,j+1,r,k-llen);


}


int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) 
    {
        a[i].idx = i;
        scanf("%d",&a[i].hp);
        insert(i,i,a[i].hp);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        insert(l,r,-d);
    }
    for(int i=1;i<=n;i++){
        a[i].hp = a[i-1].hp+d[i];
        //printf("%d ",a[i].hp);
    }
    //printf("\n");
    int khp = part(a,1,n,k);
    for(int i=1;i<=n;i++)
        if (a[i].hp <= khp)
            ans[a[i].idx] = true;
    for(int i=1;i<=n;i++)
        if(ans[i]) 
            printf("%d ",i);

    return 0;

}

暂时没有制作非常准确大数据,不能完全确定代码的正确性,如果有感兴趣的同学,可以自行研究一下~

作者:抱元守一
链接:https://www.acwing.com/activity/content/code/content/593593/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



活动打卡代码 AcWing 797. 差分

突发奇想,打算创造出一道差分和快排分区算法的题~
众所周知,唐老师特别喜欢挑战难度很高的电子游戏,有一天他挑战了一款回合对战游戏,唐老师的阵地有N个哨塔,编号由1到N,且初始时每个哨塔有自己的血量,游戏开始后,敌军会对唐老师的阵地发起M轮进攻,每轮进攻都会对一些哨塔产生等量的伤害。且满足第i轮进攻会对编号Li到Ri的哨塔造成等量伤害Di,M轮进攻结束后,唐老师需要快速对血量最低的K座哨塔进行修补,若存在与第K座哨塔相同血量仍需要输出,输出的哨塔编号个数可能多余K个,由于哨塔特别多,所以请帮忙设计程序帮助唐老师快速的找出需要修补的哨塔的编号,输出编号按从小到大顺序

输入格式:
第一行包含两个三整数N,M,K。
第二行包含N个正整数,表示编号1到N哨塔的血量。
接下来M行,每行包含三个整数L,R,D,表示一轮进攻对编号L到R的哨塔造成了D点伤害。
输出格式:
共一行,包含K个正整数,以空格分隔,表示需要修补的哨塔编号。

数据范围:
1≤N,M≤100000,
1≤L≤R≤N,
1≤K≤N,
1≤D≤1000,
1≤哨塔血量≤10000,且M轮进攻后不存在哨塔血量小于等于0的情况。

输入样例:
7 3 6
500 500 500 500 500 500 500
1 7 100
2 3 50
3 5 200
输出样例:
1 2 3 4 5 6 7

#include<iostream>
using namespace std;
const int N = 100010;

typedef struct Tower
{
    int idx;
    int hp;
}tower;

tower a[N];
int d[N];
bool ans[N];

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

int part(tower q[],int l,int r,int k)
{
    if(l == r) return q[l].hp;
    int key = q[l+r>>1].hp;
    int i=l-1,j=r+1;
    while (i < j)
    {
        do i++; while(q[i].hp<key);
        do j--; while(q[j].hp>key);
        if (i < j)
            swap(q[i],q[j]);
    }
    int llen = j-l+1;
    if( k<=llen)
        part(q,l,j,k);
    else
        part(q,j+1,r,k-llen);


}


int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) 
    {
        a[i].idx = i;
        scanf("%d",&a[i].hp);
        insert(i,i,a[i].hp);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,d;
        scanf("%d%d%d",&l,&r,&d);
        insert(l,r,-d);
    }
    for(int i=1;i<=n;i++){
        a[i].hp = a[i-1].hp+d[i];
        //printf("%d ",a[i].hp);
    }
    //printf("\n");
    int khp = part(a,1,n,k);
    for(int i=1;i<=n;i++)
        if (a[i].hp <= khp)
            ans[a[i].idx] = true;
    for(int i=1;i<=n;i++)
        if(ans[i]) 
            printf("%d ",i);

    return 0;

}


暂时没有制作非常准确大数据,如果有感兴趣的同学,可以帮忙做一下大数据,并发给我,谢谢啦



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

//可以不保存数据,节省一半内存

#include<iostream>
using namespace std;
const int N = 1010;
int sum[N][N];

int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]+tmp;
        }
    while(q--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
    }

}


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

//可以不保存数据,节省一半内存

#include<iostream>
using namespace std;
const int N = 1010;
int sum[N][N];

int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]+tmp;
        }
    while(q--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
    }

}


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

//可以不保存数据,节省一半内存

#include<iostream>
using  namespace std;
const int N =100010;
int sum[N];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        sum[i] = sum[i-1] + tmp;
    }
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",sum[r]-sum[l-1]);
    }
    return 0;
}


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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;

int main()
{
    double n;
    scanf("%lf",&n);
    if(n < 0) {n = -n;printf("-");}
    double l=0,r=n;
    while(r - l > 1e-8)
    {
        double mid = (l+r)/2;
        if (mid*mid*mid > n) r=mid;
        else l=mid;
    }
    printf("%.6lf",l);
}