头像

_LRJ_

中国矿业大学(北京)




离线:10小时前


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

_LRJ_
1天前
#include<bits/stdc++.h>

using namespace std;
int L,M;
int a[100010];

int main(){
    cin>>L>>M;
    for(int i=0;i<=L;i++) a[i]=1;
    while(M--){
        int l,r;
        cin>>l>>r;
        for(int i=l;i<=r;++i) a[i]=0;
    }
    int res=0;
    for(int i=0;i<=L;++i) res+=a[i];
    cout<<res;
    return 0;
}



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

_LRJ_
4天前
#include<bits/stdc++.h>

using namespace std;
int n,k;
int h[100010],w[100010];
bool check(int mid){
    int res=0;
    for(int i=1;i<=n;++i){
        res+= (h[i]/mid)*(w[i]/mid);
    }
    return res>=k;
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>h[i]>>w[i];
    int l=0,r=1e9;
    while(l<r){
        int mid=1+l+r>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}



活动打卡代码 AcWing 1476. 数叶子结点

_LRJ_
5天前
#include<bits/stdc++.h>

using namespace std;
int n,m;
int ans[110];
int cc=0;
vector<int> e[1110];

void dfs(int u,int ceng){
    bool is_leaf=true;
    cc=max(cc,ceng);

    for(auto x:e[u]){
        is_leaf=false;
        dfs(x,ceng+1);
    }
    if(is_leaf) ans[ceng]++;
}

int main(){
    cin>>n>>m;
    while(m--){
        int c,now;
        cin>>now>>c;
        while(c--){
            int id;
            scanf("%2d",&id);
            e[now].push_back(id);

        }
    }

    dfs(1,1);
    for(int i=1;i<=cc;++i) cout<<ans[i]<<' ';
    return 0;
}


活动打卡代码 AcWing 2875. 超级胶水

_LRJ_
5天前
#include<bits/stdc++.h>

using namespace std;

int n;
int x;
long long res=0;
int main(){
    cin>>n;
    long long pre;
    cin>>pre;
    for(int i=2;i<=n;++i){
        int now;
        cin>>now;
        res+=pre*now;
        pre+=now;
    }
    cout<<res;
    return 0;
}



_LRJ_
5天前

It can be proved that all the costs of different ways to merge n piles of stones are equal.So we just need to simply do the procession in O(N)

#include<bits/stdc++.h>

using namespace std;

int n;
int x;
long long res=0;
int main(){
    cin>>n;
    long long pre;
    cin>>pre;
    for(int i=2;i<=n;++i){
        int now;
        cin>>now;
        res+=pre*now;
        pre+=now;
    }
    cout<<res;
    return 0;
}


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

_LRJ_
5天前
#include<bits/stdc++.h>
using namespace std;

int n,m,h[100010];
bool check(double mid)
{
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        sum=1ll*sum+(long long)(h[i]/mid);
        if(sum>=m) return true;
    }
    return sum>=m;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",h+i);
    double l=0,r=1e9;
    for(int i=0;i<200;i++)
    {
        double mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%.2lf\n",l);
    return 0;
}



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

_LRJ_
6天前
#include<bits/stdc++.h>

using namespace std;
int B;

bool check(int _,int x){
    string s;
    while(x){
        int now=x%B;
        if(now<10)
        s.push_back('0'+now);
        else s.push_back('A'+now-10);
        x/=B;
    }
    int  len=s.size();

    for(int i=0;i<len;++i) if(s[i]!=s[len-1-i]) return false;
    return true;
}

string  get(int x){
    string s;
    while(x){
        int now=x%B;
        if(now<10)
        s.push_back('0'+now);
        else s.push_back('A'+now-10);
        x/=B;
    }

    reverse(s.begin() ,s.end());
    return s;
}

void check(int x){
    int now = x*x;
    if(check(x,now)) cout<<get(x)<<" "<<get(now)<<endl;
}

int main(){
    cin>>B;
    for(int i=1;i<=300;++i)check(i);

    return 0;
}



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

_LRJ_
7天前
#include<bits/stdc++.h>

using namespace std;
char g[30][30];
int res=0;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
bool st[40][40];int n,m;
void dfs(int x,int y){
    res++;
    st[x][y]=true;
    for(int i=0;i<4;++i){
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>n||a<1||b>m||b<1) continue;
        if(st[a][b]) continue;
        if(g[a][b]=='.')
        dfs(a,b);
    }
}
int main(){


    while(cin>>m>>n,n||m){
        memset(st,false,sizeof st);
        // memset(g,0,sizeof g);
        res=0;
       // if(n==0&&m==0) break;
         int x,y;
    for(int i=1;i<=n;++i){
        cin>>g[i]+1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(g[i][j]=='@') x=i,y=j;
        }
    }
    dfs(x,y);
    cout<<res<<endl;

    }

    return 0;
}


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

_LRJ_
8天前
#include<bits/stdc++.h>

using namespace std;
int n,m;
int g[110][110];
bool st[110][110];

int main(){
    int idx=1;
    cin>>n>>m;
    int i=1,j=1;
    while(idx<=n*m){
        while(j<=m&&!st[i][j]) st[i][j]=true,g[i][j]=idx++,++j;
        --j;++i;
        while(i<=n&&!st[i][j]) st[i][j]=true,g[i][j]=idx++,++i;
        --i;--j;
        while(j>=1&&!st[i][j]) st[i][j]=true,g[i][j]=idx++,--j;
        ++j;--i;
        while(i>=1&&!st[i][j]) st[i][j]=true,g[i][j]=idx++,--i;
        ++i;++j;
       // ++idx;
    }

    for(int  i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cout<<g[i][j]<<' ';
        }
        cout<<endl;
    }

    return 0;
}



活动打卡代码 AcWing 3167. 星星还是树

_LRJ_
9天前
#include<bits/stdc++.h>

using namespace std;
typedef pair<double ,double> pdd;
int n;
double ans;
pdd p[110];

double get_dist(pdd a,pdd b){
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx*dx+dy*dy);
}

double calc(pdd now){
    double res=0;
    for(int i=0;i<n;++i){
        res+=get_dist(now,p[i]);
    }

    ans=min(res,ans);
    return res;
}

double rand(double l,double r){
    return 1.0*rand()/RAND_MAX*(r-l)+l;
}

void simulate_anneal(){
    // double T=1e4;
    pdd now = {rand(0,10000),rand(0,10000)};

    for(double t=1e4;t>1e-4;t*=0.99){
        pdd np = {rand(now.first-t,now.first+t) ,rand(now.second-t,now.second +t)};
        double dt = calc(np)-calc(now);
        if(exp(-dt/t)>rand(0,1)) now=np;
    }

}
int main(){
    ans=2e9;
    cin>> n;
    for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second;
    for(int i=1;i<=100;++i) simulate_anneal();

    cout<<round(ans)<<endl;
    return 0;
}