2019-08-20 纪中NOIP模拟A组
T1 [JZOJ6310] Global warming
题目描述
给定整数 n 和 x,以及一个大小为 n 的序列 a。
你可以选择一个区间 [l,r],然后令 a[i]+=d(l<=i<=r),其中 d 满足 |d|<=x。
要求最大化 a 的最长上升子序列的长度,并输出该值。
数据范围
对于 $5\%$ 的数据点,$n,x \leq 10$
对于另外 $10\%$ 的数据点,$n,x \leq 50$
对于另外 $13\%$ 的数据点,$n \leq 1000$
对于另外 $10\%$ 的数据点,$x=0$
对于另外 $20\%$ 的数据点,$x \leq 5$,$n \leq 5 \times 10^4$
对于另外 $17\%$ 的数据点,$x=10^9$
对于 $100\%$ 的数据点,$n \leq 2 \times 10^5$,$x \leq 10^9$
分析
$Subtask$ 真是让人头大,玄学挂了两个点结果只得了 $62 \, pts$
这题有几个很显然的地方
令区间 $[l,r] \; (1 \leq l \leq r < n)$ 加上 $i \; (0 \leq i \leq x)$ 必不优于区间 $[l,n]$
令区间 $[l,r] \; (1 < l \leq r \leq n)$ 减去 $i \; (0 \leq i \leq x)$ 必不优于区间 $[1,r]$
令区间 $[l,n]$ 加上 $i \; (0 \leq i < x)$ 或令区间 $[1,r]$ 减去 $i$ 必不优于加上/减去 $x$
由于加减实际上是等价的,所以我们假定让区间 $[1,r] \; (1 \leq r < n)$ 减去 $x$
设 $f_i$ 表示减小的区间为 $[1,i-1]$ 且 $a_i$ 被选中时的最长上升子序列长度
首先正序做一遍最长上升子序列可以处理出 $f$ 数组,然后倒序做一遍找出最优解
若当前位置为 $i$,则 $ans_i=f_i \, +$ 以 $i$ 结尾的最长下降子序列长度(倒序)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 200005 int n, x, pos, ans;
int a[N], q[N], f[N]; int main() {
scanf("%d%d", &n, &x);
for (int i = ; i <= n; i++) scanf("%d", a + i);
for (int i = ; i <= n; i++) {
f[i] = lower_bound(q + , q + q[] + , a[i]) - q - ;
pos = lower_bound(q + , q + q[] + , a[i] - x) - q;
q[pos] = a[i] - x; q[] = max(q[], pos);
}
q[] = ;
for (int i = n; i; i--) {
pos = lower_bound(q + , q + q[] + , a[i], greater<int>()) - q;
q[pos] = a[i]; q[] = max(q[], pos);
ans = max(ans, f[i] + pos);
}
printf("%d", ans); return ;
}
T2 [JZOJ6311] Mobitel
题目描述
给定一个 r 行 s 列的矩阵,每个格子里都有一个正整数。
问如果从左上角走到右下角,且每次只能向右或向下走到相邻格子,那么使得路径上所有数的乘积不小于 n 的路径有多少条?
由于答案可能很大,所以请输出答案对 10^9+7 取模的结果。
数据范围
对于 $20\%$ 的数据,矩阵中的数不超过 $10$
对于 $50\%$ 的数据,$1 \leq r,s \leq 100$
对于 $100\%$ 的数据,$1 \leq r,s \leq 300$,$1 \leq n \leq 10^6$,矩阵中的数不超过 $10^6$
分析
显然可以先求出总路径数,再减去乘积小于 $n$ 的路径数得到答案
刚开始很容易想到设 $f[i][j][k]$ 表示走到点 $(i,j)$ 处乘积为 $k$ 时的路径数
但时间空间都不允许 $O(rsn)$ 的复杂度
考虑优化状态 $k$,我们发现可以保存剩下还可以乘的数的状态
即 $f[i][j][k]$ 表示走到点 $(i,j)$ 处乘积 $x$ 满足 $\lfloor \frac{n-1}{x} \rfloor =k$ 的路径数
此时 $k$ 的种类数为 $2 \sqrt{n}$,总时间复杂度为 $O(rs \sqrt{n})$
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 305
#define M 2005 const int p = 1e9 + ;
int r, c, n, m, q, sum;
int g[N][N], f[][N][M];
int inv[N], w[M], id[]; int Sum() {
ll ans = ; inv[] = ;
for (int i = r; i <= r + c - ; i++)
ans = ans * i % p;
for (int i = ; i < c; i++) {
inv[i] = (ll)(p - p / i) * inv[p % i] % p;
ans = ans * inv[i] % p;
}
return (int)ans;
} int main() {
scanf("%d%d%d", &r, &c, &n); n--;
for (int x = , y; x <= n; x = y + )
y = n / (n / x), w[++m] = n / x, id[w[m]] = m;
f[][][] = ;
for (int i = ; i <= r; i++, q ^= ) {
memset(f[q ^ ], , sizeof f[q ^ ]);
for (int j = ; j <= c; j++) {
int x; scanf("%d", &x);
for (int k = ; k <= m; k++)
f[q ^ ][j][id[w[k] / x]] = (f[q ^ ][j][id[w[k] / x]] +
(f[q][j][k] + f[q ^ ][j - ][k]) % p) % p;
}
}
for (int i = ; i <= m; i++)
sum = (sum + f[q][c][i]) % p;
printf("%d", (Sum() - sum + p) % p); return ;
}
T3 [JZOJ6312] Lottery
题目描述
定义两个序列对应位置上不同的值的个数不超过 k,则可称为 k 相似。
现在有一个长度为 n 的序列 a,将它划分为 n−l+1 个长度为 l 的子串(第 i 个子串为 a[i]~a[i+l-1])
有 q 组询问,第 j 组询问给出一个 kj,求每个子串与多少个其它的子串可称为 kj 相似。
数据范围
对于 $25\%$ 的数据点,$n \leq 300$
对于另外 $20\%$ 的数据点,$n \leq 2 \times 10^3$
对于另外 $20\%$ 的数据点,$q=1$,$k_1=1$
对于另外 $15\%$ 的数据点,$q=1$
对于 $100\%$ 的数据点,$k_j \leq l \leq n \leq 10^4$,$q \leq 100$,$a_i \leq 10^9$
分析
只要常数小,$n$ 方过一万有时也能成为正解 ——讲题人
如果直接暴力判断相似,那么时间复杂度为 $O(n^2l)$
实际上如果我们已知 $[l_1,r_1]$ 和 $[l_2,r_2]$ 的相似度,那么就可以 $O(1)$ 求出 $[l_1+1,r_1+1]$ 和 $[l_2+1,r_2+1]$ 相似度
这样判断子串之间相似的复杂度为 $O(n^2)$
如果我们用 $f[i][j]$ 表示 $i$ 串与 $j$ 串的不相似度,那么在每个子串输出答案时还需要遍历一遍其他所有子串,则输出时的时间复杂度为 $O(n^2q)$
所以可以用 $f[i][k]$ 表示与 $i$ 串不相似度为 $k$ 的子串数,但此时空间复杂度依然无法接受
我们发现询问次数非常小,所以数组第二维只需要开到 $q$,最后再用前缀和计算一下
总时间复杂度为 $O(n^2)$,空间复杂度为 $O(nq)$
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 10005
#define M 105 int n, m, l, k;
int a[N], b[M], f[N][M], pos[N]; struct Query {int val, id, num;} q[M];
bool cmp1(Query x, Query y) {return x.val < y.val;}
bool cmp2(Query x, Query y) {return x.id < y.id;} int main() {
scanf("%d%d", &n, &l);
for (int i = ; i <= n; i++)
scanf("%d", a + i);
scanf("%d", &m);
for (int i = ; i <= m; i++)
scanf("%d", &q[i].val), q[i].id = i;
sort(q + , q + m + , cmp1);
for (int i = ; i <= m; i++)
q[i].num = i, b[i] = q[i].val;
for (int i = ; i <= l; i++)
pos[i] = lower_bound(b + , b + m + , i) - b;
for (int i = ; i + l - < n; i++, k = ) {
for (int j = ; j <= l; j++)
if (a[j] != a[j + i]) k++;
int p = pos[k]; f[][p]++; f[ + i][p]++;
for (int j = ; j + i + l - <= n; j++) {
k += (a[j + l - ] != a[j + i + l - ]) - (a[j - ] != a[j + i - ]);
p = pos[k]; f[j][p]++; f[j + i][p]++;
}
}
for (int i = ; i <= n - l + ; i++)
for (int j = ; j <= m; j++)
f[i][j] += f[i][j - ];
sort(q + , q + m + , cmp2);
for (int i = ; i <= m; i++) {
for (int j = ; j <= n - l + ; j++)
printf("%d ", f[j][q[i].num]);
printf("\n");
} return ;
}
最新文章
- anomaly detection algorithm
- ASP.NET本质论第一章网站应用程序学习笔记3-对象化的Http
- 搭建SpringMVC+MyBatis开发框架五
- 利用Jquery实现http长连接(LongPoll) {转}
- Kafka源码中的Producer Record定义
- 电脑升级完Xcode8后 注释快捷键无效的问题
- logstash 处理nginx 错误日志
- NYOJ 14 场地安排
- 由12306.cn谈谈网站性能技术
- java.net.BindException: Cannot assign requested address: bind
- 简单的国际化i18n
- JVM垃圾收集器-Parallel Scavenge收集器
- windows 下借助7zip实现命令行解压缩
- addEventListener() 方法,事件监听
- jdbcTemplate的简单介绍
- python - json/pickle
- 《CLR via C#》读书笔记 之 泛型
- oracle删除数据库中的所有表
- C语言---选择结构和循环结构
- 关于transform-style:preserve-3d的些许明了