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

题目描述

如果一个正整数无法被 [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

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

思路：

• 正整数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;
}

题目描述

众所周知，对一元二次方程 $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$。

其中：

• 特殊性质 $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 行）$$

include[HTML_REMOVED]

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

}