头像

longlongAC


访客:487

离线:13小时前


活动打卡代码 AcWing 425. 明明的随机数

#include<bits/stdc++.h>

using namespace std;

int n;
const int N=10010;
int q[N];

int main()
{
    cin>>n;
    int num;
    for(int i=1;i<=n;i++)
    {
        cin>>num;
        q[num]++;
    }
    int t=0;
    for(int i=0;i<=1000;i++) 
    {
        if(q[i]>=1) t++;
    }
    cout<<t<<endl;
    for(int i=0;i<=1000;i++)
    {
        if(q[i]>=1) cout<<i<<" ";
    }
}


活动打卡代码 AcWing 413. 乒乓球

不知道乒乓球获胜的规则太难了

#include<bits/stdc++.h>

using namespace std;

void work(string str,int q)
{
    int len =str.size();        
    int a=0,b=0;
    for (int i=0;i<len&&str[i]!='E';i++)
    {   
        if(str[i]=='W') a++;
        else b++;
        if( max(a,b) >= q && abs(a-b)>=2 )
        {
            printf("%d:%d\n",a,b);
            a=b=0;
        }

    }        
    printf("%d:%d",a,b);
}

int main()
{
    string str;
    char c;
    while(cin>>c) str+=c;
    work(str,11);
    puts("\n");
    work(str,21);
}




#include<bits/stdc++.h>

using namespace std;

int n;
const int N =100010;
int a[N],s[N];


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int res=0;
    for(int i=1,j=1;i<=n;i++)
    {   
        s[a[i]]++;
        while(s[a[i]]>1)//1 2 2 3 5
        {
            s[a[j]]--;//
            j++;//2 
        }
        res = max(res,i-j+1);//1 2
    }
    cout<<res<<endl;
    return 0;
}



b[]的前缀和为a[] 所以可以根据a的前缀和公式求出差分数组b

b[]的加减C 可以求到前缀和的改变(可以画方块图理解)

还原前缀和数组 求b数组的前缀和即可

#include<bits/stdc++.h>

using namespace std;

const int N =1010;
int n,m,q;
int a[N][N],b[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]);

    //构建差分数组B[i][j]  a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i]; 推出 b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];

    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        b[x1][y1] +=c; //b[x1][y1]+=c 右下角所有矩阵的前缀和就都加上了C 
        b[x2+1][y1] -=c; //减去第一步b[x1][y1] 下方所有矩阵的前缀和多加的c
        b[x1][y2+1] -=c; //减去第一步b[x1][y1] 右边所有矩阵的前缀和多加的c
        b[x2+1][y2+1] +=c; //加上第二第三步多减去的部分c  注意这里加减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]+b[i][j]; //求前缀和 前缀和数组就是所求

    for(int i=1;i<=n;i++) //输出前缀和数组
    {
        for(int j=1;j<=m;j++)
            cout<<b[i][j]<<" ";
    cout<<endl;
    }
    return 0;
}


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

#include<bits/stdc++.h>

using namespace std;

const int N =1010;
int n,m,q;
int a[N][N],b[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]);

    //构建差分数组B[i][j]  a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i]; 推出 b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];

    while(q--)
    {
        int x1,y1,x2,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        b[x1][y1] +=c; //b[x1][y1]+=c 右下角所有矩阵的前缀和就都加上了C 
        b[x2+1][y1] -=c; //减去第一步b[x1][y1] 下方所有矩阵多加的c
        b[x1][y2+1] -=c; //减去第一步b[x1][y1] 右边所有矩阵多加的c
        b[x2+1][y2+1] +=c; //加上第二第三步多减去的部分c  注意这里加减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]+b[i][j]; //求前缀和 前缀和数组就是所求

    for(int i=1;i<=n;i++) //输出前缀和数组
    {
        for(int j=1;j<=m;j++)
            cout<<b[i][j]<<" ";
    cout<<endl;
    }
    return 0;
}




一点粗陋的见解

#include<bits/stdc++.h>

using namespace std;

const int N =100010;
int n,m,l,r,c;
int a[N],b[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]); //输入原数组
    //构造差分数组 s[i]=s[i-1]+a[i] a[i]=s[i]-s[i-1] 前者叫前缀和数组 后者叫差分数组
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];  
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&c);
        b[l]+=c; //差分数组+c b[3]+=c a[2]=b[1]+b[2] 所以a[1~L-1]无影响 只有a[L~末尾]会多加C
                 //a[l - r] 综合两者 1~l-1 未加C l~末尾会加上C 又因为r+1减了C 所以只有l~r阶段加上了C  例如l=2 r=5 2到结束+c 5到结束-C 最后只有2-5加了C后面部分无影响 
        b[r+1]-=c;//差分数组-c b[3]-=c a[2]=b[1]+b[2] a[1~r]无影响  a[2+1]=b[1]+b[2]+b[3] 有影响  所以只有a[r+1~结束]这一段减去了C  
    }

    for(int i=1;i<=n;i++) b[i]=b[i-1]+b[i]; //求差分数组的前缀和, 前缀和即为所求数组

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

    return 0;
}


活动打卡代码 AcWing 797. 差分

不太懂啊啊啊啊啊啊啊啊

#include<bits/stdc++.h>

using namespace std;

const int N =100010;
int n,m,l,r,c;
int a[N],b[N];

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

int main()
{
    cin>>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--)
    {
        scanf("%d%d%d",&l,&r,&c); //多次读入加上C
        insert(l,r,c);
    }

    for(int i=1;i<=n;i++) b[i]=b[i-1]+b[i]; //求差分数组的前缀和, 前缀和即为所求数组

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

    return 0;
}


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

可以画方格图理解

#include<bits/stdc++.h>

using namespace std;

const int N=1010;
int n,m,q;
int a[N][N],s[N][N];

int main()
{
    cin>>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]; //求前缀和

    int x1,y1,x2,y2;
    while(q--)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        cout<<(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1])<<endl; //求子矩阵的和
    }
}



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

#include<iostream>

using namespace std;

const int N=100010;
int a[N],s[N];
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    //这里是在计算前i项和并存入数组当中
    //公式推导
    //s[i]=a[1]+a[2]+a[3]+----+a[i-1]+a[i];
    //s[i-1]=a[1]+a[2]+a[3]+----a[i-1]
    //s[i]-s[i-1]=a[i] =s[i]=s[i-1]+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]);//s[r] 包含1-l这一段的和 所以减去s[l-1]
    }
    return 0;
}


活动打卡代码 AcWing 794. 高精度除法

#include<bits/stdc++.h>

using namespace std;

vector<int> div(vector<int> &A,int b,int &r)
{
    vector<int>C;
    r=0;
    for(int i=A.size();i>=0;i--)
    {
        r=r*10+A[i]; //当前位加上上一位的余数乘10 
        C.push_back(r/b);//当前位的和除以b得到商
        r%=b;//除不尽的做完 余数算到下一位头上
    }
    reverse(C.begin(),C.end()); 
    while(C.size()>1&&C.back()==0) C.pop_back();

    return C;
}

int main()
{   
    string a;
    vector<int> A;
    int b;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    int r;
    vector<int> C=div(A,b,r);

    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);

    cout<<endl<<r<<endl;

    return 0;
}