郧阳中学12/3周考题解
这周周考被基础算法虐翻了。%%%wxgdalao
命题人
wxg
题目列表
赛题 #A: zcr搞破坏 | 贪心
赛题 #B: zcr爱吃鸡2 | 离散化，二分答案，枚举，模拟
赛题 #C: zcr解谜题 | DP，最大子矩阵
zcr搞破坏
一句话题意
给出一个无向图，要求删掉图上的所有点。每一次删点的消耗是所有跟该点相连的所有未删除点的点权和。分别求最大权删法和次小权删法的消耗和。保证数据中无自环，且两点间最多有1条连边。
解法
100% 1 \leq n,\ m,\ a_i \leq 10^6
本题考察贪心思想。
试想对于边 (u, v) ，其中必然会有一个点会被加入最终答案。得到此性质后，考虑如何求最大权和最小权。对于求最大权的情况，我们需要把边中权值较大的点加入答案，而删除较小的点。
正确性的证明方面，我们应该考虑上面这个操作的完整形式。对于求最大权的情况，完整的操作应当是先对边以其中的较大权点的权值进行降序排序，再以该顺序删除每边中较大权的点。在这个过程中，大权点一定比小权点先被删除，因此能够保证求出答案的最优性。由于该操作要对每一条边进行，排序自然就没有必要，因此才有了上面的那种操作。
最小权的操作类比于最大权的操作。
关于求次小权，次小权一定存在于将最优删点顺序中相邻两点调换后的顺序的答案中，因此我们枚举调换的是哪两个点。考虑调换后对答案产生的影响，由于相邻两点的调换不会影响这两点之前、之后序列的单调性，因此只有两点间的连边会对答案造成影响。由于最多只可能有一条这样的边，我们检查是否有边，若无边则次小权等于最小权（无边对答案无影响），否则维护两点权值差的绝对值（即对答案产生的影响），次小权即是最小权加上前面影响的最小值。
总复杂度 O(nlogn) 。
代码
// Code by KSkun, 2017/12
#include <cstdio>
#include <vector>
#include <algorithm>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
int n, m, kase, a[1000005], order[1000005], ut, vt;
long long resmax = 0, resmin = 0;
std::vector<int> vec[1000005];
inline bool cmp(int u, int v) {
return a[u] < a[v];
}
int main() {
n = read();
m = read();
kase = read();
for(int i = 1; i <= n; i++) {
a[i] = read();
if(kase == 2) order[i] = i;
}
for(int i = 0; i < m; i++) {
ut = read();
vt = read();
resmax += std::max(a[ut], a[vt]);
if(kase == 2) {
vec[ut].push_back(vt);
vec[vt].push_back(ut);
resmin += std::min(a[ut], a[vt]);
}
}
printf("%lld ", resmax);
if(kase == 1) {
return 0;
}
std::sort(order + 1, order + n + 1, cmp);
long long minn = 1e15;
for(int i = 1; i < n; i++) {
int u = order[i];
bool success = false;
for(int j = 0; j < vec[u].size(); j++) {
int v = vec[u][j];
if(v == order[i + 1]) {
success = true;
break;
}
}
minn = std::min(minn, 0ll + a[order[i + 1]] - a[u]);
if(!success) {
minn = 0;
break;
}
}
printf("%lld", resmin + minn);
return 0;
}
zcr爱吃鸡2
一句话题意
给出一些点，求能够包含其中C个点的最小正方形边长。
解法
100% n \leq 1000
本题考察二分答案和枚举。
代码中，check()函数用于枚举行，check1()函数用于枚举列。
二分答案确定正方形边长的取值。然后枚举可能的正方形并且检验即可。
总复杂度O(n^2logn)。
代码
// Code by KSkun, 2017/12
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <vector>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0;
while(*s < '0' || *s > '9') s++;
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res;
}
} ip;
#define read ip.read
std::vector<std::pair<int, int> > points;
std::vector<int> tmp;
int c, n, xt, yt;
inline bool check1(int l, int r, int p) {
// 枚举列
if(r - l + 1 < c) return false;
tmp.clear();
for(int i = l; i <= r; i++) {
tmp.push_back(points[i].second);
}
sort(tmp.begin(), tmp.end());
for(int i = c - 1; i < tmp.size(); i++) {
if(tmp[i] - tmp[i - c + 1] <= p) return true;
}
return false;
}
inline bool check(int p) {
// 枚举行
int lastp = 0;
for(int i = 0; i < n; i++) {
if(points[i].first - points[lastp].first > p) {
//printf("i %d lastp %d\n", points[i].first, points[lastp].first);
if(check1(lastp, i - 1, p)) return true;
while(points[i].first - points[lastp].first > p) lastp++;
}
}
if(check1(lastp, n - 1, p)) return true;
return false;
}
int main() {
c = read();
n = read();
for(int i = 0; i < n; i++) {
xt = read();
yt = read();
points.push_back(std::make_pair(xt, yt));
}
std::sort(points.begin(), points.end());
int l = 0, r = 10005, mid;
while(r - l > 1) {
mid = (l + r) >> 1;
//printf("mid %d\n", mid);
if(check(mid)) r = mid;
else l = mid;
}
printf("%d", r + 1);
return 0;
}
感想
本题中有一些暴力技巧降低复杂度，可以学习。
zcr解谜题
一句话题意
给出一个矩阵，求最大子矩形。其中，你有一次机会把任何数字改成给定值。
解法
80% n, m \leq 100
显然我们需要更改的只有可能是选中的矩形的最小值。
最小子矩形DP+预处理最小值。
总复杂度O(n^4)
100% n, m \leq 300
考虑使用DP来递推“是否修改数字”这一状态。
dp[k][0/1]表示第k行未修改过(0)/修改过(1)数字的结果，状态转移方程如下
\begin{array}{l} dp[k][0] = max\{dp[k-1][0], 0\} + sum[k] \\ dp[k][1] = max\{dp[k-1][1], dp[k-1][0] + P - min[k]\} + sum[k] \end{array}
其中sum[k]代表当前选中的左右边界中第k行的和，min[k]代表边界中第k行的最小值。
答案在每个dp状态中，所以完成一次转移就要更新答案。
我们枚举矩形的左右边界，每一次枚举进行DP，即可得到总答案。
其实上述DP方法应该说是最大子矩形DP的一种变形，基本思路是一致的。
标程 by wxg
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,p,a[305][305],sum[305],qz[305][305],minn[305],dp[305][2],ans;
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j],qz[i][j]=qz[i][j-1]+a[i][j];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
minn[j]=a[j][i];
for(int j=i;j<=m;j++)
{
for(int k=1;k<=n;k++)
{
minn[k]=min(minn[k],a[k][j]);
sum[k]=qz[k][j]-qz[k][i-1];
}
dp[0][0]=0,dp[0][1]=-0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
dp[k][0]=max(dp[k-1][0],0)+sum[k];
dp[k][1]=max(dp[k-1][1]+sum[k],max(dp[k-1][0],0)+sum[k]-minn[k]+p);
}
for(int k=1;k<n;k++) ans=max(ans,max(dp[k][0],dp[k][1]));
if(i==1&&j==m)
{
ans=max(ans,dp[n][1]);
int cnt=0;
for(int k=n;k>1;k--)
cnt+=sum[k],ans=max(ans,cnt);
}
else ans=max(ans,max(dp[n][0],dp[n][1]));
}
}
cout<<ans<<endl;
return 0;
}
感想
本题是最大子矩形的一个变种，简单DP，有一些思维量。写的时候才发现我连最大子矩形都忘完了，药丸。
