头像

夏花花花花花




离线:15小时前


最近来访(58)
用户头像
zzr0126
用户头像
用户头像
肝帝
用户头像
cl_2
用户头像
wanghai673
用户头像
15163669008
用户头像
ZXG_DXX
用户头像
watasky
用户头像
Jun不见
用户头像
嘟嘟的神秘男友
用户头像
Heilmittel
用户头像
AcWing_czy
用户头像
布榆
用户头像
最傻的猪
用户头像
pikachu_
用户头像
wyzhii
用户头像
redsea
用户头像
zwling
用户头像
找个电子厂上班吧
用户头像
Dream_zsh

活动打卡代码 AcWing 3761. 唯一最小数

夏花花花花花
2021-07-15 20:09
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=2e5+10;
int st[N];
int ans[N];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        memset(st,0,sizeof st);
        //memset(ans,0,sizeof ans);
        for(int i=1;i<=n;i++){
            int xx;
            scanf("%d",&xx);
            if(!st[xx])ans[xx]=i;
            st[xx]++;
        }
        bool flag=0;
        //cout<<"***";
        for(int i=1;i<=n;i++){
            if(st[i]==1){
                cout<<ans[i]<<endl;
                flag=1;
                break;
            }
        }

        if(!flag)cout<<-1<<endl;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2714. 左偏树

夏花花花花花
2021-07-08 18:16
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int w[N],idx;
int n,m;
int p[N];
int L[N],R[N];
int dist[N]; 
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
bool cmp(int a,int b){
    if(w[a]!=w[b])return w[a]<w[b];
    return a<b;
}
int merge(int x,int y){
    if(x==0||y==0)return x+y;
    if(cmp(y,x))swap(x,y);
    R[x]=merge(R[x],y);
    if(dist[R[x]]>dist[L[x]])swap(R[x],L[x]);
    dist[x]=dist[R[x]]+1;
    return x;
}
int main(){
    scanf("%d",&n);
    w[0]=2e9;
    while(n--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int xx;
            scanf("%d",&xx);
            w[++idx]=xx;
            dist[idx]=1;
            p[idx]=idx;
        }
        else if(op==2){
            int x,y;
            scanf("%d%d",&x,&y);
            int px=find(x); int py=find(y);
            if(px!=py){
                if(cmp(py,px))swap(px,py);
                p[py]=px;
                merge(px,py);
            }
        }
        else if(op==3){
            int x; 
            scanf("%d",&x);
            cout<<w[find(x)]<<endl;
        }
        else {
            int x;
            scanf("%d",&x);
            x=find(x);
            if(cmp(R[x],L[x]))swap(L[x],R[x]);
            p[x]=L[x]; p[L[x]]=L[x];
            merge(L[x],R[x]);
        }
    }
} 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3493. 最大的和

夏花花花花花
2021-05-26 17:59
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll w[N];
ll s[N];
int  n,m;
bool st[N];
int main(){
    scanf("%d%d",&n,&m);
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);    
    }
    for(int i=1;i<=n;i++){
        ll xx;
        scanf("%lld",&xx);
        st[i]=xx;
    }
    for(int i=1;i<=n;i++){
        if(st[i])ans+=w[i],s[i]=s[i-1];
        else s[i]=s[i-1]+w[i];
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        int left=max(0,i-m);
        res=max(res,s[i]-s[left]);
    }
    cout<<ans+res<<endl;
} 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3485. 最大异或和

夏花花花花花
2021-05-26 17:49
#include<bits/stdc++.h>
using namespace std;
const int N=100100*31;
int son[N][2];
int cnt[N];
int idx;
int n,m;
void insert(int x,int v){
    int p=0;
    for(int i=30;i>=0;i--){
        int xx=x>>i&1;
        if(!son[p][xx])son[p][xx]=++idx;
        p=son[p][xx];
        cnt[p]+=v;
    }
} 
int query(int x){
    int p=0; int res=0;
    for(int i=30;i>=0;i--){
        int xx=x>>i&1;
        if(cnt[ son[p][!xx] ]){
            p=son[p][!xx];
            res=res<<1|1;
        }
        else {
            p=son[p][xx];
            res=res<<1;
        }
    }
    return res;
}
int s[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int xx;
        scanf("%d",&xx);
        s[i]=s[i-1]^xx;
    }
    insert(s[0],1);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(i-m-1>=0)insert(s[i-m-1],-1);
        ans=max(ans,query(s[i]));
        insert(s[i],1);
    }
    cout<<ans<<endl;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



夏花花花花花
2021-05-06 14:28

前排着重强调 这里的sizeof 必须搞M

不能sizeof c c是形参,大小只有1 (因此,debug一小时)

memcpy(c,b,sizeof ss);

%10 /10的写法要1000ms 压8位只用100ms, 记得开ll,其实复杂度瓶颈在M的大小上,,

M不变,改变%数和/数 不影响时间,,只不过%数大了能减小 M的规模从而降低时间

从此高精度的 +和* 不用vector

数组的高精度除法 也能压位吗,,,,,,

好像高除用的不是很多,,

#include<bits/stdc++.h>
using namespace std;
const int N=90,M=5;
typedef long long ll;

int f[N][N][M];
int n,m;
int ss[M];
void  add(int c[],int a[],int b[]){
    ll t=0;
    for(int i=0;i<M;i++){
        t+=a[i]+b[i];
        c[i]=t%100000000;
        t/=100000000;
    }
}
void  mul(int c[],int a[],int b){
    ll t=0;
    for(int i=0;i<M;i++){
        t+=(ll)a[i]*b;
        c[i]=t%100000000;
        t/=100000000;
    }
}
void  maxv(int c[],int a[],int b[]){
    for(int i=M-1;i>=0;i--){
        if(a[i]>b[i]){
            memcpy(c,a,sizeof ss);
            return ;
        }
        if(a[i]<b[i]){
            memcpy(c,b,sizeof ss);
            return ;
        }
    }
    memcpy(c,b,sizeof ss);
    return ;
}
void out(int c[]){
    int k=M-1; bool flag=0;
    while(k>=1&&!c[k])k--;
    for(int i=k;i>=0;i--){
        if(!flag)printf("%d",c[k]),flag=1;
        else printf("%08d",c[i]);
    }
    cout<<endl;
}
int qmi2[N][M];
int a[N][N];
int main(){
    scanf("%d%d",&n,&m);
    qmi2[0][0]=1;
    for(int i=1;i<=m;i++)mul(qmi2[i],qmi2[i-1],2);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int ans[M]={0};
    for(int i=1;i<=n;i++){
        memset(f,0,sizeof f);
        for(int len=1;len<=m;len++){
            for(int l=1;l+len-1<=m;l++){
                if(len==1){
                    mul(f[l][l],qmi2[m],a[i][l]);
                    continue;
                }
                int r=l+len-1;
                int p=m-(r-l+1)+1;
                int temp[M];
                mul(temp,qmi2[p],a[i][r]);
                add(temp,f[l][r-1],temp);
                maxv(f[l][r],f[l][r],temp);
                mul(temp,qmi2[p],a[i][l]);
                add(temp,f[l+1][r],temp);
                maxv(f[l][r],f[l][r],temp);
            }
        }
        add(ans,ans,f[1][m]);
    }
    out(ans);
}


活动打卡代码 AcWing 2938. 周游世界

夏花花花花花
2021-04-27 15:51
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+100;
#define x first
#define y second
typedef pair<int,int>PII;
PII q[N];
int stk[N],top;
bool used[N];
int n;
PII operator-(PII a,PII b){
    return {a.x-b.x,a.y-b.y};
}
PII operator+(PII a,PII b){
    return {a.x+b.x,a.y+b.y};
}
int  operator*(PII a,PII b){
    return a.x*b.y-a.y*b.x;
}
int get_dist(PII a,PII b){
    int dx=a.x-b.x;
    int dy=a.y-b.y;
    return dx*dx+dy*dy;
}
int  area(PII a,PII b,PII c){
    return (b-a)*(c-a);
}
void get_convex(){
    sort(q,q+n);
    for(int i=0;i<n;i++){
        while(top>=2&&area(q[stk[top-2]],q[stk[top-1]],q[i])<=0){
            if(area(q[stk[top-2]],q[stk[top-1]],q[i])<0)used[stk[--top]]=0;
            else top--;
        }
        stk[top++]=i;
        used[i]=1;
    }
    used[0]=0;
    for(int i=n-1;i>=0;i--){
        if(used[i])continue;
        while(top>=2&&area(q[stk[top-2]],q[stk[top-1]],q[i])<=0)top--;
        stk[top++]=i;
    }
    top--;
}
int rotating_calipers(){
    if(top<=2)return get_dist(q[0],q[n-1]);
    int res=0;
    for(int i=0,j=2;i<top;i++){
        PII d=q[stk[i]],e=q[stk[i+1]];
        while(area(d,e,q[stk[j]])<area(d,e,q[stk[(j+1)]]))j=(j+1)%top;
        res=max(res,get_dist(d,q[stk[j]]));
        res=max(res,get_dist(e,q[stk[j]]));

    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",&q[i].x,&q[i].y);
    get_convex();
    cout<<rotating_calipers()<<endl;
} 
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2785. 信号增幅仪

夏花花花花花
2021-04-27 11:22
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=5e4+10;
const double eps=1e-12;
const double pi=acos(-1);

typedef pair<double,double>PDD;
struct Circle {
    PDD p;
    double r;
};
PDD q[N];
int n;
int sign(double a){
    if(fabs(a)<eps)return 0;
    if(a<0)return -1;
    else return 1;
}
int dcmp(double x,double y){
    if(fabs(x-y)<eps)return 0;
    if(x<y)return -1;
    return 1;
}
PDD operator+(PDD a,PDD b){
    return {a.x+b.x,a.y+b.y};
}
PDD operator-(PDD a,PDD b){
    return {a.x-b.x,a.y-b.y};
}
PDD operator*(PDD a,double t){
    return {a.x*t,a.y*t};
}
PDD operator/(PDD a,double  t){
    return {a.x/t,a.y/t};
}
double operator*(PDD a,PDD b){
    return a.x*b.y-a.y*b.x;
}
PDD rotate(PDD a,double b){
    return {a.x*cos(b)+a.y*sin(b),-a.x*sin(b)+a.y*cos(b)};
}
pair<PDD,PDD> get_line(PDD a,PDD b){
    return {(a+b)/2,rotate(b-a,pi/2)};
}
double get_dist(PDD a,PDD b){
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
    auto u=p-q;
    double t=w*u/(v*w);
    return p+v*t;
}
Circle get_circle(PDD a,PDD b,PDD c){
    auto u=get_line(a,b);
    auto v=get_line(a,c);
    PDD p=get_line_intersection(u.x,u.y,v.x,v.y);
    return {p,get_dist(p,a)};
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&q[i].x,&q[i].y);
    }
    double yy,xx;
    scanf("%lf%lf",&yy,&xx);
    for(int i=0;i<n;i++){
        q[i]=rotate(q[i],yy/180.0*pi);
        q[i].x/=xx;
    }
    random_shuffle(q, q + n);
    Circle c={q[0],0};
    for(int i=1;i<n;i++){
        if(dcmp(c.r,get_dist(c.p,q[i]))<0){
            c={q[i],0};
            for(int j=0;j<i;j++){
                if(dcmp(c.r,get_dist(c.p,q[j]))<0){
                    c={(q[i]+q[j])/2,get_dist(q[i],q[j])/2};
                    for(int k=0;k<j;k++){
                        if(dcmp(c.r,get_dist(c.p,q[k]))<0){
                            c=get_circle(q[i],q[j],q[k]);
                        }
                    }
                }
            }
        }
    }
    //printf("%lf %lf\n",c.p.x,c.p.y);
    printf("%.3lf\n",c.r);
}


//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3028. 最小圆覆盖

夏花花花花花
2021-04-26 19:16

get_mid(a,b) get_mid(a,c)能过

get_mid(a,b) get_mid(b,c)就不能过 wc

Circle get_circle(PDD a,PDD b,PDD c){
    auto xx=get_mid(a,b);
    auto yy=get_mid(a,c);
    PDD res=get_line_intersection(xx.x,xx.y,yy.x,yy.y);
    return {res,get_dist(res,b)};
}
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<double ,double>PDD;
const int N=1e5+100;
const double  pi=acos(-1);
const double  eps=1e-12;
struct Line{
    PDD st,ed;
}line[N];
struct Circle{
    PDD p;
    double r;
};
PDD q[N];
PDD operator- (PDD a,PDD b){
    return {a.x-b.x,a.y-b.y};
}
PDD operator+ (PDD a,PDD b){
    return {a.x+b.x,a.y+b.y};
}
PDD operator*(PDD a,double t){
    return {a.x*t,a.y*t};
}
double get_dist(PDD a,PDD b){
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return  sqrt(dx*dx+dy*dy);
}
double  operator*(PDD a,PDD b){
    return a.x*b.y-a.y*b.x;
}
PDD operator/(PDD a,double b){
    return {a.x/b,a.y/b};
}
int  sign(double x){
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
int  dcmp(double x,double y){
    if(fabs(x-y)<eps)return 0;
    if(x<y)return -1;
    return 1;
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
    PDD u=p-q;
    double t=w*u/(v*w);
    //return {p.x+v.x*t,p.y+v.y*t};
    return p+v*t;
}
PDD rotate(PDD a,double b){
    return {a.x*cos(b)+a.y*sin(b),-a.x*sin(b)+a.y*cos(b)};
}
pair<PDD,PDD>  get_mid(PDD a,PDD b){
    return {(a+b)/2,rotate(b-a,pi/2)};
}
Circle get_circle(PDD a,PDD b,PDD c){
    auto xx=get_mid(a,b);
    auto yy=get_mid(a,c);
    PDD res=get_line_intersection(xx.x,xx.y,yy.x,yy.y);
    return {res,get_dist(res,b)};
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&q[i].x,&q[i].y);
    }
    random_shuffle(q, q + n);
    Circle c={q[0],0};
    for(int i=0;i<n;i++){
        if(dcmp(c.r,get_dist(c.p,q[i]))<0){
            c={q[i],0};
            for(int j=0;j<i;j++){
                if(dcmp(c.r,get_dist(c.p,q[j]))<0){
                    c={{(q[i]+q[j])/2},get_dist(q[i],q[j])/2};
                    for(int k=0;k<j;k++){
                        if(dcmp(c.r,get_dist(c.p,q[k]))<0){
                            c=get_circle(q[i],q[j],q[k]);
                        }
                    }
                }
            }
        }
    }
    printf("%.10lf\n",c.r);
    printf("%.10lf %.10lf\n",c.p.x,c.p.y);
}



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2957. 赛车

夏花花花花花
2021-04-26 17:00
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=10010;
typedef long double LD;
typedef pair<LD,LD>PDD;
typedef pair<int,int>PII;
const LD eps=1e-18;
struct Line {
    PDD st,ed;
    vector<int>ids;
}line[N];
int cnt;
int q[N];
int ans[N];
PDD operator-(PDD a,PDD b){
    return {a.x-b.x,a.y-b.y};
}
int ki[N],vi[N];
int sign(LD x){
    if(fabs(x)<eps)return 0;
    if(x>0)return 1;
    else return -1;
}
int dcmp(LD x,LD y){
    if(fabs(x-y)<eps)return 0;
    if(x>y)return 1;
    else return -1;
}
LD cross(PDD a,PDD b){
    return a.x*b.y-a.y*b.x;
}
LD area(PDD a,PDD b,PDD c){
    return cross(b-a,c-a);
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
    PDD u=p-q;
    LD t=cross(w,u)/cross(v,w);
    return {p.x+t*v.x,p.y+t*v.y};
}
PDD get_line_intersection(Line a,Line b){
    return  get_line_intersection(a.st,a.ed-a.st,b.st,b.ed-b.st);
}
LD get_angle(const  Line  &a){
    return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
}
bool cmp(const Line &a,const Line &b){
    LD A=get_angle(a),B=get_angle(b);
    if(!dcmp(A,B))return sign(area(a.st,a.ed,b.st))<0;
    return A<B;
}
bool on_right(Line a,Line b,Line c){
    PDD o=get_line_intersection(b,c);
    return area(a.st,a.ed,o)<0;
}
void half_plane_intersection(){
    sort(line,line+cnt,cmp);
    int hh=0,tt=-1;
    for(int i=0;i<cnt;i++){
        if(i&&!dcmp(get_angle(line[i-1]),get_angle(line[i])))continue;
        while(hh+1<=tt&&on_right(line[i],line[q[tt-1]],line[q[tt]]))tt--;
        while(hh+1<=tt&&on_right(line[i],line[q[hh]],line[q[hh+1]]))hh++;
        q[++tt]=i;
    }
    while(hh+1<=tt&&on_right(line[q[hh]],line[q[tt-1]],line[q[tt]]))tt--;
    while(hh+1<=tt&&on_right(line[q[tt]],line[q[hh]],line[q[hh+1]]))hh++;
    int k=0;
    for(int i=hh;i<=tt;i++){
        for(auto  t:line[q[i]].ids){
            ans[k++]=t;
        }
    }
    sort(ans,ans+k);
    cout<<k<<endl;
    for(int i=0;i<k;i++)cout<<ans[i]<<' ';
    cout<<endl;
}
int main(){
    map<PII,vector<int> >ids;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&ki[i]);
    for(int i=1;i<=n;i++)scanf("%d",&vi[i]);
    for(int i=1;i<=n;i++){
        ids[{ki[i],vi[i]}].push_back(i);
    }
    line[cnt++]={{0,10000},{0,0}};
    line[cnt++]={{0,0},{10000,0}};
    map<PII,vector<int> >::iterator it;

    for(it=ids.begin();it!=ids.end();it++){
        line[cnt++]={{0,it->first.first},{1,it->first.first+it->first.second},it->second};
    }
    half_plane_intersection();
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 2803. 凸多边形

夏花花花花花
2021-04-26 14:31
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=510;
const double eps=1e-8;
typedef pair<double ,double>PDD;
struct Line{
    PDD st,ed;
}line[N];
PDD pg[N],ans[N];
int q[N];
int cnt;
int sign(double x){
    if(fabs(x)<eps)return 0;
    if(x>0)return 1;
    else return -1;
}
int dcmp(double x,double y){
    if(fabs(x-y)<eps)return 0;
    if(x>y)return 1;
    return -1;
}
PDD operator-( PDD a,PDD b){
    return {a.x-b.x,a.y-b.y};
}
double cross(PDD a,PDD b){
    return a.x*b.y-a.y*b.x;
}
double get_angle(const Line &a){
    return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
}
double area(PDD a,PDD b,PDD c){
    return cross(b-a,c-a);
}
bool cmp(const Line &a,const Line &b){
    double A=get_angle(a); double B=get_angle(b);
    if(!dcmp(A,B))return area(a.st,a.ed,b.st)<0;
    return A<B;
}
PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
    PDD u=p-q;
    double t=cross(w,u)/cross(v,w);
    return {p.x+t*v.x,p.y+t*v.y};
}
PDD get_line_intersection(Line a,Line b){
    return get_line_intersection(a.st,a.ed-a.st,b.st,b.ed-b.st);
}
bool on_right(Line &a,Line &b,Line &c){
    PDD o=get_line_intersection(b,c);
    return sign(area(a.st,a.ed,o))<=0;
}
double half_plane_intersection(){
    sort(line,line+cnt,cmp);
    int hh=0,tt=-1;
    for(int i=0;i<cnt;i++){
        if(i&&!dcmp(get_angle(line[i]),get_angle(line[i-1])))continue;
        while(hh+1<=tt&&on_right(line[i],line[q[tt-1]],line[q[tt]]))tt--;
        while(hh+1<=tt&&on_right(line[i],line[q[hh]],line[q[hh+1]]))hh++;
        q[++tt]=i;
    }
    while(hh+1<=tt&&on_right(line[q[hh]],line[q[tt-1]],line[q[tt]]))tt--;
    while(hh+1<=tt&&on_right(line[q[tt]],line[q[hh]],line[q[hh+1]]))hh++;
    q[++tt]=q[hh];
    int k=0;
    for(int i=hh;i+1<=tt;i++){
        ans[k++]=get_line_intersection(line[q[i]],line[q[i+1]]);
    }
    double res=0;
    for(int i=1;i+1<k;i++){
        res+=area(ans[0],ans[i],ans[i+1]);
    }
    return res/2;
}
int main(){
    int n,m;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%lf%lf",&pg[i].x,&pg[i].y);
        }
        for(int i=0;i<m;i++){
            line[cnt++]={pg[i],pg[(i+1)%m]};
        }
    }
    double res=half_plane_intersection();
    printf("%.3lf\n",res);
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~