include[HTML_REMOVED]

using namespace std;
const int N = 100005;
int a[N],b[N],c[N];
int main(){
string s1,s2;//数字字符化
cin>>s1>>s2;
int la,lb,lc;//la是s1，lb是s2，lc是结果的大小
//C中的 size()函数是一个非常有用的函数，用于获取容器中元素的数量。
//这个函数可以用于大多数 STL 容器，比如 vector、list、set、map 等等
la=s1.size();
lb=s2.size();//la是s1的位数，lb是s2的位数
lc=max(la,lb);
for(int i=0;i<la;i) a[la-1-i]=s1[i]-‘0’;
for(int i=0;i<lb;i) b[lb-1-i]=s2[i]-‘0’;//数字字符可以通过-‘0’变成整形数字
//模拟加法
//累加（同时会加上上一步进位的数字）进位（用于下一部加上）求余（把数字存到数组里）
for(int i=0;i<lc;i){
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;//c[]是一个数组，每次传一位数字，把前面的数字去掉；
}
//判断最后一个位置是否为零

if(c[lc]) lc++;//这个时候看上边的for循环他肯定是到了lc停止循环，这个时候看for循环的最后一句话，
//c[i]=c[i]%10;也就是说有可能发生最后一位进一的情况所以if（1）lc++，方便我们之后的输出操作。
for(int i=lc-1;i>=0;i--)cout<<c[i];
//去除前导0
while(c[lc-1]==0) lc--;
return 0;
}

D - AABCC[数学] [时间复杂度分析]

D - AABCC (atcoder.jp)

问题陈述

有多少个不大于 $N$ 的正整数可以用三个素数 $a,b$ 和 $c$ 来表示 $a^2 \times b \times c^2$ ，使得 $a<b<c$ ？

• $N$是一个整数，满足 $300 \le N \le 10^{12}$。

这道题可以作为一道时间复杂度分析的例题

因为$a^2 \times b \times c^2 \le n$

所以$a^2 \times b \times c^2 \le 10^{12}$

因为$a<b<c$ ，又因为$a,b$ 和 $c$ 为素数

所以$3\le b ,2\le a $

所以$12 \times c^2 \le a^2 \times b \times c^2 \le 10^{12}$

所以$12 \times c^2 \le 10^{12}$

所以$c^2 \le \frac{10^{12}}{12}$

所以$c\le \sqrt{\frac{10^{12}}{12}}$

所以$c\le 288,676$

设$Π(x)$为素数函数

筛一下可以发现$Π(c)\le 25112$

然后直接暴力$for$遍历$i,j,k$

由于每一个$for$对于其素数都有单调性

然后总共的三层$for$的计算次数是答案的统计次数加上$break$的次数

可以近似的认为遍历次数就是答案数

因为样例给了

1000000000000

2817785

那么就可以在$2.8\times10^6$的时间复杂度内解决掉这道问题

code

#pragma GCC optimize(                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           \
    "-fdelete-null-pointer-checks,inline-functions-called-once,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-falign-functions,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2", \
    3, 2)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#define int long long
int n, m;
void solve() {
  std::cin >> n;
  auto get_prime = [&](int x) -> std::vector<int> {
    std::vector<int> res;
    std::vector<bool> st(x + 1, false);
    st[0] = st[1] = true;
    for (int i = 2; i <= x; i++) {
      if (!st[i]) {
        res.emplace_back(i);
        for (int j = i + i; j <= x; j += i) {
          st[j] = true;
        }
      }
    }
    return res;
  };
  auto p = get_prime(sqrt(n / 12));
  int m = p.size();
  int ans = 0;
  for (int i = 0; i < m; i++) {
    for (int j = i + 1; j < m; j++) {
      if (p[i] * p[i] * p[j] > n) break;
      for (int k = j + 1; k < m; k++) {
        if (p[i] * p[i] * p[j] * p[k] > n or
            p[i] * p[i] * p[j] * p[k] * p[k] > n)
          break;
        ans++;
      }
    }
  }
  std::cout << ans << "\n";
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0), std::cout.tie(0);
  std::cout << std::fixed << std::setprecision(15);
  std::cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  solve();
  return 0;
}

/*算法思想：反转链表+合并链表
1.先将一条链表分为n/2上取整长度前半部分和n-上取整n/2长度的后半部分
2.将后半部分的链表进行反转
3.将前半部分和后半部分反转后的链表交叉进行合并
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        //特判：链表为空不需要，链表长度为1时特判节省运行时间
        if(!head->next) return;

        //1.链表前后分割
        int n = 0;//计算单链表的长度n
        for(auto a = head;a;a = a->next) n++;

        int left = (n+1) / 2;//左半部分为上取整长度
        auto a = head;
        for(int i = 0;i < left - 1;i++) a = a->next;//a跳left-1次到左链表末尾位置

        //a用来分割链表，b和c用来右半部分链表的反转
        auto b = a->next,c = b->next;
        a->next = b->next = NULL;//b->next在被更新为NULL之前已被c用过。b和c是为了反转next指针的指向

        //2.右侧链表的反转
        while(c){ //反转完后b就是反转链表的头结点，c指向NULL
            auto t = c->next;
            c->next = b;
            b = c,c = t;
        }

        //3.链表的合并
        for(auto p = head,q = b;q;){ //由于上取整后半段长度等于前半段或者比前半段少一个，所以用q != NULL做判定
            auto o = q->next;//存储q的下一个结点的值
            q->next = p->next;
            p->next = q; //类似于q结点插入到p链表中

            p = q->next;//p和q指针均向原来链表中后移一个位置
            q = o;
        }

        return;
    }
};

分享一下错误心得：

我根据高中学习的几何不等式和经验大致猜了一下，越是接近平均值乘积越大，但是具体要分为多少份呢？我再次斗胆猜一个平方根（接近平方根）。
例如8的平方根接近3，那么分成三份肯定最大，15的平方根接近4，那么它肯定是分成4份最大。
然后round(8.0/3)=3,round(15.0/4)=4，那么8分为3，3，2乘积最大，15分为4，4，4，3乘积最大。
经过（手动）检验，果不其然，必然是正确答案。
于是产生代码:

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

int main() {
    int length;
    cin >> length;     //输入的数据,用于我自行检验
    //注意特殊情况的判定，小于3时不可切，等于3时分为1，1，1；
    if (length <= 2) {
        cout << 0; return 0;
    }
    if (length == 3) {
        cout << 1; return 0;
    }
    //正片开始
    //sunSize记录length所分的段数，即接近平方根的部分？
    //a用于获取最接近平均数的部分，例如8中的3，15中的4；
    //b用于补充最后一个数，例如8中最后一个2，15中最后一个3；
    //输出结果——sumSize-1个a，1个b；
    int sumSize = round(sqrt(length));
    int a = round(length * 1.0 / sumSize);
    int b = length - a * (sumSize - 1);
    cout<< pow(a, sumSize - 1) * b<<endl;
    return 0;
}

ok,完结撒花…了吗？
出现一个错误用例？？？！
11，分为3、3、3、2，乘积为54，用我的方式：11的平方根最接近3，故分为3段，11.0/3最接近4,即分为4，4，3，结果为48
裂开......
数肯定是分的越多越好，因此开平方的时候不应该舍弃
将开平方部分的四舍五入全部改为向上取整：

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

int main() {
    int length;
    cin >> length;   
    if (length <= 2) {
        cout << 0; return 0;
    }
    if (length == 3) {
        cout << 1; return 0;
    }
    int sumSize = ceil(sqrt(length));//这里小小变化了一下
    int a = round(length * 1.0 / sumSize);
    int b = length - a * (sumSize - 1);
    cout<< pow(a, sumSize - 1) * b<<endl;
    return 0;
}

这下总该?
仍然错误......
连5都错成2 2 1，这种方式还是行不通，还是乖乖使用动态规划吧，简单多了。。。

题目描述

将字符串列表编码为单个字符串。
将单个字符串解码为字符串列表。
不允许您使用任何序列化方法（例如 eval）来解决问题。

样例

5#helloWorld
[hello,World]

算法1

neetcode$

C++ 代码

class Codec {
public:

    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string res = "";
        for(auto c: strs){
        //eg: 5#hello
            res += to_string(c.size()) + "#" + c;//用非英文字符分割
        }
        return res;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> res;
        int i = 0;
        auto length = 0;

        while(i < s.size()){
            int j = i;
            while(isdigit(s[j])){
                j++;
            }

            //s.substr(i, j - i)，从s中提取一个子串，i是起点，j - i是子串长度
            //stoi()：将字符串转化为整数
            length = stoi(s.substr(i, j - i));
            //提取长度为length的子串并转化为整数
            string str = s.substr(j + 1, length);
            res.push_back(str);
            i = j + 1 + length;//更新i
        }
        return res;
    }
};

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

int main()
{
int N[9];
int V;
cin >> V;
N[0]=V;
for( int i=0; i<=9; i)
{
N[i+1] = 2*N[i];
}
for( int i=0; i<=9; i)
cout <<”N[” << i << “] = ” << N[i] <<endl;
return 0;
}

min max
包含在iostream里面