头像

zhangshuo2008




离线:4天前


活动打卡代码 AcWing 1273. 天才的记忆

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 200010,M = 18;
int f[N][M];
int w[N];
int n,m;
void init()
{
    for(int j=0;j<M;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            if(!j)f[i][j]=w[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
}
int query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    init();
    cin>>m;
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
}


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

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+17;
struct node {
    int l, r;
    int ql, qr;
    int sum;
}tr[N * 4];
int root[N],a[N],b[N];
int idx;
int n,q;
int build(int l, int r)
{
    int u = ++idx, mid = l + r >> 1;
    tr[u].ql = l, tr[u].qr = r;
    if (l == r) return u;
    tr[u].l = build(l, mid);
    tr[u].r = build(mid + 1, r);
    return u;
}
void pushup(int u)
{
    tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;
}
int modify(int p, int x)
{
    int u = ++idx;
    tr[u].l = tr[p].l, tr[u].r = tr[p].r;
    tr[u].ql = tr[p].ql, tr[u].qr = tr[p].qr;
    tr[u].sum=tr[p].sum+1;
    if (tr[u].ql == tr[u].qr)
    {
        return u;
    }
    int mid = tr[u].ql + tr[u].qr >> 1;
    if (x <= mid)tr[u].l = modify(tr[p].l, x);
    else tr[u].r = modify(tr[p].r, x);
    return u;
}
int query(int u,int v, int k)
{
    if(tr[u].ql>=tr[u].qr)return tr[u].ql;
    int x=tr[tr[v].l].sum-tr[tr[u].l].sum;
    int mid=tr[u].ql+tr[u].qr>>1;
    if(x>=k) return query(tr[u].l,tr[v].l,k);
    else return query(tr[u].r,tr[v].r,k-x);
}
void print(int u)
{
    cout<<tr[u].ql<<" "<<tr[u].qr<<" "<<tr[u].sum<<endl;
    if(tr[u].ql==tr[u].qr)return;
    print(tr[u].l);
    print(tr[u].r);
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    root[0]=build(1,m);
    for(int i=1;i<=n;i++)
    {
        int t=lower_bound(b+1,b+1+m,a[i])-b;
        root[i]=modify(root[i-1],t);
    }
    while(q--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        int t=query(root[l-1],root[r],k);
        cout<<b[t]<<endl;
    }
}


活动打卡代码 AcWing 102. 最佳牛围栏

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 101011;
double s[N];
double a[N];
int n,F;
bool check(double avg)
{
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]-avg;
    double mins=0;
    for(int k=F;k<=n;k++)
    {
        mins=min(mins,s[k-F]);
        if(s[k]-mins>=0)return true;
    }
    return false;
}

int main()
{
    double l=0,r=0;
    cin>>n>>F;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        r=max(r,a[i]);
    }
    while(r-l>1e-5)
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%d",(int)(r*1000));
}


活动打卡代码 AcWing 99. 激光炸弹

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
int s[N][N];
int main()
{
    int n,r;
    cin>>n>>r;
    r=min(r,5002);
    for(int i=1;i<=n;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        x++,y++;
        s[x][y]+=w;
    }
    for(int i=1;i<=5001;i++)
    {
        for(int j=1;j<=5001;j++)
        {
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    int res=0;
    for(int i=r;i<=5001;i++)
    {
        for(int j=r;j<=5001;j++)
        {
            res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
        }
    }
    cout<<res<<endl;
}


活动打卡代码 AcWing 97. 约数之和

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

const int mod = 9901;
int qmi(int a,int k)
{
    int res=1;
    a%=mod;
    while(k)
    {
        if(k&1)res=res*a%mod;
        k>>=1;
        a=a*a%mod;
    }
    return res;
}
int sum(int p,int k)
{
    if(k==1)return 1;
    if(k%2==0)return (1+qmi(p,k/2))*sum(p,k/2)%mod;
    if(k%2==1)return (sum(p,k-1)+qmi(p,k-1))%mod;
}

int main()
{
    int a,b;
    cin>>a>>b;
    int res=1;
    for(int i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            int s=0;
            while(a%i==0)
            {
                a/=i;
                s++;
            }
            res=res*sum(i,b*s+1)%mod;
        }
    }
    if(a>1)
    {
        res=res*sum(a,b+1)%mod;
    }
    if(a==0)cout<<0<<endl;
    else cout<<res%mod;
}


活动打卡代码 AcWing 90. 64位整数乘法

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
signed main()
{
    int a,b,p,res=0;
    cin>>a>>b>>p;
    while(b)
    {
        if(b&1)res=(res+a)%p;
        b>>=1;
        a=2*a%p;
    }
    cout<<res<<endl;
}


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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int exgcd(int a, int b, int &x, int &y)  // 扩展欧几里得算法, 求x, y,使得ax + by = gcd(a, b)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int a,b,m,x,y;
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y);
        if(b%d)puts("impossible");
        else cout<<(long long)x*(b/d)%m<<endl;
    }
}



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


活动打卡代码 AcWing 876. 快速幂求逆元

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int p=19260817;
char s1[10051], s2[10051];
int a,b;
int qmi(int a, int k, int p)  
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        k >>= 1;
    }
    return res;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n%m==0)
        {
            puts("impossible");
            continue;
        }
        else cout<<qmi(n,m-2,m)<<endl;
    }
}


活动打卡代码 AcWing 793. 高精度乘法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>A;
vector<int>B;
string a,b;
// vector<int> add(vector<int> &A, vector<int> &B)  // C = A + B, A >= 0, B >= 0
// {
//     if (A.size() < B.size()) return add(B, A);

//     vector<int> C;
//     int t = 0;
//     for (int i = 0; i < A.size(); i ++ )
//     {
//         t += A[i];
//         if (i < B.size()) t += B[i];
//         C.push_back(t % 10);
//         t /= 10;
//     }

//     if (t) C.push_back(t);
//     return C;
// }

vector<int> add(vector<int> &A,vector<int> &B)
{
    if(A.size()<B.size())return add(B,A);
    vector<int>c;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size())t+=B[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t)c.push_back(1);
    return c;
}
int main()
{
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
    vector<int>C=add(A,B);
    for(int i=C.size()-1;i>=0;i--)
    {
        cout<<C[i];
    }
}