头像

liyx19

赣州一中信奥社团




离线:1小时前


活动打卡代码 AcWing 802. 区间和

liyx19
1小时前
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3e5+5;
int a[N],s[N];
typedef pair<int,int> PII;
vector<int> alls;
vector<PII> add,query;
int find(int x){
    int l=0,r=alls.size();
    while(l<r){
        int mid=(l+r)>>1;
        if(alls[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r+1;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
    for(auto item : add){
        int x=find(item.first);
        a[x]+=item.second;
    }
    for(int i=1;i<=alls.size();i++){
        s[i]=s[i-1]+a[i];
    }
    for(auto item : query){
        int l=find(item.first),r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
}


活动打卡代码 AcWing 112. 雷达设备

liyx19
1天前
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1005;
const double eps=1e-5;
struct AC{
    double l,r;
}a[N];
int cmp(AC a,AC b){
    if(a.r==b.r) return a.l<b.l;
    return a.r<b.r;
}
int main(){
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        if(y>d){
            cout<<-1;
            return 0;
        }
        a[i].l=(double)x-sqrt(d*d-y*y);
        a[i].r=(double)x+sqrt(d*d-y*y);
    }
    sort(a+1,a+n+1,cmp);
    double maxr=-1e9;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i].l>maxr+eps) {
            ans++;
            maxr=a[i].r+eps;
        }
    }
    cout<<ans<<endl;
}


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

liyx19
2天前
#include<iostream>
#define eps 1e-5
using namespace std;
const int N=100005;
int a[N];
int n,f;
bool check(double mid){
    double s[N];
    for(int i=1;i<=n;i++){
        s[i]=a[i]-mid,s[i]+=s[i-1];
    }
    double val=1e9,ans=-1e9;
    for(int i=f;i<=n;i++){
        val=min(val,s[i-f]);
        ans=max(ans,s[i]-val);
    }
    if(ans<=0) return false;
    else return true;
}
int main(){
    cin>>n>>f;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    double l=-1e6,r=1e6;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid;
        }
        else r=mid;
    }
    cout<<(int)(r*1000);
}


活动打卡代码 AcWing 117. 占卜DIY

liyx19
3天前
#include<iostream>
using namespace std;
int a[15][5];
int tub[15],sum[15];
int main(){
    for(int i=1;i<=13;i++){
        string sb;
        getline(cin,sb);
        int cnt=0;
        sum[i]=4;
        for(int j=0;j<sb.size();j++){
            if(sb[j]>='A' && sb[j]<='Z'){
                cnt++;
                if(sb[j]=='A'){
                    a[i][cnt]=1;
                } 
                if(sb[j]=='J'){
                    a[i][cnt]=11;
                }
                if(sb[j]=='Q'){
                    a[i][cnt]=12;
                }
                if(sb[j]=='K'){
                    a[i][cnt]=13;
                }
            }
            if(sb[j]>='0' && sb[j]<='9'){
                cnt++;
                if(sb[j]=='0'){
                    a[i][cnt]=10;
                }
                else a[i][cnt]=sb[j]-'0';
            }
        }
    }
    int life=4;
    while(life>0){
        int x=a[13][5-life];
        while(x!=13){
            tub[x]++;
            x=a[x][sum[x]--];
        }
        life--;
    }
    int ans=0;
    for(int i=1;i<=12;i++){
        if(tub[i]==4) ans++;
    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 111. 畜栏预定

liyx19
3天前
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
struct AC{
    int l,r,ver;
    bool operator <(const AC &a)const
    {
        if(a.r==r) return l>a.l;
        return r>a.r;
    }
}a[N];
int cmp(AC a,AC b){
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}
priority_queue<AC> q;
int m,ans[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].ver=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(!q.empty() && q.top().r<a[i].l){
            ans[a[i].ver]=ans[q.top().ver];
            q.pop();
        }
        else{
            m++;
            ans[a[i].ver]=m;
        }
        q.push(a[i]);
    }
    cout<<m<<endl;
    for(int i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
}


活动打卡代码 AcWing 110. 防晒

liyx19
3天前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=2505;
struct Ac{
    int l,r;
}a[N];
struct Wa{
    int spf,cov;
}b[N];
int cmp(Wa a,Wa b){
    return a.spf>b.spf;
}
int CMP(Ac a,Ac b){
    return a.l>b.l;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
    }
    sort(a+1,a+n+1,CMP);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&b[i].spf,&b[i].cov);
    }
    sort(b+1,b+m+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[j].cov>0&&b[j].spf>=a[i].l && b[j].spf<=a[i].r){
                b[j].cov--;
                ans++;
                break;
            }
        }
    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 106. 动态中位数

liyx19
3天前
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct cmp
{
    bool operator ()(int &a,int &b)
    {
        return a>b;
    }
};
priority_queue<int,vector<int>,cmp> nu1,q1;
priority_queue<int> q2,nu2;
int main(){
    int P;
    cin>>P;
    while(P--){
        int ver,n,cnt=0;
        cin>>ver>>n;
        q1=nu1;
        q2=nu2;
        cout<<ver<<" "<<(n+1)/2<<endl;
        for(int i=1;i<=n;i++){
            int now;
            cin>>now;
            if(q1.empty()){
                q1.push(now);
            }
            else if(now>q1.top())
                    {
                        q1.push(now);
                    }
                 else q2.push(now);
            while(q1.size()<q2.size()){
                q1.push(q2.top());
                q2.pop();
            }
            while(q1.size()>q2.size()+1){
                q2.push(q1.top());
                q1.pop();
            }
            if(i&1){
                cnt++;
                cout<<q1.top()<<" ";
                if(cnt%10==0) cout<<endl;
            }
        }
        if(cnt%10!=0)puts("");
    }
}


活动打卡代码 AcWing 282. 石子合并

liyx19
4天前
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=310;
int s[N];
int f[N][N],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) s[i]+=s[i-1];
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=1e9;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    cout<<f[1][n];
}


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

liyx19
4天前
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int a[N][N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    int ans=-1e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int x=i;x<=n;x++){
                for(int y=j;y<=n;y++){
                    ans=max(ans,a[x][y]-a[x][j-1]-a[i-1][y]+a[i-1][j-1]);
                }
            }
        }
    }
    printf("%d",ans);
}


活动打卡代码 AcWing 116. 飞行员兄弟

liyx19
5天前
#include<iostream>
#include<cstring>
using namespace std;
const int N=10,M=1e6+5;
char c[N][N];
int a[N][N],b[N][N];
struct AC{
    int x,y;
}ans[M],res[M];
void turn(int x,int y){
    for(int i=1;i<=4;i++){
        b[i][y]^=1;
    }
    for(int j=1;j<=4;j++){
        b[x][j]^=1;
    }
    b[x][y]^=1;
}
int main(){
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin>>c[i][j];
            if(c[i][j]=='-') a[i][j]=1;
        }
    }
    int n=1e9;
    for(int i=1;i<(1<<17);i++){
        bool ok=true;int ans1=0;
        //memset(ans,0,sizeof ans);
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++) b[k][j]=a[k][j];
        }
        for(int j=1;j<=16;j++){
            if(i>>(j-1)&1){
                int dx=j/4+1,dy=j%4;
                if(!dy){
                    dy=4;
                    dx--;
                }
                turn(dx,dy);
                ans1++;
                ans[ans1]={dx,dy};
                /*if(ans1>n){
                    break;
                    ok=false;
                }*/
            }
        }
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                if(!b[j][k]){
                    ok=false;
                    break;
                }
            }
        }
        if(ok){
            cout<<ans1<<endl;
            for(int j=1;j<=ans1;j++){
                cout<<ans[j].x<<" "<<ans[j].y<<endl;
            }
            //ans1=n;
            break;
        }
    }
    /*cout<<n;
    for(int i=1;i<=n;i++){
        cout<<res[i].x<<" "<<res[i].y<<endl;
    }*/
}