字符串处理

日期识别

在小蓝处理的日期中有两种常用的形式：英文形式和数字形式。

英文形式采用每个月的英文的前三个字母作为月份标识，后面跟两位数字表示日期，月份标识第一个字母大写，后两个字母小写，日期小于 1010 时要补前导 00。

11 月到 1212 月英文的前三个字母分别是 Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec。

数字形式直接用两个整数表达，中间用一个空格分隔，两个整数都不写前导 00。

其中月份用 11 至 1212 分别表示 11 月到 1212 月。

输入一个日期的英文形式，请输出它的数字形式。

输入一个日期的英文形式。

输出一行包含两个整数，分别表示日期的月和日。

Feb08

2 8

Oct18

10 18

#include<iostream>
#include<cstring>
using namespace std;
string ri[13]={"","Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
int main()
{
    string s;
  
    cin>>s;
    int yue;
    //int yue=ri[str.substr(0,3)];//错，下标不等于元素
    for(int i=1;i<=12;i++)//****
    {
        if(s.substr(0,3)==ri[i])
        {
            yue=i;
            break;
        }
    }
    int day=(s[3]-'0')*10+s[4]-'0';
    printf("%d %d",yue,day);
}

解码

#include<iostream>
using namespace std;
int main()
{
    string s;
    cin>>s;
    for(int i=0;s[i];i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            int num=s[i]-'0'; //num次
            for(int j=0;j<num-1;j++) cout<<s[i-1];
        }
        else cout<<s[i];//有数字++没数字
    }
    return 0;
}

整数小拼接

AcWing 2874. 整数小拼接——排序+双指针 - AcWing  题解

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 1e5+10;
typedef long long ll;
ll a[N];
string s[N], sk;
ll n, k;
ll res;

int cmp(string s1, string s2) { // 字符串大小比较函数
    if(s1.size() == s2.size()) { 
        if(s1 == s2) return 0;
        else if(s1 < s2) return 1;
        else return -1;
    }
    else if(s1.size() < s2.size()) return 1;
    else return -1;
}

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) s[i] = to_string(a[i]);
    sk = to_string(k);
    int l = 1, r = n;
    while(l <= r) { // l放前面r放后面拼接
        int t = cmp(s[l] + s[r], sk);
        if(t == 1) { // 拼接后小于k
            res += r - l;
            l++;
        } else if(t == 0) { // 拼接后等于k
            res += r - l;
            l++, r--;
        } else r--; // 拼接后大于k
    }
    l = 1, r = n;
    while(l <= r) { // r放前面l放后面拼接
        int t = cmp(s[r] + s[l], sk);
        if(t == 1) {
            res += r - l;
            l++;
        } else if(t == 0) {
            res += r - l;
            l++, r--;
        } else r--;  
    }
    cout << res;
    return 0;
}

密文搜索

//因为打乱顺序，所以从主串找有子串所有同数量字母  的可能 即可
//map:映射：串(string)->数量（int)

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

using namespace std;
unordered_map<string,int> mp;

int main()
{
    string str;
    int n ;
    cin>>str;
    cin>>n;
    string s;
    while(n--)
    {
        cin>>s;
        sort(s.begin(),s.end());//****
        mp[s]++;
    }
    
    int ans=0;
    for(int i=0;i<=str.size()-8;i++)
    {
        string t=str.substr(i,8);//从i，取八字符   i   方法论*******
        //str.
        sort(t.begin(),t.end());//*****
        ans+=mp[t];
    }
    cout<<ans;
}

树形DP （在树里ds)

没有上司的舞会

#include<iostream>
#include<cstring>
using namespace std;
const int N=6010;
int h[N],e[N],ne[N];
bool has_father[N];
int happy[N];
int f[N][2],idx;
;void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
    
}
int dp(int u)
{
    f[u][1]=happy[u];  //选u
    
    for(int i=h[u];i!=-1;i=ne[i])//u连的每个儿子
    {
        int j=e[i];
        
        dp(j);
        
        f[u][1]+=(f[j][0]);  //儿子必须不选
        f[u][0]+=max(f[j][0],f[j][1]) ;//儿子可选可不选
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];
    memset(h,-1,sizeof h);
    
    for(int i=0;i<n-1;i++)
    {
        int l,k;
        cin>>l>>k;
        add(k,l);
        has_father[l]=true;
        
    }
    int root=1;
    while(has_father[root]) root++;//找根节点 根无父
    
    dp(root);
    
    printf("%d\n",max(f[root][0],f[root][1]));//根选，不选两种情况
}

生命之树

/*要在这棵树内选出一个非空节点集 S
，使得对于 S
 中的任意两个点 a,b
，都存在一个点列 {a,v1,v2,…,vk,b}
 使得这个点列中的每个点都是 S
 里面的元素，且序列中相邻两个点间有一条边相连。
 
 连通图*/
 //找最大权值的连通图
 
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;
typedef long long ll;
int e[N*2],h[N],ne[N*2],idx;
int w[N];
long long f[N];//f[u]:以u为根的包含u的所有连通块权值和
void add(int a,int b)//模拟树
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u,int father)
{
    f[u]=w[u];
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        
        if(j!=father)
        {
            dfs(j,u);//深搜 连通块
            
            f[u]+=max(0ll,f[j]);//f[j] f  // long long的0，和0比较一下，如果<=0没必要加上
        }
    }
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);//
    for(int i=1;i<=n;i++) cin>>w[i];//从i=1
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,-1);//（根）无父
   long long ans=f[1];
    for(int i=2;i<=n;i++) 
    {
        ans=max(ans,f[i]);//找最大 权值和
    }
    cout<<ans<<endl;
}

构造 找规律 推公式

矩形拼接

蓝桥杯——矩形拼接-程序员宅基地  题解

//最大八种
//https://blog.csdn.net/qq_53237241/article/details/136432327
#include<bits/stdc++.h>
using namespace std;
int a[3][2];
int main(){
    int T;    cin >> T;
    while(T--)    {
        for(int i = 0; i < 3; i++)
            cin >> a[i][0] >> a[i][1];
        int ans = 8;
        for(int i = 0; i < 3; i++)               //第1个矩形
            for(int j = 0; j < 3; j++)
                if(i != j)                       //第2个矩形
                    for(int k = 0; k < 3; k++)
                        if(k != i && k != j)     //第3个矩形
                            for(int ii = 0; ii <= 1; ii++){           //第1个有横竖两种摆法
                                for(int jj = 0; jj <= 1; jj++){       //第2个横竖摆
                                    for(int kk = 0; kk <= 1; kk++){   //第3个横竖摆
                                        if(a[i][ii] == a[j][jj] + a[k][kk]){ 
                                            ans = min(ans, 6);
                                            if(a[j][1-jj] == a[k][1-kk])
                                                ans = min(ans, 4);
                                        }
                                        if(a[i][ii] == a[j][jj] || a[j][jj] == a[k][kk])
                                            ans = min(ans, 6);
                                        if(a[i][ii] == a[j][jj] && a[j][jj] == a[k][kk])
                                            ans = min(ans, 4);
                                    }
                                }
                            }
        cout<<ans<<endl;
    }
    return 0;
}

全排列的价值

AcWing 4660. 全排列的价值 - AcWing  题解

AcWing 4660. 全排列的价值 - AcWing

#include<iostream>
using namespace std;
typedef long long LL;
const LL mod=998244353;
int main()
{
  LL n;//LL
   cin>>n;
    LL res=1;
    for(int i=3;i<=n;i++) res=(res*i)%mod;
    
    res=(res%mod*((n*(n-1)/2)%mod))%mod;//***
    cout<<res;
}

平方差

/*u=a*b

=(x+y)*(x-y)

a=x+y b=x-y

x=(a+b) /2
y=(a-b) /2
显然,只有当a,b奇偶性相同时
奇数可以分为1*u,奇偶性相同，偶数可以分为2*u/2
,注意，要想使2和u/2的奇偶性相同，u就必须是4的倍数


所以，法一：u:奇数或4的倍数

法二：奇数1 3 5 7，，，%4=1或3  偶%4==0
所以只有%4==2的不行*/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

//获取[1...x]中 4的倍数 和 奇数的个数，前者下取整，后者上取整
LL get_sum(LL x)
{
    return x / 4 + (x + 1) / 2;
}

int main()
{
    LL l, r;
    cin >> l >> r;

    cout << get_sum(r) - get_sum(l - 1); //减去集合重合的部分即可
    return 0;
}

完全二叉树的权值

波动数列

AcWing 1214. 波动数列 - AcWing  题解

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

using namespace std;

const int N = 1010, MOD = 100000007;

int n, s, a, b;
int f[N][N];

int get_mod(int a, int b)
{
    return (a % b + b) % b;
}

int main()
{
    scanf("%d%d%d%d", &n, &s, &a, &b);

    f[0][0] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < n; j++)
            f[i][j] = (f[i - 1][get_mod(j - (n - i) * a, n)] + f[i - 1][get_mod(j + (n  - i) * b, n)]) % MOD;

    printf("%d", f[n - 1][get_mod(s, n)]);

    return 0;
}

最少砝码

AcWing 3424. 最少砝码 - AcWing  题解

#include<iostream>
using namespace std;
int n;

int main()
{   cin>>n;
    int ans=1;
    int sum=1;
    int t=1;
    while(sum<n)
    {
        sum+=t*3;
        t*=3;
        ans++;
    }
    cout<<ans;
}

数学

（思维）杨辉三角形

AcWing 3418. 杨辉三角形 - AcWing  题解

AcWing 3418. 杨辉三角形（蓝桥杯C++ AB组辅导课） - AcWing  讲解

/*从最右边往左 第一个遍历到的 就是总体第一个遍历到的
从图中
左侧数字偏小 右侧偏大   若左侧也遍历到，需要很多行，序号大
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

// C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
LL C(int a, int b){
    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++){
        res = res * i / j;
        // 大于n已无意义，且防止爆LL
        if(res > n) return res;
    }
    return res;
}

bool check(int k){
    // 二分该斜行,找到大于等于该值的第一个数
    // 左边界2k，右边界为max(l, n)取二者最大即可！
    int l = 2 * k, r = max(n, l);
    while(l < r){
        int mid = l + r >> 1;
        if(C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if(C(r, k) != n) return false;
    // C(r, k)的从0开始的顺序！
    cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;
    return true;
}

int main(){
    cin >> n;
    // 从第16斜行枚举即可！
    for(int k = 16; ; k --)
        if(check(k)) break;
    return 0;
}

Fibonacci数列与黄金分割

AcWing 3177. Fibonacci数列与黄金分割(数学递推式+特判) - AcWing   题解

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

int main()
{
    int n;
    cin>>n;
    double res=1, last=1;
    for(int i=2; i<=n; i++)
    {
        last = res;
        res = 1/(1+res);
        if(abs(res-last) < 1e-9) break;
    }
    printf("%.8lf", res);

    return 0;
}

最大比例

#include<iostream>
#include<algorithm>

using namespace std;

const int N=110;

typedef long long LL;

LL x[N],a[N],b[N];
int cnt=0;

//假设原数列为 a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)
//假设抽取的数列  b0,b1,...,b(N-1)  (从小到大排好序了)
//  b1/b0,b2/b0,...,b(N-1)/b0-->  (p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)
//  我们要求的是：  （p/q）^k  (p/q)>1,所以使k最大，即求 x1~x(N-1)的最大公约数
//这里我们使用更相减损术，因为我们没有得到确切的x1~x(N-1)是多少，我们只有(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)这些的值

/*更相减损术：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。*/

//更相减损术总用较大的减去较小的
/*例子：
    98-63=35
    63-35=28
    35-28=7
    28-7=21
    21-7=14
    14-7=7
所以，98和63的最大公约数等于7。*/

//我们这里要用更相减损术的是指数，所以要让(p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)，两两计算，互除，除到结果为1,即x1=x2,此时幂次为0，结果为1，这其实就是y总的思路，再次感叹y总的才华
//把分子分母分别去算，结果是相同的因为，分子分母的幂次是相同的
LL gcd(LL a,LL b)
{
    return b? gcd(b,a%b):a;
}

LL gcd_sub(LL a,LL b)  
{
    if(a<b)  swap(a,b);  //更相减损术总是大减小（它们的底数是一样的）
    if(b==1)  return a;
    return gcd_sub(b,a/b);
}

int main()
{
    int n;
    cin>>n;

    for(int i=0; i<n; i++)  scanf("%lld",&x[i]);

    sort(x,x+n);

    for(int i=1; i<n; i++)
    {
        if(x[i] != x[i-1])
        {
            LL d=gcd(x[i],x[0]);  
            a[cnt]=x[i] / d;  //得到x[i]/x[0]的分子
            b[cnt]=x[0] / d;  //得到x[i]/x[0]的分母
            cnt++;
        }
    }

    LL up=a[0],down=b[0];
    for(int i=1; i<cnt; i++)
    {
        up=gcd_sub(up,a[i]);  //两两求最大公约数
        down=gcd_sub(down,b[i]);
    }

    cout<<up<<"/"<<down<<endl;

    return 0;
}

质因数的个数

//24=2*2*2*3
#include<iostream>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    long long ans=0;
    for(long long i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans++;
            while(n%i==0)n/=i;
        }
    }
    if(n>1) ans++; /*约数都是成对出现
    的，如果在小约数的时候结束了循
    环，那么，n的大约数我们就肯可能会遗漏
    
    
    2*2*19=76
19>sqrt(76) //19是大质因数 */
    cout<<ans;
    
}

成绩统计

#include <iostream>

using namespace std;

int n,sum1,sum2;
int a[10010];

int main()
{
  cin>>n;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    if(a[i]>=60) sum1++;//统计及格的人数
    if(a[i]>=85) sum2++;//统计优秀的人数
  }

  printf("%d%%\n",(int) (sum1*100.0/n+0.5));//+0.5: 小数 （给整数部分）进行四舍五入操作   (int)********
   
  printf("%d%%\n",(int)(sum2*100.0/n+0.5));

  return 0