头像

一抹斜阳


关注数
0
粉丝数
0
阅读量
4993


离线:17分钟前


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

一抹斜阳
19小时前
#include<iostream>
using namespace std;

int n,m,l,r;
const int N = 1e5 + 10;
int a[N],re[N];

int main(){


    cin>>n>>m;

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

    while(m--){
        scanf("%d %d",&l,&r);
        printf("%d\n",re[r] - re[l-1]);
    }

    return 0;

}


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

一抹斜阳
20小时前
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int stk[N],tt;
int n;

int main(){

    cin>>n;
    for(int i = 0;i<n;i++){
        int x;
        scanf("%d",&x);
        while(tt != 0 && stk[tt] >= x)    //把左边大于等于x的删去
            tt--;
        if(tt != 0)
            printf("%d ",stk[tt]);
        else
            printf("-1 ");

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


活动打卡代码 AcWing 829. 模拟队列

一抹斜阳
20小时前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int q[N];

int hh,tt;  //hh栈头,tt栈尾

void init(){
    tt = -1;
}

void push(int x){
    q[++tt] = x;
}

bool empty(){
    if(hh <= tt)
        return false;
    else
        return true;
}

int query(){

    return q[hh];
}

void pop(){
    ++hh;
}
int main(){


    int m;
    cin >> m;
    init();
    while(m--)
    {
        string s;
        int x;
        cin >> s;
        if(s == "push")
        {
            cin >> x;
            push(x);
        }
        else if(s == "pop")
        {
            pop();
        }
        else if(s == "query")
        {
            cout << query() << endl;
        }
        else if( s == "empty")
        {
            cout << (empty() ? "YES" : "NO") << endl;
        }
    }

    return 0;
}


活动打卡代码 AcWing 843. n-皇后问题

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

int n;
const int N = 10;
bool c[N],dg[N],udg[N];
char g[N][N];
void dfs(int k);

int main(){

cin>>n;
for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= n; j ++ )
        g[i][j] = '.';

dfs(1);
return 0;

}

void dfs(int k){
if(k == n + 1){
for (int i = 1; i <= n; i ) {
for(int j = 1;j<=n;j
)
printf(“%c”,g[i][j]);
printf(“\n”);
}
printf(“\n”);
return;
}

for(int i = 1;i<=n;i++)
    if(!c[i] && !dg[i + k - 1] && !udg[n - i + k]){
        c[i] = dg[i + k - 1] = udg[n - i + k] = true;
        g[k][i] = 'Q'; 
        dfs(k + 1);
        g[k][i] = '.';
        c[i] = dg[i + k - 1] = udg[n - i + k] = false;
    }

}




在这里插入图片描述


#include <iostream>
#include <algorithm>

using namespace std;


int n;
const int N = 10;
bool c[N],dg[N],udg[N];
char g[N][N];
void dfs(int k);

int main(){

    cin>>n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            g[i][j] = '.';

    dfs(1);
    return 0;
}

void dfs(int k){
    if(k == n + 1){
        for (int i = 1; i <= n; i ++ ) {
            for(int j = 1;j<=n;j++)
                printf("%c",g[i][j]);
            printf("\n");
        }
        printf("\n");
        return;
    }

    for(int i = 1;i<=n;i++)
        if(!c[i] && !dg[i + k - 1] && !udg[n - i + k]){
            c[i] = dg[i + k - 1] = udg[n - i + k] = true;
            g[k][i] = 'Q'; 
            dfs(k + 1);
            g[k][i] = '.';
            c[i] = dg[i + k - 1] = udg[n - i + k] = false;
        }
}


活动打卡代码 AcWing 791. 高精度加法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
string a,b;
int aa[N],bb[N],cc[N];

int main()
{


    cin>>a>>b;
    int len_a = a.length();
    int len_b = b.length();

    for(int i = 0;i<len_a;i++)
        aa[i] = a[len_a - i - 1] - '0';
    for(int i = 0;i<len_b;i++)
        bb[i] = b[len_b - i - 1] - '0';

    int len = max(len_a,len_b);

    for(int i = 0;i<len;i++){

        cc[i] = cc[i] + aa[i] + bb[i];
        cc[i+1] = cc[i] / 10;
        cc[i] = cc[i] % 10;

    }


    if(cc[len] != 0)
        len++;

    for(int i = len - 1;i>=0;i--)
        printf("%d",cc[i]);


    return 0;
}



#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
string a,b;
int aa[N],bb[N],cc[N];

int main()
{


    cin>>a>>b;
    int len_a = a.length();
    int len_b = b.length();

    for(int i = 0;i<len_a;i++)
        aa[i] = a[len_a - i - 1] - '0';
    for(int i = 0;i<len_b;i++)
        bb[i] = b[len_b - i - 1] - '0';

    int len = max(len_a,len_b);

    for(int i = 0;i<len;i++){

        cc[i] = cc[i] + aa[i] + bb[i];
        cc[i+1] = cc[i] / 10;
        cc[i] = cc[i] % 10;

    }


    if(cc[len] != 0)
        len++;

    for(int i = len - 1;i>=0;i--)
        printf("%d",cc[i]);


    return 0;
}




// N=n1+n2+…+nk,并且 n1×n2×…×nk 是最大乘积。
//尽量拆成多个3相乘,如果有余数,可以考虑用2乘以
class Solution {
public:
    int maxProductAfterCutting(int number) {

        if(number <3)
            return 1;
        if(number % 3 == 0)
            return pow(3,number/3);
        else if(number % 3 == 1)
            return pow(3,number/3 - 1)*4;
        else
            return pow(3,number/3)*2;


    }
};



活动打卡代码 AcWing 4. 多重背包问题

#include<iostream>
using namespace std;
const int N = 101;
int dp[N];
int v[N];
int w[N];
int s[N];
int main()
{
    int m,n,i,j;
    cin>>m>>n;
    for(i = 1;i<=m;i++)
    {
        cin>>v[i]>>w[i]>>s[i];
    }
    for(i = 1;i<=m;i++)
        for(j = n;j>=v[i];j--)
            for(int k = 1;(k<=s[i])&&(k*v[i]<=j);k++)
                dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);
    cout<<dp[n]<<endl;
    return 0;
}


活动打卡代码 AcWing 828. 模拟栈

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;
int stk[N],top,m;

void push(int x);
void pop();
int query();
bool empty();

int main(){

    cin>>m;
    string op;
    while(m--)
    {
        cin >> op;
        if(op == "push")
        {
            int x;
            cin>>x;
            push(x);
        }
        else if(op == "pop")
        {
            pop();
        }
        else if(op == "empty")
        {
            if(empty())
                printf("YES\n");
            else
                printf("NO\n");
        }
        else printf("%d\n",query());
    }

    return 0;

}

void push(int x){
    stk[top++] = x;
}

void pop(){
    top--;
}

int query(){
    return stk[top-1];
}

bool empty(){
    if(top > 0)
        return false;
    return true;
}