头像

sweet


访客:3843

离线


活动打卡代码 AcWing 104. 货仓选址

sweet
10个月前
#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=1;i<=n;i++)ans+=abs(a[i]-a[(n+1)/2]);
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

sweet
10个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);
        for(int i=2;i<=N;i++){
            int l=0,r=res.size()-1;
            while(l<=r){
                int mid=l+r>>1;
                if(compare(res[mid],i))l=mid+1;
                else r=mid-1;
            }
            res.push_back(i);
            for(int j=res.size()-2;j>r;j--)swap(res[j],res[j+1]);
        }
        return res;
    }
};


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

sweet
11个月前
#include<bits/stdc++.h>
using namespace std;
double n,cow[100005],m;
double sum[100005];
int check(double x){
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+cow[i]-x;
    double minv=0;
    for(int i=m,j=0;i<=n;i++,j++){
        minv=min(minv,sum[j]);
        if(sum[i]>=minv)return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>cow[i];
    double l=0,r=2000;
    while(r-l>1e-5){
        double mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    cout<<int(r*1000);
    return 0;
}


活动打卡代码 AcWing 101. 最高的牛

sweet
2019-05-27 13:04
#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll> a[10100];
map<ll,ll> q;
ll n,m,i,j,k,p,h,c[10100],d[10100];
int main()
{
    cin>>n>>p>>h>>m;
    for(i=1;i<=m;i++){
        ll A,B;
        cin>>A>>B;
        if(A>B)swap(A,B);
        if(q[A]!=B)a[i]=make_pair(A,B),q[A]=B,d[A+1]--,d[B]++;
    }
    for(i=1;i<=n;i++)c[i]=c[i-1]+d[i];
    for(i=1;i<=n;i++)cout<<c[i]+h<<endl;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

sweet
2019-02-10 09:59
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int main()
{
    int n,i,x,a=0,t;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>x;
        q.push(-x);
    }
    for(i=1;i<n;i++){
        t=q.top();
        a-=q.top();
        q.pop();
        t+=q.top();
        a-=q.top();
        q.pop();
        q.push(t);
    }
    cout<<a;
    return 0;
}



sweet
2019-02-10 09:56
class MinStack {
public:
    stack<int> SV,SM;
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        SV.push(x);
        if(SM.empty()||x<SM.top())SM.push(x);
    }

    void pop() {
        if(SV.top()==SM.top())SM.pop();
        SV.pop();
    }

    int top() {
        return SV.top();
    }

    int getMin() {
        return SM.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */


活动打卡代码 AcWing 100. IncDec序列

sweet
2019-02-09 03:45
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,a[100005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>=1;i--)a[i]=a[i]-a[i-1];
    LL pos=0,neg=0;
    for(int i=2;i<=n;i++)
        if(a[i]>0)pos+=a[i];
        else neg-=a[i];
    cout<<max(neg,pos)<<endl<<abs(pos-neg)+1;
    return 0;
}


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

sweet
2019-02-09 03:45
#include<bits/stdc++.h>
using namespace std;
int x,y,w,N,R,n,m,g[5005][5005],ans=-1;
int main()
{
    cin>>N>>R;
    n=R,m=R;
    while(N--){
        cin>>x>>y>>w;
        x++,y++;
        g[x][y]=w;
        n=max(n,x);
        m=max(m,y);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
    for(int i=R;i<=n;i++)
        for(int j=R;j<=m;j++)
            ans=max(ans,g[i][j]-g[i-R][j]-g[i][j-R]+g[i-R][j-R]);
    cout<<ans;
    return 0;
}



sweet
2019-02-09 03:06

题目描述

输入两个整数,求这两个整数的和是多少。

样例

样例输入:
3 4
样例输出:
7

算法一

BFS大法闪亮登场!

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,t;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
    cw[x].push_back(y);
    c[x].push_back(c_v);
    p[x].push_back(p_v);
    ce[y].push_back(cw[x].size()-1);
    cw[y].push_back(x);
    c[y].push_back(0);
    p[y].push_back(-p_v);
    ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
            {
                f[cw[now][i]]=min(c[now][i],f[now]);
                e[cw[now][i]]=i;
                u[cw[now][i]]=u[now]+p[now][i];
                pre[cw[now][i]]=now;
                if (vis[cw[now][i]]==0)
                    vis[cw[now][i]]=1,q.push_back(cw[now][i]);
            }
    }
    (*flow)=f[t];
    (*cost)=u[t];
    return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
    int temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
        (*flow)+=temp_flow;
        (*cost)+=temp_cost;
    }
}

int a,b;

int main()
{
    scanf("%d%d",&a,&b);
    cw.resize(0);
    cw.resize(2);
    ce.resize(0);
    ce.resize(cw.size());
    c.resize(0);
    c.resize(cw.size());
    p.resize(0);
    p.resize(cw.size());
    add_edge_1(0,1,oo_max,a);
    add_edge_1(0,1,oo_max,b);
    int ans_flow=0,ans_cost=0;
    min_cost_max_flow_1(0,1,&ans_flow,&ans_cost);
    printf("%d\n",ans_cost);
}

算法二

Dijkstra求最短路

#include<bits/stdc++.h>
using namespace std;
const int N=405;
struct Edge {
    int v,w;
};
vector<Edge> edge[N*N];
int n;
int dis[N*N];
bool vis[N*N];
struct cmp {
    bool operator()(int a,int b) {
        return dis[a]>dis[b];
    }
};
int Dijkstra(int start,int end)
{
    priority_queue<int,vector<int>,cmp> dijQue;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dijQue.push(start);
    dis[start]=0;
    while(!dijQue.empty()) {
        int u=dijQue.top();
        dijQue.pop();
        vis[u]=0;
        if(u==end)
            break;
        for(int i=0;i<edge[u].size();i++) {
            int v=edge[u][i].v;
            if(dis[v]==-1||dis[v]>dis[u]+edge[u][i].w) {
                dis[v]=dis[u]+edge[u][i].w;
                if(!vis[v]) {
                    vis[v]=true;
                    dijQue.push(v);
                }
            }
        }
    }
    return dis[end];
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    Edge Qpush;
    Qpush.v=1;
    Qpush.w=a;
    edge[0].push_back(Qpush);
    Qpush.v=2;
    Qpush.w=b;
    edge[1].push_back(Qpush);
    printf("%d",Dijkstra(0,2));
    return 0;
}

算法三

Floyd算法

#include<bits/stdc++.h>
using namespace std;
long long n=3,a,b,dis[4][4];
int main()
{
    cin>>a>>b;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=2147483647;
    dis[1][2]=a,dis[2][3]=b;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    cout<<dis[1][3];
    return 0;
}

算法四

LCT

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data,rev,sum;
    node *son[2],*pre;
    bool judge();
    bool isroot();
    void pushdown();
    void update();
    void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
    node *now=lct+ ++top;
    now->data=x;
    now->pre=now->son[1]=now->son[0]=lct;
    now->sum=0;
    now->rev=0;
    return now;
}
bool node::judge()
{
    return pre->son[1]==this;
}
bool node::isroot()
{
    if(pre==lct)return true;
    return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
    if(this==lct||!rev)return;
    swap(son[0],son[1]);
    son[0]->rev^=1;
    son[1]->rev^=1;
    rev=0;
}
void node::update()
{
    sum=son[1]->sum+son[0]->sum+data;
}
void node::setson(node *child,int lr)
{
    this->pushdown();
    child->pre=this;
    son[lr]=child;
    this->update();
}
void rotate(node *now)
{
    node *father=now->pre,*grandfa=father->pre;
    if(!father->isroot()) grandfa->pushdown();
    father->pushdown();
    now->pushdown();
    int lr=now->judge();
    father->setson(now->son[lr^1],lr);
    if(father->isroot()) now->pre=grandfa;
    else grandfa->setson(now,father->judge());
    now->setson(father,lr^1);
    father->update();
    now->update();
    if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
    if(now->isroot())return;
    for(; !now->isroot(); rotate(now))
    if(!now->pre->isroot())
    now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
    node *last=lct;
    for(; now!=lct; last=now,now=now->pre) {
        splay(now);
        now->setson(last,1);
    }
    return last;
}
void changeroot(node *now)
{
    access(now)->rev^=1;
    splay(now);
}
void connect(node *x,node *y)
{
    changeroot(x);
    x->pre=y;
    access(x);
}
void cut(node *x,node *y)
{
    changeroot(x);
    access(y);
    splay(x);
    x->pushdown();
    x->son[1]=y->pre=lct;
    x->update();
}
int query(node *x,node *y)
{
    changeroot(x);
    node *now=access(y);
    return now->sum;
}
int main()
{
    scanf("%d%d",&a,&b);
    node *A=getnew(a);
    node *B=getnew(b);
    connect(A,B);
    cut(A,B);
    connect(A,B);
    printf("%d",query(A,B));
    return 0;
}

算法五

main自递归和位运算

#include<bits/stdc++.h>
int main(int a,int b,int k)
{
    if(k)scanf("%d%d",&a,&b);
    printf("%d",b==0?a:main(a^b,(a&b)<<1,0));
    exit(0);
}

算法六

SPFA

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,op,l,r,u,v1,e;
int head[200009],ne_xt[200009],dis[200009];
int len[200009],v[200009],team[200009],pd[100009];
int lt(int x,int y,int z)
{
    op++;
    v[op]=y;
    ne_xt[op]=head[x];
    head[x]=op;
    len[op]=z;
}
int SPFA(int s,int f)
{
    for(int i=1;i<=200009;i++){dis[i]=999999999;}
    l=0,r=1,team[1]=s,pd[s]=1,dis[s]=0;
    while(l!=r){
        l=(l+1)%90000,u=team[l],pd[u]=0,e=head[u];
        while(e!=0){
            v1=v[e];
            if(dis[v1]>dis[u]+len[e]){
                dis[v1]=dis[u]+len[e];
                if(!pd[v1]){
                    r=(r+1)%90000,
                    team[r]=v1,
                    pd[v1]=1;
                }
            }
            e=ne_xt[e];
        }
    }
    return dis[f];
}
int main()
{
    scanf("%d%d",&a,&b);
    lt(1,2,a);
    lt(2,3,b);
    printf("%d",SPFA(1,3));
    return 0;
}

算法七

普通递归法

#include<iostream>
using namespace std;
long long a,b,c;
long long dg(long long a)
{
    if(a<=5)return a;
    return (dg(a/2)+dg(a-a/2));
}
int main()
{
    cin>>a>>b;
    cout<<dg(a)+dg(b);
    return 0;
}

算法八

二分法

#include<iostream>
using namespace std;
long long a,b,c;
long long dg(long long a)
{
    if(a<=5)return a;
    return (dg(a/2)+dg(a-a/2));
}
int main()
{
    cin>>a>>b;
    cout<<dg(a)+dg(b);
    return 0;
}

算法九

普通高精度

#include<bits/stdc++.h>
using namespace std;
char a1[1000],b1[1000];
int a[1000],b[1000],c[1000],la,lb,lc=1,i,x;
int main()
{
    cin>>a1>>b1;
    la=strlen(a1);
    lb=strlen(b1);
    for(i=0;i<=la-1;i++)a[la-i]=a1[i]-'0';
    for(i=0;i<=lb-1;i++)b[lb-i]=b1[i]-'0';
    while(lc<=la||lc<=lb){c[lc]=a[lc]+b[lc]+x,x=c[lc]/10,c[lc]%=10,lc++;}
    c[lc]=x;
    if(c[lc]==0)lc--;
    for(i=lc;i>=1;i--)cout<<c[i];
    return 0;
}

算法十

压位高精

#include<bits/stdc++.h>
#define p 8
#define carry 100000000
using namespace std;  
const int Maxn=50001;  
char s1[Maxn],s2[Maxn];  
int a[Maxn],b[Maxn],ans[Maxn];  
int change(char s[],int n[])   
{  
    char temp[Maxn];   
    int len=strlen(s+1),cur=0;  
    while(len/p){  
        strncpy(temp,s+len-p+1,p);
        n[++cur]=atoi(temp); 
        len-=p;
    }  
    if(len){
        memset(temp,0,sizeof(temp));  
        strncpy(temp,s+1,len);  
        n[++cur]=atoi(temp);   
    }  
    return cur;
}  
int add(int a[],int b[],int c[],int l1,int l2)  
{  
    int x=0,l3=max(l1,l2);  
    for(int i=1;i<=l3;i++){  
        c[i]=a[i]+b[i]+x;  
        x=c[i]/carry;
        c[i]%=carry;  
    }  
    while(x>0){c[++l3]=x%10;x/=10;}  
    return l3;
}  
void print(int a[],int len)  
{   
    printf("%d",a[len]);
    for(int i=len-1;i>=1;i--)printf("%0*d",p,a[i]);
    printf("\n");  
}  
int main()  
{
    scanf("%s%s",s1+1,s2+1);
    int la=change(s1,a);
    int lb=change(s2,b);
    int len=add(a,b,ans,la,lb);    
    print(ans,len);
}  

算法十一

网络流

#include<bits/stdc++.h>
using namespace std;
#define set(x) Set(x)
#define REP(i,j,k) for (int i=(j),_end_=(k);i<=_end_;++i)
#define DREP(i,j,k) for (int i=(j),_start_=(k);i>=_start_;--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()-1))
#define ALL(x) ((x).begin()+1),(x).end()
template<typename T> inline bool chkmin(T &a,const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a,const T &b){ return a < b ? a = b, 1 : 0; }
typedef long long LL;
typedef pair<int,int> node;
const int dmax=1010,oo=0x3f3f3f3f;
int n,m;
int a[dmax][dmax] , ans;
int d[dmax],e[dmax];
priority_queue <node> q;
inline bool operator >(node a,node b){ return a.y>b.y; }
bool p[dmax];
void Set(int x){ p[x]=1; }
void unset(int x){ p[x]=0; }
bool check(int x){ return x!=1 && x!=n && !p[x] && e[x]>0; }
void preflow(){
    e[1]=oo;
    d[1]=n-1;
    q.push(mp(1,n-1));
    set(1);
    while (!q.empty()){
        bool flag=1;
        int k=q.top().x;
        q.pop(),unset(k);
        DREP(i,n,1)
        if ((d[k]==d[i]+1 || k==1) && a[k][i]>0){
            flag=0;
            int t=min(a[k][i],e[k]);
            e[k]-=t;
            a[k][i]-=t;
            e[i]+=t;
            a[i][k]+=t;
            if (check(i)){
                q.push(mp(i,d[i]));
                set(i);
            }
            if (e[k]==0) break;
        }
        if (flag){
            d[k]=oo;
            REP(i,1,n)
            if (a[k][i]>0)chkmin(d[k],d[i]+1);
        }
        if (check(k)){
            q.push(mp(k,d[k]));
            set(k);
        }
    }
    ans=e[n];
}
int main(){
    n = 2, m = 2;
    int x, y;
    scanf("%d%d", &x, &y);
    a[1][2] += x + y;
    preflow();
    printf("%d\n",ans);
    return 0;
}

算法十二

线段树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 10;
struct Tree 
{
    int l, r, val;
}t[MAXN * 4];
int N = 2, a[MAXN];
inline void init() 
{
    for(int i=1; i<=N; i++) 
        scanf("%d", &a[i]);
}
void Build(int Root, int L, int R) 
{
    t[Root].l = L;
    t[Root].r = R;
    t[Root].val = 0;
    if(L == R) {
        t[Root].val = a[L];
        return ;
    }
    int m = (L + R) >> 1;
    int Next = Root * 2;
    Build(Next, L, m);
    Build(Next+1, m+1, R);
    t[Root].val = t[Next].val + t[Next+1].val;

}
void Updata(int Root, int pos, int _val) 
{
    if(t[Root].l == t[Root].r) {
                t[Root].val += _val;
                return ;
        }
        int Next = Root * 2;
        int m = (t[Root].l + t[Root].r) >> 1;
        if(pos <= m) Updata(Next, pos, _val);
        else Updata(Next+1, pos, _val);
        t[Root].val = t[Next].val + t[Next+1].val;
}
int Doit(int Root, int L, int R) 
{
    if(t[Root].l>=L && t[Root].r<=R)return t[Root].val;
    int Ans = 0;
    int Next = Root * 2;
    int m=(t[Root].l + t[Root].r) >> 1;
    if(L<=m)Ans+=Doit(Next,L,R);
    if(R>m)Ans+=Doit(Next+1,L,R);
    return Ans;
}
int main() 
{
    init();
    Build(1,1,N);
    int Ans=Doit(1,1,N);
    printf("%d", Ans);
    return 0;
}

算法十三

最小生成树

#include <cstdio>
#include <algorithm>
#define INF 2140000000
using namespace std;
struct tree{int x,y,t;}a[10];
bool cmp(const tree&a,const tree&b)
{
    return a.t<b.t;
}
int f[11],i,j,k,n,m,x,y,t,ans;
int root(int x)
{
    if (f[x]==x) return x;
    f[x]=root(f[x]);
    return f[x];
}
int main()
{
    for(i=1;i<=10;i++)f[i]=i;
    for(i=1;i<=2;i++){
        scanf("%d",&a[i].t);
        a[i].x=i+1;a[i].y=1;k++;
    }
    a[++k].x=1;a[k].y=3,a[k].t=INF;
    sort(a+1,a+1+k,cmp);
    for(i=1;i<=k;i++){
        x=root(a[i].x);
        y=root(a[i].y);
        if(x!=y)f[x]=y,ans+=a[i].t; 
    }
    printf("%d",ans);
    return 0;
}

好了,扯了那么多,我们来个正常的吧QWQ~~

#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
    cin>>a>>b;
    cout<<a+b<<endl;
    return 0;
}


活动打卡代码 AcWing 98. 分形之城

sweet
2019-02-08 12:31
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
LL T,N,A,B;
PLL calc(LL n,LL m)
{
    if(n==0)return {0,0};
    LL len=1ll<<(n-1),cnt=1ll<<(2*n-2);
    auto pos=calc(n-1,m%cnt);
    LL x=pos.first,y=pos.second;
    LL z=m/cnt;
    if(z==0)return {y,x};
    else if(z==1)return {x,y+len};
    else if(z==2)return {x+len,y+len};
    return {2*len-1-y,len-1-x};
}
int main()
{
    cin>>T;
    while(T--){
        cin>>N>>A>>B;
        auto ac=calc(N,A-1);
        auto bc=calc(N,B-1);
        double x=abs(ac.first-bc.first),y=abs(ac.second-bc.second);
        printf("%.0lf\n",sqrt(x*x+y*y)*10);
    }
    return 0
}