博客

第二题：明码

#include<iostream>
#include<bitset>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        bitset<8> t;//t为二进制8位    biset<length> t
        t = n;//将n赋给t，即将n转化为8位二进制 
        string s;
        s=t.to_string();
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='0') cout<<" ";
            else cout<<"*";
        }
        t = m;//将m赋给t，即将n转化为8位二进制 
        s=t.to_string();
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='0') cout<<" ";
            else cout<<"*";
        }
        cout<<endl;
    }
    return 0;
}

第三题：乘积尾零

#include<bits/stdc++.h>
using namespace std;
int sel5(int n)
{
    int ans=0;
    while(n)
    {
        if(n%5!=0) break;
        if(n%5==0) ans++;
        n/=5;
    }
    return ans;
}
int sel2(int n)
{
    int ans=0;
    while(n)
    {
        if(n%2!=0) break;
        if(n%2==0) ans++;
        n/=2;
    }
    return ans;
}
int num[100] = { 5650,4542,3554,473,946,4114,3871,9073,90,4329
        ,2758,7949,6113,5659,5245,7432,3051,4434,6704,3594
        ,9937,1173,6866,3397,4759,7557,3070,2287,1453,9899
        ,1486,5722,3135,1170,4014,5510,5120,729,2880,9019
        ,2049,698,4582,4346,4427,646,9742,7340,1230,7683
        ,5693,7015,6887,7381,4172,4341,2909,2027,7355,5649
        ,6701,6645,1671,5978,2704,9926,295,3125,3878,6785
        ,2066,4247,4800,1578,6652,4616,1113,6205,3264,2915
        ,3966,5291,2904,1285,2193,1428,2265,8730,9436,7074
        ,689,5510,8243,6114,337,4096,8199,7313,3685,211};
int main()
{
    int ans=0;
    int ans1=0;
    for(int i=0;i<100;i++)
    {
        ans+=sel5(num[i]);
        ans1+=sel2(num[i]);
    }
    cout<<min(ans1,ans);
    return 0;
}

第四题：测试次数

#include<bits/stdc++.h>
using namespace std;
int dp[3][1001];
int main()
{
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            dp[i][j]=j;
        }
    }
    for(int j=1;j<=1000;j++)
    {
        for(int i=2;i<=3;i++)
        {
            for(int k=1;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],max(dp[i-1][k-1]+1,dp[i][j-k]+1));
            }
        }
    }
    cout<<dp[3][1000]<<endl;
    return 0;
}

第五题：快速排序

#include<bits/stdc++.h>
using namespace std;
int quick_select(int a[], int l, int r, int k) {
    int p = rand() % (r - l + 1) + l;
    int x = a[p];
    {int t = a[p]; a[p] = a[r]; a[r] = t;}
    int i = l, j = r;
    while(i < j) {
        while(i < j && a[i] < x) i++;//从左开始找第一个大于等于x的数 
        if(i < j) {
            a[j] = a[i]; 
            j--;
        }
        while(i < j && a[j] > x) j--;
        if(i < j) {
            a[i] = a[j];
            i++;
        }
    }
    a[i] = x;
    p = i;
    if(i - l + 1 == k) return a[i];
    if(i - l + 1 < k) return quick_select(a, i+1, r, k-(i-l+1) ); //填空
    else return quick_select(a, l, i - 1, k);
}
    
int main()
{
    int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
    printf("%d\n", quick_select(a, 0, 14,5));
    return 0;
}

第六题：递增三元组

解法一：双指针

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int b[100001];
int c[100001];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i]; 
    for(int i=0;i<n;i++) cin>>c[i];
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    int l=0,r=0;
    long long int res=0;
    for(int i=0;i<n;i++)
    {
        while(l<n&&a[l]<b[i]) l++;
        while(r<n&&b[i]>=c[r]) r++;
        res+=(long long)l*(n-r);
    }
    cout<<res;
    return 0;
}

解法二：二分

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int b[100001];
int c[100001];
int erfena(int l,int r,int i)
{
    while(l<r)
    {
        int mid=(l+r)/2;
        if(a[mid]<i) l=mid+1;
        else r=mid;
    }
    return l;
} 
int erfenc(int l,int r,int i)
{
    while(l<r)
    {
        int mid=(l+r)/2;    
        if(c[mid]<=i) l=mid+1;
        else r=mid;    
    }
    return l;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    int x,y;
    long long int ans=0;
    for(int i=0;i<n;i++)
    {
        x=erfena(0,n,b[i]);
        y=erfenc(0,n,b[i]);
        ans+=(long long)x*(n-y);
    }
    cout<<ans<<endl;
    return 0;
}

解法三：前缀和

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int aa[N],cc[N],s[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i],a[i]++;
    for(int i=0;i<n;i++) cin>>b[i],b[i]++;
    for(int i=0;i<n;i++) cin>>c[i],c[i]++;
    
    for(int i=0;i<n;i++) s[a[i]]++;
    for(int i=1;i<N;i++) s[i]+=s[i-1];
    for(int i=0;i<n;i++) aa[i]=s[b[i]-1];
    memset(s,0,sizeof(s));
    for(int i=0;i<n;i++) s[c[i]]++;
    for(int i=1;i<N;i++) s[i]+=s[i-1];
    for(int i=0;i<n;i++) cc[i]=s[N-1]-s[b[i]];
    long long ans=0;
    for(int i=0;i<n;i++) ans+=(long long)aa[i]*cc[i];
    cout<<ans<<endl;
    return 0;
}

第八题：日志统计

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int num[N];    //num[i]：记录id=i的帖子的赞的数量
int flag[N];   //flag[i]：id=i的贴子曾是热帖
struct post{
    int id;
    int ts;
}p[N];                  //记录帖子
int cmp(post x,post y){ return x.ts < y.ts;  } //按时间从小到大排序
int main(){
    int n,d,k;
    cin>>n>>d>>k;
    for(int i=0;i<n;i++)
        cin>>p[i].ts>>p[i].id;
    sort(p,p+n,cmp);    //按时间从小到大排序
    for(int i=0,j=0;i<n;i++){
        num[p[i].id]++;
        while(p[i].ts-p[j].ts >= d){ 
            num[p[j].id]--; //随着时间流逝，d之前的每个贴的次数都减1
            j++;
        }
        if(num[p[i].id] >= k)   //在区间[i-d,i)上达到k个赞
            flag[p[i].id]=1;
    }
    for(int i=0;i<N;i++)
        if(flag[i]==1)
           cout<<i<<endl;
    return 0;
}

第九题：全球变暖

解法一：dfs

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int vis[N][N];
string mp[N];
int d[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
int flag;
void dfs(int x,int y)
{
    vis[x][y]=1;
    if(mp[x+1][y]=='#'&&mp[x-1][y]=='#'&&mp[x][y+1]=='#'&&mp[x][y-1]=='#') flag=1;
    for(int i=0;i<4;i++)
    {
        int nx=x+d[i][0];
        int ny=y+d[i][1];
        if(vis[nx][ny]==0&&mp[nx][ny]=='#') dfs(nx,ny);
    }
}
int main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<n;i++) cin>>mp[i];
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(vis[i][j]==0&&mp[i][j]=='#')
            {
                flag=0;
                dfs(i,j);
                if(flag==0) ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

解法二：bfs

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
string mp[N];
int vis[N][N];
int flag;
struct node{
    int x,y;
};
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(int x,int y)
{
    node start;
    queue<node>q;
    start.x=x;
    start.y=y;
    q.push(start);
    vis[x][y]=1;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(mp[now.x+1][now.y]=='#'&&mp[now.x-1][now.y]=='#'&&mp[now.x][now.y+1]=='#'&&mp[now.x][now.y-1]=='#') flag=1;
        for(int i=0;i<4;i++)
        {
            int nx=now.x+d[i][0];
            int ny=now.y+d[i][1];
            if(mp[nx][ny]=='#'&&vis[nx][ny]==0)
            {
                node next;
                next.x=nx;
                next.y=ny;
                vis[nx][ny]=1;
                q.push(next);
            }
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>mp[i];
    int ans=0;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(vis[i][j]==0&&mp[i][j]=='#')
            {
                flag=0;
                bfs(i,j);
                if(flag==0) ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}