差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:20200715比赛记录 [2020/07/16 14:54]
wzx27
+++ 2020-2021:teams:wangzai_milk:20200715比赛记录 [2020/07/16 16:56] (当前版本)
infinity37 [I - K Subsequence]
@@ 行 13: / 行 13: @@
 ===== 题解 =====
+==== D - Distribution of books ====
+题意：将一个数字序列的前x数字划分为k组，保证这k组数字的组和最大值最小。
+最大值最小很自然的就能想到二分答案，于是考虑如何在知道最大数字组和的情况下检查是否能够分为满足情况的k组。考虑dp，设$f_i$为对于到第$i$个数字最多能被分为满足答案的几组，那么dp方程就是$f_i = max(f_j)+1, sum_i - ans \leq sum_j$,于是可以按照sum为下标维护一个线段树，线段树的值是sum对应的dp值最大值，然后每次查一个后缀最大值就行了，好像树状数组也行。
+<hidden><code c++>
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+const int inf = 1<<30;
+const ll INF = 1ll<<60;
+const int N = 2e5+5;
+int n,k,dp[N],tr[N<<2],a[N],cnt;
+ll id[N],sum[N];
+void build(int p,int l,int r) {
+	tr[p] = -1;
+	if (l==r)return;
+	int mid = (l+r)>>1;
+	build(p<<1,l,mid);
+	build(p<<1|1,mid+1,r);
+}
+void _update(int p,int l,int r,int a,int b) {
+	if (l==r) {
+		tr[p] = max(tr[p],b);
+		return ;
+	}
+	int mid = (l+r)>>1;
+	if (a<=mid)_update(p<<1,l,mid,a,b);
+	else _update(p<<1|1,mid+1,r,a,b);
+	tr[p] = max(tr[p<<1],tr[p<<1|1]);
+}
+int gtaaans(int p,int l,int r,int a,int b) {
+	if (l>=a&&r<=b) return tr[p];
+	int ans = -1;
+	int mid = (l+r)>>1;
+	if (a<=mid)ans = max(ans,gtaaans(p<<1,l,mid,a,b));
+	if (b >mid)ans = max(ans,gtaaans(p<<1|1,mid+1,r,a,b));
+	return ans;
+}
+int lower(ll x) {
+	return lower_bound(id+1,id+n+1,x)-id;
+}
+int upper(ll x) {
+	return upper_bound(id+1,id+n+1,x)-id;
+}
+bool check(ll ans) {
+	build(1,1,cnt);
+	bool flag = false;
+	_update(1,1,cnt,lower(0),0);
+	for (int i = 1;i<= n;i++)
+	{
+		dp[i] = 0;
+		ll temp = sum[i]-ans;
+		int pos = lower(temp);
+		if (pos>cnt)continue;
+		int dpj = gtaaans(1,1,cnt,pos,cnt);
+		if (dpj == -1)continue;
+		else dp[i] = max(dp[i],dpj+1);
+		_update(1,1,cnt,lower(sum[i]),dp[i]);
+		if (dp[i]>=k) {flag = true;break;}
+	}
+	return flag;
+}
+int main()
+{
+	int cas;
+	scanf("%d",&cas);
+	while (cas--) {
+		scanf("%d%d",&n,&k);
+		for (int i = 1;i<= n;i++)
+		{
+			scanf("%d",&a[i]);
+			sum[i] = sum[i-1]+a[i];
+			id[i] = sum[i];
+		}
+		id[n+1] = 0;
+		sort(id+1,id+n+2);
+		cnt = unique(id+1,id+n+2)-id-1;
+		ll L = -2e14-5,R = 2e14+5,mid;
+		while (L<R) {
+			mid = (L+R)>>1;
+			if (check(mid))
+				R = mid;
+			else L = mid+1;
+		}
+		printf("%lld\n",R);
+	}
+}
+</code></hidden>
+\\
 ==== F - Fansblog ====
 给一个大质数 $1e9 \le P \le 1e14$，求小于它的最大质数 $Q$ 的阶乘 $Q!$ 模 $P$ 的值。
-猜 $Q$ 和 $P$ 之间差距不会太大，从 $P-1$ 往下枚举，用米勒拉宾素性测试。然后求阶乘的时候考虑威尔逊定理（学到了）：$(P-1)! \euquiv -1 \mod P$，注意要用快速乘^^_
+猜 $Q$ 和 $P$ 之间差距不会太大，从 $P-1$ 往下枚举，用米勒拉宾素性测试。然后求阶乘的时候考虑威尔逊定理（学到了）：$(P-1)! \equiv -1 \mod P$，注意要用快速乘^^_
 <hidden code> <code cpp>
@@ 行 267: / 行 358: @@
 </code></hidden>
 \\
+==== I - K Subsequence ====
+题意：给定一个数字序列，求k个不下降子序列，使得这些子序列的和最大。
+不下降子序列最大和好像是个比较经典的费用流模型，每个数字拆点，所有原点连这个数字前面的点，后面的点连汇点（流量1，费用0），两个点之间连流量为1，费用为$-a_i$的边，这个要找k个，那就在原点前面再连个超级原点，汇点后面来个超级汇点，流量为k即可。
+<hidden><code c++>
+#include <bits/stdc++.h>
+using namespace std;
+#define fi first
+#define se second
+typedef long long ll;
+const int INF = 1<<30;
+const int N = 4e3+20;
+typedef pair<int, int> pii;
+struct Edge {
+    int to, cap, cost, rev;
+    Edge() {}
+    Edge(int to, int _cap, int _cost, int _rev):to(to), cap(_cap), cost(_cost), rev(_rev) {}
+};
+int V;
+int h[N];
+int dis[N];
+int prevv[N];
+int pree[N];
+vector<Edge> G[N];
+void init(int n) {
+    V = n;
+    for(int i = 0; i <= V; ++i) G[i].clear();
+}
+void add(int x, int y, int cap, int cost){
+    G[x].push_back(Edge(y, cap, cost, G[y].size()));
+    G[y].push_back(Edge(x, 0, -cost, G[x].size() - 1));
+}
+int MCMF(int s, int t, int f, int &flow) {
+    int res = 0;
+    for(int i = 0; i < 1 + V; i++) h[i] = 0;
+    while(f){
+        priority_queue<pii, vector<pii>, greater<pii> > q;
+        for(int i = 0; i < 1 + V; i++) dis[i] = INF;
+        dis[s] = 0; q.push(pii(0, s));
+        while(!q.empty()) {
+            pii now = q.top(); q.pop();
+            int v = now.second;
+            if(dis[v] < now.first) continue;
+            for(int i = 0; i < G[v].size(); ++i) {
+                Edge &e = G[v][i];
+                if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]){
+                    dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
+                    prevv[e.to] = v;
+                    pree[e.to] = i;
+                    q.push(pii(dis[e.to], e.to));
+                }
+            }
+        }
+        if(dis[t] == INF) break;
+        for(int i = 0; i <= V; ++i) h[i] += dis[i];
+        int d = f;
+        for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][pree[v]].cap);
+        f -= d; flow += d; res += d * h[t];
+        for(int v = t; v != s; v = prevv[v]) {
+            Edge &e = G[prevv[v]][pree[v]];
+            e.cap -= d;
+            G[v][e.rev].cap += d;
+        }
+    }
+    return res;
+}
+int num[N];
+int main() {
+	int cas;
+	scanf("%d",&cas);
+	while (cas--)
+	{
+		int n,k;
+		scanf("%d%d",&n,&k);
+		int s = 2*n+1,t = 2*n+2;
+		int S = s+2,T = t+2;
+		init(n*2+4);
+		for (int i = 1;i<= n;i++)
+		{
+			scanf("%d",&num[i]);
+			add(s,i,1,0);
+			add(i+n,t,1,0);
+			add(i,i+n,1,-num[i]);
+		}
+		for (int i = 1;i<= n;i++)
+			for (int j = i+1;j<= n;j++)
+				if (num[j] >= num[i])
+					add(i+n,j,1,0);
+		add(S,s,k,0);add(t,T,k,0);
+		int flow = k;
+		printf("%d\n", -MCMF(S,T,INF,flow));
+	}
+	return 0;
+}
+</code></hidden>
+\\
 ==== K - Squrirrel ====

CVBB ACM Team

用户工具

站点工具

差别

页面工具