新鲜事 原文

2023年 安得广厦千万间,大庇天下寒士俱欢颜。
图片


新鲜事 原文

环岛有幸
1小时前
睡不着a


新鲜事 原文

comum
1小时前
今日总结 没有总结🧐🧐,明天继续dp,突然明天想看数论第二章了🤭🤭🤭
图片 图片



环岛有幸
1小时前

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;
}



古咩
2小时前

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

D - AABCC (atcoder.jp)

100213111_p0.png

问题陈述

有多少个不大于 $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;
}



张一腥
2小时前
/*算法思想:反转链表+合并链表
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;
    }
};



怡云
2小时前

分享一下错误心得:

我根据高中学习的几何不等式和经验大致猜了一下,越是接近平均值乘积越大,但是具体要分为多少份呢?我再次斗胆猜一个平方根(接近平方根)。
例如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,这种方式还是行不通,还是乖乖使用动态规划吧,简单多了。。。




2048
2小时前

题目描述

将字符串列表编码为单个字符串。
将单个字符串解码为字符串列表。
不允许您使用任何序列化方法(例如 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;
    }
};




张钦
3小时前

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

Pharaoh27
3小时前

min max
包含在iostream里面