头像

GREENOFYU




离线:5小时前


活动打卡代码 AcWing 1208. 翻硬币

#include<iostream>
using namespace std;
void change(string& s,int i){
    if(s[i]=='*'){
        s[i]='o';
    }else if(s[i]=='o'){
        s[i]='*';
    }
}
int main(void){
    string a,b;
    cin>>a>>b;
    int res=0;
    for(int i=0;i<a.size()-1;i++){
        if(a[i]!=b[i]){
            change(a,i);
            change(a,i+1);
            res++;
        }
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 429. 奖学金

#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
struct node{
    int a,b,c;
    int sum;
    int id;
};
node s[N];
bool cmp(node a,node b){
    if(a.sum==b.sum&&a.a==b.a){
        return a.id<b.id;
    }
    if(a.sum==b.sum){
        return a.a>b.a;
    }
    return a.sum>b.sum;
}
int main(void){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].a>>s[i].b>>s[i].c;
        s[i].sum=s[i].a+s[i].b+s[i].c;
        s[i].id=i;
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=5;i++){
        cout<<s[i].id<<" "<<s[i].sum<<endl;
    }
    return 0;
}


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

模拟

#include<iostream>
using namespace std;
const int N=10010;
bool a[N];
int main(void){
    int l,m;
    cin>>l>>m;
    for(int i=0;i<m;i++){
        int left,right;
        cin>>left>>right;
        for(int j=left;j<=right;j++){
            a[j]=true;
        }
    }
    int res=0;
    for(int i=0;i<=l;i++){
        if(!a[i]){
            res++;
        }
    }
    cout<<res;
    return 0;
}

差分

#include<iostream>
using namespace std;
const int N=10010;
int a[N];
int main(void){
    int l,m;
    cin>>l>>m;
    for(int i=0;i<m;i++){
        int left,right;
        cin>>left>>right;
        a[left]+=1;
        a[right+1]-=1;
    }
    int res=a[0]==0?1:0;
    for(int i=1;i<=l;i++){
        a[i]+=a[i-1];
        if(a[i]==0)
            res++;
    }
    cout<<res;
    return 0;
}

区间合并

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
PII a[110];
int main(void){
    int l,m;
    cin>>l>>m;
    for(int i=0;i<m;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a,a+m);
    int ed=0;
    int res=0;
    for(int i=0;i<m;i++){
        int left=a[i].first,right=a[i].second;
        if(left>ed){
            res+=left-ed;
        }
        ed=max(ed,right+1);
    }
    if(ed<l){
        res+=l-ed+1;
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

#include<iostream>
using namespace std;
const int N=110;
int v[N][N],w[N][N],s[N];
int f[N][N];
int main(void){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            for(int k=1;k<=s[i];k++){
                if(j>=v[i][k])
                    f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<f[n][m];
    return 0;
}


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

#include<iostream>
#include<climits>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
PII a[N];
int n,k;
bool check(int x){
    int res=0;
    for(int i=0;i<n;i++){
        res+=(max(a[i].first,a[i].second)/x)*(min(a[i].first,a[i].second)/x);
    }
    return res>=k;
}
int main(void){
    cin>>n>>k;
    int ma=INT_MIN;
    for(int i=0;i<n;i++){
        cin>>a[i].first>>a[i].second;
        ma=max(ma,a[i].first);
        ma=max(ma,a[i].second);
    }
    int l=0,r=ma;
    while(l<r){
        int mid=l+r+1>>1;
        if(!check(mid)){
            r=mid-1;
        }else{
            l=mid;
        }
    }
    cout<<l<<endl;
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

#include<iostream>
using namespace std;
const int N=12000,M=2100;
int v[N],w[N],cnt;
int f[M];
int main(void){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s){
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k<<=1;
        }
        if(s){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}


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

#include<iostream>
#include<climits>
#include<cmath>
#include<cstdio>
using namespace std;
const int N=100010;
double a[N];
const double eps=1e-6;
int n,m;
bool check(double x){
    int res=0;
    for(int i=0;i<n;i++){
        res+=int(a[i]/x);
    }
    return res>=m;
}
int main(void){
    cin>>n>>m;
    double ma=-999999;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ma=max(a[i],ma);
    }
    double l=0,r=ma;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)){
            l=mid;
        }else{
            r=mid;
        }
    }
    printf("%.2lf",l);
    return 0;
}



#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
    int t;
    cin>>t;
    while(t--){
        string line_a,line_b;
        int a,b;
        cin>>a>>b>>line_a;
        vector<int> num;
        for(int i=0;i<line_a.size();i++){
            if(line_a[i]>='0'&&line_a[i]<='9') num.push_back(line_a[i]-'0');
            if(line_a[i]>='A'&&line_a[i]<='Z') num.push_back(line_a[i]-'A'+10);
            if(line_a[i]>='a'&&line_a[i]<='z') num.push_back(line_a[i]-'a'+36);
        }
        reverse(num.begin(),num.end());

        vector<int> res;
        while(num.size()){
            int r=0;
            for(int i=num.size()-1;i>=0;i--){
                num[i]+=r*a;
                r=num[i]%b;
                num[i]/=b;
            }
            res.push_back(r);
            while(num.size()&&num.back()==0) num.pop_back();
        }

        reverse(res.begin(),res.end());
        for(auto x:res){
            if(x>=0&&x<=9) line_b+=char(x+'0');
            if(x>=10&&x<=35) line_b+=char(x+'A'-10);
            if(x>=36&&x<=61) line_b+=char(x+'a'-36);
        }
        cout<<a<<" "<<line_a<<endl;
        cout<<b<<" "<<line_b<<endl;
        cout<<endl;
    }
    return 0;
}



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

my version

#include<iostream>
#include<vector>
using namespace std;
bool is_ok(vector<int>& v){
    int s=v.size();
    int i=0,j=s-1;
    while(i<j){
        if(v[i]!=v[j]){
            return 0;
        }
        i++,j--;
    }
    return 1;
}
void out(vector<int>& v){
    for(int i=v.size()-1;i>=0;i--){
        if(v[i]>=10){
            cout<<char(v[i]-10+'A');
        }else{
            cout<<v[i];
        }
    }
}
int main(void){
    int b;
    cin>>b;
    for(int i=1;i<=300;i++){
        vector<int> q,v;
        int t1=i,t2=i*i;
        while(t1){
            q.push_back(t1%b);
            t1/=b;
        }
        while(t2){
            v.push_back(t2%b);
            t2/=b;
        }
        if(is_ok(v)){
            out(q);
            cout<<" ";
            out(v);
            cout<<endl;
        }
    }
    return 0;
}

standard version

#include<iostream>
#include<algorithm>
using namespace std;
char get(int a){
    if(a<10) return a+'0';
    return a-10+'A';
}
string base(int n,int b){
    string res="";
    while(n){
        res+=get(n%b);
        n/=b;
    }
    reverse(res.begin(),res.end());
    return res;
}
bool check(string s){
    int i=0,j=s.size()-1;
    while(i<j){
        if(s[i]!=s[j])
            return 0;
        i++,j--;
    }
    return 1;
}
int main(void){
    int b;
    cin>>b;
    for(int i=1;i<=300;i++){
        string num=base(i*i,b);
        if(check(num)){
            cout<<base(i,b)<<" "<<num<<endl;
        }
    }
    return 0;
}


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

bfs

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;

int n,m;
const int N=30;
char a[N][N];
bool vis[N][N];

int bfs(int sx,int sy){
    memset(vis,0,sizeof(vis));
    int res=0;
    queue<PII> q;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    q.push({sx,sy});
    vis[sx][sy]=true;
    while(q.size()){
        auto t=q.front();
        q.pop();
        res++;
        int x=t.first,y=t.second;
        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<0||tx>n||ty<0||ty>m||a[tx][ty]!='.'||vis[tx][ty]) continue;
            vis[tx][ty]=1;
            q.push({tx,ty});
        }
    }
    return res;
}
int main(void)
{
    while(cin>>m>>n,m||n){
        int x,y;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>a[i][j];
                if(a[i][j]=='@'){
                    x=i,y=j;
                }
            }
        }
        cout<<bfs(x,y)<<endl;
    }
    return 0;
}

dfs

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;

int n,m;
const int N=30;
char a[N][N];
bool vis[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int dfs(int x,int y){
    int res=1;
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]=='.'&&!vis[tx][ty]){
            res+=dfs(tx,ty);
        }
    }
    return res;
}
int main(void)
{
    while(cin>>m>>n,m||n){
        memset(vis,0,sizeof(vis));
        int x,y;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>a[i][j];
                if(a[i][j]=='@'){
                    x=i,y=j;
                }
            }
        }
        cout<<dfs(x,y)<<endl;
    }
    return 0;
}