[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 可分为 aacaabbacabb 两部分,且两者都是回文串。

  • 数据规模与约定

对于 \(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 P3199 [FJSC2017D8T1]飙车一时爽,一直飙车一直爽

YZOJ P3199 [FJSC2017D8T1]飙车一时爽,一直飙车一直爽

时间限制:2000MS      内存限制:524288KB

难度: \(4.5\)

  • 题目描述

最近 \(mnihyc\) 喜欢上了飙车,他甚至飙到了 \(40km/h\) ,这已经是严重的超速了!因此,只要他飙车时连续通过超过 \(K\) 段道路,那么他就会被交警抓走!不过幸好的是,他骑的是共享单车,所以他可以在某些路口更换他的自行车,这样交警就不会发现之前那个飙车的是他了!

简单来说,城镇中有 \(N\) 个路口,\(M\) 条双行道连接着两个不同的路口。这些路口中总共有 \(P\) 个有共享单车停靠点,分别分布在 \(a_1, a_2, \cdots, a_P\) 上。

现在 \(mnihyc\) 想知道,从 \(S\) 出发到 \(T\) ,他至少可以飙上多少段连续的道路?如果太少的话,他会选择蹲在家里推游戏的(好可怜)。

形式化的,给定一张无向图,\(\left| V \right| = N\),\(\left| E \right| = M\),边权均为 \(1\),找出一条从 \(S\) 到 \(T\) 的可重路径使得路径上相邻的关键点(\(S, T, a_1, a_2, \cdots, a_P\))之间的最大距离 \(K\) 最小

  • 输入格式

第一行一个正整数 \(CAS\) 表示测试数据组数。

每组测试数据第一行有三个数 \(N, M, P\)  如上文所述,第二行 \(P\) 个数表示 \(a_1, a_2, \cdots, a_P\) 。

接下来 \(M\) 行,每行两个数表示一条边。

最后 \(S\) 和 \(T\) 表示开始节点和的目标节点。

  • 输出格式

对于每组数据:若始终都无法找到合法的路径,输出 \(-1\),否则输出最的小的 \(K\) 。…

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\)。

 

 

 …