分类： 4.0 ~ 5.0

[ARC092D] Two Sequences

[ARC092D] Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

难度：\(4.0\)

  • Problem Statement

You are given two integer sequences, each of length \(N\): \(a_1, \cdots ,a_N\) and \(b_1, \cdots ,b_N\).

There are \(N^2\) ways to choose two integers \(i\) and \(j\) such that \(1 \leq i,j \leq N\). For each of these \(N^2\) pairs, we will compute \(a_i+b_j\) and write it on a sheet of paper. That is, we will write \(N^2\) integers in total.

Compute the XOR of these \(N^2\) integers.

给定两个长度为 \(n\) 的正整数数组 \(a,b\) ，求 \(\forall 1 \leq i,j \leq n\)，\(a_i+b_j\) 在二进制下的异或和 。

  • Input

\(n\) 和两数组 \(a,b\) 。

  • Output

答案。

  • Sample Input

  • Sample Output

  • Constraints

\(1 \leq …

YZOJ P3056 三角形最大面积

YZOJ P3056 三角形最大面积

时间限制：1000MS      内存限制：262144KB

出题人：chj2001         难度：\(4.5\)

  • 题目描述

给定平面上 \(n\) 个点，定义 \(f(A,B,C)=\frac{1}{2} \left| x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B) \right|\) 。

每次操作都会将坐标系顺时针旋转 \(\frac{\pi}{9}\) 弧度，直到与原坐标系重合。

计算每次操作前 \(f\) 的最大值，并输出所有最大值的总和。

  • 输入格式

第一行输入一个正整数 \(n\)，表示点的数量；

接下来 \(n\) 行，每行两个整数 \(x_i, y_i\) 表示最开始建立的坐标系下点的坐标。

  • 输出格式

输出所有 \(f\) 最大值的总和。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据，\(3 \leq n \leq 10000, -10000 \leq x_i, y_i \leq 10000\) 。

 

 

 …

YZOJ P3906 最长双回文串

YZOJ P3906 最长双回文串

时间限制：1000MS      内存限制：131072KB

难度：\(4.0\)

  • 题目描述

输入长度为 \(n\) 的串 \(S\) ，求 \(S\) 的最长双回文子串 \(T\)，即可将 \(T\) 分为两部分 \(X, Y\)（\(\left|X\right|, \left|Y\right| \geq 1\)），且 \(X, Y\) 都是回文串。

  • 输入格式

一行由小写英文字母组成的字符串 \(S\)。

  • 输出格式

一行一个整数，表示最长双回文子串的长度。

  • 样例输入

  • 样例输出

  • 样例说明

从第二个字符开始的字符串 aacaabbacabb 可分为 aacaa 与 bbacabb 两部分，且两者都是回文串。

  • 数据规模与约定

对于 \(100\%\) 的数据， \(2 \leq \left|S\right| \leq 10^5\)。

 

 

Source: BZOJ 2565…

YZOJ P3216 行商

YZOJ P3216 行商

时间限制：1000MS      内存限制：262144KB

难度：\(4.0\)

  • 题目描述

有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。

挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。

  • 输入格式

第一行，两个整数 \(n\)，\(m\)；

接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。

  • 输出格式

一个整数 \(ans\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

 \(1 \leq n \leq 10^6\)，\(1 \leq m \leq 4^{31}\)，\(1 \leq w_i \leq 3\)，\(1 \leq c_i \leq 10^9\) 。

 

 

 …

[FJWC2019 Day3] 签到题

[FJWC2019 Day3] 签到题

时间限制： 1000ms               内存限制：256MB

难度： \(4.5\)

  • 题目描述

作为一道签到题，自然只能包含最基本的算法。本题的任务很简单，给定一个长度为 \(n\) 的序列 \(a\)，你要将其排序。

由于出题人很菜，不会排序算法，他决定自己编一个。他想找到一个数 \(x\)，使得序列中的所有数字都异或上 \(x\) 后序列恰好按从小到大排列。

顺带，这个序列会被进行若干次修改，每次修改后你需要回答当前是否存在一个 \(x\) 满足序列中数字异或上 \(x\) 后按从小到大排列，如果有，请你给出最小的 \(x\) 。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个非负整数，表示序列 \(a\) 。

第三行一个非负整数 \(q\) ，表示修改次数。

接下来 \(q\) 行，每行一个正整数 \(x\) 和一个非负整数 \(y\)，表示将序列中第 \(x\) 个元素修改为 \(y\) 。

  • 输出格式

输出 \(q+1\) 行，每行一个整数，第一行表示一开始最小的合法 \(x\) ，之后 \(q\) 行依次表示每次修改后最小的合法 \(x\)，如果不存在则这一行输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(20\%\) 的数据，\(n,m \le 500\)，所有数字不超过 \(2^9\) ​​。

对于 \(50\%\) 的数据，\(n,m \le 1000\) 。

对于 \(100\%\) 的数据，\(n,m \le {10}^6\)​​，所有数字不超过 \(2^{30}\) ​​。

 

 

YZOJ P4263…

[FJWC2019 Day2] 直径

[FJWC2019 Day2] 直径

时间限制：1000MS      内存限制：524288KB

难度： \(4.0\)

  • 题目描述

你需要构造一棵至少有两个顶点的树，树上的每条边有一个非负整数边权。树上两点 \(i,j\) 的距离 \(dis(i,j)\) 定义为树上连接 \(i\) 和 \(j\) 这两点的简单路径上的边权和。

我们定义这棵树的直径为，所有满足 \(1 \leq i < j \leq n\) 的 \((i,j)\) 中，\(dis(i,j)\) 最大的。如果有多个这样的 \((i,j)\)，那么均为直径。

作为一个构造题，你需要构造一个恰有 \(k\) 个直径的树。可以证明在给定的限制下一定有解。

  • 输入格式

一行一个正整数 \(k\)，表示你需要构造出一个恰有 \(k\) 个直径的树。

  • 输出格式

第一行一个正整数 \(n\)，表示你构造的树的点数。

接下来 \(n-1\) 行，每行三个整数 \(i,j,w\)，表示一条连接点 \(i\) 和 \(j\) （点的编号为 \(1,2, \cdots, n\)）的树边，边权为 \(w\) 。

  • 样例输入

  • 样例输出

  • 样例说明

这只是一种符合题意的输出，可能还有其他输出。在这个输出中，直径为 \((1,5),(3,5),(4,5)\) 。

  • 数据规模与约定

注意，你需要构造出的树必须满足 \(2 \leq n \leq 5000, 0 \leq w \leq 10^5\) ！

对于 \(30pts\) 的数据，\(1\leq k \leq 2000\) ；

对于 \(100pts\) 的数据，\(1\leq k \leq 5 \times 10^6\) 。

 

 

YZOJ P4260…

[FJWC2019 Day1] 全连

[FJWC2019 Day1] 全连

时间限制：1000MS      内存限制：262144KB

难度： \(4.5\)

  • 题目描述

给定两个长度为 \(n\) 的序列 \(a\) 和 \(t\)，可以在其中选择一些元素构成集合 \(S\) ，使得 \(\sum\limits_{i \in S}{a_i \times t_i}\) 最大。

同时，集合 \(S\) 还要满足 \(\forall i \in S, \forall j \in (i-t_i, i+t_i)\) ， \(j \notin S\) 。

  • 输入格式

第一行一个整数 \(n\) ；

第二行 \(n\) 个整数表示序列 \(t\) ；

第三行 \(n\) 个整数表示序列 \(a\) 。

  • 输出格式

一行一个整数，即答案。

  • 样例输入

  • 样例输出

  • 样例说明

\(S=\{1,3,5\}\)，答案 \(=2 \times 3 + 2 \times 2 + 2 \times 4 = 18\) 。

  • 数据规模与约定

保证 \(t_i \leq n\) ， \(a_i \leq 10^9\) ，\(1 \leq n \leq 10^6\) 。

 

 

YZOJ P4257, YZOJ P3993…

YZOJ P3754 Gab数列

YZOJ P3754 Gab数列

时间限制：2000MS      内存限制：131072KB

难度： \(4.5\)

  • 题目描述

给定数列 \(a_1,a_2,\cdots,a_n\)，定义数列 \(b_1,b_2,\cdots,b_m\) 为 Gab数列 当且仅当它满足：

1，\(\forall 1\le i\le m\) 满足 \(b_i\in\mathbf{N^*}\) 且 \(1\le b_i\le n\)

2，\(\sum_\limits{i=1}^{m}b_i\le k\)

求 \(\sum_\limits{i=1}^{m}a_{b_i}\) 的最大值。

  • 输入格式

第一行三个整数 \(n\)，\(m\) 和 \(k\) 。

第二行 \(n\) 个整数 \(a_i\) 。

  • 输出格式

输出仅一行，为最大值。

  • 样例输入

  • 样例输出

  • 样例说明

对应的 Gab数列 可以为 \(\{1,5,5,1,1,1\}\) 。

  • 数据范围

对于 \(15\%\) 的数据，\(n,m\le 8\)，\(k\le 50\)；

对于 \(40\%\) 的数据，\(n,m,k\le 200\)；

对于另外 \(5\%\) 的数据，满足 \(m=k\)；

对于另外 \(5\%\) 的数据，对于 \(1\le i\le j\le n\)，\(a_i\ge a_j\)；

对于 \(100\%\) 的数据，\(n\le 3000\)，\(k\le 8000\)，\(m\le 1000\)，\(1\le a_i\le 10^9\)，\(m\le k\)。

 

 

 …