头像

漂流瓶_4

qwq


访客:2476

离线:7小时前


活动打卡代码 AcWing 1509. 打怪

漂流瓶_4
2个月前
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int N=100001,inf=0x7f7f7f7f;
int n,a,b,w,tota,ans;
struct gw{
    int x,y;
    bool operator < (const gw b)const{
        return y<b.y;
    }
}s[N],t[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>w>>a>>b;
    a+=b;
    fs(i,1,n,1){
        cin>>s[i].x>>s[i].y;
    }
    fs(i,1,n,1){
        if(s[i].x<=a) t[++tota]=s[i];
    }
    sort(t+1,t+tota+1);
    fs(i,1,tota,1){
        w-=t[i].y;
        if(w>=0) ans++;
        if(w<=0){
            cout<<ans;
            return 0;
        }
    }
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 1511. 笨鸟

漂流瓶_4
2个月前

qaq




漂流瓶_4
2个月前

算法

(暴力枚举) $O(n)$

维护每个区间的最高点和最低点即可。

参考文献

y总的课

C++ 代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=1000001,inf=0x7f7f7f7f;
int n,ans[N],f,u,d,l;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>f;
    fs(i,1,n,1){
        int x,a,b;cin>>x>>a>>b;
        a++,b--;
        u+=x-l;
        d-=x-l;
        if((u&1)!=(b&1)) b--;
        if((d&1)!=(a&1)) a++;
        u=min(u,b);
        d=max(d,a);
        if(u<d){
            cout<<"Stupid bird!";
            return 0;
        }
        ans[i]=(x+d)/2;
        l=x;
    }
    fs(i,1,n,1) cout<<ans[i]<<'\n';
    cout<<ans[n];
    return 0;
}




漂流瓶_4
2个月前

算法

(浮点数二分) $O(\log n)$

直接二分即可,实际上最后会搞出公式$\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$,即$c=\frac{ab}{a+b}\text{。(积在和上飞)。}$

如果小了就$l=mid$,大了就$r=mid$。

C++ 代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x7f7f7f7f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline bool xr(bool x,bool y){
    return x==y?0:1;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
ull ksm(ull a,ull b){
    ull ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
        }
        base*=base;
        b>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){
    if(b) return gcd(b,a%b);
    return a;
}
bool prm(int k){
    if(k<2) return 0;
    if(k==2||k==3) return 1;
    if(k%6!=1&&k%6!=5) return 0;
    for(int i=5;i<=sqrt(k);i+=6)
        if(k%i==0||k%(i+2)==0) return 0;
    return 1;
}
db x,y,c;
db chk(db s){
    db p=sqrt(x*x-s*s),q=sqrt(y*y-s*s);
    return p*q/(q+p);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>x>>y>>c;
    db l=0,r=min(x,y);
    while(r-l>1e-5){
        db mid=(l+r)/2;
        if(chk(mid)>c) l=mid;
        else r=mid;
    }
    cout<<fixed<<setprecision(3)<<l;
    return 0;
}




漂流瓶_4
2个月前

算法

(浮点数二分) $O(\log n)$

直接二分即可,实际上最后会搞出公式$\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$,即$c=\frac{ab}{a+b}\text{。(积在和上飞)。}$

如果小了就$l=mid$,大了就$r=mid$。

C++ 代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x7f7f7f7f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline bool xr(bool x,bool y){
    return x==y?0:1;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
ull ksm(ull a,ull b){
    ull ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
        }
        base*=base;
        b>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){
    if(b) return gcd(b,a%b);
    return a;
}
bool prm(int k){
    if(k<2) return 0;
    if(k==2||k==3) return 1;
    if(k%6!=1&&k%6!=5) return 0;
    for(int i=5;i<=sqrt(k);i+=6)
        if(k%i==0||k%(i+2)==0) return 0;
    return 1;
}
db x,y,c;
db chk(db s){
    db p=sqrt(x*x-s*s),q=sqrt(y*y-s*s);
    return p*q/(q+p);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>x>>y>>c;
    db l=0,r=min(x,y);
    while(r-l>1e-5){
        db mid=(l+r)/2;
        if(chk(mid)>c) l=mid;
        else r=mid;
    }
    cout<<fixed<<setprecision(3)<<l;
    return 0;
}



活动打卡代码 AcWing 1510. 楼梯

漂流瓶_4
2个月前
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x7f7f7f7f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline bool xr(bool x,bool y){
    return x==y?0:1;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
ull ksm(ull a,ull b){
    ull ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
        }
        base*=base;
        b>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){
    if(b) return gcd(b,a%b);
    return a;
}
bool prm(int k){
    if(k<2) return 0;
    if(k==2||k==3) return 1;
    if(k%6!=1&&k%6!=5) return 0;
    for(int i=5;i<=sqrt(k);i+=6)
        if(k%i==0||k%(i+2)==0) return 0;
    return 1;
}
db x,y,c;
db chk(db s){
    db p=sqrt(x*x-s*s),q=sqrt(y*y-s*s);
    return p*q/(q+p);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>x>>y>>c;
    db l=0,r=min(x,y);
    while(r-l>1e-5){
        db mid=(l+r)/2;
        if(chk(mid)>c) l=mid;
        else r=mid;
    }
    cout<<fixed<<setprecision(3)<<l;
    return 0;
}




漂流瓶_4
2个月前
#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int N=100001,inf=0x7f7f7f7f;
int n,a,b,w,tota,ans;
struct gw{
    int x,y;
    bool operator < (const gw b)const{
        return y<=b.y;
    }
}s[N],t[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>w>>a>>b;
    a+=b;
    fs(i,1,n,1){
        cin>>s[i].x>>s[i].y;
    }
    fs(i,1,n,1){
        if(s[i].x<=a) t[++tota]=s[i];
    }
    sort(t+1,t+tota+1);
    fs(i,1,tota,1){
        w-=t[i].y;
        if(w>=0) ans++;
        if(w<=0){
            cout<<ans;
            return 0;
        }
    }
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 1508. 划拳

漂流瓶_4
2个月前
#include <iostream>
using namespace std;
int k,a,b;
int main(){
    cin >> k;
    while (k--){
        int x, y;
        cin >> x >> y;
        if (x == y) continue;
        if (x == 20 && (y == 5 || y == 10)) b += 10;
        else if (y == 20 && (x == 5 || x == 10)) a += 10;
        else{
            int t = x - y;
            if (t < 0) b -= t;
            else a += t;
        }
    }
    cout << a << ' ' << b;
   return 0;
}


活动打卡代码 AcWing 887. 求组合数 III

漂流瓶_4
2个月前
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 6;
ll ksm(ll a, ll b, ll p){
    ll res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
ll c(ll a, ll b, ll p){
    ll res = 1;
    for(int i = 1, j = a;i <= b;++i, --j){
        res = res * j % p;
        res = res * ksm(i, p - 2, p) % p;
    }
    return res % p;
}

ll lucas(ll a, ll b, ll p){
    if(a < p && b < p) return c(a, b, p);
    return c(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}

int main(){
    int n;cin>>n;
    while(n--){
        ll a, b;cin>>a>>b;
        ll p; cin>>p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

漂流瓶_4
2个月前
#include<iostream>
#include<vector>
using namespace std;
vector<int> s(100010,0),b(100010,0);
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) b[i]=s[i]-s[i-1];
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    for(int i=1;i<=n;i++){
        b[i]=b[i-1]+b[i];
        cout<<b[i]<<' ';
    }
    return 0;
}