FZU Monthly-201903 tutorial

时间:2023-03-08 16:16:04

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题。请其他同学记住这个可能的错误点。