2019计蒜客信息学提高组赛前膜你赛 #2（TooYoung,TooSimple,Sometimes Naive

计蒜客\(2019CSP\)比赛第二场

巧妙爆零这场比赛(我连背包都不会了\(QWQ\)

\(T1\) \(Too\) \(Young\)

大学选课真的是一件很苦恼的事呢！

\(Marco\)：“我要两年毕业！我要选尽量多的学分！这些课统统选上！”

长者："你啊，\(Too Young\)！你看看作业量，你做的完吗？"

\(Marco\)（笑容逐渐消失\(.gif\)）：”那可咋整啊?“

长者："还能咋整？退课呗！“

已知 \(Marco\) 选了 \(N(1 \leq N \leq 500)\)门课，每门课有学分 \(w_i\)，劳累度 \(v_i\)和挂科概率 \(p_i\)；

其中，\(w_i\)为 \([1,5]\) 范围内的一个正整数，\(v_i\)是 \(int\) 范围内正整数， \(p_i\)是 \([0,1]\)范围内小数；

现在 \(Marco\) 想退掉某些课使得自己的劳累度尽量小，但是，如果 \(Marco\) 的学分总数达不到给定的 \(MINX\)，他会被退学。

\(Marco\)想知道，在期望学分大于等于 \(MINX\) 的情况下，他的最小劳累度是多少。

注意：如果一门课挂科，\(Marco\) 将付出 \(v_i\)的劳累度但是无法获得相应学分；否则，\(Marco\) 将付出 \(v_i\)的劳累度并收获 \(w_i\)的学分。

输入格式

第一行一个正整数 \(N\) 表示课程数量

接下来 \(N\) 行，每行空格分开的 \(3\) 个数 \(w_i,v_i\)和 \(p_i\)，含义如题面所述

最后一行一个正整数 \(MINX\) 表示所需最小学分。

输出格式

一行一个正整数表示最小劳累度。

数据范围

本题共 \(10\) 个测试点，每个测试点 \(10\) 分。

对于 \(10\%\) 的数据，\(1 \leq N \leq 10\)

对于 \(30\%\) 的数据，\(1 \leq N \leq 20\)

对于另外 \(20\%\) 的数据，\(p_i=0\)

对于 \(100\%\) 的数据，

\(1 \leq N \leq 500\) ，

\(w_i\)是正整数且 \(1 \leq wi \leq 5\)，

\(p_i\)最多包含 \(2\) 位小数且 \(0 \leq pi \leq 1\)，

\(v_i\)是 \(int\) 范围内正整数.

保证全选的情况下 \(Marco\) 不会被退学。

题解：

一眼背包题……

可以发现学分就是背包问题里的费用(体积，疲劳度就是背包问题里的价值，而我们的最终目的有所改变，不再是满足小于等于背包容量的最大价值，而是大于等于背包容量的最小价值

有一些细节需要注意

1.精度问题：

我们在背包问题中，物品的体积一定是个整数，但是在这道题里，它却可能是个小数，怎么办呢

我们发现\(p\)是一个二位小数，只要乘一个\(100\)，就会变成一个整数

但是仍须注意的是，在转\(int\)以前(乘\(100\)以前，一定要加一个\(0.1\)，不然会因为精度丢失而导致学分数减少

关于该精度问题，计蒜客杜昊老师给出的答复:(我超喜欢这位老师的-W-

因为 double 浮点数在计算机内部保存的时候并不一定是一个准确的值，例如 100 保存的时候有可能是 99.9999999 ,为了防止这种情况下我强制截断成 int 的时候使得 100 变成 99，所以 +0.01，因为这个值对我的整数部分是不会有影响的

2.上下界处理问题：

这道题不同于普通的背包，我们要在所有超出背包体积的价值里取一个最小值，所以我们需要求出所有的可能体积，而不是只求最小学分

请恰代码：

#include<bits/stdc++.h>
using namespace std;
#define rint register int
int n, MIN;
long long sum, w[510], v[510], dp[250010], ans = ( 1ll << 60ll );
inline int read( void ){
int re = 0, f = 1; char ch = getchar();
while( ch > '9' || ch < '0' ){
if( ch == '-' ) f = -1;
ch = getchar();
}
while( ch >= '0' && ch <= '9' ){
re = re * 10 + ch - '0';
ch = getchar();
}
return re * f;
}
int main( void ){
n = read();
for( rint i = 1; i <= n; i++ ){
w[i] = read(); v[i] = read();
double p; scanf( "%lf", &p );
w[i] *= ( int )( 100.0 * ( 1.0 * ( 1.0 - p ) ) + 0.1 );
sum += w[i];
}
MIN = read(); MIN *= 100;
for( rint i = 1; i <= sum; i++ ) dp[i] = ( 1ll << 60ll );
sum = 0; int j = 0;
for( rint i = 1; i <= n; i++ ){
for( sum += w[i], j = sum; j >= w[i]; j-- ){
dp[j] = min( dp[j], dp[j - w[i]] + v[i] );
}
}
for( rint i = MIN; i <= sum; i++ ){
ans = min( ans, dp[i] );
}
printf( "%lld", ans );
return 0;
}


\(T2\) \(Too\) \(Simple\)

打题干是最痛苦的

长者：“说你 \(Too Young\) 你还不相信，看这道题你会不会做！”

有一个二维平面，\(x,y\) 坐标范围都是 \([-10^9,10^9]\) ，平面上有 \(N\) 个特殊位置 \((X_i,Y_i)\) ，每次可以向四连通(上,下,左,右)的格子走一步，定义 \((S,T)\) 到 \((X_i,Y_i)\)的距离为从 \((S,T)(S,T)\) 走到 \((X_i,Y_i)\) 的最小步数。 \(Q\) 次询问，给定 \((S,T)\) ，求这个点到所有特殊位置的距离之和。

数据范围：\(1 \leq N,Q \leq 10^6 1 \leq S,T,X_i,Y_i \leq 10^9\)

\(Marco\)：“这是哪里来的大水题啊？我用脚趾头都能把这题切掉！”

长者：“你啊，\(Too Young，Too Simple\)！其他条件不变，如果把条件中的四连通改成八连通，你还会做吗？”

\(Marco\) 陷入了沉思……于是，他找来你帮他解决这个问题。

注：八连通的定义：与 \((x,y)\) 八连通的格子分别为 \((x,y+1),(x,y-1),(x+1,y),(x-1,y),(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1)\)。

输入格式

第一行一个数字 \(T\) 表示数据组数；

对于每组数据，

第一行两个数字 \(N,Q\) 分别表示 特殊位置数量和询问次数。

接下来 \(N\) 行，每行两个数字 \(X_i,Y_i\)表示特殊位置坐标；

接下来 \(Q\) 行，每行两个数字 \(S,T\) 表示询问起点坐标。

输出格式

对于每组数据输出 \(Q\) 行，

每行一个整数表示这个点到特殊位置的距离之和。

数据范围

本题共 \(5\) 个测试点，每个测试点 \(20\) 分。

对于 \(20\%\) 的数据，\(T=1\), \(1 \leq N,Q \leq 5000, 1 \leq S,T,X_i,Y_i \leq 1000\)

对于 \(40\%\) 的数据，所有数据中 \(N*Q\) 的总和不超过 \(5*10^7\)

对于另外 \(20\%\) 的数据，\(T=1\),\(1 \leq S,T,X_i,Y_i \leq 1000\)

对于 \(100\%\) 的数据，\(N\) 的总和和 \(Q\) 的总和均不超过 \(10^6\),\(1 \leq S,T,X_i,Y_i \leq 10^91≤S\)

题解

切比雪夫距离与曼哈顿距离的转化，不懂的百度请(很简单的

将切比雪夫距离转化之后，我们就不需要比较大小了，直接算出曼哈顿距离来，再经过一些转化即为切比雪夫距离，也就是乘个\(2\)。

将切比雪夫距离转化之后，

切比雪夫距离求的是两个坐标的\(x,y\)差值的的较大者，而曼哈顿距离求的是两坐标差值的和，即\(( x_1 - x_2) + ( y _ 1 - y _ 2)\)

将读入的点变为\(( x + y, x - y)\)，然后求曼哈顿距离，求出来的就是原来点对的切比雪夫距离

但是一个一个的暴力求距离会\(TLE\)，所以我们要想一些办法

前缀和

可以把已知点按\(x\)排序，然后再按\(y\)排一次，这样只要二分查找到询问点的位置，就可以很快解决了

这个前缀和是一维的，原因很好想，因为曼哈顿距离的\(xy\)没有关系，先求出\(x\)然后再求出\(y\)，两者加起来就好了

\(update\) \(2019.11.13\)

终于过了，计蒜客的杜昊老师实在是太好了\(QWQ\)，他帮我看了三次代码了\(QWQ\)，那八十分是因为忘开\(longlong\)了……

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define ll long long
int n, q, T;
ll x[1000010], y[1000010], sumx[1000010], sumy[1000010];
ll ans;
inline int read( void ){
int re = 0, f = 1; char ch = getchar();
while( ch > '9' || ch < '0' ){
if( ch == '-' ) f = -1;
ch = getchar();
}
while( ch >= '0' && ch <= '9' ){
re = re * 10 + ch - '0';
ch = getchar();
}
return re * f;
}
int main( void ){
T = read();
while( T-- ){
n = read(); q = read();
for( rint i = 1; i <= n; i++ ){
int t1, t2;
t1 = read(); t2 = read();
x[i] = t1 + t2; y[i] = t1 - t2;
}
sort( x + 1, x + 1 + n ); sort( y + 1, y + 1 + n );
for( rint i = 1; i <= n; i++ ){
sumx[i] = sumx[i - 1] + x[i]; sumy[i] = sumy[i - 1] + y[i];
}
for( rint i = 1; i <= q; i++ ){
ans = 0;
ll qx, qy; qx = read(); qy = read();
ll lowx, lowy;
lowx = upper_bound( x + 1, x + 1 + n, qx + qy ) - x - 1;
lowy = upper_bound( y + 1, y + 1 + n, qx - qy ) - y - 1;
ans += ( ( ( lowx * ( qx + qy ) ) - sumx[lowx] ) + ( sumx[n] - sumx[lowx] ) - ( ( n - lowx ) * ( qx + qy ) ) );
ans += ( ( ( lowy * ( qx - qy ) ) - sumy[lowy] ) + ( sumy[n] - sumy[lowy] ) - ( ( n - lowy ) * ( qx - qy ) ) );
ans >>= 1;
printf( "%lld\n", ans );
}
}
return 0;
}