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
