DDOSvoid's Blog

题目描述

http://codeforces.com/gym/101889/attachments/download/7471/statements-2017-latam-regional.pdf

简要题意：

题目描述

https://atcoder.jp/contests/agc038/tasks/agc038_c

简要题意：求 $\sum_{i=1}^n\sum_{j=1}^n[a_i,a_j]$​

$n\le 2\times 10^5,a_i\le 10^6$

题目描述

https://www.luogu.com.cn/problem/P5653

简要题意：你现在有一个数 $x$，初始为 $0$，接下来 $n$ 分钟，每分钟可以将其加上 $[-k,k]$，同时需要保证每分钟结束时 $x\le a_i$，令 $b_i$ 为第 $i$ 分钟结束时的数，现在有一个长度为 $n$ 的序列 $w_i$，最大化 $\sum_{i=1}^nb_iw_i$

$n\le 10^6$

题目描述

https://www.luogu.com.cn/problem/P2107

简要题意：$x$ 轴上有 $n$ 个位置，第 $i$ 个位置的坐标为 $x_i$，初始时你位于 $0$，从 $x$ 走到 $y$ 需要花 $|x-y|$ 的时间，在第 $i$ 个位置，可以花 $t_i$ 的时间得到这个位置的收益（只能得到一次），每个位置的收益都是 $1$，现在你只有 $m$ 的时间，求最大收益

$n,m\le 10^5$

题目描述

https://www.luogu.com.cn/problem/P2949

简要题意：现在有 $n$ 个工作可以完成，完成每个工作需要 $1$ 的时间，完成第 $i$ 个工作可以获得 $c_i$ 的收益，第 $i$ 个工作的截止时间是 $d_i$，求最大获利

$n\le 10^5$

简介

大概像是一种 $dp$ ?

题目描述

https://www.luogu.com.cn/problem/P5655

简要题意：有 $T$ 组数据，给定一个长度为 $n$ 的序列 $a_i$，$m$ 次询问 $[a_l,a_{l+1},\cdots,a_r]$，答案对 $10^9+7$​ 取模

$n,m,T\le 300,a_i\le 2^{60}$

题目描述

https://www.luogu.com.cn/problem/CF1422F

题目描述

https://www.luogu.com.cn/problem/U39019

题目描述

题目背景

无

题目描述

给定⼀个 n 个点， m 条边的带权⽆向图， 其中有 s 个点是加油 站。 每辆车都有⼀个油量上限 b ， 即每次⾏⾛距离不能超过 b ， 但在加油站可 以补满。 q 次询问， 每次给出 x, y, b ， 表示出发点是 x ， 终点是 y ， 油 量上限为 b ， 且保证 x 点和 y 点都是加油站， 请回答能否从 x ⾛到 y 。 • n,m,s,q≤ 2×10)

输入输出格式

输入格式：

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000)，表示点数、加油站数和边数。 第二行包含s个互不相同的正整数c[1],c[2],…c[s]，表示每个加油站。 接下来m行，每行三个正整数u[i],v[i],d[i]，表示u[i]和v[i]之间有一条长度为d[i]的双向边。 接下来一行包含一个正整数q(1<=q<=200000)，表示询问数。 接下来q行，每行包含三个正整数x[i],y[i],bi，表示一个询问。

输出格式：

输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。

输入输出样例

输入样例#1：
6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

输出样例#1：
TAK
TAK
TAK
NIE

简要题意：给定⼀个 $n$ 个点， $m$ 条边的带权⽆向图， 其中有 $s$ 个点是加油站。 每辆车都有⼀个油量上限 $b$ ， 即每次⾏⾛距离不能超过 $b$ ， 但在加油站可以补满。 $q$ 次询问， 每次给出 $x$，$y$，$b$ ， 表示出发点是 $x$ ， 终点是 $y$ ， 油量上限为 $b$ ， 且保证 $x$ 点和 $y$ 点都是加油站， 请回答能否从 $x$ ⾛到 $y$

$n,m,q\le 2\times 10^5$