头像

庞加莱复现




离线:7小时前


最近来访(81)
用户头像
天元之弈
用户头像
tomousw
用户头像
Dec.
用户头像
我是雷电将军的狗
用户头像
大黄咬它
用户头像
将军JOE
用户头像
itdef
用户头像
Foraino0267
用户头像
清风不是峰
用户头像
PrinceS
用户头像
NULL_
用户头像
eyetofreedom
用户头像
芒果黄桃冰
用户头像
Homuramio
用户头像
Ethereal-
用户头像
Fatin
用户头像
debugger
用户头像
goodgoodstudydaydayup
用户头像
Skuy
用户头像
yyylll

新鲜事 原文

打卡有点多,刷屏了,见谅


活动打卡代码 AcWing 100. 增减序列

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5;
unsigned int n;
int main(int argc,char* argv[]){
    //freopen("xxxxxxxx.in","r",stdin);freopen("xxxxxxxx.out","w",stdout);
    scanf("%d",&n);
    long long plus=0,minus=0;
    int x,y;
    scanf("%d",&y);
    _for(i,2,n){
        scanf("%d",&x);
        int b=x-y;
        b>0?plus+=b:minus-=b;
        y=x;
    }
    printf("%lld\n%lld\n",max(plus,minus),abs(plus-minus)+1);
    return 0;
    //fclose(stdin);fclose(stdout);
}



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

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=5e3;
int s[maxn+10][maxn+10];
int n,m,r,c;
int get_val(int a,int c2){
    int b=min(a+m,r),d=min(c2+m,c);
    return s[b][d]-s[a-1][d]-s[b][c2-1]+s[a-1][c2-1];
}
int main(int argc,char* argv[]){
    cin>>n>>m;
    m--;
    _for(i,1,n){
        int x,y,w;
        cin>>x>>y>>w;
        x++,y++;
        r=max(r,x),c=max(c,y);
        s[x][y]+=w;
    }
    _for(i,1,r){
        _for(j,1,c){
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            //cout<<s[i][j]<<' ';
        }
        //puts("");
    }
    if(m>r&&m>c){
        cout<<s[r][c]<<endl;
        return 0;
    }
    int ans=0;
    _for(i,1,r)_for(j,1,c){
        ans=max(ans,get_val(i,j));
    }
    cout<<ans<<endl;
    return 0;
}



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

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef unsigned long long ull;
ull mul(ull a,ull b,ull p){
    ull ans=0;
    for(;b;b>>=1){
        if(b&1)ans=(ans+a)%p;
        a=a*2%p;
    }
    return ans;
}

int main(int argc,char* argv[]){
    //freopen("xxxxxxxx.in","r",stdin);freopen("xxxxxxxx.out","w",stdout);
    ull a,b,p;
    scanf("%ld%ld%ld",&a,&b,&p);
    printf("%ld\n",mul(a,b,p));
    return 0;
    //fclose(stdin);fclose(stdout);
}



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

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=1e5;
const double eps=1e-5;
int n,f;
double a[maxn+10],s[maxn+10];
bool check(double mid){
    s[0]=0;
    _for(i,1,n)s[i]=s[i-1]+a[i]-mid;
    double ans=-1e8,min_val=1e8;
    _for(i,f,n){
        min_val=min(min_val,s[i-f]);
        ans=max(ans,s[i]-min_val);
    }
    return ans>0;
}
int main(){
    scanf("%d%d",&n,&f);
    _for(i,1,n)scanf("%lf",&a[i]);
    double l=-1e6,r=1e6,mid=0;
    while(r-l>eps){
        mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%ld\n",ull(r*1000));
    return 0;
}



活动打卡代码 AcWing 107. 超快速排序

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=5e5;
ull n,a[maxn+10],cnt;
ull b[maxn+10];
void merge(int l, int r){
    if(r==l) return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1;
    _for(k,l,r) if(j>r || i<=mid && a[i]<=a[j]) b[k]=a[i++];
    else b[k]=a[j++],cnt+=mid-i+1;
    _for(i,l,r)a[i]=b[i];
    return;
}
int main(int argc,char* argv[]){
    //freopen("P1908_6.in","r",stdin); 
    while(cin>>n && n){
        cnt=0;
        _for(i,1,n)cin>>a[i];
        merge(1,n);
        //_for(i,1,n)cout<<a[i]<<' ';
        cout<<cnt<<endl;
    }
    return 0;
}



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

class Solution {
    public:
        vector<int> specialSort(int N) {
            vector<int> a;
            for(int i=(N+1)/2;i;i--){
                a.push_back(i);
                if(N-i+1!=i)a.push_back(N-i+1);
            }
            stable_sort(a.begin(),a.end(),compare);
            return a;
        }
};



活动打卡代码 AcWing 168. 生日蛋糕

//T在: 9876 6 
#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=1e4,maxm=20,INF=0x3f3f3f3f;
int n,m;
int q=INF;
int h[maxm+1],r[maxm+1];
int v=0,s=0;
int sqr(int x){return x*x;}                 //优化1 
int cub(int x){return x*x*x;}               //优化3
int minv[maxm+1];                           //优化3 
void dfs(int k){
    if(k==0){
        if(v==n)q=min(q,s);
        return;
    }
    if(minv[k]+v>n)return;                  //优化3(体积可行性剪枝) 
    //if(s>q)return;                        //优化4(面积最优性剪枝) 
    if(s+ 2*(n-v)/r[k+1] > q)return;         //优化5(面积最优性剪枝) 
    int t1=min(int(sqrt(n-v)),r[k+1]-1);    //优化1
    __for(R,t1,k){                          //优化2 
        if(k==m)s=R*R;
        int t2=min((n-v)/sqr(R),h[k+1]-1);  //优化1 
        __for(H,t2,k){                      //优化2 
            r[k]=R,h[k]=H;
            v+=R*R*H;
            s+=2*R*H;
            dfs(k-1);
            v-=R*R*H;
            s-=2*R*H;
        }
    }
    return;
}
int main(){
    cin>>n>>m;
    memset(h,0,sizeof(h));
    memset(r,0,sizeof(r));
    r[m+1]=h[m+1]=INF;
    _for(i,1,m+1)minv[i]=minv[i-1]+cub(i);   //优化3 
    dfs(m);
    if(q==INF)q=0;
    printf("%d\n",q);
    return 0;
}


活动打卡代码 AcWing 167. 木棒

//AC
#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;i++)
#define __for(i,a,b) for(int i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const int maxn=1e5;
int n;
int a[maxn+10],b[maxn+10];
int cnt,len;
int vis[maxn+10]; 
bool cmp(int a,int b){return a>b;}
bool dfs(int k){//匹配第k根木棒 
    if(k>cnt)return 1;//全部匹配完成 
    if(b[k]==len)return dfs(k+1);//当前木棒匹配完成 
    _for(i,1,n) if(vis[a[i]]){
        if(b[k]+a[i]<=len){
            vis[a[i]]--;b[k]+=a[i];
            if(dfs(k))return 1;
            vis[a[i]]++;b[k]-=a[i];
            if(b[k]==0)return 0;          //优化3 
            if(b[k]+a[i]==len)return 0;   //优化4 
        }
    }
    return 0;
}

int main(){
    while(cin>>n){
        if(!n)break;
        int sum=0;
        cnt=len=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(vis,0,sizeof(vis));
        _for(i,1,n){
            cin>>a[i];
            vis[a[i]]++;
            sum+=a[i];
        }
        sort(a+1,a+n+1,cmp);
        n=unique(a+1,a+n+1)-(a+1);
        for(len=2;len<=sum;len++)if(sum%len==0){
            cnt=sum/len;
            if(dfs(1)){
                cout<<len<<endl;
                continue;
            }
        }
    }
    return 0;
}




活动打卡代码 AcWing 171. 送礼物

#include<bits/stdc++.h>
#define _for(i,a,b) for(ull i=a;i<=b;i++)
#define __for(i,a,b) for(ull i=a;i>=b;i--)
typedef unsigned long long ull;
using namespace std;
const ull maxn=46,maxm=1e7;
ull w,n,g[maxn+10];
ull dep1,dep2;
ull wei1[maxm+10],cnt=0;
bool vis[maxn+10];
ull ans=0;
inline ull read(){
    char ch=getchar();ull x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
void dfs1(ull k,ull w2){
    if(w2>w)return;
    if(k>dep1){
        wei1[++cnt]=w2;
        return;
    }
    dfs1(k+1,w2);
    dfs1(k+1,w2+g[k]);
    return;
}
void dfs2(ull k,ull w2){
    if(w2>w)return;
    if(k<dep2){
        int l=1,r=cnt;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(wei1[mid]<=w-w2) l=mid;
            else r=mid-1;
        }
        ans=max(ans,wei1[l]+w2);
        return;
    }
    dfs2(k-1,w2);
    dfs2(k-1,w2+g[k]);
}
int main(){
    w=read(),n=read();
    _for(i,1,n)g[i]=read();
    sort(g+1,g+n+1,greater<ull>());
    dep1=n>>1,dep2=dep1+1;
    dfs1(1,0);
    sort(wei1+1,wei1+cnt+1);
    cnt=unique(wei1+1,wei1+cnt+1)-(wei1+1);
    dfs2(n,0);
    printf("%ld\n",ans);
    return 0;
}