1、握手问题

知识点：模拟

        这道题很简单。但是不知道考试的时候有没有写错。一开始的43个人握手，仅需要两两握手，也就是从42个握手开始，而非43.很可惜。这道题没有拿稳这5分。也很有可能是这5分导致没有进决赛。

总结：
1、将题目要求的大的数值进行抽象出来，例如写成一个变量m,n。

2、然后，使用较小的数字，将m设置为5，n设置为3。

3、然后手算看看结果是否与程序相同。

4、相同的话，再使用题目要求的数值填入n和m中。

#include
using namespace std;
long long cnt;
const int n = 50;  // 总人数
const int m = 43;  // 无需特殊处理的人数
int main()
{
	// 先处理前面没有限制的43个人。  他们之间两两握手
	for (int i = m-1; i >= 1; i--)  // 注意这里不是43，而是42
	{
		cnt += i;
	}
	// 后处理有限制的7人  他们分别与上述43人握手
	cnt += 43 * (n-m);
	cout << cnt;
	return 0;
}

2、小球反弹

 

看着很难，考试的时候直接放弃了，现在也没有去写正解。

3、好数

知识点：模拟

        逻辑非常简单，10分钟不到就能够写出来。但是考试的时候很紧张，写了20分钟。没有很清晰的写出下标之间的关系，当时很乱。

        最终结果：100分。折算后：10分

#include
using namespace std;
int n;
int cnt;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string str = to_string(i);
        int len = str.size();  // 获取数字的长度
        int b = 1;  // 当前位数
        int j;
        for (j = len - 1; j >= 0; j--)  // 从数字末尾开始判断
        {
            if (b % 2 == 1)  // 需要检测当前奇数位数的数值为奇数
            {
                if (str[j] % 2 == 1)
                {
                    b++;
                    continue;
                }
                else
                    break;
            }
            else  // 检测当前偶数位的数值是否为偶数
            {
                if (str[j] % 2 == 0)
                    b++;
                else
                    break;
            }
        }
        if (j == -1)
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

4、R格式

 知识点：高精度。

        高精度类型的题目我几乎没有做过。所以当时看到是很慌的。本题浮点数的位数很大，我仅仅使用double进行存储，肯定只能通过极少数的测试样例。

        最终结果：本题拿到24分。折算为题目的分数就是：10*0.24 = 2.4分

        当时考试过程中，想到了使用string来存储，但是写了半天，还是不知道怎么处理。

        最终写出来的效果是：string解决位数较低的情况，和直接使用double存储应该没两样。当时还不如直接使用double存储。。。

        后面想着时间还剩多的话，就回来写用string解决位数较高的情况。但是后面还是没能回来。

#include
using namespace std;
int n;
double d;
int main()
{
    cin >> n >> d;
    long long temp = pow(2, n);
    double pre = d * temp;
    // 进行四舍五入——采用笨方法
    string str = to_string(pre);
    int i;
    for (i = 0; i < str.size(); i++)
    {
        if (str[i] == '.')
            break;
    }
    // 判断小数点后一位是否小于5
    if (str[i + 1] < 5)
        cout << int(pre) << endl;
    else
    {
        cout << int(pre) + 1 << endl;
    }
    return 0;
}

5、宝石组合

知识点：最大公因数、最小公倍数、XXX

        考试中，看到题目，就想到了使用dfs，dfs在考试前，自己练了好多道题目了。后来发现，直接使用for循环，也可以得到答案。很像没有必要使用dfs。考试中，浪费了很多时间进行dfs编码，最终写的还是简单的for循环。

经验：

1、写完gdc和lcm函数后，先测试一下。

2、先想出整个题目的思路，再进行编码。

3、先想想有没有什么简单的思路，在考试中先使用简单的思路进行求解。有时间再回来写正解。

结果：时间超时，但是拿到了33分。折算后就是：15*0.33 = 5分

#include
using namespace std;
int n;
long long Max = -1;
int res[3];
int gcd(int a, int b)
{
	while (a % b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return b;
}
int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}
int main()
{
	cin >> n;
	vector v(n, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			for (int k = j + 1; k < n; k++)
			{
				long long p1 = v[i] * v[j] * v[k];
				long long p2 = lcm(v[i], v[j]);
				long long p3 = lcm(v[i], v[k]);
				long long p4 = lcm(v[j], v[k]);
				long long p5 = lcm(p2, v[k]);
				long long temp = p1 * p5 / (p2 * p3 * p4);
				if (temp > Max)
				{
					Max = temp;
					res[0] = v[i];
					res[1] = v[j];
					res[2] = v[k];
 				}
			}
		}
	}
	
	for (int i = 0; i < 3; i++)
	{
		cout << res[i] << " ";
	}
	return 0;
}

 6、数字接龙

知识点：dfs、bfs

        老毛病了：写了40分钟，发现自己题目都没有完全搞懂。思路没有捋顺就开始编程。

        中途发现，自己平时练习的bfs和本题还是有区别的。这道题还要存储路径过程。我很少练这个。

        最终考试提交的就是一堆不完整的代码。但是写了-1的情况，所以花了40分钟，最终和花1分钟写的效果一样。

        出乎意料的是，直接输出-1居然在dot.cpp网站上能通过超过一半的测试样例， 拿到了55分！！！折算后：15*0.55 = 8分

#include
using namespace std;
int main()
{
    cout << -1 << endl;
    return 0;
}

 7、爬山

知识点：贪心算法

        使用贪心策略，只考虑当前的最优解。即，先对高山进行大到小排序，魔法提前使用。

        这样子写肯定不是正解，但是在考场上，我当时的水平只能这么写着先了。

        考场上的策略不太行，应该使用别的策略。

        我当时想的是：排完序后，就对山施展魔法，直至改山比第二座山低，就对下一座山施展魔法。

        现在回想起来，存在漏洞，第一座山比第二座山低了之后，应该将第一座山插至山序列的恰当位置，而非不处理。

        以下程序是修复漏洞后的程序，通过3个测试用例，其余测试用例超时。有一个测试用例答案错误。得分：25。折算后：20*0.25 = 5

其实这题，要是不清楚优先使用魔法1还是2，也可以专门写一个针对20%的测试用例的，只使用魔法2。

#include
using namespace std;
int n;
int p;
int q;
//bool cmp(int a, int b)
//{
//	return a > b;
//}
int main()
{
	cin >> n >> p >> q;
	vector v(n, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	sort(v.rbegin(), v.rend());  // 递减排序
	
	// 求不等式：x/2>根号x    求得：当x>4时，使用/，即使用魔法2时，作用效果没有使用魔法1的好。
	/*
	易错点：上述条件对于实数成立。但是题目中，魔法2还可以向下取整。
	当x<=4时，均为魔法2的效果更加。
	当x = 5时，使用魔法1，变成了2.23； 使用魔法2，变成了2  魔法2更佳
	当x = 6时，使用魔法1，变成了2.4；  使用魔法2，变成了3  魔法1更佳
	当x = 7时，使用魔法1，变成了2.6；  使用魔法2，变成了3  魔法1更佳
	综上所属，x<=5时，使用魔法2；x>5时，使用魔法1
	*/
	// 始终都对第一座最大的山使用魔法
	while (p || q)
	{
		if (v[0] > 5)  // 优先使用魔法1
		{
			if (p > 0)  // 魔法1还可以使用
			{
				v[0] = sqrt(v[0]);
				if (n > 1)
				{
					if (v[0] < v[1]) //使用魔法后比后面的小，需要重新排序
						sort(v.rbegin(), v.rend());
				}
				p--;
			}
			else
			{
				if (q > 0)
				{
					v[0] /= 2;
					if (n > 1)
					{
						if (v[0] < v[1]) //使用魔法后比后面的小，需要重新排序
							sort(v.rbegin(), v.rend());
					}
					q--;
				}
			}
		}
		else // 优先使用魔法2
		{
			if (q > 0)  
			{
				v[0] /= 2;
				if (n > 1)
				{
					if (v[0] < v[1]) //使用魔法后比后面的小，需要重新排序
						sort(v.rbegin(), v.rend());
				}
				q--;
			}
			else
			{
				if (p > 0)  // 魔法1还可以使用
				{
					v[0] = sqrt(v[0]);
					if (n > 1)
					{
						if (v[0] < v[1]) //使用魔法后比后面的小，需要重新排序
							sort(v.rbegin(), v.rend());
					}
					p--;
				}
			}
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += v[i];
	}
	cout << ans;
	return 0;
}

8、接龙

知识点：前缀和

        这道题考试的时候没有做，直接输出的用例答案，应该0分。

        本次考试过程中，我很多题目都太渴望求正解，以致于解决速度慢，还不如直接暴力解。

再加上紧张所以编程不能冷静，return 0 又没有写，第一题又粗心了。所以排名二等奖垫底。

        要是解决上述问题，并且把拔河这题写了，就能够拿到省一了！！！

        考试的时候，没有注意到题目说明了所选的每组人编号是连续的。且第2组人编号一定大于第1组人的

        自己考试的时候，把题目想复杂了，以致于这道题没有进行解答。

        解法一：选上所有选手，但题目并未这么要求。

        答案错误。通过一个测试用例，答案拿了9分。折算后为：20*0.09= 1.8

#include
using namespace std;
int n;
int Min = 1e9;
int main()
{
    cin >> n;
    vector v(n + 1, 0);
    vector vs(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        vs[i] = vs[i - 1] + v[i];
    }
    for (int i = 1; i < n; i++)  // 第一组选择前i个人，第一组不可能选所有人，否则第2组没人可选了。
    {
        long long grp1 = vs[i];
        long long grp2 = vs[n] - vs[i];
        long long temp = abs(grp1 - grp2);
        if (temp < Min)
            Min = temp;
    }
    cout << Min << endl;
    return 0;
}

        解法2：使用了4层循环，标记选手范围的l1，r1,l2,r2。非常好理解。注意一下下标，不要写错即可。

        通过3个测试用例。得分27，超时。折算后：20*0.27 = 5.4 

#include
using namespace std;
int n;
int Min = 1e9;
int main()
{
    cin >> n;
    vector v(n + 1, 0);
    vector vs(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        vs[i] = vs[i - 1] + v[i];
    }
   
    for (int l1 = 0; l1 < n; l1++)  // l1位置
    {
        for (int r1 = l1 + 1; r1 < n; r1++)  // r1位置
        {
            long long grp1 = vs[r1] - vs[l1];
            for (int l2 = r1; l2 <= n; l2++)
            {
                for (int r2 = l2 + 1; r2 <= n; r2++)
                {
                    long long grp2 = vs[r2] - vs[l2];
                    long long temp = abs(grp1 - grp2);
                    if (temp < Min)
                        Min = temp;
                }
            }
        }
    }
    cout << Min << endl;
    return 0;
}

 

经验总结：

1、看清楚题目限制条件。

        例如：题目讲到的拔河人数序号一定是递增的——这就导致不会说，有1、2、3、4、5个人，选15一组，24一组。而是一定是选连续的人为1组。这就极大地简化了题目的难度。

2、比赛过程中，不要总是想着上来就求解正解。而是先去尝试纯暴力解法，以节约时间。

        有时候题目纯暴力也需要花很多时间来解决。先做出了纯暴力的解法，留够充足的时间后面再做正解，而且前面的纯暴力会为后续提供思路的。

3、一定一定有了完整的思路、明确这么做是正确的（超时也没关系），才开始编程。

        编程切忌没有思路，或者是有了一丢丢思路就开始编程。这样子的效率极低。而且容易在遇到某个解决不了的问题时，前功尽弃，徒劳而费。

4、学会使用抽象编程。

        例如第一题，将某个变量抽象后，就可以使用某个数值较小的测试用例来检验程序的正确，以保证不因粗心丢分。

5、今天静下心来，没有压力的情况下，拿了40.5分。这个分数应该可以拿省一的。

        感觉自己练的题目也不少，但是自己最终拿到的奖项还是有点弱了。还是自身应试能力不强，编程经验缺乏，水平没有发挥到位。如果有小伙伴想要冲蓝桥杯省一的，一定要提前跟着网上的视频，覆盖知识点后，再进行刷题。题目不管难易，都从暴力解出发，正确每道题目都能拿下一定的分数。