线段树(懒标记) + 区间贪心
好家伙，乍一看是网络流...求最大流...
个人认为是个好题！！！重点分析一下：
题解：
https://blog.csdn.net/iroy33/article/details/88894362?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164846947416782089346345%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164846947416782089346345&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-4-88894362.142^v5^pc_search_result_cache,143^v6^control&utm_term=+L3-017+%E6%A3%AE%E6%A3%AE%E5%BF%AB%E9%80%92+%2830+%E5%88%86%29&spm=1018.2226.3001.4449
题意：
给n-1个长度为1的小区间(连在一起的)，每个小区间有一个容量限制(所有经过这个小区间的流量总和<容量限制)，
给m个询问点对a b，每个询问点对a b就表示，a向b流东西；要你选若干个点对，使得总流量最大。
区间问题：怎么选？怎么排序？
1. 首先很直观的，每个点对之间的最大流量就是其路径上小区间的最小值
2. 我们把询问点对转换成询问区间，比较好看一点
3. 画一下图，就能发现得开始分类讨论了：(开始贪心)
(1)两个询问区间没有交集，则我们这两个询问区间都要流满
(2)如果出现覆盖的情况，则选则小的询问区间，因为大区间收到的限制更多，而且占用更多资源
(3)出现两个有部分交集的情况：假设前一个区间[l1,r1]的流量为f1，后一个[l2,r2]为f2
则一定要满足f1 < min([l1,r1]) , f2 < min([l2,r2]) , f1+f2 < min(中间交集部分)。
我们考虑这样一种方法：
先直接取d = min([l1,r1])，[l1,r1]的小区间全部 - d，然后处理[l2,r2]；
如果[l1,r1][l2,r2]交集部分出现负数，则说明选[l1,r1]比选[l2,r2]更优，选[l1,r1]是对的；
如果交集部分不是负数，则说明处理完[l1,r1]后，[l2,r2]还可以流一些，则我们继续取min([l2,r2])就行！！！
这样一直取到最后就是最优解了！
4. 下面考虑如何对询问区间进行排序：
由于我们的思想，所以我们要尽量让区间展开，所以可以先按照右端点从小到大排；
如果相等，则说明出现区间包含的情况，则我们要先处理小的区间，所以再按照左端点从大到小排。
（右端点相同，左端点越大，区间越短）
为什么不能先左端点从小到大排呢？考虑如果有区间包含的情况，这样排的话大区间先处理，这显然是不行的；
而按照右端点先排，则大区间会后处理，是对的！！！
5. 因此：
我们就读的时候处理一下区间，排个序，从前往后扫，用线段树维护小区间，每次查询出最小值；
然后区间修改，重复...所以要用到懒标记...
6. 思考一下懒标记下传的时候，这个区间最小值要怎么维护？？？
【】 注意这里我们的懒标记是区间加减，并不影响区间最小值的确定，
【】【】 所以下传的时候只需要让区间的最小值也-lazy就行，即tr[左右儿子].v -= lazy;
7. 注意：按照y总的想法，这里的懒标记是不包含当前区间的，所以在打懒标记的时候，当前区间的最小值也要更新！！！
学到了，这个题！！！
#include<iostream>
#include<bits/stdc++.h>
#include<map>
#include <unordered_map>
#define pb push_back
#define coutt cout<<"------------"<<endl;
#define int long long
using namespace std;
// typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
int n,m;
int w[maxn];
struct node //维护小区间，最小值
{
int l,r;
int v;
int lazy; //懒标记
}tr[maxn * 4];
struct Point //点对
{
int sta,en;
}po[maxn];
bool cmp(Point a,Point b)
{
if(a.en == b.en) return a.sta > b.sta;
return a.en < b.en;
}
void pushup(int u)
{
tr[u].v = min(tr[u*2].v , tr[u*2+1].v);
}
void pushdown(int u) //下传懒标记
{
if(tr[u].lazy) //如果当前有懒标记
{
tr[u*2].lazy += tr[u].lazy;
tr[u*2+1].lazy += tr[u].lazy;
tr[u*2].v += tr[u].lazy;
tr[u*2+1].v += tr[u].lazy;
tr[u].lazy = 0; //清空懒标记
}
}
void build(int u,int l,int r)
{
if(l == r) tr[u] = {l,r,w[r],0};
else
{
tr[u] = {l,r}; //这个别忘了！
int mid = (l + r) >> 1;
build(u*2, l, mid); //建左边
build(u*2+1, mid + 1, r); //建右边
pushup(u);
}
}
void update(int u,int l,int r,int v)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].lazy += v; //打懒标记
tr[u].v += v; //记得更新最小值(懒标记是不包含当前区间的哦)
return;
}
pushdown(u); //区间要裂开，下传懒标记
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) update(u*2, l, r, v); //左边有交集，走左边
if(r > mid) update(u*2+1, l, r, v);
pushup(u);
}
int query(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
pushdown(u); //下传懒标记
int mid = (tr[u].l + tr[u].r) >> 1;
int l_min = 1e18 , r_min = 1e18; //注意这里要设置成1e18，不然最后一个点过不去
if(l <= mid) l_min = query(u*2,l,r); //左边有交集，查左边
if(r > mid) r_min = query(u*2+1,l,r);
return min(l_min , r_min);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<n;i++) scanf("%lld", &w[i]); //输入小区间
build(1,1,n-1); //对小区间建树，只有n-1个哦
for(int i=1;i<=m;i++) //输入点对
{
int a,b;
cin>>a>>b;
if(a > b) swap(a,b);
po[i] = {a,b};
}
sort(po+1,po+1+m,cmp);
int ans = 0;
for(int i=1;i<=m;i++)
{
int sta = po[i].sta;
int en = po[i].en;
//按照题目的下标设定，应该查询[sta,en-1]，但是由于我是[1,n]建树，所以查询区间改成[sta+1,en]
int num = query(1,sta+1,en);
if(num > 0) //正数才加流量
{
ans += num;
update(1,sta+1,en,-num); //当前区间-num
}
}
cout<<ans<<endl;
return 0;
}
等待下一道…
蓝桥杯——垒骰子（dfs dp 矩阵快速幂 ）
ps：蓝桥杯的题是真的难…
题解：https://blog.csdn.net/Zhengyangxinn/article/details/105391972?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165372037116780366591399%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165372037116780366591399&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-105391972-null-null.142^v11^pc_search_result_control_group,157^v12^new_style1&utm_term=%E5%9E%92%E9%AA%B0%E5%AD%90&spm=1018.2226.3001.4449
1、先暴力一波，每个合法方案最后每个骰子能转动4次，即共4^n;
所以暴力dfs出合法方案数，然后*(4^n)
int vis[10][10]; //标记是否互斥
int mp[10]; //标记对面
void init()
{
mp[1] = 4;
mp[4] = 1;
mp[2] = 5;
mp[5] = 2;
mp[3] = 6;
mp[6] = 3;
}
int n,m;
ll ans;
int dfs(int u,ll cnt)
{
if(cnt == 0) return 1;
ll sum = 0;
for(int i=1;i<=6;i++)
{
if(vis[i][u]) continue;
sum = (sum + dfs(mp[i],cnt-1)) % mod;
}
return sum;
}
int main()
{
init();
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
vis[a][b] = vis[b][a] = 1;
}
for(int i=1;i<=6;i++) ans = (ans + dfs(mp[i],n-1)) % mod; //枚举第一个骰子下面的面
cout<<(ans*qmi(4,n,mod)%mod) % mod<<endl;
return 0;
}
2、优化一下，用dp，具体看题解，好难哇！
int vis[10][10]; //标记是否互斥
int mp[10]; //标记对面
void init()
{
mp[1] = 4;
mp[4] = 1;
mp[2] = 5;
mp[5] = 2;
mp[3] = 6;
mp[6] = 3;
}
int n,m;
ll sum;
ll dp[maxn][7]; //dp[i][j]表示垒完第i个骰子，向下的面是j的合法方案数
int main()
{
init();
cin>>n>>m;
while(m--)
{
int a,b;
cin>>a>>b;
vis[a][b] = vis[b][a] = 1;
}
for(int i=0;i<=6;i++) dp[1][i] = 1; //初始化
for(int i=2;i<=n;i++) //从第2个骰子开始枚举
{
for(int j=1;j<=6;j++) //枚举i-1个骰子向下的面
{
for(int k=1;k<=6;k++) //枚举第i个骰子向下的面
{
if(vis[mp[j]][k]) continue;
dp[i][k] = (dp[i][k] + dp[i-1][j]) % mod;
}
}
}
sum = 0;
for(int i=1;i<=6;i++) sum = (sum + dp[n][i]) % mod;
ll ans = (sum * qmi(4,n,mod)) % mod;
cout<<ans<<endl;
return 0;
}
矩阵快速幂
