头像

SayonaraGzm




离线:52分钟前


最近来访(69)
用户头像
neepoo
用户头像
kekekuli_0
用户头像
人形柠檬
用户头像
greater
用户头像
我是syy
用户头像
Thu_yc
用户头像
fujang
用户头像
leoma
用户头像
Jackie_2
用户头像
嘉然是牛马
用户头像
AvastandhazyM
用户头像
sToOwPhoebe
用户头像
itdef
用户头像
sailei
用户头像
显微镜
用户头像
D.Y.L.
用户头像
HeXing
用户头像
zst2001
用户头像
Fighting_Peter
用户头像
nsuCony


SayonaraGzm
4小时前

前言

传送门:
总体思路很流畅,就是代码不怎么好写

思路

题目要求两个操作 :
- 区间更新 : 懒标记 (难写啊!
- 区间查询 : 查询$gcd$更不好写!

区间更新的优化 :

区间$+$ 或者 $-$ 一个数 可以用 差分 变成单点操作

区间查询优化 :

根据 $gcd(a,b) = gcd(a,b-a)..... gcd(a,b,c,d…) = gcd(a,b-a,c-b,…)$

公式请拐弯到y总视频

因此我们只需要特殊处理 第一个点 和 后面用 差分处理 即可

CODE

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ned '\n'
const int N = 5e5+10;
int n,m;
ll w[N];

struct node
{
    int l,r;
    ll sum,d;
} tr[N*4];
void pushup(node &u,node &l,node &r)
{
    u.sum = l.sum + r.sum;
    u.d = __gcd(l.d,r.d);
}

void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(int u,int l,int r)
{
    if(l == r)
    {
        ll b = w[r] -w[r-1];
        tr[u] = {l,r,b,b};
    }
    else
    {
        tr[u].l  =l ;
        tr[u].r = r;
        int mid  =l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(int u,int x,ll v)
{
    if(tr[u].l == x && tr[u].r == x)
    {
        ll b = tr[u].sum + v;
        tr[u] = {x,x,b,b};
    }else
    {
        int mid = tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        pushup(u);
    }
}
node query(int u,int l,int r)
{
    if(tr[u].l >=l  && tr[u].r <=r ) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >>1;
        if(r<=mid) return query(u<<1,l,r);
        else if(l>mid) return query(u<<1|1,l,r);
        else
        {
            auto left = query(u<<1,l,r);
            auto right = query(u<<1|1,l,r);
            node res;
            pushup(res,left,right);
            return res;

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

    build(1,1,n);

    int l,r;
    ll d;
    char op[2];

    while(m -- )
    {
        cin>>op>>l>>r;



        if(*op == 'Q')
        {
            auto left = query(1,1,l);
            node right({0,0,0,0});
            if(l+1<=r) right = query(1,l+1,r);
            cout<<abs(__gcd(left.sum,right.d))<<ned;

        }
        else
        {
            cin>>d;
            modify(1,l,d);
            if(r+1<=n)
            modify(1,r+1,-d);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

前言

本题链接 :
滑动窗口 : 维护一个大小为 $k$ 的 区间的 最大值和 最小值

思路

取 $f[i]$表示 以$a[i]$结尾,长度不超过$m$最大值

对于区间和 : 我们可以用前缀和维护 $sum[r] - sum[l]$

因此暴力做法 可以对于每一个$i$我们都枚举左端点 :

$f[i] = max(S[i] - S[j]) (1<=i-j<=m)$
即 :
$f[i] =S[i] - min S[j] (1<=i-j<=m)$

因此我们可以通过单调队列优化

即 :
从前往后,记录一个长度不超过$m$的区间最小值

CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10,INF =1e9;
int n,m;
int s[N],q[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>s[i],s[i]+=s[i-1];

    int res = -INF;
    int hh = 0 ,tt = 0 ;

    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-m) hh++;

        res = max(res,s[i]-s[q[hh]]);

        while(hh<=tt && s[q[tt]] >= s[i])
        tt--;

        q[++tt] = i;
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}



前言

本题链接 :
滑动窗口 : 维护一个大小为 $k$ 的 区间的 最大值和 最小值

思路

取 $f[i]$表示 以$a[i]$结尾,长度不超过$m$最大值

对于区间和 : 我们可以用前缀和维护 $sum[r] - sum[l]$

因此暴力做法 可以对于每一个$i$我们都枚举左端点 :

$f[i] = max(S[i] - S[j]) (1<=i-j<=m)$
即 :
$f[i] =S[i] - min S[j] (1<=i-j<=m)$

因此我们可以通过单调队列优化

即 :
从前往后,记录一个长度不超过$m$的区间最小值

CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+10,INF =1e9;
int n,m;
int s[N],q[N];

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>s[i],s[i]+=s[i-1];

    int res = -INF;
    int hh = 0 ,tt = 0 ;

    for(int i=1;i<=n;i++)
    {
        if(q[hh]<i-m) hh++;

        res = max(res,s[i]-s[q[hh]]);

        while(hh<=tt && s[q[tt]] >= s[i])
        tt--;

        q[++tt] = i;
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}



前言

传送门 : https://www.acwing.com/problem/content/8/
貌似之前就做过了 (地下城的 HP和护甲值)

思路

原先 $01$背包的状态转移方程是

$f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i])$

选在容量为$j$的情况下选前$i$件物品的选法

既然多加了一维 并且这维 和 体积是同一属性的 那么 状态转移方程应该是

$f[i][j] = max(f[i-1][j][k],f[i-1][j-v][k-m]+w[i])$

优化 :
因为都只是用了到$i-1$层 所以我们可以删除该层

但是为了不影响答案,我们需要从大到小枚举

因此优化后的状态转移方程为
$f[j][k] = max(f[k][m],[j-v][k-m]+w[i])$

CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N];
int n,V,M;
int v[N],m[N],w[N];

void solve()
{
    cin>>n>>V>>M;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>m[i]>>w[i];

    for(int i=1;i<=n;i++)
        for(int j = V;j>=v[i];j--)
            for(int k=M;k>=m[i];k--)
            f[j][k] =max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
    cout<<f[V][M];

}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


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

前言 :

前言 : https://www.acwing.com/problem/content/3493/

思路

将 除法 转换为 乘法

CODE

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int res = 0;
    int n;cin>>n;
    for(int i=1;i<n;i++)
    {
        if( ((i*i)%n)*2 < n)
            ++res;
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int  res = 0 ;
    for(int i=1;i<=5;i++)
    {
        string s;cin>>s;
        if(s[0] == s[2]&&(s[3]-'0')==(s[1]-'0')+1)
        ++res;
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


活动打卡代码 AcWing 3496. 特殊年份

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int  res = 0 ;
    for(int i=1;i<=5;i++)
    {
        string s;cin>>s;
        if(s[0] == s[2]&&(s[3]-'0')==(s[1]-'0')+1)
        ++res;
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
long long  exgcd(long long  a, long long  b, long long  &x, long long  &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    long long  d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}
int  main()
{
    long long  a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b;
    return 0;
}


活动打卡代码 AcWing 873. 欧拉函数

前言

传送门 : https://www.acwing.com/problem/content/875/
真简单啊 嘻嘻

思路

欧拉函数 : 求 $(1-N)中 和 N 互质的数的个数$
公式如下 :
$\phi(N)=N \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \ldots \times \frac{p_{m}-1}{p_{m}}$

公式证明 :
1. 对于每一个自然数 我们都刻有拆成 他的质因子倍数的乘积 (算术基本定理)
2. 根据容斥原理我们可以知道,我们所求的答案就是 $(1-N)$这个集合当中 不包括他质因子的倍数的 集合

在这里插入图片描述

CODE

/// 对一个数N 求出1~N 中的 互质数的个数
#include <bits/stdc++.h>
using namespace std;
int phi(int x)
{
    int res = x;
    for(int i=2; i<=x/i; i++)
        if(x%i == 0 )
        {
            /// N * (1-1/p)的变形
            res = res/i * (i-1);
            while(x%i == 0 ) x/=i;
        }
        if(x>1) res = res /x *(x-1);
        return res;
}
void solve()
{
    int n;cin>>n;
    cout<<phi(n)<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t -- )
    solve();
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

.。。。

#include <bits/stdc++.h>
using namespace std;
const int N  = 1e5+10;
int sum[N],a[N];
void cal()
{

}
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i],sum[i] = a[i];

    sort(a+1,a+1+n);
    long long res=  0,t = 0;
    for(int i =1;i<=n;i++)
    {
        res  += t;
        t+=a[i];
    }


    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}