1.完全背包法:f[i][j]表示在不超过j的背包,能放入1到i的数字的总方案数

状态转移方程:f[i][j] = f[i-1][j] + f[i][j - i]

  • 推导
    f[i][j] = f[i-1][j] + f[i-1][j - i], f[i-1][j - 2i] …
    f[i][j-i] = f[i-1][j-i] + f[i-1][j - 2i] + f[i-1][j-3i]
    f[i][j] = f[i-1][j] + f[i][j-i]

f[i-1][j]表示一个i数字都没拿,而f[i-1][j - i], f[i-1][j - 2i], f[i-1][j-3i]…表示为依次拿了1,2,3…k个i的数字

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];


int main(){

    int n;
    cin >> n;

    for(int i = 1; i <= n; i ++ ) f[i][0] = 1;

    for(int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            f[i][j] = f[i-1][j];
            if (j >= i){
                f[i][j] = (f[i-1][j] + f[i][j - i]) % mod;
            }
        }
    }

    cout << f[n][n] << endl;

    return 0;

}


1.1完全背包优化(一维)

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N];


int main(){

    int n;
    cin >> n;

    f[0] = 1;

    for(int i = 1; i <= n; i ++ ){
        for (int j = i; j <= n; j ++ ){

            f[j] = (f[j] + f[j - i]) % mod;   // f[i][j] = f[i-1][j] + f[i][j - i] 
                                              // 由于f[i-1][j]表示一个i数字都没拿,不用担心01背包的同一层多拿i的问题。
        }
    }

    cout << f[n] << endl;

    return 0;

}

2. 总和是i, 数字个数有j个的所有方案

状态转移方程:f[i][j] = f[i-1][j-1] + f[i-j][j]

  • 其中以最小数字至少有一个1 和 最小数字没有1来划分
  • f[i-1][j-1]去掉一个1,那么总和减1,数字的个数减1。表示最小数字至少有一个1。
  • f[i-j][j] 所有数字减1,总和减1,数字个数不变,还是正整数,合法。表示最小数字没有1。
 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int f[N][N];


int main(){

    int n;
    cin >> n;
    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ ){
        for (int j = 1; j <= i; j ++ ){
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
        }
    }

    int res;

    for (int i = 0; i < n; i ++ ) res = (res + f[n][i+1]) % mod;

    cout << res << endl;

    return 0;
}



guanchen
11分钟前

题目描述

如果一个正整数无法被 [2,a] 范围内的任何整数整除,则称其为不合群数。

请你计算并输出 [2,b] 范围内的最大不合群数。

样例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        for (int i = b; i > a; i --) {

            /* 合群标记默认 false */
            boolean hequnFlag = false;

            // 
            for (int j = 2; j <= a && j * j <= i ; j++) {
                if(i % j  == 0){
                    hequnFlag = true;
                    break;
                }
            }
            if( !hequnFlag ){
                // 不合群
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }

}


算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



刘帅哥
12分钟前
//3706
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int a = 2, b = 3, c;
    if(n == 1) cout << 2;
    else if(n == 2) cout << 3;
    else{
        for(int i = 3;i <= n;i++){
            c = a + b;
            a = b;
            b = c;
        }
        cout << b;
    }
    return 0;
}



Zoe_56
22分钟前

思路:

  • 正整数x无法被 [2,a]范围内的任何整数整除
    → x不属于[2, a]
  • [2,b]范围内的最大不合群数
    → x属于(a, b]

    → 素数是不合群数

    → 非素数只要无法被[2,a]范围内的数整除也是不合群数

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

int main()
{
    ios::sync_with_stdio(false);

    int a, b; cin >> a >> b;
    int Max = -1;

    for (int i = b; i > a; i--) 
    {
        bool yes = true;
        for (int j = 2; j <= a && j * j <= i; j++)
            if (i%j == 0) {
                yes = false;
                break;
            }
        if (yes) {
            cout << i << endl;
            return 0;
        }
    } 
    cout << -1 << endl;

    return 0;
}



冰中月
28分钟前

题目描述

众所周知,对一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$,可以用下述方式求实数解:

  • 计算 $\Delta = b ^ 2 - 4ac$,则:
    1. 若 $\Delta < 0$,则该一元二次方程无实数解;
    2. 否则 $\Delta \geq 0$,此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$;
      • 其中,$\sqrt \Delta$ 表示 $\Delta$ 的算数平方根,即使得 $s^2 = \Delta$ 的唯一非负实数 $s$。
      • 特别的,当 $\Delta = 0$ 时,这两个实数解相等;当 $\Delta > 0$ 时,这两个实数解互异。

例如:

  • $x ^ 2 + x + 1 = 0$ 无实数解,因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$;
  • $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x_{1, 2} = 1$;
  • $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x_1 = 1, x_2 = 2$;

在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。

例如 $12$ 和 $18$ 的最大公因数是 $6$,即 $\gcd(12, 18) = 6$。

现在给定一个一元二次方程的系数 $a, b, c$,其中 $a, b, c$ 均为整数且 $a \neq 0$

你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解,并按要求的格式输出。

在本题中输出有理数 $v$ 时须遵循以下规则:

  • 由有理数的定义,存在唯一的两个整数 $p$ 和 $q$,满足 $q > 0$,$\gcd(p, q) = 1$ 且 $v = \frac pq$。
  • 若 $q = 1$,则输出 {p},否则输出 {p}/{q},其中 {n} 代表整数 $n$ 的值;
  • 例如:
    • 当 $v = -0.5$ 时,$p$ 和 $q$ 的值分别为 $-1$ 和 $2$,则应输出 -1/2
    • 当 $v = 0$ 时,$p$ 和 $q$ 的值分别为 $0$ 和 $1$,则应输出 0

对于方程的求解,分两种情况讨论:

  1. 若 $\Delta = b ^ 2 - 4ac < 0$,则表明方程无实数解,此时你应当输出 NO
  2. 否则 $\Delta \geq 0$,此时方程有两解(可能相等),记其中较大者为 $x$,则:
    1. 若 $x$ 为有理数,则按有理数的格式输出 $x$。
    2. 否则根据上文公式,$x$ 可以被唯一表示为 $x = q_1 + q_2 \sqrt r$ 的形式,其中:
      • $q_1, q_2$ 为有理数,且 $q_2 > 0$;
      • $r$ 为正整数且 $r > 1$,且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$(即 $r$ 不应是 $d ^ 2$ 的倍数);

此时:

  1. 若 $q_1 \neq 0$,则按有理数的格式输出 $q_1$,并再输出一个加号 +
  2. 否则跳过这一步输出;

随后:

  1. 若 $q_2 = 1$,则输出 sqrt({r})
  2. 否则若 $q_2$ 为整数,则输出 {q2}*sqrt({r})
  3. 否则若 $q_3 = \frac{1}{q_2}$ 为整数,则输出 sqrt({r})/{q3}
  4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$,此时输出 {c}*sqrt({r})/{d}

上述表示中 {n} 代表整数 $n$ 的值,详见样例。

如果方程有实数解,则按要求的格式输出两个实数解中的较大者。

否则若方程没有实数解,则输出 NO

输入格式

输入的第一行包含两个正整数 $T, M$,分别表示方程数和系数的绝对值的上界;

接下来 $T$ 行,每行包含三个整数 $a, b, c$。

输出格式

输出 $T$ 行,每行包含一个字符串,表示对应询问的答案,格式如题面所述。

每行输出的字符串中间不应包含任何空格

数据范围

对于所有测试数据有:$1 \leq T \leq 5000$,$1 \leq M \leq 10 ^ 3$,$|a|,|b|,|c| \leq M$,$a \neq 0$。

QQ截图20231030152951.png

其中:

  • 特殊性质 $A$:保证 $b = 0$;
  • 特殊性质 $B$:保证 $c = 0$;
  • 特殊性质 $C$:如果方程有解,那么方程的两个解都是整数。

输入样例:

9 1000
1 -1 0
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

输出样例:

NO
/
*()
/+()/
+()/
/+*()/

算法1

(大模拟) $O(n^2)$

题目写得很恐怖,其实所代表的意思并不难。
也就是考验你的语文水平和耐心。

不好意思,和同学写规则怪谈写多了,注意事项出现了好多类似“你需要”“不需要”“在遵守”的字眼…

我们梳理一下题意:

给出 一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$,求出在实数范围内较大的 $x$。

然而我们并不需要想如何求解,题目中已经给出了方法。

这里建议先去看懂题目,然后看我们的解题过程,可能会清楚一点。

  • 计算 $\Delta = b ^ 2 - 4ac$,则:
    1. 若 $\Delta < 0$,则该一元二次方程无实数解,此时我们输出 NO。记得需要回车。
    2. 否则 $\Delta \geq 0$,此时该一元二次方程有两个实数解 $x_{1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$;而题目中我们只需要求较大的 $x$ 即可。

从上述的第 $2$ 点开始分类讨论:

($1$) $\Delta = 0$

我们把 $x$ 的式子抄下来:$x = \frac{-b \pm \sqrt \Delta}{2a}$。

为了方便描述。
我们

将 $-b \pm \sqrt \Delta$ 记为$p$;
将 $2a$ 记为 $q$。

于是 $x = \frac{p}{q}$。

由于此时 $\Delta = 0$
所以 $\sqrt{\Delta} = 0$,所以 $p = -b + \sqrt{\Delta} = -b + 0 = -b$。

接下来我们将分子分母同时除以 $gcd(p,q)$ 使 $x$ 化为最简分式。(最简公分母即为 $gcd(p,q)$)

同时,我们把分母的负号移到分子上。

由于此时 $\sqrt{\Delta} = 0$ ,所以 $x$ 必为 有理数
我们直接按分数的输出方法输出 $x$ 即可。

注意: $x$ 可能为整数此时不要输出 $/q$




($2$) $\Delta \geq 0$

这种情况会比上面的情况复杂得多,请耐心观看。

首先,我们

将 $-b$ 记为$p$;
将 $2a$ 记为 $q$。
将 $ \sqrt \Delta$ 定义为 $sd$

注意:
1. 此时 $p$ 的定义与上文定义有些许不同,表现为没有 $\pm \sqrt \Delta$。
2. $sd$ 中的 $\sqrt \Delta$ 没有 $\pm$,原因后面讲。
3. $sd$ 变量属性为 $long \ long$,原因后面讲。

此时我们的 $x = \frac{p + sd}{2a}$。

以下分两种情况讨论:


① ${sd}^2 = \Delta$,即 $\Delta$ 为 完全平方数

由于我们的 $sd$ 为 $long \ long$ 属性,存储时会将 $\sqrt \Delta$ 四舍五入。
那我们就可以根据此种特性判断 $\Delta$ 是否为 完全平方数。(此处解释完成注意事项 $3$)

我们将 $q$ 中的负号移到 分子的$p$ 上。
接着 $p + sd$。

$Q:$ 为什么此处 $p$ 不先加上 $sd$ 再进行$\underline{负号转移}$ (指将分母的负号移到分子上) ?

$A:$ 按问题中所说的方法不能保证 $x$ 为较大解。

为了更加清楚地看到问题,我们设 $p = 4$,$q = -2$,$sd = 3$。

问题中的方法: $x = \frac{4 + 3}{-2} = \frac{-7}{2} = - \frac{7}{2}$
正确的方法: $x = \frac{-4 + 3}{-(-2)} = \frac{-1}{2} = - \frac{1}{2}$

显然正确方法中的 $x$ 更大。

注意事项 $2$ 的意义就是为了不要在此过程中加上绝对值符号,会更加麻烦。

接下来约分后输出

注意: $q = 1$ 时不需要输出 $/q$。


② ${sd}^2 \not= \Delta$,即此时 $\Delta$ 不为 完全平方数

说一句与分类讨论无关的话:你可能觉得 $sd$ 只是用于判断 $\Delta$ 是否为完全平方数,但事实上不是这样的,我们在后面把 $\sqrt{\Delta}$ 化为最简二次根式时也会用到。所以不要把它写在 $if$ 里面。

由于此时 $\Delta$ 不为完全平方数,所以 $\sqrt{\Delta}$ 为无理数,我们需要将其化为最简二次根式再输出,所以此时我们根据题意改变 $x$ 的表示,分批输出。

$$x = \frac{p}{q} + \frac{ \pm \sqrt{\Delta}}{q}$$

首先我们输出 $x$ 中的 $\frac{p}{q}$。

约为最简分式,将 $q$ 中的负号移到 $p$ 上,输出。(此处说过多次,不再赘述)

注意:

  1. 当 $p = 0$ 时 $\frac{p}{q} = 0$ (显而易见),不需要输出
  2. 在遵循上述条件 $1$ 的情况下,如果 $q = 1$ ,不需要输出 $/q$

接下来处理后半部分的 $\frac{ \pm \sqrt{\Delta}}{q}$。

我们将 $\sqrt{\Delta}$ 化为最简二次根式(题目中有解释),将其记为 $d1 \sqrt{d2}$。

$Q:$ 如何化简呢?
$A:$ 定义 $d1 = 1$,$d2 = \Delta$。

执行 $for$ 循环,$i$ 从 $sd$ 开始,不断减 $1$,直到 $i = 1$ 为止。(从后往前是为了节约时间)

过程中我们定义 $j = i^2$。
如果 $\Delta$ 能被 $j$ 整除,我们将 $j$ 从根号中开出,将 $d1$ 乘 $i$ ,把 $d2$ 除以 $j$,$break$。

这里怕一些低年级的巨佬没学过二次根式,我们举一个例子:

这里需要知道 $\sqrt{ab} = \sqrt{a} × \sqrt{b}$

此时我们需要化简 $\sqrt{12}$。

根据上述公式我们可以: $\sqrt{12} = \sqrt{4 × 3} = \sqrt{4} × \sqrt{3} = 2 × \sqrt{3} = 2 \sqrt{3}$

然后按照常规方法化简分式,输出。

$Q:$ 为什么 $q$ 赋值时 取了绝对值。(此处见代码 $q = abs(2 * a)$)
$A:$ 与之前 $sd$ 为什么不加 $\pm$ 差不多,是 $x$ 需输出较大值的问题。

我们把后半部分的分式抄下来: $\frac{ \pm \sqrt{\Delta}}{q}$。

  • 当 $q$ 为负数时,我们 上方 $ \pm \sqrt{\Delta}$ 取 $- \sqrt{\Delta}$ 时整个分式为正数,显然比负数大
  • 当 $q$ 为正数时,我们 上方 $ \pm \sqrt{\Delta}$ 取 $+ \sqrt{\Delta}$ 时整个分式为正数,显然比负数大

这个问题就解决了。

注意:
1. $q = d1$时,$q$ 与 $d1$ 抵消,直接输出 sqrt(d2)即可;
2. $q = 1$时,不需要输出 $/q$;
3. $d1 = 1$时,不需要输出 $d1$。

完结撒花!

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e3 + 10;
long long t,M;
int main(){
    scanf("%lld%lld",&t,&M); // 读入,当然 M 在代码中并没有什么用处(
    while(t --){ // 多测
        long long a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        long long delta = b * b - 4 * a * c; // 计算 delta
        if(delta < 0) printf("NO\n"); // 无解
        else if(delta == 0){ // delta = 0 的情况
            long long p = -b,q = 2 * a;
            long long g = __gcd(abs(p),abs(q));
            p /= g;
            q /= g;
            if(q < 0){
                p = -p;
                q = -q;
            }
            if(q == 1) printf("%lld\n",p);
            else printf("%lld/%lld\n",p,q);
        }
        else{ // delta >= 0 的情况
            long long p = -b,q = 2 * a;
            long long sd = (long long)sqrt(delta);
            if(sd * sd == delta){ // delta 为 完全平方数
                if(q < 0){
                    p = -p;
                    q = -q;
                }
                p += sd;
                long long g = __gcd(abs(p),abs(q));
                p /= g;
                q /= g;
                if(q == 1) printf("%lld\n",p);
                else printf("%lld/%lld\n",p,q);
            }
            else{ // delta 不为 完全平方数
                long long g = __gcd(abs(p),abs(q)); // 前一个分式的处理
                p /= g;
                q /= g;
                if(q < 0){
                    p = -p;
                    q = -q;
                }
                if(p != 0){
                    if(q == 1) printf("%lld+",p);
                    else printf("%lld/%lld+",p,q);
                }
                long long d1 = 1,d2 = delta;
                q = abs(2 * a); // 后一个分式的处理
                for(long long i = sd;i >= 1;i --){
                    long long j = i * i;
                    if(d2 % j == 0){
                        d2 /= j;
                        d1 *= i;
                        break;
                    }
                }
                int gdq = __gcd(abs(d1),abs(q));
                q /= gdq;
                d1 /= gdq;
                if(q < 0){
                    q = -q;
                    d1 = -d1;
                }
                if(q == d1) printf("sqrt(%lld)\n",d2);
                else if(q == 1) printf("%lld*sqrt(%lld)\n",d1,d2);
                else if(d1 == 1) printf("sqrt(%lld)/%lld\n",d2,q);
                else printf("%lld*sqrt(%lld)/%lld\n",d1,d2,q);
            }
        }
    }
    return 0;
}

应该是最为详细的题解了,$AcWing$ 和 $Luogu$ 上都是。

$$(共 355 行)$$




谢丽君
38分钟前

include[HTML_REMOVED]

using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b;
return 0;

}



新鲜事 原文

https://www.acwing.com/activity/content/introduction/11/group_buy/181885/?from=app_share acwing嗯算法基础课[脱单doge]有需要的拼拼
图片


新鲜事 原文

https://www.acwing.com/activity/content/introduction/11/group_buy/181885/?from=app_share acwing嗯算法基础课[脱单doge]有需要的拼拼
图片


新鲜事 原文

https://www.acwing.com/activity/content/introduction/11/group_buy/181885/?from=app_share acwing嗯算法基础课[脱单doge]有需要的拼拼
图片


新鲜事 原文

reCaptcha/Captcha 原来也是检测鼠标移动轨迹和谷歌所有服务浏览记录,来判断是不是人。不只是选的方格。鼠标移动到勾,以及选方格时的轨迹也算了... (大概)