头像

垫底抽風

垫底抽风粉丝团




离线:2小时前


最近来访(9588)
用户头像
1eave
用户头像
一人舛木
用户头像
Saber青铜--孙
用户头像
天蝎座的流星
用户头像
eyetofreedom
用户头像
不要不听话
用户头像
小宋最可爱
用户头像
种花家的蒟蒻
用户头像
limie
用户头像
杨xyz
用户头像
lexorigliasso
用户头像
娇._8
用户头像
封禁用户
用户头像
种花家的兔兔
用户头像
起きない皓流
用户头像
Finn2009
用户头像
月亮供电不足
用户头像
Andy2035
用户头像
sz_jinzikai
用户头像
zeng9999jian


垫底抽風
2小时前

算法1

由于我们输入的这个序列是无序的,而我们要把这些数字两两统一,于是我们就要先排序,这样才能使操作次数最少
我们接下来只需要累加两两相差的值,每次累加到a[i+1]-a[i]
于是我们就能得到一下代码:

for(int i=1;i<=n;i+=2)c+=a[i+1]-a[i];

最终输出c即可

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int c=0;
    for(int i=1;i<=n;i+=2)c+=a[i+1]-a[i];
    cout<<c;
}



新鲜事 原文

垫底抽風
17小时前
⣠⣤⣤⣤⡀⠀⠀⢀⣀⣀⣤⣤⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⣾⣻⣻⣻⣻⡿⠚⠉⠉⠀⠀⠀⠀⠀⠀⠈⠙⠲⣴⣻⣻⣻⣷⣄ ⢸⣻⣻⣻⣻⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢻⣻⣻⣻⣻ ⠀⠻⣻⣻⠏⠀⠀⠀⠀⣶⠿⠿⢿⣷⣄⢠⡿⠿⠶⠦⠀⢹⣻⣻⣻ ⠀⠀⢈⡏⠀⠀⠀⠀⠈⠑⠺⣻⠟⠉⠁⠈⠛⢿⠆⠀⠀⠀⢻⠋⠁ ⠀⠀⡼⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠂⠀⢀⠀⢠⡄⠀⠀⠀⢸⡀⠀ ⢀⣴⡇⠀⠀⠀⠀⠀⠀⠶⢿⣻⣉⣛⣻⣻⣛⣉⡻⣦⠀⠀⠀⣇⠀ ⣾⣻⡇⠀⠀⠀⠀⠀⠀⠄⢸⡟⢿⣯⣭⣭⣽⣻⠃⠈⠀⠀⠀⣻⣧ ⣻⣻⣻⣦⡀⠀⠀⠀⠀⠈⠿⠶⣭⣭⣬⡭⠁⠀⠀⠀⢀⣼⣻⣻⣧ ⣻⣻⣻⣻⣻⣶⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣴⣻⣻⣻⣻⣻ ⣻⣻⣻⣻⣻⣻⣻⣻⣻⣷⣶⣶⣶⣶⣶⣾⣻⣻⣻⣻⣻⣻⣻⣻⣻


活动打卡代码 AcWing 525. 小凯的疑惑

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

main()
{
    int a, b;
    cin >> a >> b;
    cout << a * b - (a + b); 
}



算法1

真·提高组

(别说我是抄代码的我只是短代码的题直接用模板级补全写的)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

main()
{
    int a, b;
    cin >> a >> b;
    cout << a * b - (a + b); 
}



算法1

  • 如题所示:$a×b=x$

看到素数两个字我们先把函数代码写好(这里不多解释):

bool prime(int x){
    if(x==1)return 0;//1不是素数
    for(int i=2;i<=x/i;i++)
        if(x%i==0)return 0;//能被其他数整除,不是质数
    return 1;//质数
}

如果我们想把时间复杂度降低,我们就需要用单重循环,而我们之前说过
所以ab就是in/i
判断是不是质数就是prime(i)prime(n/i)
但是我们要注意——整除
所以我们还要进行特判:i<=n/i&&n%i==0
最终输出即可

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
bool prime(int x){
    if(x==1)return 0;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)return 0;
    return 1;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(prime(i)&&prime(n/i)&&i<=n/i&&n%i==0){
            cout<<i<<' '<<n/i;
            return 0;
        }
    }
}



活动打卡代码 AcWing 154. 滑动窗口

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[1000001],s[1000001],i,p,q;
int main()
{
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
    p=0;
    q=0;
    for(i=1;i<=n;i++){
        if(i-s[p]>=k)p++;
        while(p<=q&&a[i]<=a[s[q]])q--;
        q++;
        s[q]=i;
        if(i>=k)cout<<a[s[p]]<<' ';
    }
    cout<<'\n';
    p=0;
    q=0;
    for(i=1;i<=n;i++){
        if(i-s[p]>=k)p++;
        while(p<=q&&a[i]>=a[s[q]])q--;
        q++;
        s[q]=i;
        if(i>=k)cout<<a[s[p]]<<' ';
    }
}

作者:垫底抽風
链接:https://www.acwing.com/solution/content/134061/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 253. 普通平衡树

#include<bits/stdc++.h>
using namespace std;
const int INF=1e8;
int n;
struct Node
{
    int l,r;
    int key,val;
    int cnt,size;
}tr[100010];
int root,idx;
void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
int get_node(int key)
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].cnt=tr[idx].size=1;
    return idx;
}
void zig(int &p) 
{
    int q=tr[p].l;
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
    pushup(tr[p].r),pushup(p);
}
void zag(int &p) 
{
    int q=tr[p].r;
    tr[p].r=tr[q].l,tr[q].l=p,p=q;
    pushup(tr[p].l),pushup(p);
}
void build()
{
    get_node(-INF),get_node(INF);
    root=1,tr[1].r=2;
    pushup(root);
    if(tr[1].val<tr[2].val)zag(root);
}
void insert(int &p,int key)
{
    if(!p)p=get_node(key);
    else if(tr[p].key==key)tr[p].cnt++;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val)zig(p);
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val)zag(p);
    }
    pushup(p);
}
void remove(int &p,int key)
{
    if(!p)return;
    if(tr[p].key==key){
        if(tr[p].cnt>1)tr[p].cnt--;
        else if(tr[p].l||tr[p].r){
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val){
                zig(p);
                remove(tr[p].r,key);
            }
            else{
                zag(p);
                remove(tr[p].l,key);
            }
        }else p=0;
    }
    else if(tr[p].key>key) remove(tr[p].l,key);
    else remove(tr[p].r,key);
    pushup(p);
}
int get_rank_by_key(int p,int key)
{
    if(!p)return 0;  
    if(tr[p].key==key)return tr[tr[p].l].size+1;
    if(tr[p].key>key)return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)
{
    if(!p)return INF;
    if(tr[tr[p].l].size>=rank)return get_key_by_rank(tr[p].l,rank);
    if (tr[tr[p].l].size+tr[p].cnt>=rank)return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
int get_prev(int p,int key)
{
    if(!p)return -INF;
    if(tr[p].key>=key)return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key)  
{
    if(!p)return INF;
    if(tr[p].key<=key)return get_next(tr[p].r,key);
    return min(tr[p].key, get_next(tr[p].l,key));
}
int main()
{
    build();
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1)insert(root,x);
        else if(opt==2)remove(root,x);
        else if(opt==3)cout<<get_rank_by_key(root,x)-1<<endl;
        else if(opt==4)cout<<get_key_by_rank(root,x+1)<<endl;
        else if(opt==5)cout<<get_prev(root,x)<<endl;
        else cout<<get_next(root, x)<<endl;
    }
}


活动打卡代码 AcWing 275. 传纸条

#include<bits/stdc++.h>
using namespace std;
int n,m,f[51][51][51][51],a[51][51],x;
int main()
{
    int i1,i2,j1,j2;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>a[i][j];
    for(i1=1;i1<=n;i1++)
        for(j1=1;j1<=m;j1++)
            for(i2=1;i2<=n;i2++)
                for(j2=1;j2<=m;j2++){
                    int x=0;
                    x=max(x,f[i1][j1-1][i2][j2-1]);
                    x=max(x,f[i1-1][j1][i2-1][j2]);
                    x=max(x,f[i1][j1-1][i2-1][j2]);
                    x=max(x,f[i1-1][j1][i2][j2-1]);
                    if(i1==i2&&j1==j2)f[i1][j1][i2][j2]=x+a[i1][j1];
                        else f[i1][j1][i2][j2]=x+a[i1][j1]+a[i2][j2];
                }
    cout<<f[n][m][n][m];
}

作者:垫底抽風
链接:https://www.acwing.com/solution/content/130267/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


活动打卡代码 AcWing 240. 食物链

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+1;
int fa[N],d[N];
int ff(int x){
    if(fa[x]==x)return x;
    int r=ff(fa[x]);
    d[x]+=d[fa[x]];
    return fa[x]=r;
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=n;i++)fa[i]=i;
    int ans=0;
    for(int i=1;i<=k;i++){
        int t,a,b;
        cin>>t>>a>>b;
        if(a>n||b>n){
            ans++;
            continue;
        }
        else if(t==2&&a==b){
            ans++;
            continue;
        }
        else{
            int rel;
            if(t==2)rel=1;
            else rel=0;
            int x=ff(a),y=ff(b);
            if(x==y){
                if((((d[a]-d[b])%3)+3)%3!=rel)ans++;
            }
            else{
                fa[x]=y;
                d[x]=d[b]-(d[a]-rel);
            }
        }
    }
    cout<<ans;
}


活动打卡代码 AcWing 1100. 抓住那头牛

#include<bits/stdc++.h>
using namespace std;
int s[100001],p[100001];
int a,b,h,t,x;
bool v[100001];
int main()
{
    int next;
    cin>>a>>b;
    h=1;//把头指针置为1
    t=1;//把尾指针置为1
    p[1]=a;
    s[1]=0;
    while(h<=t){
        x=p[h];
        if(x==b){//抓住了那头牛
            cout<<s[h];
            return 0;
        }
        next=x+1;//模拟x+1
        if(next<=100000&&v[next]==0){
            t++;
            p[t]=next;
            s[t]=s[h]+1;
            v[next]=1;
        }
        next=x-1;//模拟x-1
        if(next>=0&&v[next]==0){
            t++;
            p[t]=next;
            s[t]=s[h]+1;
            v[next]=1;
        }
        next=x*2;//模拟x*2
        if(next<=100000&&v[next]==0){
            t++;
            p[t]=next;
            s[t]=s[h]+1;
            v[next]=1;
        }
        h++;//头指针增加,不然死循环
    }
    return 0;
}

作者:垫底抽風
链接:https://www.acwing.com/solution/content/125572/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。