前言

本文用于记录笔者在北航OJ上的做题记录，将会把一些遇到困难/有趣的题目做法记录下来，供自己复习以及后来者参考。做题过程中有不会的题目参考了北航OJ通关攻略

程设

17级信息类程设

第一次上机

C 你会向上取整嘛？

用ceil函数逃课

F N*3 + 1 problem

使用龟速乘防止爆ll

第一次练习赛

B 你会写月份的英文吗

用std::map存储月份和月份的英文，然后用find函数查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
  int num;
  cin >> num;
  map<int, string> mp;
  mp[1]  = "January";
  mp[2]  = "February";
  mp[3]  = "March";
  mp[4]  = "April";
  mp[5]  = "May";
  mp[6]  = "June";
  mp[7]  = "July";
  mp[8]  = "August";
  mp[9]  = "September";
  mp[10] = "October";
  mp[11] = "November";
  mp[12] = "December";
  if (mp.find(num) != mp.end())
    cout << mp[num];
  else
    cout << "Wrong month";
}

第二次上机

D 成双成对的尾巴

枚举猜出规律，然后打表

E QZZ的世界观测

先对面积排个序，必然是大的包住两个小的，之后的包含便只有8种情况，枚举即可

第二次练习赛

C 逆序对统计

归并排序求逆序对数量，暂时还不会（哈哈，大类招生）

E 阶乘的小尾巴

数学，不会

第三次上机

C TQ有点二

__builtin_popcount只能数32位的，所以用不了
此外，暴力移位会T掉
观察（百度）可得，n每与上n-1一次，1的个数就减一，所以只要不断与上n-1，直到n为0，就可以得到1的个数

第三次练习赛

B 翻转数字

strtoll,atoll,atoi用起来

D 一段楼梯有n级

递推：有n个台阶时，设有count(n)种走法，最后一步走1个台阶，有count(n-1)种走法；最后一步走2个台阶，有count(n-2)种走法。于是count(n)=count(n-1)+count(n-2)。

E 求凸多边形面积

把第一个点作为顶点，此后每两个相邻的点作为底边端点，计算三角形面积，累加即可。三角形面积使用叉乘求解，因为叉乘带正负，所以要套一层abs。
推广：任意多边形？凸包？

第四次上机

C 数字统计

不使用前缀和优化也可过

E 金币

不使用前缀和优化也可过

第四次练习赛

A three investigators

STL字符串的使用还要继续加强

22级信息类程设（不开放）

第一次上机

J 繁琐的识别mini

注意处理多位数和以负号开头的表达式

第一次练习赛

G 字符处理机器

输出一些字符时候要加上反斜杠

I 组三角形

考察博弈论，奇数个数的时候先手必胜，偶数个数的时候后手必胜。
偶数时候后手只需看最大数，先手拿走哪个数，后手就拿走最大数-先手者拿的数，例如21=1+20=2+19…先手者拿20就拿1，这样最后就会剩下一个最大数和一组和等于最大数的数，不能组成三角形。如果先手者拿21，那么最大数变成20=1+19=2+18..中间剩一个10，拿走它，回到前述情况。
奇数时候先手者只需拿走最大数，后手者就会面对偶数的情况时的先手。

J 有理数

一条斜对角线上分子分母和为定值。
除此之外，可以通过分析算出一条对角线上假分数的个数。

第二次上机

J void学英语

哈哈，读入一个数之后记得吸一下换行符啊！不然下一行用gets，cin.getline读入字符串会读入该换行符
windows的换行符是\r\n,linux的换行符只有\n，在windows系统下用gets会吞掉每一行最后面的\r\n,但是linux下用gets只会吞掉最后一个\n
那么问题来了，如果数据是在windows环境下构造的，换行符用的是\r\n，但是服务器是linux，管理员直接把windows下生成的数据没经过任何处理就移动到了linux的服务器里
在oj的测评时，每一行的最后都会多一个\r,所以有时候会稀里糊涂的wa
fgets保留换行符，所以输出时候使用printf就自带换行了

K 作业调度

对于每一个任务单独处理，分为到达时间是否早于上一个任务完成时间讨论。

第二次练习赛

F 五八三十五

熟练掌握把数的每一位取出来的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (1) {
  while (x) {
    if (num[x % 10])
      num[x % 10]--;
    else {
      cout << ans;
      return 0;
    }
    x /= 10;
  }
  backup_x++;
  x=backup_x;
  ans++;
}

G 魔法实验1.0

偶数每次除以2不一定得到偶数，所以对于一个偶数化奇的最优办法是和奇数相加。
因此，存在奇数时，和每一个偶数相加即可。
否则，找到一个为了变成奇数，除以2次数最少的偶数，浓缩成奇数，再和每一个奇数相加。

H 眼睛哥的时间

I 哪吒的水题（一）

J 回文日期

遍历一年中每一个合法的月和日，根据四位数字构造出对应的回文日期。
之后，找到最近的一前一后回文日期。（办法是遍历时候每轮更新）
最后计算相差的天数。

第三次上机

E 翻转正整数

1
2
取出整数a高位示例: a&0xffff0000
取出整数a低位示例: a&0x0000ffff

G void学数学

位运算会超时
直接统计次数，只出现一次的数输出就行了…
还有，多测不清空，爆零两行泪：memset(times, 0, 5010*sizeof(int));

I 反码计算机

先来复习一下三种码的概念：
原码：符号位+数值的二进制表示
反码：正数的反码就是原码，负数的反码是对应正数取反。
补码：正数的补码就是原码，负数的补码是对应正数取反再加1。（没有符号位一说）
根据反码的定义，正数的反码就是原码，负数的反码是对应正数取反。
如果是正数，本身即为反码，如果是负数，就直接对对应的正数取反就能得到反码了。
之后再使用C语言的位运算即可解决本题。
当然同样的，输出的时候也是先判断数字的正负，对于负数，先输出符号，再将数字取反后输出。
充分利用sscanf判断正负号读入：

1
2
3
4
if (sscanf(a, "-%d", &a_num))
  a_num = ~a_num;
else
  sscanf(a, "%d", &a_num);

J 不可分解的01串

润了

第三次练习赛

C 去买花生

第一个数字根本没用。吃完了之后要用getchar连着吃两次才能接下来读入字符…

D 重炮的进制转换

对每一位十六进制数字，首先将读入的字符型变量转换成对应的整型变量，然后依次取出该整型变量的二进制表示
的后四位并输出即可。

E 十进制数按位与

对个位进行取最小值并输出就可以了，注意处理0，我用了一个栈存的倒序输出，要去除前导0的同时还要注意数字一开始就等于0的情况，这时不用去除0了，直接输出0之后程序结束。

H AsadaShino的分组加密

1
2
3
4
5
6
7
8
9
10
printf("%04X", a[i]);//打印四位十六进制，字母用大写输出
test1 += __builtin_popcount(tmp);
//查询十六进制的每一位上是否为字母（每一位取出来大于9）
while (tmp)
{
  if (tmp % 16 > 9)
     test2++;
  tmp /= 16;
}

G 二舅也许能治好我的精神内耗

分奇偶讨论，奇数无解。注意到0异或x＝x，因此两个0和一个x/2

I 狼了个狼

分解质因数，每个因子只出现一次乘起来就是最小值，至于操作次数要将因子出现次数向上匹配到一个2的幂，然后再判断是否需要扩增倍数。

J ACM组队

用unordered_map存索引再遍历搜索哪个次数为1会超时。
满分做法暂时没有学会

第四次上机

H 式神们夜里不睡觉

通过10进制数为中介完成。
注意负进制的整除取余数，顺次倒写这一过程中余数可能为负数。由于除数一定是负数才能导致这种情况，所以可以从商“借”1，加到余数中使得其为正。
注意我们算余数时候是一直除以进制数，除到商为0为止，但如果一开始就是0则需要特判一下，0在任何进制都是0

I 破损的三角铁

用4根铁棒组成正三角形，则必有两个相等边，另外两根铁棒较短，加和之后相等，注意到5000的数据范围，所以时间复杂度O(n2)可以通过。枚举所有的长度，记numi为该长度木棒的数量。首先选取两根长度为i的木棒，接着二重循环从1枚举j（！！终点是i-j等于j且可以取到这一情况才算结束），则另一根木棒为i-j。接着分i-j是否与j相等讨论，计算出选择的方案数，用乘法原理相乘。不要忘了途中取模。

第四次练习赛

F Cirno的完美位运算教室2022

lowbit运算：x&-x，返回x的二进制表示中最低位的1所对应的数值。
我们知道，一个负数的补码是其绝对值的原码取反加一，有了这个前置知识，这个运算的实现原理
留给读者思考。
有了lowbit运算之后就很好分析了，题目要求的y，需要至少有一位与x都是1，至少有一位与x不同。

  1. x如果是1，y等于3
  2. x只有一位1，且这个1不在最低位上，则y等于x+1
  3. x有多位1，则lowbit值即为所求

G 魔理沙的行窃预兆1

DP，dp[1]=0，从dp[2]开始计算，在前面的格子中，选择能到达的本格的，再取dp的min

H 希卡式打孔纸带·alter

感谢2006 Oshwiciqwq和2109 BenWalker的讲解。
反向思考，题目的两种操作可以反向为：

  1. 反转
  2. 把尾部为0的数右移，并在前面补上任意数（因为在原来左移时这些高位是被舍弃的）

考虑把目标数经过一定数量的操作变成1：

  1. 尾部为0则右移。为什么不选择反转？因为反向时从0翻转到1相当于正向的从1到0，而起点1是有许多0的，只有1需要通过反转制造出来。因此，选择反转会导致操作次数增加。
  2. 特例：-2的补码为111110，这时只需要取反一次就回到起点000001，需要特判。
  3. 最终数变成1
  4. 操作的过程中出现0，在操作的过程中要给次数32后直接结束，否则因为0右移始终得0，会死循环
  5. 前述右移时，到底补充什么数？考虑正着左移之前的情况，要么最高两位不同，要么最高两位相同。最高两位不同，说明最高位之前取反过一次，但此时这个最高位要消失了，之前的取反就浪费了一次，所以在次数最少的情况下，不会让他不同。

第五次上机

I 隔板问题

递归解决。由于题目要求输出每一种方案，因此需要用全局数组保存方案。为了和下标统一，递归函数的参数最好设置为“当前正在处理第几组”，而不是“还剩几个隔板”，这样递归那一组时候，便能找到对应下标存进去了。