网站建设可以用什么语言,企业管理软件定制开发,wordpress下载地址插件,做推广哪个平台效果好E - Lucky bag(简单状态压缩dp#xff09;
题目链接 题意#xff1a;给你n个物品#xff0c;m个福袋#xff0c;让你将这n个物品用m个福袋打包(福袋可以为空#xff09;#xff0c;让分完之后的总方差最小#xff0c;输出最小方差。
思路#xff1a;其实由题目的数据… E - Lucky bag(简单状态压缩dp
题目链接 题意给你n个物品m个福袋让你将这n个物品用m个福袋打包(福袋可以为空让分完之后的总方差最小输出最小方差。
思路其实由题目的数据范围n16可以大概推出应该是状态压缩dp
我们用f [ i ][ j ] 表示当前状态 i (二进制表示用 j 个袋子的最小平方差
那么我们的答案就是f [(1n)-1][ d ]/d;
如何状态计算和状态转移呢
那么应该有两种状态转移
1第一种就是加空福袋
2第二种就是f[i][j] f[i-x][j-1] f[x][1],其中x为j的子集就是转移前的一个转态 题解代码
#include bits/stdc.h
using namespace std;
int main(void)
{int n, d, x;long double w[15];long double ave 0;long double dp[(1 15)][16];long double y;cin n d;for (int i 0; i n; i) // 计算总体均值cin w[i], ave w[i];ave / ((long double)d);for (int i 0; i (1 n); i) // 枚举所有状态{y 0; // 统计该状态下的物品花费for (int j 0; j n; j){if (i (1 j))y w[j];}dp[i][1] pow(y - ave, 2);for (int j 2; j d; j) // 进行状态转移{dp[i][j] dp[i][j - 1] dp[0][1]; // 1:物品数不变多了一个空袋子x i;while (x 0) // 2:枚举其状态转移的上一个状态,遍历j的i的所有子集{dp[i][j] min(dp[i][j], dp[i - x][j - 1] dp[x][1]);x (x - 1) i;// cout x endl;}}}cout setprecision(10) (dp[(1 n) - 1][d] / ((long double)d)) endl;return 0;
} F - Random Update Query
题意给你一个长度为n为数组以及m次操作每次操作给出 l , r , x将 l 到 r 里面随机一个数改为x问数组的期望值
思路其实简单分析一下可以知道就是涉及加法乘法双懒标记以及区间修改单点查询的线段树,(懒标记维护时先乘后加就是板子
#include bits/stdc.h
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl \n
#define lowbit(x) x (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pairint, int PII;
typedef pairdouble, double PDD;
#define LF(x) fixed setprecision(x)
#define max(a, b) (((a) (b)) ? (a) : (b))
#define min(a, b) (((a) (b)) ? (a) : (b))
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N 1e6 10, M 1010, inf 0x3f3f3f3f, mod 998244353, P 13331;
const double eps 1e-8;
int n, m;
int w[N];
struct node
{int l, r;int sum;int add;int mul;
} tr[N 2];
int qpow(int a, int b)
{int res 1;while (b){if (b 1)res res * a % mod;a a * a % mod;b 1;}return res;
}
void change(int u, int ADD, int MUL)
{tr[u].sum tr[u].sum * MUL % mod (tr[u].r - tr[u].l 1) * ADD % mod;tr[u].mul tr[u].mul * MUL % mod;tr[u].add (tr[u].add * MUL % mod ADD) % mod;
}
void pushdown(int u)
{change(u 1, tr[u].add, tr[u].mul);change(u 1 | 1, tr[u].add, tr[u].mul);tr[u].add 0;tr[u].mul 1;
}
void pushup(int u)
{tr[u].sum (tr[u 1].sum tr[u 1 | 1].sum) % mod;
}
void build(int u, int l, int r)
{tr[u] {l, r, 0, 0, 1};if (l r){tr[u] {l, r, w[l], 0, 1};return;}int mid l r 1;build(u 1, l, mid);build(u 1 | 1, mid 1, r);pushup(u);
}
void modify(int u, int l, int r, int ADD, int MUL)
{if (tr[u].l l tr[u].r r){change(u, ADD, MUL);return;}pushdown(u);int mid tr[u].l tr[u].r 1;if (l mid)modify(u 1, l, r, ADD, MUL);if (r mid)modify(u 1 | 1, l, r, ADD, MUL);pushup(u);
}
int query(int u, int x)
{if (tr[u].l x tr[u].r x)return tr[u].sum;pushdown(u);int ans 0;int mid tr[u].l tr[u].r 1;if (x mid)return query(u 1, x);elsereturn query(u 1 | 1, x);
}
void solve()
{cin n m;for (int i 1; i n; i)cin w[i];build(1, 1, n);while (m--){int l, r, x;cin l r x;int t r - l 1;int p qpow(t, mod - 2);modify(1, l, r, x * p % mod, (t - 1) * p % mod); // 前面为要加的数后面为要乘的数}for (int i 1; i n; i)cout query(1, i)%mod ;
}
signed main()
{Yshanqian;int T;T 1;// cin T;for (int cases 1; cases T; cases){// coutCase #cases: ;solve();}return 0;
}
