比赛链接：
https://ac.nowcoder.com/acm/contest/11175
A 科学家的模型
模拟题，对每行数字和排序，最小值是1的肯定是9。
除去9之后，如果第3大和第4大相等，那么一定是8
之后全是0
#include <bits/stdc++.h>
using namespace std;
char mp[5][5];
int num[5];
int main() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cin >> mp[i][j];
num[i] += mp[i][j] - '0';
}
}
sort(num, num + 5);
if (num[0] == 1) cout << 9 << endl;
else if (num[2] == num[3]) cout << 8 << endl;
else cout << 0 << endl;
}
B 音乐家的曲调
考虑DP
我们找每个点可以到达的最前面那个点，然后列出方程转移一下。
f
[
i
]
[
3
]
=
m
a
x
(
f
[
i
−
1
]
[
3
]
,
f
[
p
r
e
−
1
]
[
2
]
+
(
i
−
p
r
e
+
1
)
)
f[i][3]=max(f[i-1][3],f[pre-1][2]+(i-pre+1))
f
[
i
]
[
3
]
=
m
a
x
(
f
[
i
−
1
]
[
3
]
,
f
[
p
r
e
−
1
]
[
2
]
+
(
i
−
p
r
e
+
1
)
)
f
[
i
]
[
2
]
=
m
a
x
(
f
[
i
−
1
]
[
2
]
,
f
[
p
r
e
−
1
]
[
2
]
+
(
i
−
p
r
e
+
1
)
)
f[i][2]=max(f[i-1][2],f[pre-1][2]+(i-pre+1))
f
[
i
]
[
2
]
=
m
a
x
(
f
[
i
−
1
]
[
2
]
,
f
[
p
r
e
−
1
]
[
2
]
+
(
i
−
p
r
e
+
1
)
)
f
[
i
]
[
1
]
=
m
a
x
(
f
[
i
−
1
]
[
1
]
,
f
[
p
r
e
−
1
]
[
2
]
+
(
i
−
p
r
e
+
1
)
)
f[i][1]=max(f[i-1][1],f[pre-1][2]+(i-pre+1))
f
[
i
]
[
1
]
=
m
a
x
(
f
[
i
−
1
]
[
1
]
,
f
[
p
r
e
−
1
]
[
2
]
+
(
i
−
p
r
e
+
1
)
)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
const int MOD = 1e9 + 7;
char s[N];
int pre[N], lmax[N];
int dp[N][4];
queue<int> que[26];
void solve () {
int n, m; cin >> n >> m;
cin >> (s + 1);
lmax[0] = 1;
for (int i = 1; i <= n; i++) {
que[s[i]-'a'].push(i);
lmax[i] = max(lmax[i], lmax[i-1]);
if (que[s[i]-'a'].size() > m) {
int now = que[s[i]-'a'].front();
que[s[i]-'a'].pop();
pre[i] = now;
lmax[i] = max(lmax[i], pre[i] + 1);
}
}
//for (int i = 1; i <= n; i++) cout << lmax[i] << endl;
for (int i = 1; i <= n ;i++) {
dp[i][3] = max(dp[i-1][3], dp[lmax[i] - 1][2] + (i - lmax[i] + 1));
dp[i][2] = max(dp[i-1][2], dp[lmax[i] - 1][1] + (i - lmax[i] + 1));
dp[i][1] = max(dp[i-1][1], dp[lmax[i] - 1][0] + (i - lmax[i] + 1));
}
cout << dp[n][3] << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef ACM_LOCAL
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
solve();
return 0;
}
C 哲学家的沉思
转化一下题意变成找每个数后第一个大于它的数。
然后用nxt数组串起来，倍增处理一下之后暴力跳就可以了。
f
[
i
]
[
j
]
=
f
[
f
[
i
]
[
j
−
1
]
]
[
j
−
1
]
f[i][j]=f[f[i][j-1]][j-1]
f
[
i
]
[
j
]
=
f
[
f
[
i
]
[
j
−
1
]
]
[
j
−
1
]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10;
const int MOD = 1e9 + 7;
int r[N], a[N], stk[N], top;
int f[N][21];
void solve () {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
a[n+1] = INF;
for (int i = 1; i <= n + 1; i++) {
while (top && a[i] > a[stk[top]]) r[stk[top]] = i, f[stk[top]][0] = i, top--;
stk[++top] = i;
}
for (int i = 0; i <= 20; i++) f[n][i] = f[n+1][i] = n + 1;
for (int j = 1; j <= 20; j++) {
for (int i = 1; i <= n; i++) {
f[i][j] = f[f[i][j-1]][j-1];
}
}
for (int i = 1; i <= m; i++) {
int L, R; cin >> L >> R;
int now = L, ans = 0;
for (int j = 20; ~j; j--) {
if (f[now][j] <= R) {
ans += (1 << j);
now = f[now][j];
}
}
cout << ans + 1 << endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef ACM_LOCAL
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
solve();
return 0;
}
D 数学家的迷题
查询区间积后素因子的个数。
本来最早的想法是主席树，但有修改就显得很麻烦了，瞄了一眼题解发现了bitset，马上就懂了。
我们只要把pushup中的bitset进行或运算即可，质因数分解常数太大还tle好多次。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
int prime[N], cnt, tot, a[N];
bool is_prime[N];
unordered_map<int, int> mp;
void get_prime(){
memset(is_prime, true, sizeof is_prime);
is_prime[0] = is_prime[1] = false;
for(int i = 2 ; i < N;i++){
if (is_prime[i]) prime[++cnt] = i;
for(int j = 1; j <= cnt && 1ll * i * prime[j] < N;j++){
is_prime[i * prime[j]] = false;
if(i % prime[j] == 0) break;
}
}
}
struct node {
int l, r;
bitset<10005> bi;
}t[50005 << 2];
void push_up(int u) {
t[u].bi = t[u<<1].bi | t[u<<1|1].bi;
}
void build(int u, int l, int r) {
t[u].l = l, t[u].r = r;
if (l == r) return;
int mid = (l + r) >> 1;
build(u<<1, l, mid);
build(u<<1|1, mid+1, r);
}
void add(int u, int pos, int y) {
if (t[u].l == t[u].r) {
t[u].bi.set(y);
return;
}
int mid = (t[u].l + t[u].r) >> 1;
if (pos <= mid) add(u<<1, pos, y);
else add(u<<1|1, pos, y);
push_up(u);
}
void reset(int u, int pos) {
if (t[u].l == t[u].r) {
t[u].bi.reset();
return;
}
int mid = (t[u].l + t[u].r) >> 1;
if (pos <= mid) reset(u<<1, pos);
else reset(u<<1|1, pos);
push_up(u);
}
bitset<10005> query(int u, int ql, int qr) {
if (ql <= t[u].l && qr >= t[u].r) return t[u].bi;
int mid = (t[u].l + t[u].r) >> 1;
bitset<10005> l, r, ans;
if (qr <= mid) return query(u<<1, ql, qr);
else if (ql > mid) return query(u<<1|1, ql, qr);
else {
l = query(u<<1, ql, qr);
r = query(u<<1|1, ql, qr);
ans = l | r;
return ans;
}
}
void solve () {
get_prime();
for (int i = 1; i <= cnt; i++) mp[prime[i]] = i;
int n, m; cin >> n >> m;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
int now = a[i];
for (int j = 2; j*j <= now; j++) {
if (now % j == 0) {
add(1, i, mp[j]);
}
while (now % j == 0) now /= j;
}
if (now != 1) add(1, i, mp[now]);
}
while (m--) {
int opt, l, r; cin >> opt;
if (opt == 1) {
int id, x; cin >> id >> x;
reset(1, id);
int now = x;
for (int j = 2; j*j <= now; j++) {
if (now % j == 0) {
add(1, id, mp[j]);
}
while (now % j == 0) now /= j;
}
if (now != 1) add(1, id, mp[now]);
} else {
cin >> l >> r;
bitset<10005> ans = query(1, l, r);
printf("%d\n", ans.count());
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef ACM_LOCAL
freopen("input", "r", stdin);
freopen("output", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
#endif
solve();
return 0;
}