10.22 CSP-J模拟
“这是一场难度约为 $CSP-J$ 的模拟赛”
正确的，一针见血的。这么说我都不晓得当年怎么拿的2=（悲
T1 考场上想到了前缀和这么个鬼东西，也在考虑是不是该旋转矩阵，然后发现自己完全转不来，只能随手敲个 $O(n^2k)$ 的暴力前缀和，然后 $n \leq 400$ 的数据硬是越界了8个点。高低也算个黄题吧。
T2 只记得以前做过一道类似的，但是看到超级大的 $k$ 是在想不吃什么不超时的揭解法了，随手敲了个优先队列交上去准备骗点分。黄题水准罢。
T3 一眼线段树模板题，然后我用字符串操作写了30行的代码直接跑路，要不是那个数据太坑说不准还能骗点分。可能有个绿题。
T4 是真的没头绪，大概猜出来是个 $dp$ 但是完全不知道方程怎么推，然后完全没动（悲。绿到蓝吧。
T1 sum
题意： 给定一个 $n * m$ 的矩阵，可以随意选一个点向上下左右走 $k$ 步，求取得的和的最大值。
solution：
把矩阵旋转45度后利用前缀和求解。
这个旋转的方法确实有点骚。
code1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
int n,k,mp[1005][1005],pre[1005][1005],ans=-0x7fffffff,m,x,y,xr,xl,yr,yl;
int main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&mp[i][j]);
}
}
m=n*2-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) pre[i+j-1][n-i+j]=mp[i][j];
}
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++) pre[i][j]=pre[i][j]+pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
x=i+j-1,y=n-i+j;
//xr=x+k;yr=y+k;yl=y-k;xl=x-k;
xr=min(m,x+k);
yr=min(m,y+k);
xl=max(1,x-k);
yl=max(1,y-k);
int cnt=pre[xr][yr]-pre[xr][yl-1]-pre[xl-1][yr]+pre[xl-1][yl-1];
//if(cnt>ans) cout<<xr<<" "<<yr<<" "<<xl<<" "<<yl<<endl;
ans=ans>cnt?ans:cnt;
}
}
printf("%d",ans);
return 0;
}
一个小设想：能不能不旋转直接前缀和求值？理论复杂度是 $O(n^2k)$ 确实只有 $WA$没有 $TLE$ 。
（30pts）
1 |
|
T2 number
题意： 一个 $n$ 个元素的序列 $A$ 以及 $m$ 个元素的序列 $B$ ，求 第k小的 $a_i * b_j$。
solution：
50pts（考场code）：因为肯定满足 $a_i b_j <a_{i+1} b_j$ 所以先将所有 $a_1 b_j$ $push$ 进优先队列，然后依次取出堆顶元素，压入 $a_{i+1} b_j$
，一直循环 $k$ 次即可。
100pts： 同样事由于具有单调性，所以可以二分答案，$check$ 利用单调性枚举即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
const int maxn=2e5+10;
inline 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<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
ll n,m,k,a[maxn],b[maxn];
bool check(ll mid){
ll t=0;
ll j=m;
for(int i=1;i<=n;i++){
while(j>=1&&a[i]*b[j]>=mid) j--;
t+=j;
}
return t>=k;
}
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
n=in;m=in;k=in;
for(int i=1;i<=n;i++) a[i]=in;
for(int i=1;i<=m;i++) b[i]=in;
sort(a+1,a+1+n);
sort(b+1,b+1+m);
ll l=0,r=a[n]*b[m]+1;
while(l+1<r){
ll mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid;
}
printf("%lld",l);
return 0;
}
T3 bigint
题意： 一个长度为 $n$ 的长整数，区间修改，区间赋值。
solution： 一眼线段树模板。只不过因为区间维护的是个整数的一段，所以需要一些小小的预处理。还有很多细节。不明白对拍出来没有问题但是 OJ 上任然是 $WA$ 。
如果你直接利用字符串的操作，也可以骗到 $50pts$ ,代码量是线段树的三分之一，何乐而不为呢？考场上10分钟打完就直接跑路，然后发现输入的 $l$ 和 $r$ 有亿点点坑。
“我们从大整数的最低位（最右边）开始标号”
不要问我怎么被坑了，问就是样例太有迷惑性了。
1 |
|
96行，这么看起来还是字符串来的划算
字符串的算法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
const ll mod=1e9+7;
string s;
ll opt,l,r,n,m,L,R;
char v;
int main(){
freopen("bigint.in","r",stdin);
freopen("bigint.out","w",stdout);
scanf("%lld%lld",&n,&m);
cin>>s;
while(m--){
scanf("%lld%lld%lld",&opt,&L,&R);
l=n-R-1;r=n-L-1;
if(opt==1){
ll res=0;
for(int i=l;i<=r;i++){
res=res*10+s[i]-'0';
res%=mod;
}
printf("%lld\n",res);
}
if(opt==2){
int ch;
scanf("%d",&ch);
v=ch+'0';
for(int i=l;i<=r;i++) s[i]=v;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
T4 array
题意： 有一个数组 $A$ ,可以随意修改 $k$ 个值，最小化 $T(A)=max_{i-2}^n|A_i-A_{i-1}|$ 的值。
solution： 看到题我还以为是差分。玄学 $dp$ （确信 。首先考虑最大化最小值，毫无疑问用二分（机房$dalao$原话），然后考虑用 $dp$ 来做 $check$ ,很明显的一点，对于两点 $i,j$ ，如果不需要修改，那么他们的计算结果一定小于等于二分值 $mid*(j-i)$ ，所以我们从最坏情况开始向前枚举。那么最坏情况就是修改所有点，我们记录 $dp_i$ 表示前i个全部修改，后 $i+1~n$ 的点合法最小代价。然后从 $i+1$ 向后枚举，如果枚举到一个点满足段首所述性质，那么就修改两个点之间的所有点。最后看一下当前代价是否小于等于 $k$ 即可。这个 $dp$ 是真的毒瘤。
代码就将就理解吧，因为我当时候也没太听懂，现在又要去刷题了（逃1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
inline 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<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
ll n,k,a[2005],dp[2005];
bool check(ll m){
for(int i=n;i>=1;i--){
dp[i]=n-i-1;
for(int j=i+1;j<=n;j++){
if(abs(a[j]-a[i])<=m*(j-i)) dp[i]=min(dp[i],dp[j]+j-i-1);
}
if(dp[i]+i<=k) return true;
}
return false;
}
int main(){
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
n=in;k=in;
for(int i=1;i<=n;i++) a[i]=in;
ll l=0,r=2e9,ans=r;
while(l<=r){
ll mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
