T2-1

#include <cstdio>//单调栈
using namespace std;
int n, ans, stk[8][105], p[8], i, j;
int main(){/
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &i, &j);//给定第i个栈和插入栈的值
            while (stk[i][p[i]] > j) {//如果破坏了单调性就弹出元素至单调状态
                --p[i];
                ++ans;
            }
        if (stk[i][p[i]] != j) {//此时已满足单调性 插入元素移动下标
            stk[i][++p[i]] = j;
            ++ans;
        }
    }
    printf("%dn", ans);
    return 0;
}

(16)若将第002行的“using namespace std;”删去，程序仍可以正常执行，且对于相同的输入数据，输出结果不变（✔）

本段代码使用了C语言的标准不需要使用命名空间stl

(17)若将第003行的“int”改为“long long”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（✗）

int为32位有符号整型 long long为64位有符号整型数据大于 $2^{32}$ 的时候int会发生溢出

(18)若将第 013 行的“++p[i]”改为“p[i]++”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（ ✗）

“++p[i]” 执行p[i]+=1 并返回p[i]本身这一左值

“p[i]++” 执行p[i]+=1 并返回执行前p[i]的拷贝这一右值

++p[i]由于参与表达式内部运算，改变语义会导致数据变化

(19)若将第 014 行的“++ans”改为“ans++”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（✔）

同上，++ans本身不作为表达式内部变量参与运算，故无影响

(20)程序输出的 ans 值不可能为 0（✔）

若输入的n==0，则ans被值初始化为0,反之则不为0，输入规则内指出所有数据为正整数，故不为0

(21)该程序的算法时间复杂度为（$O(n)$ ）

可将stk[8][105]视作 8个元素的所含数据的集合，近似于

struct STKS{
    int num[105]
}stk[8];

内层while在常数级别的p[i]≈105的下标上运动,不受输入量n影响

外循环为执行n次，故复杂度为O(n)

(22)程序输出的 ans 值最大可能为（2n-1）

最大的简单情况为插入n-1个单调的元素后再插入一个小于第一个元素的元素

插入最后一个元素前此时由于先前未破坏单调性 ans == n-1

插入最后一个元素后内层while又执行了n-1次，此时ans==2n-2

if语句插入后，ans+=1,ans==2n-1.

具体原因为：每个元素至多进栈一次 ,出栈一次,最后一个元素入栈时已经完成了n次操作，故而不能出栈，理想情况下为2n-1次对ans的自增

又已知理想情况存在，故 $max(ans)=2n-1$

T2-2


#include<cstdio>
using namespace std;
bool valid(int k,int m){
    int now=0;
    for(int i=1;i<=k;i++){
        now = (now + m) % (2 * k - i + 1);//约瑟夫环？
            if(now==0)
                now=2*k-i+1//now仅可取值[1,2k-i+1]
            if(now<=k)
                return false;
            now--;
    }
    return true;
}

int main(){
    int k;
    cin>>k;
    int m=k + 1;
    while(!valid(k,m))
        m++;
    cout<<m;
    return 0;
}

(23)valid 函数的算法时间复杂度为 O(k)（此处的 k 特指程序输入的 k）（✔）

内层循环最多处理k次,正确

(24)若将第 005 行改为“for (int i = 0; i < k; i++) {”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（✗）

等价于i在循环内部表达式内减1，尚无此同余定理 ,错误

(25)若将第 018 行的“k + 1”改为“k”，程序执行或许会变慢，但仍可以被正常执行，且对于相同的输入数据，输出结果不变。（✗）

代入特殊值k=0得出1,修改后得出0

(26)程序输出的m值最小可能为（1）。

同上,m>=k+1,故最小为1

(27)若输入的k为4，程序将输出(32)

**作者未找到除代入以外的更优解！

整理valid可得合法情况为:

$$
forall J{i,m}=(J{i-1,m}+m-1)mod(2k-i+1) ~~~~ {J_{i,m}∈[k+1,2k-i+1]} ~~~~ i∈[1,k]
$$

可转化为

\forall J_{i,m}=(J_{i-1,m}+m-1) \mod (2k-i) ~~ {J_{i,m} \in [k+1,2k]} ~~ i \in [0,k-1]

不合法情况为:

$$
exist J{i,m}=(J{i-1,m}+m-1)mod(2k-i+1) ~~~~ {J_{i,m}∈[1,k]}~~~~i∈[1,k]
$$

(28)若输入的k为5，程序将输出（）

T2-3

#include<cstdio>
#include<cstring>
using namespace std;
int n,a[35],rt[35][35],val[35][35];

long long calc(int l,int r){
    if(l > r)
        return 1;
    if(val[l][r]!=-1)
        return val[l][r]；
    if(l==r)
        val[l][r]=a[l];
        rt[l][r]=a[l];
    else{
        for(int i=l;i<=r;i++){
            if(calc(1,i-1)*calc(i+1,r)+a[i]>val[l][r]){
                val[l][r]=calc(l, i - 1) * calc(i + 1, r) + a[i];
                rt[l][r]=i;
            }
        }
    }
    return val[l][r];
}

void output(int l,int r){
    if (r<l)
        return;
    printf("%d",rt[l][r]);
    output(l,rt[l][r]-1);
    output(rt[l][r]+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(val,-1,sizeof(val));
    printf("%lldn",calc(1,n));
    output(1,n);
    return 0;
}

(29)该程序的算法的时间复杂度为$O(n^3)$(✔)

calc函数对每个子区间都进行了$O(n)$复杂度的选值，

总共有$n^2$个子区间，故总复杂度为$O(n^3)$

(30)该程序在执行过程中不会出现数据类型的溢出。（ ✗）

calc函数返回long long类型，val采用int型存储，有溢出可能

(31)若输入数据能保证该程序在执行过程中不会出现数据类型的溢出，那么将第018行的“>”改为“>=”，对于相同的输入数据，程序输出的第一行结果不变。（ ✔）

第一行为左右子区间乘积值+中间值的选择的最大值，>=不影响数据大小的动态规划，仅影响可替换的rt中的结构

(32)若n的输入为4，程序输出的第一行结果最大可能为（ 1830 ）

读入每个数都取最大值，最后求出来的乘积和才为最大值，

故输入数据为4/30 30 30 30 的情况下,顶层calc的四种情况为

a[1]为中间值仅加上右子树的最大值30+30*30 最终为960

a[2]为中间值 $左子树右子树+a[2] = 30(30+30)+30 =1830$

a[3]为中间值 $左子树右子树+a[3]=30(30+30)+30=1830$

a[4]为中间值仅加上左子树的最大值30+30*30 最终为960

(33)若输入数据为6 / 7 1 5 8 8 2（这里的斜线表示换行），程序输出的第二行结果为（A 2 1 4 3 5 6）

推理

排除C与D，因为二者实际为同一个划分策略

排除B，因为A优于B

比较 A 和 F 和 E A为407 F为368，E为128

(34)若将第29行代码与第31行代码互换位置，输入数据同上一题，程序输出的第二行结果为（6 5 3 4 1 2）。

前序表达式变成了倒序表达式 $右-左-根$

画出树状结构，即可得出表达式

或者直接倒置上题A选项，因为前序表达式与倒序表达式拼接恰好为回文字符串

T3-1

（1）生产任务

给定$n$种零部件，第$i$种零部件有$x_i$个。现在要用这些零部件生产机器。机器有两种。每生产一
台机器A需要$a_1$个零部件1，$a_2$个零部件2……$a_n$个零部件$n$。每生产一台机器B需要$b_1$个零部件1，
$b_2$个零部件2……$b_n$个零部件$n$。假设任意一个零部件都不可以被切割使用，请计算最多可以生产出多
少台机器。
输入数据保证$1 ≤ n ≤ 100000，1 ≤ x_i, a_i, b_i ≤ 109$。

#include<cstdio>
#include<algorithm>
using namespace std;

long long n,x[100005],a[100005],b[100005];

bool check(long long k){
    long long l=0,r=k;
    for (int i = 1; i <= n; i++) 
        if(___①___){ 
            if (___②___) 
                return false; 
        }
        else{
            long long p = x[i] - b[i] * k; 
            long long q = a[i] - b[i]; 
            if (a[i] > b[i]) 
            r = ___③___; 
            else 
            l = ___④___; 
            if (l > r) 
               return false; 
        }
    return true; 
}

int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&x[i]);    //每种零部件的数量
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);    //生产机器A对每种零部件的单位需求
    for(int i=1;i<=n;i++)
        scanf("%lld", &b[i]);  // 生产机器B对每种零部件的单位需求
    long long l = 0, r = 1e9; 
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        ___⑤___ 
    }
    printf("%lldn", l);
    return 0; 
}

本题为基本二分算法

观察main函数中的l,r和mid声明，可以推测本题使用了二分

再次注意15行的$long~long~p~=~x[i]-b[i]*k$

可知$check(int~k)$通过代入B机器的生产数量计算A机器的生产数量

条件的两种状态影响下一次k的选择，$l==r$时候为全部机器的最大生产数量

(35)①处应填（E）

A．$a[i] < b[i]$
B．$a[i] <= b[i]$
C．$a[i] > b[i]$
D．$a[i] >= b[i]$
E．$a[i] == b[i]$
F．$a[i] != b[i]$

阅读程序可知未被覆盖的情况只有a[i]==b[i]

(36)②处应填（A）

A．$a[i] k > x[i]$
B．$a[i] k < x[i]$
C．$a[i] x[i] > k$
D．$a[i] x[i] < k$
E．$k x[i] > a[i]$
F．$k x[i] < a[i]$

如果a[i]==b[i] 则造A,造B在i零件的情况下代价一样，仅拿一个做判断即可

答案在A、B之间，但由于尚不清楚返回后的操作，故先跳过

(37)③处应填（B）

A．$max(r, p / q)$
B．$min(r, p / q)$
C．$max(r, p / q + (int)(p~mod~q != 0))$
D．$min(r, p / q + (int)(p~mod~q != 0))$
E．$max(r, p / q + (int)(p ~mod~ q == 0))$
F．$min(r, p / q + (int)(p ~mod~ q == 0))$

首先，p为造了k台B机器后，剩下的零件量，若p为负则为需要的零件量

q为A，B机器所需零件的差值,

$$
frac{x[i]-k*b[i]}{a[i]-b[i]}=t
$$

$$
x[i]-ta[i]-(k-t)b[i]=left
$$

且有

$$
p~mod~q ~=~left
$$

故而

$$
x[i]-ta[i]-(k-t)b[i]=p~mod~q
$$

此时$p~mod~q$若等于0则说明x[i]已全部用光

若不为0,a[i]>b[i]时，a[i]-b[i]不能补充需要的零件量，仅能消耗剩下的零件量，故不操作，仅为p/q

r用于记录t能取的最大值，r初始值为k，若要更新仅能取小，故选择B

(38)④处应填（C）

A．max(l, p / q)
B．min(l, p / q)
C．max(l, p / q + (int)(p % q != 0))
D．min(l, p / q + (int)(p % q != 0))
E．max(l, p / q + (int)(p % q == 0))
F．min(l, p / q + (int)(p % q == 0))

分析同上，注意到此时a[i]<b[i]，此时$p~mod~q$若不为0(小于或大于),，则剩下的零件可以多制造一台机器A,

l用于记录t能取的最小值，故选择C

(39)⑤处应填（C）

A．if (check(mid)) l = mid; else r = mid;
B．if (check(mid)) l = mid; else r = mid + 1;
C．if (check(mid)) l = mid; else r = mid – 1;
D．if (check(mid)) r = mid; else l = mid;
E．if (check(mid)) r = mid; else l = mid + 1;
F．if (check(mid)) r = mid; else l = mid – 1;

check在最大值小于最小值时返回false，说明k值太大应当减小，则36题为A

二分的目的是为了让数据区间减少一半，故而本题选择C而非A,B

T3-2

给定n个结点的无向图，结点编号1至n。图中共有n条边。每条边恰好连接着两个不同的结点。

每个结点恰好连接着两条无向边。现在，我们要对每个结点染色，但任意相邻的两个结点不可以被染
成相同的颜色。假设可选的颜色共有k种，请计算共有多少种不同的合法染色方案（对于两种方案，
假设存在某一编号的结点在两方案中被染了不同颜色，则认为这两种方案是不同的）。
输入数据保证1 ≤ n ≤ 100000，1 ≤ k ≤ 109。

#include<cstdio>
#include<cstring>
#include<algotithm>
using namespace std;

const int MOD =1e9+7;
int n,k,adj[100005][2],cnt[100005];
long long f[100005];
bool vis[100005];

long long fpow(int x,int k){//快速幂
    long long ans=1;
    for(;k;k>>=1,x=x*x%MOD)
        if(___①___)
            ans*=x;
    return ans;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1,a,b;i<=n;i++){
        scanf(%d%d",&a,&b);  // 每条无向边连接的两端结点
         if (adj[a][0]) adj[a][1] = b; 
            else adj[a][0] = b;
        if (adj[b][0]) adj[b][1] = a;
            else adj[b][0] = a;
    }
     for (int i = 1; i <= n; i++) {
        if (vis[i]) continue; 
        int len = 1, x = i; 
        vis[x] = true; 
        while (1) {
            if (adj[x][0] && !vis[adj[x][0]]) { 
                 x = adj[x][0];
                 vis[x] = true;
                 len++; 
            } 
            else if (adj[x][1] && !vis[adj[x][1]]) {
                x = adj[x][1]; 
                vis[x] = true;
                len++;
            }
            else break; 
        } 
        cnt[len]++; 
    } 
    f[1] = ___②___;
    f[2] = 1LL * k * (k - 1) % MOD;
    f[3] = ___③___; 
    for (int i = 4; i <= n; i++) 
         f[i] = ___④___; 
    long long ans = 1; 
    for (int i = 1; i <= n; i++) 
        if (cnt[i]) 
            ans = ___⑤___; 
    printf("%lldn", ans);
    return 0; 
}

离散数学中经典的染色问题
因为每个点都与两个不同的点连接，且有n个点和n条边，根据图论的知识可得知这是一张首尾相衔的简单环
输入数据中通过读入每条无向边连接的两端节点来构建此环
本题的预处理阶段具有极大的迷惑性，仿佛此图为一个森林，实则不然，因为n个点n条边的无向简单图只有一种可能

(40) ①处应填(D)

A. k / 2 == 0
B. k / 2 != 0
C. k % 2 == 0
D. k % 2 != 0
E. k & 2 == 0
F. k & 2 != 0

fpow函数是显而易见的快速幂
k%2!=0暨是k二进制的此刻最低位为1
此时可以用ans*=x,x取$1,2,4,8,16….2^n$

(41)②处应填（B）

A.1
B.k
C.k-1
D.k+1
E.k-2
F.k+2
f[1]对应了第一个点可染的颜色数故选B

(42)③处应填(F)

A. 1LL k (k + 1) % MOD
B. 1LL (k + 1) (k + 2) % MOD
C. 1LL k k % MOD (k + 1) % MOD
D. 1LL k k % MOD (k – 1) % MOD
E. 1LL k (k + 1) % MOD (k + 2) % MOD
F. 1LL k (k – 1) % MOD (k – 2) % MOD

f[2]为长度为2的链可染的颜色数,直接为k*(k-1)

f[3]为长度为3的链可染的颜色数,易得出$k(k-1)(k-1)$ 并无此答案，考虑实际为长度为3的头部固定的环的染色数，

故得出$f[3]=k(k-1)(k-2)$

(43)④处应填(F)

A. (f[i – 1] (k – 1) + f[i – 2] (k + 2)) % MOD
B. (f[i – 1] (k – 2) + f[i – 2] (k + 1)) % MOD
C. (f[i – 1] (k + 1) + f[i – 2] (k – 2)) % MOD
D. (f[i – 1] (k + 2) + f[i – 2] (k – 1)) % MOD
E. (f[i – 1] (k – 1) + f[i – 2] (k – 2)) % MOD
F. (f[i – 1] (k – 2) + f[i – 2] (k – 1)) % MOD

见递推式，考虑当前问题与子问题的关系

结构上来说,长度为i的环仅仅比i-1的环多增加了一个点,但位置不同会导致染色数的不同

如果在$[a,a+1]~~~a∈[1,i-2]$之间插入，$f[i]~=f[i-2]*(k-1)$

如果在$[i-1,1]$之间插入，$f[i]~=f[i-1]*(k-2)$

加法原理可得$f[i]=f[i-1](k-2)+f[i-2](k-1)$

(44)⑤处应填（A）

A. (ans fpow(f[i], cnt[i])) % MOD
B. (ans + fpow(f[i], cnt[i])) % MOD
C. (ans fpow(f[i], cnt[i] – 1)) % MOD
D. (ans + fpow(f[i], cnt[i] – 1)) % MOD
E. (ans * fpow(f[i], cnt[i] + 1)) % MOD
F. (ans + fpow(f[i], cnt[i] + 1)) % MOD

此时根据题意可知ans并不是一个头部固定的环的染色数，故需要对其排列,

本题具有迷惑性,实际上只需要对f[maxlen]的情况进行计算

现在只需要考虑每个点都为开头的情况，乘法原理可知只需要连续相乘即可计算

故$ans=f[maxlen]^{maxlen}$，正好是A

作者： PsyChen

“Though this be madness,there is method in it.” 查看PsyChen的所有文章

BCSP-X大题题解

T2-1

(16)若将第002行的“using namespace std;”删去，程序仍可以正常执行，且对于相同的输入数据，输出结果不变（✔）

(17)若将第003行的“int”改为“long long”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（✗）

(18)若将第 013 行的“++p[i]”改为“p[i]++”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（ ✗）

(19)若将第 014 行的“++ans”改为“ans++”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（✔）

(20)程序输出的 ans 值不可能为 0（✔）

(21)该程序的算法时间复杂度为（$O(n)$ ）

(22)程序输出的 ans 值最大可能为（2n-1）

T2-2

(23)valid 函数的算法时间复杂度为 O(k)（此处的 k 特指程序输入的 k）（✔）

(24)若将第 005 行改为“for (int i = 0; i < k; i++) {”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（✗）

(25)若将第 018 行的“k + 1”改为“k”，程序执行或许会变慢，但仍可以被正常执行，且对于相同的输入数据，输出结果不变。（✗）

(26)程序输出的m值最小可能为（1）。

(27)若输入的k为4，程序将输出(32)

(28)若输入的k为5，程序将输出（）

T2-3

(29)该程序的算法的时间复杂度为$O(n^3)$(✔)

(30)该程序在执行过程中不会出现数据类型的溢出。（ ✗）

(31)若输入数据能保证该程序在执行过程中不会出现数据类型的溢出，那么将第018行的“>”改为“>=”，对于相同的输入数据，程序输出的第一行结果不变。（ ✔）

(32)若n的输入为4，程序输出的第一行结果最大可能为（ 1830 ）

(33)若输入数据为6 / 7 1 5 8 8 2（这里的斜线表示换行），程序输出的第二行结果为（A 2 1 4 3 5 6）

(34)若将第29行代码与第31行代码互换位置，输入数据同上一题，程序输出的第二行结果为（6 5 3 4 1 2）。

T3-1

（1）生产任务

本题为基本二分算法

(35)①处应填（E）

(36)②处应填（A）

(37)③处应填（B）

(38)④处应填（C）

(39)⑤处应填（C）

T3-2

(40) ①处应填(D)

(41)②处应填（B）

(42)③处应填(F)

(43)④处应填(F)

(44)⑤处应填（A）

作者： PsyChen

发表回复取消回复

2024 年 12 月
一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

T2-1

(16)若将第002行的“using namespace std;”删去，程序仍可以正常执行，且对于相同的输入数据，输出结果不变（✔）

(17)若将第003行的“int”改为“long long”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（✗）

(18)若将第 013 行的“++p[i]”改为“p[i]++”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（ ✗）

(19)若将第 014 行的“++ans”改为“ans++”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变（✔）

(20)程序输出的 ans 值不可能为 0（✔）

(21)该程序的算法时间复杂度为（$O(n)$ ）

(22)程序输出的 ans 值最大可能为（2n-1）

T2-2

(23)valid 函数的算法时间复杂度为 O(k)（此处的 k 特指程序输入的 k）（✔）

(24)若将第 005 行改为“for (int i = 0; i < k; i++) {”，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（✗）

(25)若将第 018 行的“k + 1”改为“k”，程序执行或许会变慢，但仍可以被正常执行，且对于相同的输入数据，输出结果不变。（✗）

(26)程序输出的m值最小可能为（1）。

(27)若输入的k为4，程序将输出(32)

(28)若输入的k为5，程序将输出（ ）

T2-3

(29)该程序的算法的时间复杂度为$O(n^3)$(✔)

(30)该程序在执行过程中不会出现数据类型的溢出。（ ✗）

(31)若输入数据能保证该程序在执行过程中不会出现数据类型的溢出，那么将第018行的“>”改为“>=”，对于相同的输入数据，程序输出的第一行结果不变。（ ✔）

(32)若n的输入为4，程序输出的第一行结果最大可能为（ 1830 ）

(33)若输入数据为6 / 7 1 5 8 8 2（这里的斜线表示换行），程序输出的第二行结果为（A 2 1 4 3 5 6）

(34)若将第29行代码与第31行代码互换位置，输入数据同上一题，程序输出的第二行结果为（6 5 3 4 1 2）。

T3-1

（1）生产任务

本题为基本二分算法

(35)①处应填（E）

(36)②处应填（A）

(37)③处应填（B）

(38)④处应填（C）

(39)⑤处应填（C）

T3-2

(40) ①处应填(D)

(41)②处应填（B）

(42)③处应填(F)

(43)④处应填(F)

(44)⑤处应填（A）

作者： PsyChen

发表回复 取消回复

(28)若输入的k为5，程序将输出（）

发表回复取消回复