头像

Mr.Lonely




离线:1天前


活动打卡代码 AcWing 1350. 密码运算

#include<iostream>
#include<algorithm>
using namespace std;
const int N=10;
int a[N];
int n;



int get(int n)//求每一个数有多少位
{
    int cnt=0;
    while(n)
    {
        n/=10;
        cnt++;
    }
    return cnt;
}

bool has_num(int num)//判断该数的每一位是不是都在数组中
{
    int cnt=0;
    int c=num;
    while(num)
    {
        int i=num%10;
        for(int j=0;j<n;j++)
        {
            if(i==a[j])
                cnt++;
        }
        num/=10;
    }
    if(cnt==get(c)) return true;
    return false;
}

int main()
{

    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);//先排序,得到最小值和最大值
    int res=0;
    int min1=111*a[0],max1=111*a[n-1];//枚举第一个数
    int min2=11*a[0],max2=11*a[n-1];//枚举第二个数
    for(int i=min1;i<=max1;i++)
        for(int j=min2;j<=max2;j++)
        {
            int second=j%10,first=j/10;
            int a=i*second,b=i*first;//a是第一个乘积,b是第一个乘积
            if((get(a)==3) && (get(b)==3) && (get(a+10*b)==4) && has_num(a) && has_num(b) && has_num(a+10*b) && has_num(i) && has_num(j))
                res++;//判断数的长度以及数是否符合
        }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1349. 修理牛棚

#include<iostream>
#include<algorithm>
using namespace std;
const int N=210;
int a[N],b[N];
int m,s,c;
int main()
{
    cin>>m>>s>>c;
    for(int i=0;i<c;i++)
        cin>>a[i];
    sort(a,a+c);//将牛按从左到右的顺序排好
    for(int i=1;i<c;i++)//求出每个牛之间的距离
        b[i]=a[i]-a[i-1]-1;
    int res=a[c-1]-a[0]+1;//刚开始用一整块板子盖住所有的牛
    sort(b+1,b+c,greater<int>());//将间隙从大到小排序
    for(int i=1;i<=m-1&&i<c;i++)//运用贪心的思想,减去最大的前m-1个间隙,这样总的板长就是最短的
    {
        res-=b[i];
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1348. 搭配牛奶

贪心思想,先选择价格便宜的(此题和背包问题不一样,因为每种物品可以细分为单个)

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int M=5010;
PII a[M];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>a[i].first>>a[i].second;
    sort(a,a+m);
    int res=0;
    for(int i=0;(i<m)&&n;i++)
    {
        int t=min(n,a[i].second);
        n-=t;
        res+=t*a[i].first;
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1347. 双重回文

#include<iostream>
#include<algorithm>
using namespace std;

string base(int n,int b)//将十进制数字转化为b进制
{
    string res;
    while(n)
    {
        res+=n%b+'0';
        n/=b;
    }
    reverse(res.begin(),res.end());
    return res;
}

bool check(string num)//判断是否为回文数
{
    for(int i=0,j=num.size()-1;i<j;i++,j--)
        if(num[i]!=num[j]) return false;
    return true;
}

int main()
{
    int n,s;
    cin>>n>>s;
    for(int i=s+1,j=0;j<n;i++)//从s+1开始遍历所有的数
    {
        int cnt=0;
        for(int b=2;b<=10&&cnt<2 ;b++)//遍历所有进制
        {
            string num=base(i,b);
            if(check(num)) cnt++;
        }
        if(cnt==2)
        {
            cout<<i<<endl;
            j++;
        }
    }
}



活动打卡代码 AcWing 1345. 序号命名

#include<iostream>
using namespace std;

int get(char c)
{
    if(c<='O') return (c-'A')/3+2;
    if(c<='S') return 7;
    if(c<='V') return 8;
    return 9;
}

int main()
{
    string num,s;
    cin>>num;
    bool has=false;
    while(cin>>s)
    {
        string ans;
        for(char c:s) ans+=get(c)+'0';
        if(ans==num)
        {
            has=true;
            cout<<s<<endl;
        }
    }
    if(!has) cout<<"NONE"<<endl;
    return 0;
}


活动打卡代码 AcWing 1342. 断开的项链

将链拉开后复制一段放在后面,遍历每一个字符时,如果是w的话可以直接通过,如果是其他字符,判断当前的颜色种类是多少,颜色的状态可以用两位的二进制数来表示

#include<iostream>
using namespace std;
const int N=710;
int n;
char s[N];

int get(char h)
{
    if(h=='b') return 2;
    return 1;
}

int main()
{
    cin>>n>>s;
    for(int i=0;i<n;i++)
        s[i+n]=s[i];
    int res=0;
    for(int i=0;i<n;i++)
    {
        int l=i,r=i+n-1;
        int cnt=0,left=0,right=0;
        while(l<=r &&(s[l]=='w'||(left|get(s[l]))!=3))
        {
            if(s[l]!='w') left|=get(s[l]);
            cnt++;
            l++;
        }
        while(l<=r &&(s[r]=='w'||(right|get(s[r]))!=3))
        {
            if(s[r]!='w') right|=get(s[r]);
            cnt++;
            r--;
        }
        res=max(res,cnt);
    }
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1344. 转换

#include<iostream>
#include<vector>
using namespace std;
typedef vector<string> VS;
int n;

void mirror(VS &a)
{
    for(int i=0;i<n;i++)
        for(int j=0,k=n-1;j<k;j++,k--)
            swap(a[i][j],a[i][k]);
}

void rotate(VS &a)//顺时针旋转90度等价于关于左上右下的对角线对称然后水平镜面对称
{
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            swap(a[i][j],a[j][i]);
    mirror(a);
}

int check(VS &a,VS &b)
{
    auto c=a;
    for(int i=1;i<=3;i++)
    {
        rotate(c);
        if(c==b) return i;
    }
    c=a;
    mirror(c);
    if(c==b) return 4;
    for(int i=1;i<=3;i++)
    {
        rotate(c);
        if(c==b) return 5;
    }
    if(a==b) return 6;
    return 7;
}

int main()
{
    cin>>n;
    string s;
    VS a,b;
    for(int i=0;i<n;i++) cin>>s,a.push_back(s);
    for(int i=0;i<n;i++) cin>>s,b.push_back(s);
    cout<<check(a,b)<<endl;
    return 0;
}


活动打卡代码 AcWing 1343. 挤牛奶

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=5010;
PII a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        a[i]={l,r};
    }
    sort(a,a+n);
    int ans1=0,ans2=0;
    int start=a[0].first,end=a[0].second;
    for(int i=1;i<=n;i++)
    {
        if(a[i].first<=end)
        {
            end=max(end,a[i].second);
        }
        else
        {
            ans1=max(ans1,end-start);
            ans2=max(ans2,a[i].first-end);
            start=a[i].first;
            end=a[i].second;
        }
    }
    ans1=max(ans1,end-start);
    cout<<ans1<<' '<<ans2<<endl;
    return 0;
}


活动打卡代码 AcWing 862. 三元组排序

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=10010;
int main()
{

    struct Rec
    {
        int x;
        float y;
        string z;
        bool operator<(const Rec &w)const
        {
            return x<w.x;
        }
    };
    int n;
    cin>>n;
    vector<Rec> r(n);
    for(int i=0;i<n;i++)
    {
        int x;
        float y;
        string z;
        cin>>x>>y>>z;
        r[i]={x,y,z};
    }
    sort(r.begin(),r.end());
    for(int i=0;i<n;i++)
        printf("%d %.2f %s\n",r[i].x,r[i].y,r[i].z.c_str());
    return 0;
}



class Solution {
public:
    int NumberOf1(int n) {
        int res=0;
        while(n)
        {
            n-=n&-n;
            res++;
        }
        return res;
    }
};