丑数：把只包含质因子2、3和5的数称作丑数

例如6、8都是丑数，但14不是，因为它包含质因子7

丑数
判断丑数：

#include<bits/stdc++.h>
using namespace std;
int a[5]={2,3,5};//打表
int main()
{
    int m,n;
    cin>>n;
    while(n--)
    {
        cin>>m;
        for(int i=0;i<3;++i)
            while(m%a[i]==0)
                m/=a[i]; 
        if(m==1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

丑(萌)数约数的个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[4]={2,3,5};
int b[4]; 
int main()
{
    ll n;
    while(cin>>n)
    {
        if(n==0)break;
        ll cnt=1;
        for(int i=0;i<3;++i)
        {
            b[i]=0;
            while(!(n%a[i]))
            {
                n/=a[i];
                b[i]++;
            }
            cnt*=b[i]+1;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

模板参照 (作者：Ncik)：输出第几个丑数是几

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n);
        dp[0] = 1;
        int l2 = 0, l3 = 0, l5 = 0;
        for(int i = 1; i < n; ++i) {
            // 生成第i+1小的丑数
            dp[i] = min(min(dp[l2] * 2, dp[l3] * 3), dp[l5] * 5);
            if (dp[i] == dp[l2] * 2) {
                ++l2;
            }
            if (dp[i] == dp[l3] * 3) {
                ++l3;
            } 
            if (dp[i] == dp[l5] * 5) {
                ++l5;
            }
        }
        return dp[n - 1];
    }
};

acwing第$6$次周赛

3734. 求和

/*
4 7 44 47..
题意：把给出的l,r划分在包含4和7的序列中
题解：dfs+取交集累加每段区间的和

可以用dfs求出在[1,1e9]所有整数
注意10个4爆int，要开long long
100 = 2^2(4个)
1000 = 2^3(8个)
1e9 = 2000.?
共2000多个区间

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> s;

void dfs(int u,ll x){
    s.push_back(x);
    if(u==10) return ;
    dfs(u+1,x*10+4);
    dfs(u+1,x*10+7);
}
int main(){
    dfs(0,0);
    sort(s.begin(),s.end());//对区间进行排序

    ll l,r,res = 0;
    cin >> l >>r;
    for(int i=1;i<s.size();i++){
        ll a = s[i-1]+1,b =s[i];
        res += s[i] * max(0ll, (min(r, b) - max(l, a) + 1));//取交集
    }
    cout<<res<<endl;


    return 0;
}

acwing第$2$次周赛

3626. 三元一次方程

/*
数据范围: n<=1000;
可以考虑o(n^2) /
*/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;

void solve(){
    for(int i=0;i<=1000;i++){
        for(int j =0;j<1000;j++){
            int x = n-3*i-5*j;
            int y =x%7;
            if(x>=0 && y==0) {//!
                cout<<i<<" "<<j<<" "<<x/7<<endl;
                return ;//!
            }
        }
    }
    cout<<"-1"<<endl;
}

int main()
{
    int t;cin >> t;
    while(t--){
        cin >> n;
        solve();
    }

    return 0;
}

3627. 最大差值

/*
题意：对一个序列进行增加减少操作，求序列最大差值
思路：每次操作可以看作是将两杯水合并
k次操作，对k+1杯水进行操作，不断倒水问题

*/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int a[N];
int main()
{
    ll t,n,k,sum;
    cin >> t;
    while(t--){
        cin >> n >>k;
        sum = 0;
        for(int i=0;i<n;i++) cin >>a[i];
        sort(a,a+n,greater<int>());//从大到小

        for(int i=0;i<k+1;i++){
            sum+=a[i];
        }
        cout<<sum<<endl;
    }

    return 0;
}

acwing 第$4$次周赛

3694. A还是B

题意：比较字符串中A 和 B的个数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int sum1=0,sum2=0;
    int n;
    string s;cin >>n;
    getchar();
    cin >> s;
    for(auto c:s){
        if(c=='A') sum1++;
        else if(c=='B') sum2++; 
    }
    if(sum1>sum2) cout<<"A"<<endl;
    else if(sum1<sum2) cout<<"B"<<endl; 
    else cout<<"T"<<endl; 
}

3695. 扩充序列

/*
题意：序列 = 原序列+ （大于等于原序列的数字a）+原序列
思路：找规律
如果是 k 是奇数，恒为 1；
如果是 k 是偶数，再讨论

*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main()
{
    LL n ,k;
    cin >> n>> k;
    LL cnt = 1;
    while(!(k&1)) {
        ++cnt;
        k>>=1;
    }
    cout<<cnt<<endl;
    return 0;
}

acwing第$7$次周赛

3758. 距离零点的时刻

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t,h,m;cin >> t;
    while(t--){
        cin >> h>> m;
        cout<<1440-60*h-m<<endl;//用总的减现在的

    }

    return 0;
}

3759. 第k个字符串

/*
题意：按字典序输出第k个含有a,b的字符串 
思路：本题 n[3,1e5] 该数据范围考虑的算法为 O(n)
 (一共就两个b)可以枚举b
 看 k 到底属于哪个范围 

*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int t;cin >> t;
    while(t--){
        int n,k;
        cin >> n >> k;
        for(int i= n-1;i;i--){//固定第一个b的位置 
            if(k >n-i) k-=n-i;// n-i是第二个b的情况 
            else {
                string s(n,'a');
                s[i-1] = s[n-k] ='b';
                cout<<s<<endl;
                break;
            }
        }
    }
    return 0;
} 

acwing第$5$次周赛

3726. 调整数组

/*
题意：对序列进行多次操作判断最后序列每个数是否相等
思路：判断偶数和奇数的个数，加2是不会影响奇偶性的

*/

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

int main()
{
    int t,n,sum1,sum2,a;cin>> t;
    while(t--){
        sum1 =0,sum2=0;
        cin >> n;
        for(int i =0;i<n;i++){
            cin >> a;
            if(a&1) sum1++;
            else sum2++;
        }
        if(sum1==0 || sum2 ==0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

    return 0;
}

3727. 乘方相加

/*
题意：判断a 数组的元素能否由v数组操作得到 
思路：如果将所有的 vi 用 k进制表示
     则第 i 次操作就相当于是在 vi 的第 i 位上加 1
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100;
int s[N];
int main()
{
    ll t,n,k,x;
    cin >> t;
    while(t--){
        cin >> n >>k;
        memset(s,0,sizeof(s));
        while(n--){
            cin >>x;
            for(int j = 0;x;j++){
                s[j] += x%k;
                x/=k;
            }
        }
         int flag = 0;
        for(int i =0 ;i<N;i++){
            if(s[i]>1) flag=1;
            }
        if(flag) puts("NO");
         else puts("YES");
    }
    return 0;
}

acwing第$8$次周赛

3771. 选取石子

/*
题意：x - y = ax - ay;
思路：ax -x = ay - y;
利用哈希表来存属性ai-i相同的key值
value值记得开long long

*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,ll> mp;

int main()
{
    int n,x;cin >>n;
    for(int i =1;i<=n;i++){
        cin >>x;
        mp[x-i]+=x;
    }
    ll res = 0;
    for(auto&[k,v]:mp) res = max(res,v);
    cout<<res<<endl;
}

3770. 最小消耗

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    int t,n,a,b,c;cin >> t;
    string s;
    while(t--){
        cin >> n >> a >> b >>c;
        getchar();
        int ans = 0;
        cin >> s;
        for(int i=0;i<s.size();i++){
            if(s[i]=='0') ans+=min(a,b+c);
            else if(s[i]=='1') ans+=min(b,a+c);
        }
        cout<<ans<<endl;
    }

    return 0;
}

acwing 第$9$次周赛

3778. 平衡数组

/*
题意：操作m次最后使得数组所有数字相等
思路：
最后是所有数字相等 = 所有数字相对大小为0
操作使得其他数字加上i = 把自身减去i（相对大小不变）

*/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        int n;
        scanf("%d", &n);
        printf("%d\n", n);
        for(int i = 1; i <= n; i ++)  printf("%d ", i);  puts("");
    }
    return 0;
}

3779. 相等的和

/*
思路：把每列总和减去当前数组值存在哈希表里
用count查找是否存在不同列中相同的值
哈希表可以用于查找，判断是否相等
数据范围是2e5,时间复杂度控制在O(n)

*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>//unordered_map执行效率要比map高很多

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int w[N];

int main()
{
    int m;
    scanf("%d", &m);

    unordered_map<int, PII> S;
    for (int i = 1; i <= m; i ++ )
    {
        int n, sum = 0;
        scanf("%d", &n);
        for (int j = 1; j <= n; j ++ )
        {
            scanf("%d", &w[j]);
            sum += w[j];
        }
        for (int j = 1; j <= n; j ++ )
        {
            int t = sum - w[j];
            if (S.count(t) && S[t].x != i)
            {
                puts("YES");
                printf("%d %d\n", S[t].x, S[t].y);
                printf("%d %d\n", i, j);
                return 0;
            }
            S[t] = {i, j};
        }
    }

    puts("NO");
    return 0;
}

acwing 第$19$次周赛

树上有猴

题目要求任意时刻猴子数量都在$[0,w]$区间，所以我们假设初始猴子数量为 $0$，并统计所有时刻（包括初始时刻）中猴子数量的最大值和最小值，得到一个相对范围 $[mincnt,maxcnt]$。我们只需要将这个相对范围在规定范围 $[0,w]$ 内“滑动”即可，总方案数为： $result=max(0,w−(maxcnt−mincnt)+1)$

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 

int main() {
    ll n, w;
    cin >> n >> w;
    // 由于初始时刻数量为 0，也应被统计到最值中
    // cur 记录当前时刻猴子的总数量
    ll maxcnt = 0, mincnt = 0, cur = 0;

    for(int i = 0; i < n; ++i) {
        // 读入当前时刻猴子变化量
        ll x;
        cin >> x;
        // 加入到结果中，并取最值
        cur += x;
        maxcnt = max(maxcnt, cur);
        mincnt = min(mincnt, cur);
    }
    printf("%lld\n", max((ll)0, w - (maxcnt - mincnt) + 1));
    return 0;
}

acwing 第$28$次周赛

子序列

如果数据范围很大：前缀和预处理
#include<bits/stdc++.h>
using namespace std;

int r()//快读
{
    int x=0;char ch;bool f=1;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f?x:-x;
}
const int maxn=1e2+5;
string s;
int n;
int preq[maxn],sumq[maxn];
int main()
{
    cin>>s;
    n=s.length();
    s='0'+s;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='Q')preq[i]=1;
        preq[i]+=preq[i-1];//Q前缀和
        if(s[i]=='A')sumq[i]=preq[i];
        sumq[i]+=sumq[i-1]; //每个A和之前的Q形成的QA数量
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='Q')ans+=sumq[i-1];//QAQ的数量
    }
    cout<<ans;
    return 0;
}