T1 摘水果

签到题。

T2 纸牌计数

你有n张牌和m个字符串(m<=n<=60),每张牌上文字形如"1C","2A"(数字+字母),字符串形如(1)"1C"(2)"?C"(3)"??",其中?表示通配符,求从n张牌无放回抽m张能与m个字符串匹配的概率。
m张牌与m个字符串匹配当且仅当：存在一个一一映射f,使得字符串i和牌f(i)匹配，即字符串i和牌f(i)的每一位要么相同，要么有一个为"?".

题解：背包dp.
设f[i][j][k][p]表示处理到第i个字母第j个数字牌,目前已经用了k张?i牌,p张??牌,设(1)对应牌数为s(i,j),总牌数card(i,j),则
\( f[i][j][k][p]=\Sigma_{q,r} f[i][j-1]
[k-q][p-r]*C(card(i,j),q+r+s(i,j)) \)
\( f[i][0][k][p]=f[i-1][9][s(i-1)][p] \)

T3 SQL查询

实现一个SQL解释器，能够执行基本的SQL查询任务（仅限SELECT的部分句式）。数据表有五种形式，内容在输入最开始给出。
一些较难的句式如支持两表连接查询"(WHERE) COLUMN = COLUMN".
表长(行数)n<=10000.

题解：没有什么特别坑点的题，将查询问句拆成若干个部分分别解析即可。由于n<=10000,两表暴力查询是o(n^2)会T，故还要采用map/hash等优化.
顺带一提，题面还指出本题测试数据的询问句式为下发样例子集，所以用if-else也能解题。

T4 调度器

实现一个单核CPU、IO的调度函数，调用函数时发生的事件包括"时间片结束","某新任务到来","某任务运行结束","某任务请求IO","某任务IO结束请求CPU".每个任务不能同时占用CPU和IO资源，且CPU,IO资源分别只能同时给一个任务使用。每个任务有高低两个优先级之分，并给出了start_time和ddl，最终分数为在ddl内完成的高优先级任务数0.7+低优先级ddl内完成任务数0.3.最后还有性能分测试。

题解：据说写FIFO能够骗到50分.
根据评分规则，显然应当将ddl靠前的任务优先做完，其次优先级高任务要优先做完。还有就是如果某个请求执行时间太长则优先级应当降低。还有一个优化是如果一个任务已经超过了ddl则优先级应当降到最低。如果参数调整很好应该能拿到很高的分数。

T5 评测鱼

本问题分为四个子问题，需要写一段在32位RISC-V架构CPU上运行的汇编代码，在正确基础上时钟周期最少。
RISC-V的特点：5级流水、无cache、无分支预测
下发文件提供了RISC-V-gcc/g++编译器，可以编译得到RISC-V能运行的汇编代码。
下发的测试文件能够精确计算运行花费的时钟周期数.
你不能使用任何c/c++标准库.

t1 amulb

输入a,b,输出a*b.

仿照下发样例aplusb中a+b的结果（如下），只需一个周期即可完成任务.
mul a0, a0, a1

t2 fib

求fibonacci[n]%m. (n<=10^5,m<=10^8)

线性做法能得到6分左右.
由于RISC-V的特性，访问内存仅需1周期，故对于小数据(n<=40)可以提前打表；同理线性做法用f[i]=f[i-1]+f[i-2]实际比z=y+x,z=y,y=x更快.
更快解法使用矩阵快速幂求fib/倍增求fib,此时会遇到两个int相乘爆int的问题(32位不支持LL),所以还要手写快速加法。
trick:有人利用提交到OJ上反馈的时钟周期结果反推输入数据,可以说是非常有才了(

t3 sort

sort.

快速排序/基数排序/归并排序,归并似乎会T.
高分解法为针对不同范围的n用不同的基数进行排序.
先写一个c代码,再利用工具编译后提交.s文件即可，如果编译开O3得分会显著提高.

t4 fruit

T1做成函数.

原方法为o(n^3)(n<=100),似乎可以用线段树优化到o(n^2).不过如果o(n^3)写得好也能拿到不错的分数.