头像

llll


访客:10903

离线:4天前


活动打卡代码 AcWing 255. 第K个数

llll
9天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
int n, m, cnt, root[maxn], a[maxn];
int lsh[maxn], tot;
struct node{ int l, r, sum; }T[maxn * 40];
#define mid ((l+r)>>1)
void update(int l, int r, int &x, int y, int pos){
    T[++cnt] = T[y]; T[cnt].sum++; x = cnt;
    if (l == r) return;
    if (pos <= mid) update(l, mid, T[x].l, T[y].l, pos);
    else update(mid + 1, r, T[x].r, T[y].r, pos);
}
int query(int l, int r,int x, int y, int k){
    if (l == r) return l;
    int sum = T[T[y].l].sum - T[T[x].l].sum;
    if (sum >= k)   return query(l, mid, T[x].l, T[y].l, k);
    else return query(mid + 1, r, T[x].r, T[y].r, k-sum);
}
map<int, int>mp;
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];lsh[i] = a[i];
    }
    sort(lsh + 1, lsh + 1 + n);
    tot = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
    for (int i = 1; i <= n; i++){
        int x = a[i];
        a[i] = lower_bound(lsh + 1, lsh + 1 + tot, a[i]) - lsh;
        mp[a[i]] = x;
    }
    for (int i = 1; i <= n; i++)
        update(1, n, root[i], root[i - 1], a[i]);
    while (m--){
        int l, r, k;
        cin >> l >> r >> k;
        cout << mp[query(1, n, root[l - 1], root[r], k)] << endl;
    }
    return 0;
}



活动打卡代码 AcWing 244. 谜一样的牛

llll
9天前
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+100;


int c[N];
void add(int x,int v)
{
    while(x<N)
    {
        c[x]+=v;
        x+=x&-x;
    }
}
int check(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=x&-x;
    }
    return ans;
}
int a[N],ans[N];

int main()
{
    int n;
    cin>>n;
    add(1,1);
    for(int i=2;i<=n;i++) cin>>a[i],add(i,1);
    for(int i=n;i>=1;i--)
    {
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(mid)>=a[i]+1)  r=mid;
            else l=mid+1;
        }
        ans[i]=r;
        add(r,-1);
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
} 



llll
9天前
#include<bits/stdc++.h>
using namespace std;

#define ll long long 

const int N=5e5+100;

ll a[N],b[N];

struct node
{
    ll v,g;
}t[N<<2];
#define ls x<<1
#define rs x<<1|1
void build(int l,int r,int x)
{
    if(l==r) 
    {
        t[x].v=b[l];
        t[x].g=b[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    t[x].g=__gcd(t[ls].g,t[rs].g);
    t[x].v=t[ls].v+t[rs].v;
}
ll query(int l,int r,int L,int R,int x)
{
    //if(L>R) return 0;
    if(L<=l&&r<=R)  return t[x].g;
    int mid=l+r>>1;
    ll ans=0;
    if(R<=mid)  return query(l,mid,L,R,ls);
    if(L>mid) return query(mid+1,r,L,R,rs);
    else return __gcd(query(l,mid,L,R,ls),query(mid+1,r,L,R,rs));
} 
void update(int l,int r,int p,ll v,int x)
{
    if(l==r) 
    {
        t[x].v+=v;
        t[x].g+=v;
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid) update(l,mid,p,v,ls);
    else if(p>mid) update(mid+1,r,p,v,rs);
    t[x].g=__gcd(t[ls].g,t[rs].g);
    t[x].v=t[ls].v+t[rs].v;
}
ll getsum(int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R) return t[x].v;
    int mid=l+r>>1;
    ll ans=0;
    if(L<=mid) ans=ans+getsum(l,mid,L,R,ls);
    if(R>mid ) ans=ans+getsum(mid+1,r,L,R,rs);
    return ans; 
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    build(1,n,1);
    while(m--)
    {
        char c[4];
        int l,r;
        ll v;
        scanf("%s",&c);
        if(c[0]=='Q') 
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",abs(__gcd(getsum(1,n,1,l,1),query(1,n,l+1,r,1))));
        }
        else
        {
            scanf("%d%d%lld",&l,&r,&v);
            update(1,n,l,v,1);
            if(r+1<=n)update(1,n,r+1,-v,1);
        }
    } 
    return 0;
} 


活动打卡代码 AcWing 289. 环路运输

llll
9天前
#include<bits/stdc++.h>
using namespace std;

const int N=2e6+100;

int a[N],q[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i+n]=a[i];
    int l=0,r=-1;
    int len=n/2;

    int ans=0;
    for(int i=1;i<=2*n;i++)
    {
        while(l<=r&&i-q[l]>len) l++;
        ans=max(ans,a[i]+a[q[l]]+i-q[l]);
        while(l<=r&&a[i]-i>=a[q[r]]-q[r]) r--;
        q[++r]=i;
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 288. 休息时间

llll
9天前
#include<bits/stdc++.h>
using namespace std;

int dp[2][4000][2];//前i小时睡了j 小时当前这一小时睡觉没  

int w[4000];
int main()
{

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    memset(dp,-0x3f,sizeof dp);
    //第n小时不睡觉 
    dp[1][0][0]=0,dp[1][1][1]=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i&1][j][0]=max(dp[(i-1)&1][j][1],dp[(i-1)&1][j][0]);
            dp[i&1][j][1]=-0x3f3f3f3f;
            if(j)dp[i&1][j][1]=max(dp[(i-1)&1][j-1][1]+w[i],dp[(i-1)&1][j-1][0]);
        }
    } 
    int res=dp[n&1][m][0];

    memset(dp,-0x3f,sizeof dp);
    //第n小时睡觉
    dp[1][0][0]=0,dp[1][1][1]=w[1];
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i&1][j][0]=max(dp[(i-1)&1][j][1],dp[(i-1)&1][j][0]);
            dp[i&1][j][1]=-0x3f3f3f3f;
            if(j)dp[i&1][j][1]=max(dp[(i-1)&1][j-1][1]+w[i],dp[(i-1)&1][j-1][0]);
        }
    } 
    res=max(res,dp[n&1][m][1]);
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 283. 多边形

llll
10天前
#include<bits/stdc++.h>
using namespace std;


const int N=110;


char c[N];
int w[N];

int f[N][N],g[N][N]; 
int main()
{

    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>w[i];
        c[i+n]=c[i];
        w[i+n]=w[i];
    }

    int ans=-0x3f3f3f3f;
    for(int len=1;len<=n;len++)
    {
        for(int l=1;l+len-1<=2*n;l++)
        {
            int r=l+len-1;
            if(len==1) f[l][r]=g[l][r]=w[l];
            else
            {
                f[l][r]=-0x3f3f3f3f,g[l][r]=0x3f3f3f3f;
                for(int k=l;k<r;k++)
                {
                    char op=c[k+1];
                    if(op=='t')
                    {
                        f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
                        g[l][r]=min(g[l][r],g[l][k]+g[k+1][r]);
                    }
                    else
                    {
                        int x1=f[l][k]*f[k+1][r],x2=f[l][k]*g[k+1][r];
                        int x3=g[l][k]*g[k+1][r],x4=g[l][k]*f[k+1][r];
                        f[l][r]=max(f[l][r],max(max(x1,x2),max(x3,x4)));
                        g[l][r]=min(g[l][r],min(min(x1,x2),min(x3,x4)));
                    }
                }
            }
            if(len==n) ans=max(ans,f[l][r]);
        }
    }

    cout<<ans<<endl;;
    for(int i=1;i<=n;i++) if(f[i][i+n-1]==ans) cout<<i<<' ';

    return 0;
}


活动打卡代码 AcWing 298. 围栏

llll
10天前
#include<bits/stdc++.h>
using namespace std;


const int N=2e5+100;


struct node
{
    int l,p,s;
    bool operator<(const node &M) const
    {
        return s<M.s;
    } 
}a[200]; 


int q[N];
int dp[110][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i].l>>a[i].p>>a[i].s;
    sort(a+1,a+1+m);
    for(int i=1;i<=m;i++)
    {
        int h=0,t=-1;
        int l=a[i].l,p=a[i].p,s=a[i].s;
        for(int j=0;j<=n;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j) dp[i][j]=max(dp[i][j],dp[i][j-1]);
            while(h<=t&&q[h]<j-l) h++;
            if(j>=s&&h<=t)
            {
                int k=q[h];
                dp[i][j]=max(dp[i][j],dp[i-1][k]+(j-k)*p);
            }
            if(j<s)
            {
                while(h<=t&&dp[i-1][q[t]]+(j-q[t])*p<=dp[i-1][j]) t--;
                q[++t]=j;
            }
        }
    }
    cout<<dp[m][n]<<endl;
    return 0;
} 


活动打卡代码 AcWing 299. 裁剪序列

llll
10天前
#include<bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll f[N], m, sum;
int a[N], n;
deque<int> q;
multiset<ll> heap;
multiset<ll>::iterator it;

int main() {
    scanf("%d%lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > m) {
            puts("-1");
            return 0;
        }
    }
    for (int i = 1, j = 0; i <= n; i++) {
        sum += a[i];
        while (sum > m)sum -= a[++j];
        while (!q.empty() && q.front() <= j) {
            if (q.size() > 1)
                heap.erase(heap.find(f[q.front()] + a[*(++q.begin())]));
            q.pop_front();
        }
        while (!q.empty() && a[q.back()] <= a[i]) {
            if (q.size() > 1 )
                heap.erase(heap.find(f[*(-- --q.end())] + a[q.back()]));
            q.pop_back();
        }
        if (!q.empty())heap.insert(f[q.back()] + a[i]);
        q.push_back(i);
        f[i] = f[j] + a[q.front()];
        if (!heap.empty())f[i] = min(f[i], *heap.begin());
    }
    printf("%lld\n", f[n]);
    return 0;
}




llll
4个月前
#include <iostream>

using namespace std;

const int N = 1000010;

char s[N];

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> s;
        int k = 0;
        for (int i = 0; s[i]; i ++ )
        {
            s[k ++ ] = s[i];

            if (k >= 3 && s[k - 3] == s[k - 2] && s[k - 2] == s[k - 1]) k -- ;
            if (k >= 4 && s[k - 4] == s[k - 3] && s[k - 2] == s[k - 1]) k -- ;
        }
        s[k] = '\0';
        cout << s << endl;
    }
    return 0;
}



活动打卡代码 AcWing 677. 找零

llll
4个月前
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    n = 1024 - n;
    int res = 0;

    int coins[4] = {64, 16, 4, 1};
    for (int i = 0; i < 4; i ++ )
    {
        res += n / coins[i];
        n %= coins[i];
    }

    cout << res << endl;

    return 0;
}