静静的小窝

这是之前出的一道题，稍微进行了一些小修改。
题目链接:https://codeforces.com/contest/894/problem/A

1. 最简单的方法就是搜索遍历所有的可能的排列情况，即枚举结果字符串的每一位在原字符串中的位置，故复杂度为$O(n^3)$，如果需要的匹配的字符串更长，那么复杂度更高。

2. 随后可以发现目标字符串要完全符合要求，意即只要有一位不符合就一定不被计算，故可剪枝，只有当前面的字符串都符合要求的时候才继续遍历，常数可以进行优化为原来的$\frac{1}{26}$，但复杂度仍旧不变。

3. 从前面的剪枝可以发现并不一定要遍历每种可能才可以，可以保存中间量直接相加即动态规划。

可以一维存储原字符串的下标，一维存目标字符串的下标，表示到目前为止符合的字符串数量，随后从前往后相加得最后得数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

for (int j = 0; j < 105; j++)
{
    for (int i = 1; i < 5; i++)
    {
        dp[i][j] = 0;
    }
    dp[0][j]=1;
}
for (int j = 0; j < st.length(); j++)
{
    for (int i = 0; i < 3; i++)
    {
        if (st[j] == base[i])
        {
            dp[i + 1][j + 1] = dp[i][j] + dp[i+1][j];
        }
        else
        {
            dp[i + 1][j + 1] = dp[i + 1][j];
        }
    }

最后输出dp[3][st.length()]作为答案。

可以注意到过程当中一直是dp[i]到dp[i+1]，说明实际并不需要这一维度，可以删去这一维度到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

for (int i = 1; i < 5; i++)
{
    dp[i] = 0;
}
dp[0] = 1;
for (int j = 0; j < st.length(); j++)
{
    for (int i = 0; i < 3; i++)
    {
        if (st[j] == base[i])
        {
            dp[i + 1] = dp[i] + dp[i + 1];
        }
        else
        {
            dp[i + 1] = dp[i + 1];
        }
    }
}

同时注意到else实际上什么都没有做，可以直接删去。

这是几个月前的VY223的周记，放出来和大家交流一下。

Journal 1

It’s the first week of my Summer 2022, the term with VY223, which is also my first full online term. Fully online gives more challenging with some advantages. For example, I could read more times in the chat box rather than just listen to others’ works one time.

There are many reasons why I take this class as an engineering student.

First, I think there are no conflicts between engineering and creative writing. Let me provide some conditions that it helps. This week, the Student Science and Technology Innovation Association of JI, cooperating with other institutes, organized a competition in computer programming. Instead of just giving definitions directly, we need to use a story to make them up to help to understand.

Also, I need HU course credits. So I chose many classes in the first and the second round of course selection because there were much more people who want to have HU classes than the maximum limits, so I selected many classes to increase the chance that I could get one HU class. Luckily, I caught VY223 from other candidates.

During the third round, I received many emails, telling me that some courses had empty seats to select. However, I didn’t drop VY223 for its first experience, in which I followed the instruction to finish a short story. The process, that writing sentences to build a grotesque universe without thinking of detailed logic relations at first and then adding details to fill the story, lured me in immediately.

For me, a person who prefer science fiction and detective novels, a good idea is the soul of a story. For example, Around the World in Eighty Days written by Jules Verne is a story about a debt that whether one can travel around the world in eighty days. The best point I think is that after failing to come back to London on time, they surprisingly got one more day thanks to the time zone. Points like that make a story good because it will never let you down at the end of the story with many hints through the story.
For a short story, like the one we make in the first class, a clear aim should be given to the main character which could lead to the development of the story and keep the readers’ will to explore what will happen or why something happened. What’s more, not like stories that have more space to introduce the background at the beginning of the story, short stories can give hints about the world during the actions of the main character that leave enough space for the readers to have their own understanding.

John died.

Mr. Smith opened his diary with a strong sense of curiosity, wondering what made him stir the city for a month. Reading John’s diary, Smith believed he knew what happened.

Everything started two months ago which was the time John started his diary by his self-introduction “As one of the young individuals who had just graduated as a doctor in 2050, full of hope in life, John, the writer, is sitting behind the screen, with his hands flying above the keyboard.”, followed by his recalling what his parents told him when he was young.

现在做梦，常常是把小学初中高中的元素搅和在一起，魔幻地学习，考试。就让我在这里也魔幻一点吧。

　　月黑风高夜，刹那间，铃声打破了那沙沙声统治的寂静，信使飞遍校园，透入每一个忘记时间者的心。教室内，走廊上，厕所中，办公室里，电脑房的黑暗下，每个人顿了一下，把离开程序载入内存。

　　有的CPU空闲的人即刻读取执行，趁其他人的卡顿冲入食堂，只留给后来者一条巨龙；有的人修改优先级，拿下了最后的夜宵；也有的人慢慢悠悠关闭电源，遁入黑暗中，在校园的隧道里穿梭，或重回光明，或重现于黑暗中以机械波代 that of 电磁会友。那些配置差，系统加载错的人就惨了，程序直接从内存中抹除了。十余分钟后，当最后的答疑结束，负荷逐渐降低，查看日志时，惊叫：惨了，书包还在教室里。

　　什么？你问我为什么这么清楚？那当然是因为，这就是我！

　　冲出办公室，右边是白色的走廊，左边，是黑的五彩斑斓的教室窗户，反射的五颜六色掩盖不了折射的暗淡。一间，两间，三间，好的，它黑了。锁上的有后门，锁上的也有前门。趴在窗户上，五彩斑斓不见了，只有前后空调不断发出的声光（幸好没有电）扰动着我的心。

　　老师从旁边经过，给我支了一个招，从窗户翻进去。翻窗，不是什么难事。上课前总有好心的同学翻进去帮忙打开锁住的门。可是，我却从来没有这么干过。窗不是落地窗，翻前要先翻墙。说是墙，却又不高，矮矮的墙在我眼前是如此高大：要不算了，找保安吧。

　　幸好，有老师的帮助，${动作描写}。

　　回到寝室，一边写作业，一边回想晚自习发生的事情。

　　作业做完，趴在桌子上睡，不知多久，接连的声音从旁发出。啊，不知道是谁拿来了一个电蚊拍，关闭教室的灯光，烟花不止地绽放（注：学校不处于管制范围内。）。许是累了，那布朗运动的星向着地平线趋近，最后是tan90°的光与激昂的交响乐。

　　离开教室，回头看去，窗户下不再有原来的光亮，而是一层又一层的黑。

　　继续走，到二楼，走到楼的最西边，沿着楼梯向上爬。咔擦，不可一世的把手向我臣服。走进房间，找到一台电脑，享受沐浴。

　　写好作业，从厕所走出，关灯，睡觉。

这是春季学期的周记作业中的一篇，提到的比赛是蓝桥杯，祝我国赛顺利。

I want to write down what I experienced this weekend about booking a bus. A computer programming contest will be held on a campus of USST, which is in the northeast of Shanghai, at 9 a.m. and many JI students are willing to take part in it and thus it is decided to book a bus for students to come there. I was assigned to book the bus of SJTU’s logistics department.

省赛的经历在写作业的时候写了一部分。比赛过程中感觉自己好久没有打过比赛了，非常不自信，基本上按着最稳的写法写，能短则短，像最短路也是三重循环，害怕自己哪里有疏忽（但还是浮点数操作出了问题）。一个感觉就是之前一位填答案题是比较简单的，但是做了之后发现其实时空限制放宽了，但是必须保证自己写对，不能有一点问题，而写代码的题目根据题目条件还有拿部分分的可能。国赛的时候还是求稳，算质数还是暴力法（一开始数组开小了还炸了一次）。少数的没有暴力的也没有来得及对拍测验。只能说还是离开NOIP很久了，完全没有感觉，也忘了不少东西。不过蓝桥杯能查函数还是很好的，之前高中有一次优先队列忘记拼写，还是到头文件库里找的。希望这次国赛能有个好成绩吧。
写了个题解，大家可以看看。

此文使用了mathjax，请等待公式加载
这是2021年蓝桥杯国赛A组C++的一道题目。

　　首先考虑异或操作的特性，可以交换，所以不妨考虑 $a \geq b \geq c$的情况。随后根据三个数字异或为0，不难看出每一位的异或结果都是0。这也就是说每一位的三个数字只有两种可能，2个1一个0或三个0。不难知道a的首位一定是1，所以另外两个数字在此处必为一1一0。可由此用反证法证明3个数必不相等：
　　如果三个数相等，二进制下首位必相等，与首位一1一0矛盾。如果只有两个数相等，那么这两个数在2进制下必定同1同0。为了满足三个数异或为0，第三个数每一位都只能为0，得出第三数为0，无法形成三角形。