题目链接：https://vjudge.net/contest/147974#overview。
A题，费用流，不会。。跳过了。
B题，给一个图，问至少添加几条边能成为强连通图。显然缩点，要使得成为一个scc，任意一个点都要至少一个入度和出度，而一条边可以提供一个入度和出度，因为答案为max（入度为0的点，出度为0的点）。如果要求最多能添加几条使得还不是scc，则参照：最多添加几条使得还不是scc。如果是无向图问至少添加几条使得是边双联通，则参照：至少添加几条使得边双联通。
C题，线段树区间合并，貌似暑假的时候写过类似的，但是忘记了。。代码如下：
//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define t_mid (l+r>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls,l,t_mid
#define rson rs,t_mid+1,r
using namespace std;
const int N = + ; int a[N];
// sub表示节点o的lcis的最长长度，l_val和r_val分别表示这个节点最左边和最右边的值分别是多少
// l_sub表示这个节点从最左边开始的最长的lcis的长度，r_sub同
int sub[N<<],l_val[N<<],r_val[N<<],l_sub[N<<],r_sub[N<<];
int T,n,q;
void up(int o,int l,int r)
{
int len = r - l + ;
l_val[o] = l_val[ls], r_val[o] = r_val[rs]; // 更新l_val,r_val
// 更新sub的值
sub[o] = max(sub[ls], sub[rs]);
if(r_val[ls] < l_val[rs]) sub[o] = max(sub[o], r_sub[ls]+l_sub[rs]); // 更新l_sub,r_sub
l_sub[o] = l_sub[ls];
if(l_sub[o] == len-len/ && r_val[ls] < l_val[rs]) l_sub[o] += l_sub[rs]; r_sub[o] = r_sub[rs];
if(r_sub[o] == len/ && r_val[ls] < l_val[rs]) r_sub[o] += r_sub[ls];
}
void build(int o,int l,int r)
{
if(l == r)
{
sub[o] = l_sub[o] = r_sub[o] = ;
l_val[o] = r_val[o] = a[l];
return ;
}
build(lson);
build(rson);
up(o,l,r);
}
void update(int o,int l,int r,int pos,int x)
{
if(l == r)
{
l_val[o] = r_val[o] = x;
return ;
}
if(pos <= t_mid) update(lson,pos,x);
else update(rson,pos,x);
up(o,l,r);
}
int query(int o,int l,int r,int ql,int qr)
{
if(l == ql && r == qr) return sub[o];
int ans = ;
if(qr <= t_mid) ans = query(lson,ql,qr);
else if(ql > t_mid) ans = query(rson,ql,qr);
else
{
ans = max(query(lson,ql,t_mid), query(rson,t_mid+,qr));
// 注意下面一行的两个min
if(r_val[ls] < l_val[rs]) ans = max(ans, min(r_sub[ls], t_mid-ql+) + min(l_sub[rs], qr-t_mid));
}
return ans;
} int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",a+i);
build(,,n);
while(q--)
{
char s[];
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[] == 'U') update(,,n,x+,y);
else printf("%d\n",query(,,n,x+,y+));
}
}
return ;
}
线段树区间合并
D题，分组背包，每组中，先选择一个，然后该组中其他的有三个选择，不选，或者从之前一组中转移（也就是放弃了这组中第一个选的而选这组中的这个），或者从这组中的转移（这组中的第一个要选）。代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <stack>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
const int N = + ; int n,m,k;
vector<pii> v[];
int dp[][+]; int main()
{
while(scanf("%d%d%d",&n,&m,&k) == )
{
for(int i=;i<=k;i++) v[i].clear();
for(int i=;i<=n;i++)
{
int pos,mo,val;
scanf("%d%d%d",&pos,&mo,&val);
v[pos].push_back(pii(mo,val));
}
int sum = ;
int flag = ;
for(int i=;i<=k;i++)
{
if(v[i].size() == )
{
flag = ;
break;
}
sort(v[i].begin(), v[i].end());
sum += v[i][].first;
}
if(sum > m || flag == )
{
printf("Impossible\n");
continue;
}
memset(dp,,sizeof dp);
for(int i=;i<=k;i++)
{
for(int j=;j<v[i].size();j++)
{
int w = v[i][j].first, val = v[i][j].second;
for(int mask=m;mask>=w;mask--)
{
if(j == ) dp[i][mask] = dp[i-][mask-w] + val;
else dp[i][mask] = max({dp[i][mask], dp[i-][mask-w]+val, dp[i][mask-w]+val});
}
}
}
printf("%d\n",dp[k][m]);
}
}
分组背包
E题，直接暴力枚举即可。完全背包也行。第一次wa是因为认为贪心先拿最小的最优，其实不然。例如：53--10,11,23。显然11的拿3个再拿10的两个比较好。