头像

Estrus




离线:2天前


最近来访(113)
用户头像
骏杰
用户头像
飘逸的红雨
用户头像
Kazimierz
用户头像
勇敢珑珑
用户头像
帽子
用户头像
yxc的接班人
用户头像
凛冬_15
用户头像
lza123
用户头像
ღSupperღ
用户头像
直言不
用户头像
小女子只会影响我debug的速度
用户头像
Acwer
用户头像
细致的山奈琴
用户头像
_如鲸向海
用户头像
小马珍珠
用户头像
Passer
用户头像
旷梦
用户头像
rsaldjfoasidhfsd
用户头像
KAWS
用户头像
小会儿来敲代码了

活动打卡代码 AcWing 482. 合唱队形

Estrus
5个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int h[N],g[N],f[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];
    for(int i=0;i<n;i++){
        f[i]=1;
        for(int j=0;j<i;j++)
            if(h[i]>h[j])f[i]=max(f[i],f[j]+1); 
    }
    for(int i=n-1;~i;i--){
        g[i]=1;
        for(int j=n-1;j>i;j--)
            if(h[i]>h[j])g[i]=max(g[i],g[j]+1);
    }
    int res=0;
    for(int i=0;i<n;i++)
        res=max(res,f[i]+g[i]-1);
    cout<<n-res<<endl;  
    // for(int i=0;i<n;i++)
    //     cout<<g[i]<<" ";
    // cout<<endl;
    return 0;
}


活动打卡代码 AcWing 1014. 登山

Estrus
5个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int h[N],g[N],f[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>h[i];
    for(int i=0;i<n;i++){
        f[i]=1;
        for(int j=0;j<i;j++)
            if(h[i]>h[j])f[i]=max(f[i],f[j]+1);
    }

    for(int i=n-1;i>=0;i--){
        g[i]=1;
        for(int j=n-1;j>i;j--)
            if(h[i]>h[j])g[i]=max(g[i],g[j]+1);
    }
    int res=0;
    for(int i=0;i<n;i++)
        res=max(res,f[i]+g[i]-1);
    cout<<res<<endl;
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Estrus
5个月前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int f[N],h[N];
int main(){
    int K;
    cin>>K;
    while(K--){
        int n;
        cin>>n;
        memset(f,0,sizeof f);
        for(int i=0;i<n;i++)
            cin>>h[i];
        for(int i=0;i<n;i++){
            f[i]=1;
            for(int j=0;j<i;j++)
                if(h[i]>h[j])f[i]=max(f[i],f[j]+1);
        }

        int res=0;
        for(int i=0;i<n;i++)
            res=max(res,f[i]);
        memset(f,0,sizeof f);    
        for(int i=0;i<n;i++){
            f[i]=1;
            for(int j=0;j<i;j++)
                if(h[i]<h[j])f[i]=max(f[i],f[j]+1);
        }
        for(int i=0;i<n;i++)
            res=max(res,f[i]);
        cout<<res<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1242. 修改数组

Estrus
6个月前
/*
给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅AN],数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 A2,A3,⋅⋅⋅,AN。

当修改 Ai 时,小明会检查 Ai 是否在 A1∼Ai−1 中出现过。

如果出现过,则小明会给 Ai 加上 1;如果新的 Ai 仍在之前出现过,小明会持续给 Ai 加 1,直到 Ai 没有在 A1∼Ai−1 中出现过。

当 AN 也经过上述修改之后,显然 A 数组中就没有重复的整数了。

现在给定初始的 A 数组,请你计算出最终的 A 数组。

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。

输出格式
输出 N 个整数,依次是最终的 A1,A2,⋅⋅⋅,AN。

数据范围
1≤N≤105,
1≤Ai≤106
输入样例:
5
2 1 1 3 4
输出样例:
2 1 3 4 5
*/
#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int a[N];
bool st[N];
int p[N],righ[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
void link(int x){
    int l, r;
    if (st[x - 1])
    {
        l = find(p[x - 1]);
        p[x-1] = x;
    }
    if (st[x + 1])
    {
        r = find(p[x + 1]);
        p[x] = r;
    }
    if (st[x - 1] && st[x + 1])
        p[l] = r;
}
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < N; i++)
        p[i] = i;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (!st[x])
        {
            a[i] = x;
            st[x]=true;
            link(x);
        }

        else
        {

            int root = find(x);

            int t = root+1;
            a[i] = t;
            st[t] = true;
            link(t);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 2875. 超级胶水

Estrus
6个月前
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N=1e5+10;
int a[N];
LL res,total;

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        res+=total*a[i];
        total+=a[i];
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 3419. 双向排序

Estrus
6个月前
/*
给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n),即 ai=i。

小蓝将对这个序列进行 m 次操作,每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列,或者将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

请求出操作完成后的序列。

输入格式
输入的第一行包含两个整数 n,m,分别表示序列的长度和操作次数。

接下来 m 行描述对序列的操作,其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时,表示将 a1,a2,⋅⋅⋅,aqi 降序排列;当 pi=1 时,表示将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

输出格式
输出一行,包含 n 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。

数据范围
对于 30% 的评测用例,n,m≤1000;
对于 60% 的评测用例,n,m≤5000;
对于所有评测用例,1≤n,m≤105,0≤pi≤1,1≤qi≤n。

输入样例:
3 3
0 3
1 2
0 2
输出样例:
3 1 2
样例解释
原数列为 (1,2,3)。

第 1 步后为 (3,2,1)。

第 2 步后为 (3,1,2)。

第 3 步后为 (3,1,2)。与第 2 步操作后相同,因为前两个数已经是降序了。
*/
#include <iostream>
#include <algorithm>

using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10;

PII stk[N];
int ans[N];

int main()
{
    int n, m;
    int top = 0;
    cin>>n>>m;
    while (m--)
    {
        int p, q;
        cin >> p >> q;

        if (!p)
        {

            while (top && stk[top].x == 0)
                q = max(q, stk[top--].y);
            while (top >= 2 && stk[top - 1].y <= q)
                top -= 2;
            stk[++top] = {0, q};
        }
        else if (top)
        {
            while (top && stk[top].x == 1)
                q = min(q, stk[top--].y);
            while (top >= 2 && stk[top - 1].y >= q)
                top -= 2;
            stk[++top] = {1, q};
        }
    }
    int k = n, l = 1, r = n;
    for(int i=1;i<=top;i++)
    {
        if(stk[i].x==0)
            while(r>stk[i].y&&l<=r)ans[r--]=k--;
        else 
            while(l<stk[i].y&&l<=r)ans[l++]=k--;
        if(l>r)break;
    }
    // for (int i = 1; i <= n; i++)
    //     cout << ans[i] << " ";
    // cout << endl;
    if(top%2)
        while(l<=r)ans[l++]=k--;
    else while(l<=r)ans[r--]=k--;
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 3420. 括号序列

Estrus
6个月前
/*
给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。

例如,对于括号序列 (((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()()、()(())、(())()、(()()) 和 ((()))。

输入格式
输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和右括号。

输出格式
输出一个整数表示答案,答案可能很大,请输出答案除以 1000000007 (即 109+7) 的余数。

数据范围
对于 40% 的评测用例,|s|≤200。
对于所有评测用例,1≤|s|≤5000。

输入样例:
((()
输出样例:
5
*/
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 5010, MOD = 1e9 + 7;

LL f[N][N];
char s[N];
int cnt, n;
LL work()
{
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '(')
            for (int j = 1; j <= n; j++)
                f[i][j] = f[i - 1][j - 1];
        else
        {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
            for (int j = 1; j <= n; j++)
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
        }
    }
    for (int i = 0; i <= n; i++)
        if (f[n][i])
            return f[n][i];
    return -1;
}
int main(int argc, char const *argv[])
{
    cin >> s + 1;
    n = strlen(s + 1);
    LL l = work();
    reverse(s + 1, s + 1 + n);
    for (int i = 1; i < n + 1; i++)
        if (s[i] == '(')
            s[i] = ')';
        else
            s[i] = '(';
    LL r = work();
    cout << r * l % MOD << endl;

    return 0;
}



活动打卡代码 AcWing 3492. 负载均衡

Estrus
6个月前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII; // 结束时间, 消耗的资源
const int N = 2e6 + 10;
int n, m;
int resources[N];
priority_queue<PII, vector<PII>, greater<PII>> heap[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%d", &resources[i]);
    while (m--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        while (heap[b].size() && heap[b].top().first <= a)
        {
            resources[b] += heap[b].top().second;
            heap[b].pop();
        }
        if (d > resources[b])
            cout << "-1" << endl;
        else
        {
            heap[b].push({a + c, d});
            resources[b] -= d;
            cout << resources[b] << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 3491. 完全平方数

Estrus
6个月前
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N=1e6+10;
LL x,res=1;
LL primes[N];
int cnt;
void divide(LL x){
    LL n=x;
    for(int i=2;i<=n/i;i++){
         if (n % i == 0)
        {
            int s = 0; //指数
            while (n % i == 0)
            {
                n /= i;
                s++;
            }
            if(s%2){
                primes[cnt++]=i;
            }
        }
    }
    if(n>1)primes[cnt++]=n;
}
bool check(LL x){
    for(int i=2;i<=x/i;i++)
        if(x%i==0)return false;
    return true;
}
int main(){
    cin>>x;
    if(check(x))
    {
        cout<<x<<endl;
        return 0;
    }
    else{
        // 拆分成数论的格式
        divide(x);
        for(int i=0;i<cnt;i++)
            res*=primes[i];
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 3490. 小平方

Estrus
6个月前
#include<iostream>
using namespace std;
int res;
int main(){
    int x;
    cin>>x;
    for(int i=1;i<x;i++)
        if(i*i%x*2<x)res++;
    cout<<res<<endl;
    return 0;
}