FZU Monthly-201903 tutorial

FZU Monthly-201903 tutorial

题目(难度递增)	easy	easy-medium	medium	medium-hard	hard
思维难度	ABF	G	CH	D	E

A. Derivative

对于本题，你只需要有着扎实的高等数学基础即可通过。出题人的原意是希望这道题能够成为第二档难度，然而他似乎不知道有在线求导这样神奇的网站，于是，这道题就成为了简单题。

复杂度为O(1)。

B. Fzuacmicpc

本题写法较多，只要你认真读题了且C语言基础过关，就一定会做。

在此给出一个简单的提示：你可以把数组复制一遍来处理字符串头尾相连的问题

C.Heroes

本题是一道基础的搜索题。

在本题中，零散的水晶其实只需要计数即可，重点是八个蛋（バクダン，炸弹）周围的水晶。由于炸弹只有8个，因此我们对炸弹进行编号，枚举每个炸弹是否选取，利用搜索求得对应情况下通过炸弹获取的水晶数量即可。剩余的水晶可以就直接购买需要的数量。

D. Ksubstring

注意到如果所有字符如果都有大于等于k个，那么可以取全部，不然这些不足k个的字符会把整个字符串切开，就变成了子问题，递归去做就行了。复杂度O(26 * n)

E.Magicwall

如果选定了[l, r] 这段区间，那么调整到中位数是最优的，所以就是滑窗维护中位数，可以开两个set，保证集合大小差小于等于1，以及一个集合的最小值大于等于另一个集合最大值，这样就可以维护需要消耗的代价了。

提供出题人的标程供参考：

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define endl "\n"
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int P = 1e9 + 7;
int add(int a, int b) {if((a += b) >= P) a -= P; return a;}
int sub(int a, int b) {if((a -= b) < 0) a += P; return a;}
int mul(int a, int b) {return 1ll * a * b % P;}
int kpow(int a, int b) {int r=1;for(;b;b>>=1,a=mul(a,a)) {if(b&1)r=mul(r,a);}return r;}
//----

const int N = 5e5 + 7;
set<pair<ll, int> > s[2];
ll sum[2], ans, a[N];
int n, k;

inline void ADD(int o, pair<ll, int> &x) {
	s[o].insert(x);
	sum[o] += x.fi;
}

inline void DEL(int o, pair<ll, int> &x) {
	s[o].erase(x);
	sum[o] -= x.fi;
}

void modify() {
	while (sz(s[1]) < sz(s[0])) {
		auto t = *(--s[0].end());
		ADD(1, t);
		DEL(0, t);
	}
	while (sz(s[1]) - 1 > sz(s[0])) {
		auto t = *s[1].begin();
		ADD(0, t);
		DEL(1, t);
	}
	while (1) {
		auto x = *s[1].begin(), y = *(--s[0].end());
		if (x.fi < y.fi) {
			DEL(1, x);DEL(0, y);
			ADD(1, y);ADD(0, x);
		}else break;
	}
}

int main() {
	//freopen("a.in","r",stdin);
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	//cout << setiosflags(ios::fixed);
	//cout << setprecision(2);
	cin >> n >> k;
	rep(i, 1, n+1) cin >> a[i];
	rep(i, 1, k+1) {
		auto t = mp(a[i], i);
		ADD(0, t);
	}
	modify();
	ans = sum[1] - sum[0] - (k & 1) * (*s[1].begin()).fi;
	rep(i, k+1, n+1) {
		auto t = mp(a[i-k], i-k), t2 = mp(a[i], i);
		if (s[0].count(t)) DEL(0, t), ADD(0, t2);else DEL(1, t), ADD(1, t2);
		modify();
		ans = min(ans, sum[1] - sum[0] - (k & 1) * (*s[1].begin()).fi);
	}
	cout << ans;
	return 0;
}

F.Monoid-group

事实上，题面是离散数学中关于群的定义。按照题目要求写三重循环进行判定即可。

复杂度O(N^3)。

G.Ninja

这道题的本意是考察矩阵乘法的应用，但是出出来后发现远比预先设计的来的简单。

对于题目给出的数据，用邻接矩阵进行存储后进行一次自乘，即可得到一次移动所能获得的得分。将最高得分乘上K就是最后的结果。

复杂度为O(N^3)

H.Permutation-generation

形如：

n n-1 n-2 n-3 ... n-t k 1 2 3 .. c

从大到小依次填写，直到逆序对超过，选择合适的k，使得逆序对得到满足之后，剩下数字顺序排列

出题人的一些话：

参考了上次月赛的结果，这次月赛的题目设置相对简单，结果也基本符合预期。如果你能够在这次月赛中通过三题或以上，那么你的代码水平应该能够在C语言期末考试，以及校赛中获得一个不错的成绩。

这次月赛共有95人报名，51人成功地做出题，希望参赛的大家能够向周围的同学宣传我们的月赛，使得以后的月赛能够有更多的同学参与到其中来，共同营造快乐的编程坏境。

比赛趣味统计：

全场第一个AC： 陈华能同学在开场9分钟时以惊人的手速AC了B题。随后，林闽沪同学以微弱差距在不到一分钟之内通过了A题。

全场最后一个有效AC：鲍子涵同学在16:56提交了D题WA掉了之后，在16:57再此提交成功AC，成为了全场最后一个有效AC题目的选手。

全场最顽强的选手：陈华能同学在15：35成功AC了D题，在AC之前，他一共提交了9次，其中6次TLE，3次WA，但是他一直在努力调试。最终他获得了全场第3名的好成绩。

全场最虐心的选手：吴少冰同学在14：47提交了一份判定为WA的D题代码。只有在后台默默围观的出题人知道，他的做法其实是正确的，只是没有判断题目中表明的输出-1的情况。吴少冰同学在这道题上奋斗了接近2个小时，做出了各种各样的尝试，最后在16:43分成功发现问题并AC了D题，成为全场第5名。

全场最有灵性的选手： 鲍子涵同学在H题的代码中，同时使用了关闭同步的cout和传统输入输出方式导致了WA。在出题人以为他要因此卡题的时候，鲍子涵同学在13分钟内发现了这个很不明显的问题然后成功AC了H题。请其他同学记住这个可能的错误点。