A
求出来到每座山的距离后，就可以计算出每只猫等待的时间与出发时间的关系。
如果出发时间为$x$,求出来只猫的等待时间。这里用$b_i$表示第i只猫的等待时间。然后我们将这些时间排序。问题就转化为了，从m个有序的数中，选出p个，每个数字覆盖以其为开头的一段区间。这段区间的贡献为$x\times num-sum$,其中x为当前选定的数字。$num$为覆盖区间的长度。$sum$为覆盖区间的数字和。
这样就可以得到一个$m^2p$的朴素dp。 $f[i][j]$表示选出i个点，覆盖前j个元素，最小贡献。 $f[i][j]=\min\limits_{k=1}^i{f[i-1][k - 1]+b[k]\times j+(j-k)\times b[k]-(sum[j]-sum[k]))}$
然后就很斜率优化了。。。
/*
* @Author: wxyww
* @Date: 2019-08-07 19:31:15
* @Last Modified time: 2019-08-07 19:49:05
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 50010,M = 1010;
#define int ll
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
ll sum[N];
int n,m,p,f[N],g[N],a[N];
ll b[N];
ll B(int x) {
return sum[x] - x * b[x] + g[x - 1];
}
bool cmp(int x,int y) {
return x > y;
}
int q[N];
int calc(int x,int y) {
return b[x] * y + B(x);
}
bool check(int p1,int p2,int p3) {
return 1ll * (B(p2) - B(p3)) * (b[p3] - b[p1]) > 1ll * (B(p1) - B(p3)) * (b[p3] - b[p2]);
}
main() {
n = read(),m = read(),p = read();
for(int i = 2;i <= n;++i) a[i] = a[i - 1] + read();
for(int i = 1;i <= m;++i) {
int x = read(),y = read();
b[i] = y - a[x];
}
sort(b + 1,b + m + 1,cmp);
for(int i = 1;i <= m;++i) sum[i] = sum[i - 1] + b[i];
memset(f,0x3f,sizeof(f));
f[0] = 0;
for(int j = 1;j <= p;++j) {
for(int i = 0;i <= m;++i) g[i] = f[i];
memset(f,0x3f,sizeof(f));
f[0] = 0;
int head = 1,tail = 0;
for(int i = 1;i <= m;++i) {
while(head < tail && check(q[tail],q[tail - 1],i)) --tail;
q[++tail] = i;
while(head < tail && calc(q[head + 1],i) <= calc(q[head],i)) ++head;
f[i] = calc(q[head],i) - sum[i];
}
}
cout<<f[m]<<endl;
return 0;
}
B
非常interesting的一道题。
考虑倒着做。用某大佬的话说就是”拔地鼠”，只有当某个位置所在的行和列不含有除这个位置外的地鼠，这个位置才可以被”拔出来”。我们将其拔出来之后，将他所在的行和列都标记为灰色。表示可能为白色(有地鼠)，也可能为黑色(无地鼠)。
然后开始bfs,将尽量多的点刷为灰色。
最后比较一下非灰色的点是不是与初始状态相同。
需要特判初始状态本就与终止状态相同的情况。还有，如果某一行和某一列都为灰色，那么他们的交点处初始必须是白色。否则就无法开始。
/*
* @Author: wxyww
* @Date: 2019-08-07 20:10:07
* @Last Modified time: 2019-08-07 20:26:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
char s1[N][N],s2[N][N];
int sum1[N],sum2[N],vis1[N],vis2[N],vis[N][N],col[N][N];
queue<pair<int,int> >q;
int main() {
int n = read(),m = read();
int bz = 0;
for(int i = 1;i <= n;++i) scanf("%s",s1[i] + 1);
for(int i = 1;i <= n;++i) scanf("%s",s2[i] + 1);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
if(s1[i][j] != s2[i][j]) bz = 1;
if(!bz) {
puts("1");return 0;
}
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
if(s2[i][j] == 'X') {
sum1[i]++;sum2[j]++;
col[i][j] = 1;
}
}
}
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
if(s2[i][j] == 'X' && sum1[i] == 1 && sum2[j] == 1) {
q.push(make_pair(i,j));
vis[i][j] = 1;
}
}
}
while(!q.empty()) {
int x = q.front().first,y = q.front().second;q.pop();
if(vis1[x] <= 2) {
vis1[x]++;
for(int i = 1;i <= m;++i) {
if(col[x][i] == 1) {
sum1[x]--;sum2[i]--;
}
col[x][i] = 2;
}
for(int i = 1;i <= m;++i)
if(!vis[x][i] && !sum1[x] && !sum2[i]) q.push(make_pair(x,i)),vis[x][i] = 1;
}
if(vis2[y] <= 1) {
vis2[y]++;
for(int i = 1;i <= n;++i) {
if(col[i][y] == 1) sum1[i]--,sum2[y]--;
col[i][y] = 2;
}
for(int i = 1;i <= n;++i)
if(!vis[i][y] && !sum1[i] && !sum2[y]) q.push(make_pair(i,y)),vis[i][y] = 1;
}
}
bz = 0;
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
if(s1[i][j] == 'O' && vis1[i] && vis2[j]) bz = 1;
}
}
if(!bz) {
puts("0");return 0;
}
bz = 0;
for(int i = 1;i <= n;++i) {
for(int j = 1;j <= m;++j) {
if(!vis1[i] && !vis2[j] && s1[i][j] != s2[i][j]) bz = 1;
}
}
if(bz) puts("0");
else puts("1");
return 0;
}
C
毒瘤防AK题。。。并不想写。
总结
T1一开始写了一个假的dp，浪费了大量时间。T2骗分成分较大，数据有点水。T3到最后有点着急，没写出来。。。
T1这种简单题应该做对并及时对拍。T2没思路只能乱搞了。T3.。。。