头像

凌乱之风

SDUT




离线:4分钟前


活动打卡代码 AcWing 422. 校门外的树

凌乱之风
11小时前
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node{
    int l,r;
}a[N],b[N];
bool cmp(node a,node b){
    return a.l<b.l;
}
int main(){
    int l,m,i;
    cin>>l>>m;
    for(i=0;i<m;i++){
        cin>>a[i].l>>a[i].r;
    }
    sort(a,a+m,cmp);
    int right=a[0].r,left=a[0].l,ans=1,sum=0;
    b[ans].l=left,b[ans].r=right;
    for(i=1;i<m;i++){
        if(a[i].l>right){
            b[ans].l=left;
            b[ans].r=right;
            ans++;
            left=a[i].l;
            right=a[i].r;
        }
        else{
            right=max(right,a[i].r);
            b[ans].r=right;
        }
    }
    b[ans].l=left;
    b[ans].r=right;
    for(i=1;i<=ans;i++){
        sum+=b[i].r-b[i].l+1;
    }
    cout<<l-sum+1<<endl;
}


活动打卡代码 AcWing 839. 模拟堆

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], ph[N], hp[N], cnt;
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}
void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}
void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}
int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
}


活动打卡代码 AcWing 838. 堆排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],idx;
void down(int u){
    int t=u;
    if(u*2<=idx&&h[u*2]<h[t]){
        t=u*2;
    }
    if(u*2+1<=idx&&h[u*2+1]<h[t]){
        t=u*2+1;
    }
    if(t!=u){
        swap(h[t],h[u]);
        down(t);
    }
}
int main(){
    int n,m,i;
    cin>>n>>m;
    idx=n;
    for(i=1;i<=n;i++){
       cin>>h[i];
    }
    for(i=n/2;i;i--){
        down(i);
    }
    while(m--){
        cout<<h[1]<<" ";
        h[1]=h[idx];
        idx--;
        down(1);
    }
}


活动打卡代码 AcWing 1227. 分巧克力

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int h[N],w[N],n,k;
bool check(int x){
    int i,res=0;
    for(i=0;i<n;i++){
        res+=(w[i]/x)*(h[i]/x);
    }
    if(res>=k) return true;
    else return false;
}
int main(){
    int i;
    cin>>n>>k;
    for(i=0;i<n;i++) cin>>h[i]>>w[i];
    int l=0,r=1e5;
    while(l<r){
        int mid=l+(r-l)/2;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    cout<<l-1<<endl;
}


活动打卡代码 AcWing 680. 剪绳子

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N],m,n;
bool check(double len){
    int res=0,i;
    for(i=0;i<n;i++){
        res+=a[i]/len;
    }
    if(res>=m) return true;
    else return false;
}
int main(){
    int i;
    cin>>n>>m;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    double l=0,r=1e9;
    while(r-l>1e-3){
        double mid=l+(r-l)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf\n",l);
}


活动打卡代码 AcWing 1346. 回文平方

#include<bits/stdc++.h>
using namespace std;
char get(int x){
    if(x<=9) return x+'0';
    else return x+'A'-10;
}
string base(int x,int b){
    string num;
    while(x) num+=get(x%b),x/=b;
    reverse(num.begin(),num.end());
    return num;
}
bool check(string num){
    int i;
    for(i=0;i<num.size();i++){
        if(num[i]!=num[num.size()-i-1]) return 0;
    }
    return 1;
}
int main(){
    int b,i;
    cin>>b;
    for(i=1;i<=300;i++){
        auto num=base(i*i,b);
        if(check(num)) cout<<base(i,b)<<" "<<num<<endl;
    }
}


活动打卡代码 AcWing 1113. 红与黑

#include<bits/stdc++.h>
using namespace std;
const int N=25;
char a[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1},w,h,sum;
void dfs(int x,int y){
    if(x<0||y<0||x>=h||y>=w||a[x][y]=='#') return ;
    a[x][y]='#';
    sum++;
    dfs(x+dx[0],y+dy[0]);
    dfs(x+dx[1],y+dy[1]);
    dfs(x+dx[2],y+dy[2]);
    dfs(x+dx[3],y+dy[3]);
}
int main(){
    int i,j;
    while(cin>>w>>h){
        sum=0;
        int x,y;
        if(w==0&&h==0) break;
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                cin>>a[i][j];
                if(a[i][j]=='@'){
                    x=i;
                    y=j;
                }
            }
        }
        dfs(x,y);
        cout<<sum<<endl;
    }
}



#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int p[N],cnt[N];
int find(int x){
    if(p[x]!=x){
        p[x]=find(p[x]);
    }
    return p[x];
}
int main(){
    int n,m,i;
    cin>>n>>m;
    for(i=0;i<n;i++){
        p[i]=i;
        cnt[i]=1;
    }
    while(m--){
        int a,b;
        string op;
        cin>>op;
        if(op=="C"){
            cin>>a>>b;
            a=find(a),b=find(b);
            if(a!=b){
                p[a]=b;
                cnt[b]+=cnt[a];
            }
        }
        else if(op=="Q1"){
            cin>>a>>b;
            if(find(a)==find(b)){
                cout<<"Yes"<<endl;
            }
            else{
                cout<<"No"<<endl;
            }
        }
        else if(op=="Q2"){
            cin>>a;
            cout<<cnt[find(a)]<<endl;
        }
    }
}


活动打卡代码 AcWing 756. 蛇形矩阵

#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int main(){
    int n,m,i,j,d=1,x=1,y=1;
    cin>>n>>m;
    for(i=0;i<m+2;i++){
        a[n+1][i]=1;
        a[0][i]=1;
    }
    for(i=0;i<n+2;i++){
        a[i][m+1]=1;
        a[i][0]=1;
    }
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    for(i=1;i<=n*m;i++){
        a[x][y]=i;
        x+=dx[d];
        y+=dy[d];
        if(a[x+dx[d]][y+dy[d]]!=0){
            d=(d+1)%4;
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}


活动打卡代码 AcWing 836. 合并集合

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int p[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main(){
    int n,m,i;
    cin>>n>>m;
    for(i=0;i<n;i++) p[i]=i;
    while(m--){
        int a,b;
        char op;
        cin>>op>>a>>b;
        if(op=='M'){
            p[find(a)]=find(b);
        }
        else{
            if(find(a)==find(b)){
                cout<<"Yes"<<endl;
            }
            else{
                cout<<"No"<<endl;
            }
        }
    }
}