|
（注：为了方便，本文将 $S$ 中 $1$ 的个数限制设为 $K$） 这种计数类的问题大概率是 DP，可以往这个方面想。 考虑状态的设计，由于这道题存在进位的问题，而且进位是从低到高的，所以可以按二进制位从低到高考虑。 那么状态里肯定要有两维：$(i,j)$，分别表示当前的位数，和已经确定的 $a$ 中元素的数量。 但是题中对二进制 $1$ 的个数限制为 $K$，而且进位相当烦人，这时就可以考虑直接把它们设进状态。 毕竟这题数据范围不大，就算不是正解也能拿不少分。 由此，设计出一个 DP： 设 $f(i,j,k,q)$ 表示 $0\sim i-1$ 位已经考虑过，当前考虑第 $i$ 位，$a$ 中已经有 $j$ 个元素确定，目前 $S$ 中有 $k$ 个 $1$，且从 $0\sim i-1$ 推过来的进位数为 $q$ 时的权值和。 初始状态：$f(0,0,0,0)=1$。 发现这个状态并不是很好从前面转移来，那么我们就用已有的状态往后转移（刷表）。 考虑在第 $i$ 位放 $t(0\le t\le n-j)$ 个 $a$ 中的元素，那么 $S$ 中 $1$ 的个数会变成 $k + ((t + q)\bmod 2)$，向第 $i+1$ 位进 $\lfloor \frac{t+q}{2} \rfloor$ 个 $1$。 那么接下来的状态就是 $f(i+1,j+t,k+((t+q)\bmod 2),\lfloor \frac{t+q}{2} \rfloor)$。 现在来算一算这次转移的贡献，直接放式子： $$f(i,j,k,q) \times \mathrm C_{n-j}^t \times v_i^t$$ 这个式子并不难理解，就是在 $a$ 剩下的 $n-j$ 个元素中选 $t$ 个，会产生 $v_i^t$ 的权值。 剩余要注意的就是统计答案。累加上所有的 $f(m+1,n,k,q)$。 但因为这题二进制 $1$ 的个数至多为 $K$，而且 $m+1$ 位及以后显然还会有进位产生的 $1$，不难发现，这个状态的 $S$ 中真正的 $1$ 的个数是 $k+\text{popcount}(q)$。 所以还要在枚举时判断一下 $k+\text{popcount}(q) \le K$。 那么这道题就做完了。时间复杂度 $O(mn^4)$，卡得很紧，组合数和 $v_i^t$ 都要预处理出来。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 35;
const int maxm = 105;
ll C[maxn][maxn];
int n,m,K;
ll v[maxm],pw[maxm][maxn],popcnt[maxn];
int lowbit(int x) {
return x & -x;
}
int popcount(int x) {
int ans = 0;
for(;x;x -= lowbit(x))++ ans;
return ans;
}
ll f[maxm][maxn][maxn][maxn >> 1];
int main() {
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
for(int i = 0;i <= m;++ i) {
scanf("%lld",&v[i]);
pw[i][0] = 1ll;
for(int j = 1;j <= n;++ j)pw[i][j] = pw[i][j - 1] * v[i] % mod;
}
for(int i = 0;i <= n;++ i) {
C[i][0] = 1ll;
for(int j = 1;j <= i;++ j) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
popcnt[i] = popcount(i);
}
f[0][0][0][0] = 1ll;
for(int i = 0;i <= m;++ i) {
for(int j = 0;j <= n;++ j) {
for(int k = 0;k <= K;++ k) {
for(int q = 0;q <= (n >> 1);++ q) {
for(int t = 0;t <= n - j;++ t) {
(f[i + 1][j + t][k + (t + q & 1)][t + q >> 1] += f[i][j][k][q] * C[n - j][t] % mod * pw[i][t] % mod) %= mod;
}
}
}
}
}
ll ans = 0;
for(int k = 0;k <= K;++ k) {
for(int q = 0;q <= (n >> 1);++ q) {
if(k + popcnt[q] <= K) {
(ans += f[m + 1][n][k][q]) %= mod;
}
}
}
printf("%lld\n",ans);
return 0;
}
题目3625 [NOIP 2021]数列
 8
评论
2024-06-22 16:48:27
|
|
|
令 $N=| S|$。 首先发现，枚举 $C$ 再判断前缀消耗的时间很多，这样行不通。 转向考虑枚举 $AB$，得出所有的 $(AB)^i$，不难发现可以用哈希+调和做到 $O(N\ln N)$。 现在考虑 $f(A)\le f(C)$ 的限制。 设 $pre(i)=f(S_{1\sim i}),suf(i)=f(S_{i+1\sim n})$。 当前枚举到 $AB$ 的长度为 $x$，则 $AB$ 对答案的贡献为 $\sum\limits_{i}\sum\limits_{j=1}^x [pre(j)\le suf(x\times i+1)]$。 预处理出 $pre(1\sim n),suf(1\sim n)$，用树状数组维护，时间复杂度为 $O(TN\ln N\log N)$。 虽然常数小，但只有 $84\text{pts}$。 仔细地思考下，这个东西真的必须要用树状数组维护吗？ 设 $sum(i,j)= \sum\limits_{k=1}^i [pre(i)\le j]$，则 $AB$ 的贡献变为 $\sum\limits_{i}sum(x,x\times i+1)$。 而 $sum$ 数组显然可以用前缀和维护。 时间复杂度 $O(T(N\ln N+N\times 26))$，足以通过。
题目3509 [NOIP 2020]字符串匹配
AAAAAAAAAAAAAAAAAAAAAAAAA
11
评论
2024-06-22 16:46:08
|
|
|
考虑枚举 $r$，计算出所有满足题意的 $l$ 的数量。 设 $S$ 为 $A$ 的前缀和数组，若 $L \le S_r - S_l \le R$，则区间 $(l,r]$ 满足题意。 作一个简单的变化就能求出 $S_l$ 的范围：$S_r - R\le S_l\le S_r - L$。 那么我们依次枚举 $1\ldots N$ 作为 $r$，维护 $S_0 \ldots S_{r - 1}$ 即可。 可以使用树状数组+离散化或者动态开点权值线段树，我选择的是树状数组+离散化。 时间复杂度 $O(N\log N)$。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
const int maxm = 4e5 + 5;
int n,cnt;
ll L,R,a[maxn],d[maxm],c[maxm],s[maxn];
int sum[maxm];
int lowbit(int x) {
return x & -x;
}
void add(int x,int y) {
if(!x)return ;
for(;x <= cnt;x += lowbit(x))sum[x] += y;
return ;
}
int query(int x) {
int ans = 0;
for(;x;x -= lowbit(x))ans += sum[x];
return ans;
}
int main() {
scanf("%d%lld%lld",&n,&L,&R);
d[++ cnt] = s[0] = 0;
for(int i = 1;i <= n;++ i) {
scanf("%lld",&a[i]);
s[i] = s[i - 1] + a[i];
d[++ cnt] = s[i];
d[++ cnt] = s[i] - L;
d[++ cnt] = s[i] - R;
}
for(int i = 1;i <= cnt;++ i)c[i] = d[i];
sort(c + 1 , c + 1 + cnt);
cnt = unique(c + 1 , c + 1 + cnt) - c - 1;
for(int i = 1;i <= 3 * n + 1;++ i)d[i] = lower_bound(c + 1 , c + 1 + cnt , d[i]) - c;
add(d[1] , 1);//提前插入 s[0]
ll ans = 0;
for(int i = 1;i <= n;++ i) {
ans += query((int)d[3 * i]) - query((int)d[3 * i + 1] - 1);
add((int)d[3 * i - 1] , 1);
}
printf("%lld",ans);
return 0;
}
题目3687 [BJOI2016]回转寿司
7
评论
2024-06-22 16:44:05
|
|
|
首先可以证明，当 $A$ 数组和 $B$ 数组均为升序排列时，$\sum\limits_{i=1}^n (a_i-b_i)^2$ 最小。 （upd：现在学到了，这个结论的原理是排序不等式） 但在这道题中，我们只需要让在升序排列中，两数组中下标相同的数对应即可。 以样例中 $A,B$ 数组为例，将它们分别离散后列出： $A: 2 \ \ 3 \ \ 1 \ \ 4$ $B: 3 \ \ 2 \ \ 1 \ \ 4$ 根据上述结论，当 $A_i = x$ 时，$B_i$ 也应该等于 $x$。 也就是说，如果建立一个数组 $C$，令 $C_{A_i}=B_i$ 的话，应该满足 $C_i=i$。 但在样例中，可以列出 $C$ 数组： $C: 1 \ \ 3 \ \ 2 \ \ 4$ 我们的目标是让 $C$ 数组升序排列，而每次交换最多消除一个逆序对。 故题目的答案就是 $C$ 数组的逆序对数。 求逆序对可以用树状数组或归并排序，代码中使用的是归并排序。 时间复杂度 $O(N\log N)$
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
int x,id;
node() {
x = id = 0;
}
node(int x,int id):x(x),id(id){}
bool operator < (const node& p)const {
return x < p.x;
}
}a[maxn],b[maxn];
int n,c[maxn],d[maxn];
typedef long long ll;
const ll mod = 1e8 - 3;
ll ans = 0;
void MergeSort(int l,int r) {
if(l >= r)return ;
int mid = l + r >> 1;
MergeSort(l , mid);
MergeSort(mid + 1 , r);
for(int k = l,i = l,j = mid + 1;k <= r;++ k) {
if(j > r||(i <= mid&&d[i] < d[j])) {
c[k] = d[i ++];
}
else c[k] = d[j ++],(ans += mid - i + 1) %= mod;
}
for(int k = l;k <= r;++ k)d[k] = c[k];
return ;
}
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i)scanf("%d",&a[i].x),a[i].id = i;
for(int i = 1;i <= n;++ i)scanf("%d",&b[i].x),b[i].id = i;
sort(a + 1 , a + 1 + n);
sort(b + 1 , b + 1 + n);
for(int i = 1;i <= n;++ i)d[a[i].id] = b[i].id;
MergeSort(1 , n);
printf("%lld",ans);
return 0;
}
题目1438 [NOIP 2013]火柴排队
7
评论
2024-06-22 16:42:45
|
|
|
（不知道为什么很多人把这题划分为树形 DP，我觉得是贪心）
Subtask 1：$m=1$
对于 $m=1$ 的情况，直接求树的直径即可。 时间复杂度 $O(n)$，期望得分 $\rm{20\ pts}$。
Subtask 2：$a_i=1$
菊花图的情况，按边权从大到小排序。
答案为 $\min\limits_{i=1}^m \{l_i+l_{2m-i+1}\}$。
时间复杂度 $O(n\log n)$，期望得分 $\rm{15\ pts}$
Subtask 3：$b_i=a_i+1$一条链的情况，显然二分答案，贪心判断即可。 时间复杂度 $O(n\log n)$，期望得分 $\rm{20\ pts}$。 Correct Answer显然这道题的主体是二分答案。 考虑判断当前答案 $k$ 是否满足。 我们要构造 $\ge m$ 条长度 $\ge k$ 的路径，而且还不能有重边。 一开始我在尝试淀粉质，但发现无重边这个东西实在是难以处理。 不如另辟蹊径，我们考虑枚举一个点 $u$ 对答案的贡献。 也就是经过点 $u$，且 $u$ 的深度是路径上所有点中深度的最小值的路径个数。 首先，递归到子树里，并把子树里 $\lt k$ 的最大一条路径长度穿上来，保存在一个 `std::multiset` 中。 然后利用 `std::multiset` 的二分统计答案，在这个过程中统计出 $\lt k$ 的最大路径长度，递归回去。 时间复杂度 $O(n\log^2 n)$。
// Problem: #438. 【NOIP2018】赛道修建
// Contest: UOJ
// URL: https://uoj.ac/problem/438
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define SIT std::multiset<int>::iterator
typedef std::pair<int,int> pii;
const int maxn = 5e4 + 5;
std::vector<pii> G[maxn];
int n,m,dp[maxn],ans,res;
void DFS(int u,int fa) {
for(auto& [v , w] : G[u]) {
if(v == fa)continue ;
DFS(v , u);
res = std::max(res , dp[u] + dp[v] + w);
dp[u] = std::max(dp[u] , dp[v] + w);
}
return ;
}
void GetMaxLength() {
res = 0;
DFS(1 , 0);
return ;
}
int dfs(int u,int fa,int k) {
std::multiset<int> s;
for(auto& [v , w] : G[u]) {
if(v == fa)continue ;
int t = dfs(v , u , k) + w;
if(t >= k)++ ans;
else s.insert(t);
}
int Max = 0;
for(;!s.empty();) {
res = *s.begin();
s.erase(s.begin());
SIT it = s.lower_bound(k - res);
if(it == s.end())Max = std::max(Max , res);
else s.erase(it),++ ans;
}
return Max;
}
int main() {
scanf("%d %d",&n,&m);
for(int i = 1,u,v,t;i < n;++ i) {
scanf("%d %d %d",&u,&v,&t);
G[u].pb(v , t);
G[v].pb(u , t);
}
GetMaxLength();
int l = 1,r = res,mid;
while(l <= r) {
mid = (l + r) >> 1;
ans = 0;
dfs(1 , 0 , mid);
if(ans >= m)l = mid + 1;
else r = mid - 1;
}
printf("%d\n",r);
return 0;
}
题目3055 [NOIP 2018]赛道修建
7
评论
2024-06-22 16:38:33
|
|
|
首先，两两互质等价于两个集合的质数集无交集。 那么从质数的方面考虑，不难想到状态压缩 DP。 但是打个表发现 $500$ 以内的质数接近 $100$ 个，显然压缩不了。 考虑一个解决这种问题相当常用的方法：根号分治。 注意到 $22$ 以内的质数只有 $8$ 个，而 $22$ 以上的质数至多会被一个数包含一次，称这些质数为「大质数」。 因为它们至多被包含一次，我们可以直接分类讨论它们在哪个集合。 具体地，我们把前 $8$ 个质数压缩状态，把 $2\sim n$ 除去前 $8$ 个质数的结果升序排序。 依次枚举 $2\sim n$，开三个 DP 数组： $f(j,k)$：表示当前第一个集合状态为 $j$，第二个集合状态为 $k$ 的方案数。 $F(j,k)$：表示当前第一个集合状态为 $j$，第二个集合状态为 $k$，且当前枚举到的「大质数」都在第一个集合的方案数。 $G(j,k)$：表示当前第一个集合状态为 $j$，第二个集合状态为 $k$，且当前枚举到的「大质数」都在第二个集合的方案数。 注：其实这里本该是 $f(i,j,k)$，不过可以直接滚动数组滚掉第一维的阶段，所以我没有写在式子里。 转移相当简单：$F(j|s,k)=\sum F(j,k),G(j,k|s)=\sum G(j,k)$ 而 $f$ 数组较为特殊：$f(j,k)=F(j,k)+G(j,k)-f(j,k)$ 原因不难理解：$F(j,k),G(j,k)$ 都经过了一轮转移，但 $f(j,k)$ 还保留着上一轮的结果。 直接 $F(j,k)+G(j,k)$ 会将 $f(j,k)$ 计算两遍，所以要再减回来。 还有一些小细节：比如 $f(j,k)$ 复制到 $F(j,k),G(j,k)$，以及 $f(j,k)$ 的计算条件可以参考代码。 时间复杂度 $\mathcal{O}(n\times 2^{16})$
// Problem: #129. 【NOI2015】寿司晚宴
// Contest: UOJ
// URL: https://uoj.ac/problem/129
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
typedef long long ll;
typedef std::pair<int,int> pii;
const int maxn = 505;
int n,prime[10] = {2 , 3 , 5 , 7 , 11 , 13 , 17 , 19};
pii a[maxn];
ll p,f[maxn][maxn],F[maxn][maxn],G[maxn][maxn];
int main() {
scanf("%d %lld",&n,&p);
for(int i = 2;i <= n;++ i) {
auto& [s , res] = a[i];
res = i;
for(int k = 0;k < 8;++ k) {
if(res % prime[k])continue ;
s |= 1 << k;
for(;!(res % prime[k]);res /= prime[k]);
}
}
std::sort(a + 2 , a + n + 1 , [&](const pii& p,const pii& q) {
return p.second < q.second;
});
f[0][0] = 1;
for(int i = 2;i <= n;++ i) {
auto& [s , res] = a[i];
if(res == 1||res != a[i - 1].second) {
memcpy(F , f , sizeof(f));
memcpy(G , f , sizeof(f));
}
for(int j = 255;~ j;-- j) {
for(int k = 255;~ k;-- k) {
if(j & k)continue ;
if(!(s & k))(F[j | s][k] += F[j][k]) %= p;
if(!(s & j))(G[j][k | s] += G[j][k]) %= p;
}
}
if(i == n||res == 1||res != a[i + 1].second) {
for(int j = 0;j < 256;++ j) {
for(int k = 0;k < 256;++ k) {
if(j & k)continue ;
f[j][k] = (F[j][k] + G[j][k] - f[j][k] + p) % p;
}
}
}
}
ll ans = 0;
for(int j = 0;j < 256;++ j) {
for(int k = 0;k < 256;++ k) {
if(j & k)continue ;
(ans += f[j][k]) %= p;
}
}
printf("%lld",ans);
return 0;
}
题目2020 [NOI 2015]寿司晚宴
7
评论
2024-06-22 16:32:43
|