写在前面

水一发题解喵。

可能有更优解,这里仅做参考。

T1 核桃王国的战争

由于只有一个数与其他数奇偶性不一样,那么只需要判断 aia_iai1a_{i-1}ai+1a_{i+1} 的奇偶性是否相同即可。

但是要注意注意,头尾要特判!

代码写短一点会很好看捏:

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	int a[15];
	for (int i = 1;  i<= 10; i++) cin >> a[i];
	if (a[1] % 2 != a[2] % 2 && a[1] % 2 != a[3] % 2) cout << a[1]; //a[1]特判
	if (a[10] % 2 != a[9] % 2 && a[10] % 2 != a[8] % 2) cout<<a[10]; //a[10]特判
	else for (int i = 2; i <= 9; i++) if (a[i] % 2 != a[i-1] % 2 && a[i] % 2 != a[i+1] % 2) {cout << a[i];return 0;} //找到直接输出结束	
	return 0;
}

T2 吃核桃的nana

0分解法:

这都要讲?

用一个结构体存储,优先选取营养高且饱腹值低的。

赛时一交,WA0分两行泪。

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {int x, y;}a[10005];
int m, n;
bool cmp(node a, node b)
{
	if (a.y == b.y) return a.x > b.x;
	return a.y > b.y;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y;
	sort(a+1, a+m+1, cmp);
	int ans = 0, sum = 0, j = 1;
	while (sum + a[j].x < n)
	{
		sum += a[j].x,ans+=a[j].y;
		j++;
	}
	cout << ans;
	return 0;
}

AC解法:

赛时看了10分钟,才发现,这不就是01背包吗喵!

模版一打即可,具体不解释,或者可以去看这个博客

#include <bits/stdc++.h> 
using namespace std;
int n, v[100005], w[100005], W, f[100005];
int main()
{
    cin >> W >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = W; j >= w[i]; j--) 
        {
            f[j] = max(f[j], f[j - w[i]] + v[i]); //01背包模版,不做解释
        }
    }
    cout << f[W];
    return 0;
}

T3 学习英语的nana

60分做法:

直接枚举,碰到不是元音的字母直接输出即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u')
			cout << s[i];
	}
	return 0;
}

AC做法:

仔细看题!!!空字符串要输出 -1!

有4个测试点为无解(亲测)。

加个判断即可AC这题。

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	string s, a;
	cin >> s;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u')
			a += s[i];
	}
	if (a != "") cout << a; //无解
	else cout << -1;
	return 0;
}

T4 严谨的nana老师

本题坑点多。我们先来讲0分做法喵:

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	int n, m, a[100005];
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1, x; i <= m; i++)
	{
		cin >> x;
		for (int j = 1; j <= n;j ++)
		{
			if (a[j] >= x) {cout << a[j] << " "; break;} //寻找第一个比此学生吃得饱的重量大的核桃
		}
	}
	return 0;
}

赛时一交,WA,0分。

为啥啊喵?仔细一看题目,哦原来没保证序列有序,需要自己排个序。那就加个 sort

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	int n, m, a[100005];
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1); //提前排序
	for(int i = 1, x; i <= m; i++)
	{
		cin >> x;
		for (int j = 1; j <= n;j ++)
		{
			if (a[j] >= x) {cout << a[j] << " "; break;}
		}
	}
	return 0;
}

再交一发,TLE,还是0分。(赛时真的抓狂了(〃>皿<) )

sort 的时间复杂度大概为 O(nlogn)O(n \log n),寻找的过程最坏时时间复杂度为 O(mn)O(mn)1n,m1×1051ai,bj1×1051≤n,m≤1×10^5,1≤a_i,b_j≤1×10^5,不爆才怪啊喵。

好接下来就是100分的AC代码:

赛时思考半小时,突然想到:只要我开一个数组,提前预处理每一个吃得饱的重量所需要的最轻的核桃,之后直接调用(毕竟保证可以满足所有学生),那么时间复杂度就可以降为近 O(nlogn)O(n \log n) 喵!。

那么我们就建一个数组 f[100005],用 fif_i 表示如果一个学生吃得饱的重量为 ii 时,所需要的最轻的核桃的重量。只要在输入时预处理好即可。

排序完再预处理的时候,从 f1f_1 为左端点 ll 开始处理,每次将 aia_i 取出为右端点 rr,将 flfrf_l \sim f_r 全部赋值为 aia_i,最后更新左端点 l=ai+1l = a_i + 1,重复上述操作,直至 aa 数组遍历完即可。

最后直接调用 fxf_x 即可。1n,m1×1051≤n,m≤1×10^5 是过得了了喵。交上去,AC!

总结一下坑点:

  • 要排序!
  • 直接枚举会爆,用预处理

AC CODEAC \space CODE

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	int n, m, a[100005], f[100005], l = 1; //左端点初始为1
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1); //排序
	for (int i = 1; i <= n; i++)
	{
		for (int j = l; j <= a[i]; j++) f[j] = a[i]; //赋值操作
		l = a[i] + 1; //更新左端点
	}
	for(int i = 1, x; i <= m; i++)
	{
		cin >> x;
		cout << f[x] << " "; //直接输出
	}
	return 0;
}

赛后想了一下,诶我是不是可以用 STL 的 lower_bound 啊?