第一讲C++

第一题Long Loong
For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.
You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.
思路：1.输入n；
2.先输出L；
3.通过for 循环输出N个o；
4.输出ng；

第二题YES or YES?
There is a string s of length 3, consisting of uppercase and lowercase English letters. Check if it is equal to "YES" (without quotes), where each letter can be in any case. For example, "yES", "Yes", "yes" are all allowable.
思路：因为yes的形式可以是YES,YEs,YeS,Yes,yES,yEs,yes,yeS.对每个进行判断较繁琐，所以我将输入的s每个字母转成大写，将其与YES进行比较

第三题Even?Odd?G
Bessie那惨无人道的二年级老师搞了一个有 N 个正整数 I 的表叫Bessie去判断“奇偶性”（这个词语意思向二年级的学生解释，就是“这个数是单数，还是双数啊？”）。Bessie被那个表的长度深深地震惊到了，竟然跟栋栋的泛做表格一样多道题！！！毕竟她才刚刚学会数数啊。
写一个程序读入N个整数，如果是双数，那么在单立的一行内输出"even"，如果是单数则类似地输出"odd".
思路：对于奇偶性判断，首先想法是将一个数除以2，若能整除则为偶数，若不能整除则为奇数。但在这题中，数字最大可到10的60次方，在C++中会溢出，并且，每个数字最后一位数字的奇偶性和数字本身奇偶性一致，所以可以只将每个数字的最后一位数字提取出来，判断最后一位数字的奇偶性。

第四题Problem Generator
Vlad is planning to hold m rounds next month. Each round should contain one problem of difficulty levels 'A', 'B', 'C', 'D', 'E', 'F', and 'G'.
Vlad already has a bank of n problems, where the i-th problem has a difficulty level of ai. There may not be enough of these problems, so he may have to come up with a few more problems.
Vlad wants to come up with as few problems as possible, so he asks you to find the minimum number of problems he needs to come up with in order to hold m rounds.
For example, if m=1, n=10, a= 'BGECDCBDED', then he needs to come up with two problems: one of difficulty level 'A' and one of difficulty level 'F'.
思路：1.先统计已有的题目中，每种难度的题目有多少题；
2.通过循环判断每种难度题目还需几题；
3.将每种难度需要题数相加.

第五题rules
小A制定了一些规则，每条规则有一个代号，代号为不超过10的9次方的非负整数。
小A的国家有n位居民，每位居民每天会且仅会遵守1条规则。小A记录了m天里每天每位居民遵守的规则代号。
现在小 A 想要考察代号为k的规则是否符合民意，具体考察方法如下：
• 如果在某一天里，有大于等于一半的人遵守了规则k，那么小A认为在这一天规则k是符合民意的。
• 如果在大于等于一半的天数里，规则k符合民意，那么他会认为规则k是正确的。否则，他会认为规则k是错误的。
如果小A的规则k是正确的，请你输出YES，否则请你输出NO。
思路：1.通过循环对一天中遵守规则k的人数进行统计；
2.判断这一天规则k是否符合民意，若符合则cnts+1；
3.通过循环统计m天中规则k符合民意天数；
4.判断cnts是否大于等于m的一半.

第六题Many Replacement
You are given a string S of length N consisting of lowercase English letters.
You will perform an operation Q times on the string S. The i-th operation(1≤i≤Q) is represented by a pair of characters(ci,di), which corresponds to the following operation:
• Replace all occurrences of the character ci in S with the character di.
Print the string S after all operations are completed.
思路：这题最开始想的是通过循环q次每次都在循环n次将str逐个转换，但考虑到1<=n<=2e5，每次循环都转换必然超时。所以考虑找到26个小写单词在q次转换后每个对应的字母。

第七题 更好的交换
小 S 有一个奇怪的机关拼图。这个拼图可以看作一个 n行 n 列的方阵 A，第 i行第 j列的位置上有一个正整数 Ai,j。
与寻常拼图不同的是，这个机关拼图上的数字不能随意移动，必须按照如下规则之一操作：
• 选择拼图上的第 x行和第 y 行，交换这两行；
• 选择拼图上的第 x列和第 y列，交换这两列。
为了复原这个拼图，小 S 将会操作共 m 次，每次操作格式如下：
• 1 x y，表示交换第 x行和第 y行；
• 0 x y，表示交换第 x列和第 y列；
请你输出复原后的拼图。
思路：第一次写的时候在循环中每次操作都把整个方阵一起交换，因为方阵是二维数组，导致了几次超时。后来发现，在每次操作时，行列变换并不互相影响，所以可以通过两个数组row[],col[]分别记录操作后的行列对应最开始方阵的行列

学习总结：学会计算程序的时间复杂度，通过问题6，问题7的解决，明白在程序超时时该如何进行优化。并且通过学习，了解了一些C++的语法。