30 场 edu a2e 第 3 场
2.26 - 2.28
A.Deadline
求函數
数学
令
令
由不等式
时间复杂度
#include <bits/stdc++.h>
using namespace std;
void solve() {
int a, b;
scanf("%d %d", &a, &b);
puts(ceil(2.0 * sqrt(b)) > a + 1 ? "NO" : "YES");
}
int main() {
int t; scanf("%d", &t);
while (t --) solve();
return 0;
}
不会数学自闭了
B.Yet Another Meme Problem
求满足下列要求整数对
其中
数学
记
发现方程只与
则只要求出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int a, b; ll ans = 0;
scanf("%d %d", &a, &b);
for (ll i = 10; ; i *= 10) {
if ((i - 1) > b) break;
ans += a;
}
printf("%lld\n", ans);
}
int main() {
int t; scanf("%d", &t);
while (t --) solve();
return 0;
}
C.Two Arrays
求序列对
|A| = |B| = m A 单调不降,B 单调不升A_i \leq B_i 1 \leq A_i, B_i \leq n
DP,组合数学
DP 做法
由于不关心具体的值,所以对今后的选择有影响的只有
即对于每种
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM = 1e3 + 10, MAXN = 10 + 10, P = 1e9 + 7;
int n, m;
ll f[MAXN][MAXM], fans;
int main() {
scanf("%d %d", &m, &n);
for (int i = 0; i < m; ++i) f[1][i] = m - i;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = j; k < m; ++k) f[i][j] = (f[i][j] + (f[i - 1][k] * (k - j + 1)) % P) % P;
}
}
for (int i = m - 1; i >= 0; --i) fans = (fans + f[n][i]) % P;
printf("%lld\n", fans % P);
return 0;
}
组合计数做法
考虑将
则问题转化为求长度为
令
即将
暴力阶乘即可
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
ll qpower(ll a, int x) { ll ret = 1; for (; x; x >>= 1, a = a * a % P) x & 1 ? ret = ret * a % P : 0; return ret; }
ll n, m, ans;
int main() {
scanf("%lld %lld", &n, &m);
ll ans = 1;
for (ll i = n; i <= n + (m << 1) - 1; ++i) ans = ans * i % P;
for (ll i = 1; i <= (m << 1); ++i) ans = ans * qpower(i, P - 2) % P;
printf("%lld\n", ans);
return 0;
}
妙死了
D.Minimax Problem
给出
二分答案,状压
一眼套路二分答案
二分这个最大的值
对于每列我们记录
这个二分出的值为真当且仅当存在至少两行
那么我们记录
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10, MAXM = 8 + 10, MAXVAL = 5e5;
int n, m, val[MAXN][MAXM], ans1, ans2;
bool check(int x) {
int num[MAXN], cnt[MAXVAL], MAXS = (1 << m) - 1; // cnt[S] 表示与状态为 S 的序列并起来合法的序列的编号
memset(num, 0, sizeof num), memset(cnt, 0, sizeof cnt);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) if (val[i][j] >= x) num[i] |= (1 << (j - 1));
int cpm = MAXS ^ num[i];
cnt[cpm] = i;
for (int tmp = num[i]; tmp; tmp = (tmp - 1) & num[i]) cnt[tmp | cpm] = i;
}
for (int i = 1; i <= n; ++i) {
if (cnt[num[i]]) { ans1 = i, ans2 = cnt[num[i]]; return true; }
}
return false;
}
int main() {
scanf("%d %d", &n, &m);
int l = 0, r = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) scanf("%d", &val[i][j]), r = max(r, val[i][j]);
}
while (l <= r) {
int mid = (l + r) >> 1;
check(mid) ? l = mid + 1, ans = mid : r = mid - 1;
}
printf("%d %d\n", ans1, ans2);
return 0;
}
E.Messenger Simulator
维护一个长度为
数据结构,单点修改,区间前缀和
维护最上十分简单,如果一个数
首先是一个重要的观察:一个数最下下标只可能在两种情况中出现:
- 在对与这个数的某次操作之前
- 终态
以及一个非常关键的小 trick 是,对一个元素的操作可以转换为将一个元素的下标变为全局最上下标
那么问题变为单点修改,全局求 rk
可以用平衡树实现,也可以使用 BIT
对于 BIT 做法,维护其下标的值域,具体而言,维护长度为
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 6e5 + 10;
int n, m, bit[MAXN], ansmax[MAXN], ansmin[MAXN], pos[MAXN];
void add(int pos, int val) { for (int i = pos; i <= n + m; i += (i & (-i))) bit[i] += val; }
int query(int pos) { int ret = 0; for (int i = pos; i; i -= (i & (-i))) ret += bit[i]; return ret; }
int main() {
scanf("%d %d", &n, &m);
iota(ansmax + 1, ansmax + n + 1, 1), iota(ansmin + 1, ansmin + n + 1, 1), iota(pos + 1, pos + n + 1, m + 1);
for (int i = 1; i <= n; ++i) add(pos[i], 1);
int idx = m;
for (int _ = 1, x; _ <= m; ++_) {
scanf("%d", &x);
ansmin[x] = 1;
ansmax[x] = max(ansmax[x], query(pos[x]));
add(pos[x], -1);
pos[x] = idx --;
add(pos[x], 1);
}
for (int x = 1; x <= n; ++x) ansmax[x] = max(ansmax[x], query(pos[x])), printf("%d %d\n", ansmin[x], ansmax[x]);
return 0;
}
这个小 trick 不明觉厉
总结
好
- D 独立地,很快的写出来了
- 做题速度加快了很多,3 天昨晚
不好
- 数学能力有待加强
- 写题解的非常之慢,以后应该是
3 天之内就要把题解挂到博客上去