POJ 2279. Mr. Young's Picture Permutations (线性DP)

题面

Description

Mr. Young wishes to take a picture of his class. The students will stand in rows with each row no longer than the row behind it and the left ends of the rows aligned. For instance, 12 students could be arranged in rows (from back to front) of 5, 3, 3 and 1 students.

1
2
3
4
5
6
7
X X X X X

X X X

X X X

X

In addition, Mr. Young wants the students in each row arranged so that heights decrease from left to right. Also, student heights should decrease from the back to the front. Thinking about it, Mr. Young sees that for the 12-student example, there are at least two ways to arrange the students (with 1 as the tallest etc.):

1
2
3
4
5
6
7
 1  2  3  4  5     1  5  8 11 12

6 7 8 2 6 9

9 10 11 3 7 10

12 4

Mr. Young wonders how many different arrangements of the students there might be for a given arrangement of rows. He tries counting by hand starting with rows of 3, 2 and 1 and counts 16 arrangements:

1
2
3
4
5
123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146

45 46 35 36 34 36 34 35 25 26 24 26 24 25 26 25

6 5 6 5 6 4 5 4 6 5 6 4 5 4 3 3

Mr. Young sees that counting by hand is not going to be very effective for any reasonable number of students so he asks you to help out by writing a computer program to determine the number of different arrangements of students for a given set of rows.

Input

The input for each problem instance will consist of two lines. The first line gives the number of rows, k, as a decimal integer. The second line contains the lengths of the rows from back to front (n1, n2,…, nk) as decimal integers separated by a single space. The problem set ends with a line with a row count of 0. There will never be more than 5 rows and the total number of students, N, (sum of the row lengths) will be at most 30.

Output

The output for each problem instance shall be the number of arrangements of the N students into the given rows so that the heights decrease along each row from left to right and along each column from back to front as a decimal integer. (Assume all heights are distinct.) The result of each problem instance should be on a separate line. The input data will be chosen so that the result will always fit in an unsigned 32 bit integer.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
1
30
5
1 1 1 1 1
3
3 2 1
4
5 3 3 1
5
6 5 4 3 2
2
15 15
0

Sample Output

1
2
3
4
5
6
1
1
16
4158
141892608
9694845

题目大意

NN个学生( 身高为 11~ NN )排成kk 行拍照,从后到前每行分别有N1,N2,,NkN_{1}, N_{2}, \cdots, N_{k} 个学生。现在要求每行学生从左到右的身高和每列学生从后到前的身高必须按降序排列,求排列这些学生站位的方法总数。

题解

分析

首先考虑到每行的人数 NiN_{i}是给定的,且在转移过程中需要维护当前学生的站位状态,又注意到本题的数据范围很小(N30N \leq 30k5k \leq 5),因此可以将状态表示为 f(x1,x2,x3,x4,x5)f(x_1,x_2,x_3,x_4,x_5), 其中 xix_{i} 表示第ii 行当前的学生数目。

再注意到安排学生一定是按照 11~ NN的顺序进行的,且当第 N1N-1名学生的站位安排好后,第 NN 名学生的站位就随之确定。但第ii (1i<N1 \leq i < N) 名学生的站位确定时,第i+1i+1 名学生要站在哪一行与前ii 名学生的站位有关(因为位置没有填满);同时注意到,显然这种情况不能出现:

1
2
1 4
2 3

这是因为在第1行尚未填满时,第2行已被率先填满,故 44只能被填在第1行剩下的空位中。这要求我们必须尽可能先填满后面的行,再去填充前面的行;即要求对第 ii行和第i+1i+1 行,任何状态中一定有xi>xi+1x_{i}>x_{i+1}。此时,行和列的降序关系皆可以得到满足。

因此设计状态转移方程为

f(x1,x2,x3,x4,x5)=f(x11,x2,x3,x4,x5)+[x1>x2]f(x1,x21,x3,x4,x5)+[x2>x3]f(x1,x2,x31,x4,x5)+[x3>x4]f(x1,x2,x3,x41,x5)+[x4>x5]f(x1,x2,x3,x4,x51)f(x_1,x_2,x_3,x_4,x_5)=f(x_1-1,x_2,x_3,x_4,x_5)+\\ [x_1>x_2] \cdot f(x_1,x_2-1,x_3,x_4,x_5)+\\ [x_2>x_3] \cdot f(x_1,x_2,x_3-1,x_4,x_5)+\\ [x_3>x_4] \cdot f(x_1,x_2,x_3,x_4-1,x_5)+\\ [x_4>x_5] \cdot f(x_1,x_2,x_3,x_4,x_5-1)

其中记号 [][] 是艾弗森约定。

最终目标为 f(N1,N2,N3,N4,N5)f(N_1,N_2,N_3,N_4,N_5)

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef unsigned int uint;
typedef long long ll;

int a[6];
uint dp[31][16][11][9][7];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);

int k = 0;
while (cin >> k && k) {
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= k; i++)
cin >> a[i];

dp[1][0][0][0][0] = 1;
for (int x1 = 1; x1 <= a[1]; x1++) {
for (int x2 = 0; (a[2] == 0) || (x2 <= a[2]); x2++) {
for (int x3 = 0; (a[3] == 0) || (x3 <= a[3]); x3++) {
for (int x4 = 0; (a[4] == 0) || (x4 <= a[4]); x4++) {
for (int x5 = 0; (a[5] == 0) || (x5 <= a[5]); x5++) {
dp[x1][x2][x3][x4][x5] += dp[x1 - 1][x2][x3][x4][x5];

if (a[2] && x2 > 0 && x1 >= x2) {
dp[x1][x2][x3][x4][x5] += dp[x1][x2 - 1][x3][x4][x5];

if (a[3] && x3 > 0 && x2 >= x3) {
dp[x1][x2][x3][x4][x5] += dp[x1][x2][x3 - 1][x4][x5];

if (a[4] && x4 > 0 && x3 >= x4) {
dp[x1][x2][x3][x4][x5] += dp[x1][x2][x3][x4 - 1][x5];

if (a[5] && x5 > 0 && x4 >= x5) {
dp[x1][x2][x3][x4][x5] += dp[x1][x2][x3][x4][x5 - 1];
}
}
}
}

if (a[5] == 0)
break;
}
if (a[4] == 0)
break;
}
if (a[3] == 0)
break;
}
if (a[2] == 0)
break;
}
}

cout << dp[a[1]][a[2]][a[3]][a[4]][a[5]] << endl;
}

return 0;
}

Bonus Time

这是lyd大佬当年的代码,我佛了,%%%

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
var
f:array[1..30,0..30,0..15,0..10,0..9,0..6]of dword;
a:array[1..5]of integer;
i,j,k,l,m,n,o,p:longint;
begin
repeat
readln(n);
if n=0 then break;
m:=0;
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
read(a[i]);
inc(m,a[i]);
end;
for i:=1 to m do
for j:=0 to a[1] do
for k:=0 to a[2] do
for l:=0 to a[3] do
for o:=0 to a[4] do
for p:=0 to a[5] do
f[i,j,k,l,o,p]:=0;
f[1,1,0,0,0,0]:=1;
for i:=1 to m-1 do
for j:=1 to a[1] do
for k:=0 to a[2] do
for l:=0 to a[3] do
for o:=0 to a[4] do
for p:=0 to a[5] do
begin
if j<>a[1] then f[i+1,j+1,k,l,o,p]:=f[i+1,j+1,k,l,o,p]+f[i,j,k,l,o,p];
if (k<>a[2])and(k<j) then f[i+1,j,k+1,l,o,p]:=f[i+1,j,k+1,l,o,p]+f[i,j,k,l,o,p];
if (l<>a[3])and(l<k) then f[i+1,j,k,l+1,o,p]:=f[i+1,j,k,l+1,o,p]+f[i,j,k,l,o,p];
if (o<>a[4])and(o<l) then f[i+1,j,k,l,o+1,p]:=f[i+1,j,k,l,o+1,p]+f[i,j,k,l,o,p];
if (p<>a[5])and(p<o) then f[i+1,j,k,l,o,p+1]:=f[i+1,j,k,l,o,p+1]+f[i,j,k,l,o,p];
end;
writeln(f[m,a[1],a[2],a[3],a[4],a[5]]);
until false;
end.

A. 解方程 (暴力) [Comet OJ Contest #0]

题面

Description

小象同学在初等教育时期遇到了一个复杂的数学题,题目是这样的:给定自然数 nn,确定关于x,y,zx,y,z 的不定方程

xn+yz=0\sqrt{x-\sqrt{n}} + \sqrt{y} - \sqrt{z}=0 的解。

当时的小象同学并不会做这道题。多年后,经过高等教育的洗礼,小象同学发现这道题其实很简单。小象同学认为你一定也会做这道题,所以把这道题留给了你。为了便于输出,你不需要输出每一组解 (x,y,z)(x,y,z),你只需要给出解的数量和所有解的 xyzxyz之和对(109+7)(10^{9}+7) 取模的值即可。注意,解的数量不对109+710^{9}+7 取模。

Input

输入包含多组测试数据。输入的第一行包含一个正整数 T  (1T104)T\;(1 \leq T \leq 10^{4}) ,表示测试数据的组数。接下来依次描述每组测试数据,对于每组测试数据:

仅一行,包含一个非负整数 n  (0n2×109)n\;(0\leq n \leq 2 \times 10^{9}) ,含义如题面所示。

Output

对于每组数据,输出一行。若方程有无穷多组自然数解,则在这一行输出 ‘‘infty”\text{‘‘infty''}(不含引号),否则在这一行输出两个整数,其中第一个整数表示方程的解数,第二个整数 表示所有解的 xyzxyz之和对(109+7)(10^{9}+7) 取模的值,这两个整数之间用恰好一个空格隔开,行末不要有多余的空格。

Sample Input

1
2
3
4
3
6
12
24

Sample Output

1
2
3
0 0
1 12
2 72

Hint

n=12n=12时,方程唯一的解为x=4,y=1,z=3x=4,y=1,z=3

n=24n=24时,方程的两组解为 x=5,y=2,z=3x=5,y=2,z=3x=7,y=1,z=6x=7,y=1,z=6

题解

首先注意到显然当且仅当 n=0n=0nn为完全平方数时,给定方程有无穷多组解,通解为(n,c,c)(\sqrt{n},c,c) ,其中cc 是任意自然数。

现在,考察何时方程有有限多组解。将所给方程做如下变换

xn=zy\sqrt{x-\sqrt{n}}=\sqrt{z}-\sqrt{y}

两边平方得

xn=y+z2yzx-\sqrt{n}=y+z-2\sqrt{yz}

移项得

x(y+z)=n2yzx-(y+z)=\sqrt{n}-2\sqrt{yz}

此时,考虑两种情况:

  • 方程左右两边均为 00

此时,显然有

{x=y+zn=4yz\left \{ \begin{matrix} x=y+z \\ n = 4yz \end{matrix} \right.

  • 方程左右两边均不为 00

因为 $x,y,z\in \mathbb{N} $,故 x(y+z)Zx-(y+z) \in \mathbb{Z},故应当也有 n2yzZ\sqrt{n}-2\sqrt{yz} \in \mathbb{Z}。若 n4yzn \neq 4yz,则当且仅当 nnyzyz均为 00或完全平方数(但不同时为00)时,满足该条件;这是不可能的。因为,若nnyzyz00 时,必有n=yz=0n=yz=0;若nnyzyz 均不为00 ,则nn 必须为完全平方数,此时方程有无穷多组解。

综上,当且仅当 {x=y+zn=4yz\left \{ \begin{matrix} x=y+z \\ n=4yz \end{matrix} \right. 成立时,方程有有限多组解。

此时注意到当且仅当 nn44的倍数时,方程有解;又注意到 n2×109n \leq 2 \times 10^{9},因此遍历[1,n][1, \sqrt{n}] 寻找nn 的因子即可。时间复杂度O(n)O(\sqrt{n})

注意此题long long会超时

代码

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
45
46
#include <bits/stdc++.h>
using namespace std;

const int MODULO = 1e9 + 7;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int t = 0;
cin >> t;

while (t--) {
int n = 0;
cin >> n;

if (n == 0 || (int)sqrt((double)n) * (int)sqrt((double)n) == n) {
cout << "infty" << endl;
continue;
}

if (n % 4) {
cout << 0 << " " << 0 << endl;
continue;
}

n /= 4;
int m = (int)sqrt((double)n + 0.5);

int ans = 0, num = 0;
for (int i = 1; i <= m; i++) {
if (n % i)
continue;

num++;

int z = n / i;
int x = ((long long)i + z) % MODULO;
ans = ((long long)ans + (long long)x * n % MODULO) % MODULO;
}

cout << num << " " << ans << endl;
}

return 0;
}

HDU 6050. Funny Function (快速幂,逆元)

题面

Description

Function Fx,yF_{x,y} satisfies:

F1,1=F1,2=1F1,i=F1,i1+2F1,i2  (i3)Fi,j=k=jj+N1Fi1,k  (i2,j1)F_{1, 1} = F_{1, 2} = 1 \\ F_{1, i} = F_{1, i - 1} + 2 * F_{1, i - 2} \; (i \geq 3) \\ F_{i, j} = \sum_{k = j}^{j + N - 1}F_{i - 1, k} \; (i \geq 2, j \geq 1)

For given integers NNand MM,calculate Fm,1F_{m, 1} modulo109+710^{9} + 7.

Input

There is one integer T in the first line.

The next T lines,each line includes two integers N and M .

1<=T<=10000,1<=N,M<2^63.

Output

For each given N and M,print the answer in a single line.

Sample Input

1
2
3
2
2 2
3 3

Sample Output

1
2
2
33

题解

F1,iF_{1, i}aia_{i} ,则

ai=ai1+2ai2  (i3)a_{i} = a_{i - 1} + 2a_{i - 2} \; (i \geq 3)

p0,qRp \neq 0, q \in \mathbb{R} 使得

ai+kai1=p(ai1+kai2)a_{i} + ka_{i - 1} = p(a_{i - 1} + ka_{i - 2})

两式对照并解得 {p=1k=2\left \{ \begin{matrix} p = -1 \\ k = -2 \end{matrix} \right.{p=2k=1\left \{ \begin{matrix} p = 2 \\ k = 1 \end{matrix} \right. .

  • {p=1k=2\left \{ \begin{matrix} p = -1 \\ k = -2 \end{matrix} \right. 成立

此时记 bi1=ai2ai1b_{i - 1} = a_{i} - 2a_{i - 1} ,易得

bi=(1)ib_{i} = (-1)^{i}

ai2ai1=(1)i1a_{i} - 2a_{i - 1} = (-1)^{i - 1} . 此时有

ai(1)i+2ai1(1)i1=1\frac{a_{i}}{(-1)^{i}}+2\frac{a_{i - 1}}{(-1)^{i - 1}} = -1

ci=ai(1)ic_{i} = \dfrac{a_{i}}{(-1) ^ {i}} ,易得

ci=13(2)i13c_{i} = \frac{1}{3}(-2)^{i} - \frac{1}{3}

ai=1)ici=2i3+(1)i13a_{i} = (-1)^{i}c_{i} = \frac{2^{i}}{3} + \frac{(-1)^{i - 1}}{3}

  • {p=2k=1\left \{ \begin{matrix} p = 2 \\ k = 1 \end{matrix} \right. 成立

易知此时亦有 ai=2i3+(1)i13a_{i} = \dfrac{2^{i}}{3} + \dfrac{(-1)^{i - 1}}{3} 成立。

综上,此时有

F1,i=13(1)i1+132i(1)F_{1, i} = \frac{1}{3} \cdot (-1)^{i - 1} + \frac{1}{3} \cdot 2^{i} \tag{1}

此时考虑

F2,i=k=ii+N1F1,k=k=1i+N1F1,kk=1i1F1,k(2)F_{2, i} = \sum_{k=i}^{i+N-1}F_{1,k}=\sum_{k=1}^{i+N-1}F_{1,k}-\sum_{k=1}^{i-1}F_{1,k} \tag{2}

又,此时有

i=1nF1,i=13i=1n(1)i1+13i=1n2i=16(1+(1)n+1)+23(2n1)\sum_{i=1}^{n}F_{1,i} = \frac{1}{3}\sum_{i=1}^{n}(-1)^{i-1}+\frac{1}{3}\sum_{i=1}^{n}2^{i} \\ =\frac{1}{6}\cdot(1+(-1)^{n+1})+\frac{2}{3}\cdot(2^{n}-1)

代入 (2)(2) 式可得

F2,i=13(1)i+N(1)i2+13(2N1)2i(3)F_{2, i} = \frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)\cdot2^{i} \tag{3}

类似地,易得

F3,i=13(1)i+N(1)i2+13(2N1)22i(4)F_{3,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{2}\cdot2^{i} \tag{4}

此时,由归纳法易证

Fm,i=13(1)i+N(1)i2+13(2N1)m12i(5)F_{m,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{m-1}\cdot2^{i} \tag{5}

因此

Fm,1=13[(m  mod  2)+2(2N1)m1](6)F_{m,1}=\frac{1}{3}[(m\;\mathbf{mod}\;2)+2\cdot(2^{N}-1)^{m-1}] \tag{6}

用快速幂计算即可。

代码

此题 NNMM 都是2632^{63} 范围,因此要用 unsigned long long

kk 乘法千万不能忘了逆元。。。这次居然很脑抽地居然把逆元忘了导致赛中自闭orz = =

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
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const ull MODULO = 1e9 + 7;

ull power(ull a, ull b, ull p);
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);

int t = 0;
cin >> t;

while (t--) {
ull n = 0, m = 0;
cin >> n >> m;

if (m == 1) {
cout << 1 << endl;
continue;
}

ull x1 = n & 1;
ull x2 = (2 * power(power(2, n, MODULO) - 1, m - 1, MODULO)) % MODULO;

ull ans = (x1 + x2) * 333333336 % MODULO;

cout << ans << endl;
}

return 0;
}

ull power(ull a, ull b, ull p) {
ull ans = 1 % p;

for (; b; b >>= 1) {
if (b & 1)
ans = (ull)ans * a % p;
a = (ull)a * a % p;
}

return ans;
}

Codeforces 1133D. Zero Quantity Maximization (map, 精度)

题面

Description

You are given two arrays aaand bb, each containsnn integers.

You want to create a new array ccas follows: choose some real (i.e. not necessarily integer) number dd, and then for every i[1,n]i \in [1, n] letci:=dai+bic_i := d \cdot a_i + b_i.

Your goal is to maximize the number of zeroes in array cc. What is the largest possible answer, if you choose dd optimally?

Input

The first line contains one integer nn (1n21051 \le n \le 2 \cdot 10^5) — the number of elements in both arrays.

The second line contains nnintegers a1a_1, a2a_2, …,ana_n (109ai109-10^9 \le a_i \le 10^9).

The third line contains nnintegers b1b_1, b2b_2, …,bnb_n (109bi109-10^9 \le b_i \le 10^9).

Output

Print one integer — the maximum number of zeroes in array cc, if you choose dd optimally.

Examples

Input

1
2
3
5
1 2 3 4 5
2 4 7 11 3

Output

1
2

Input

1
2
3
3
13 37 39
1 2 3

Output

1
2

Input

1
2
3
4
0 0 0 0
1 2 3 4

Output

1
0

Input

1
2
3
3
1 2 -1
-6 -12 6

Output

1
3

Note

In the first example, we may choose d=2d = -2.

In the second example, we may choose d=113d = -\dfrac{1}{13}.

In the third example, we cannot obtain any zero in array cc, no matter which dd we choose.

In the fourth example, we may choose d=6d = 6.

题目大意

给出两个长度为 nn(1n2105)(1 \leq n \leq 2 \cdot 10^{5})的数组 aabb ,求实数dd 使得对所有i[1,n]i \in [1, n] 计算下式

c[i]=da[i]+b[i]c[i] = d \cdot a[i] + b[i]

数组 cc00 的数目尽可能多。

题解

分析

da[i]+b[i]=0d \cdot a[i] + b[i] = 0,则有 d=b[i]a[i]d = -\dfrac{b[i]}{a[i]}。但 dd会爆 double 精度,此时用 pair 维护 <-b[i] / gcd, a[i] / gcd> 即可。但此时要注意处理 b[i]a[i] 的正负号关系(e.g. 11=11\dfrac{1}{1} = \dfrac{-1}{-1} ,但在直接按此存储则会导致被认作为不同的值)。也可用 long double 维护dd 。之后用 map 统计出现次数最多的 d 即可。

注意特判 a[i]=0a[i] = 0的情况。此时有 c[i]=b[i]c[i] = b[i],若 b[i]=0b[i] = 0 ,则c[i]c[i] 必为00

代码

pair 维护

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
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

#define ABS(x) ((x) > 0 ? (x) : -(x))

const int MAXN = 2e5 + 10;

int a[MAXN], b[MAXN];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n = 0;
while (cin >> n) {
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];

int ans = 0, cnt0 = 0;

map<pair<int, int>, int> m;
for (int i = 1; i <= n; i++) {
if (a[i] == 0) {
if (b[i] == 0)
cnt0++;
} else {
pair<int, int> p = make_pair(-b[i], a[i]);
if (p.first < 0 || (p.first == 0 && p.second < 0)) {
p.first *= -1;
p.second *= -1;
}
int d = __gcd(ABS(p.first), ABS(p.second));
p.first /= d;
p.second /= d;

if (m.find(p) == m.end())
m.insert(make_pair(p, 1));
else
m[p]++;

ans = max(ans, m[p]);
}
}

cout << ans + cnt0 << endl;
}

return 0;
}

long double维护

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
45
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAXN = 2e5 + 10;

int a[MAXN], b[MAXN];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n = 0;
while (cin >> n) {
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];

map<ld, int> m;
int ans = 0, cnt0 = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == 0) {
if (b[i] == 0)
cnt0++;
} else {
ld d = -(ld)b[i] / a[i];

if (m.find(d) == m.end())
m.insert(make_pair(d, 1));
else
m[d]++;

ans = max(ans, m[d]);
}
}

cout << ans + cnt0 << endl;
}

return 0;
}

Codeforces 1030A. In Search of an Easy Problem(Codebait) [Codeforces Round

题面

Description

When preparing a tournament, Codeforces coordinators try treir best to make the first problem as easy as possible. This time the coordinator had chosen some problem and asked nn people about their opinions. Each person answered whether this problem is easy or hard.

If at least one of these nn people has answered that the problem is hard, the coordinator decides to change the problem. For the given responses, check if the problem is easy enough.

Input

The first line contains a single integer nn (1n1001 \le n \le 100) — the number of people who were asked to give their opinions.

The second line contains nnintegers, each integer is either 00or 11. If ii-th integer is 00, then ii-th person thinks that the problem is easy; if it is11, thenii-th person thinks that the problem is hard.

Output

Print one word: “EASY” if the problem is easy according to all responses, or “HARD” if there is at least one person who thinks the problem is hard.

You may print every letter in any register: “EASY”, “easy”, “EaSY” and “eAsY” all will be processed correctly.

Sample Input 1

1
2
3
0 0 1

Sample Output 1

1
HARD

Sample Input 2

1
2
1
0

Sample Output 2

1
EASY

题解

题目大意

给你一个大小为n的数组,元素只有0和1,如果数组中存在元素为1,则输出HARD,否则输出EASY,并且每个字母大小写随便

分析

直接根据题意模拟,真·签到题

代码

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
#include <bits/stdc++.h>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n = 0;
while(cin >> n) {
bool isone = false;
for(int i = 1; i <= n; i++) {
int a = 0;

cin >> a;
if(a == 1) {
isone = true;
}
}

if(isone) cout << "HARD" << endl;
else cout << "EASY" << endl;
}

return 0;
}

A. Magic Mirror(新手题,字符串处理) [2018 ACM-ICPC Jiaozuo Online Contest]

题面

Description

Jessie has a magic mirror.

Every morning she will ask the mirror: ‘Mirror mirror tell me, who is the most beautiful girl in the world?’ If the mirror says her name, she will praise the mirror: ‘Good guy!’, but if the mirror says the name of another person, she will assail the mirror: ‘Dare you say that again?’

Today Jessie asks the mirror the same question above, and you are given a series of mirror’s answers. For each answer, please output Jessie’s response. You can assume that the uppercase or lowercase letters appearing anywhere in the name will have no influence on the answer. For example, ‘Jessie’ and ‘jessie’ represent the same person.

Input

The first line contains an integer T(1T100)T(1 \le T \le 100), which is the number of test cases.

Each test case contains one line with a single-word name, which contains only English letters. The length of each name is no more than 1515.

Output

For each test case, output one line containing the answer.

Sample Input

1
2
3
2
Jessie
Justin

Sample Output

1
2
Good guy!
Dare you say that again?

题解

题目大意

给出 TT个长度小于1515 的字符串,判断其是否与字符串Jessie相等(忽略大小写)。

分析

完全的新生级签到题,读入字符串后将每个字符都转为小写,之后判断是否与jessie相等即可。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;

const int MAXN = 20;
char name[MAXN];

int main() {
int t = 0;
scanf("%d", &t);

while(t--) {
scanf("%s", name);

int len = (int)strlen(name);
for(int i = 0; i < len; i++)
name[i] = tolower(name[i]);

if(!strcmp(name, "jessie")) printf("Good guy!\n");
else printf("Dare you say that again?\n");
}

return 0;
}

F. Sorting (排序,浮点数精度) [2017 CCPC China-Hunan Invitional]

Description

Bobo has nntuples(a1,b1,c1),(a2,b2,c2),,(an,bn,cn)(a_1, b_1, c_1), (a_2, b_2, c_2), \dots, (a_n, b_n, c_n) .
He would like to find the lexicographically smallest permutation p1,p2,,pnp_1, p_2, \dots, p_nof1,2,,n1, 2, \dots, n such that fori{2,3,,n}i \in \{2, 3, \dots, n\} it holds that

api1+bpi1api1+bpi1+cpi1api+bpiapi+bpi+cpi\frac{a_{p_{i - 1}} + b_{p_{i - 1}}}{a_{p_{i - 1}} + b_{p_{i - 1}} + c_{p_{i - 1}}} \leq \frac{a_{p_i} + b_{p_i}}{a_{p_i} + b_{p_i} + c_{p_i}}

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer nn.

The ii-th of the following nnlines contains 33integers aia_i,bib_i andcic_i.

Output

For each test case, print nnintegersp1,p2,,pnp_1, p_2, \dots, p_n seperated by spaces.
DO NOT print trailing spaces.

Constraint

  • 1n1031 \leq n \leq 10^3
  • 1ai,bi,ci2×1091 \leq a_i, b_i, c_i \leq 2 \times 10^9
  • The sum of nndoes not exceed10410^4.

Sample Input

1
2
3
4
5
6
7
8
9
10
2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1

Sample Output

1
2
3
2 1
1 2
1 2 3

题解

题目大意

给你 nn个三元组,要求给出这 nn个三元组的一个排列,使得对i{2,3,,n}i \in \left \{ 2, 3, \cdots, n \right \} 都满足题给关系。

分析

题给关系中的不等式只涉及 pi1p_{i - 1}pip_{i} 两个元素,实际上相当于对三元组重载了小于号。因此,本题实际上是对读入的三元组序列进行排序。因此,我们用一个Node结构体存储三元组的三个变元和读入时在原序列中的位置即可。

1
2
3
4
struct Node {
long long a, b, c;
int id;
}

同时,在比较三元组关系时,因为本题数据卡精度较严,因此不能用double,而应交叉相乘再比较,同时在这过程中约去一些相同的项(避免爆long long)。

(api1+bpi1)(api+bpi+cpi)(api+bpi)(api1+bpi1+cpi1))(a_{p_{i-1}}+b_{p_{i-1}})(a_{p_{i}}+b_{p_{i}}+c_{p_{i}}) \leq (a_{p_{i}} + b_{p_{i}})(a_{p_{i-1}}+b_{p_{i-1}}+c_{p_{i-1}}))

(api1+bpi1)cpi(api+bpi)cpi1(a_{p_{i-1}} + b_{p_{i-1}})c_{p_{i}} \leq (a_{p_{i}} + b_{p_{i}})c_{p_{i-1}}

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
typedef long long ll;

struct Node {
ll a, b, c;
int id;

bool operator < (const Node& x) const {
ll q1 = c * (x.a + x.b);
ll q2 = x.c * (a + b);

if(q2 == q1) return id < x.id;
else return q2 < q1;
}
} t[MAXN];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n = 0;
while(cin >> n) {
for(int i = 1; i <= n; i++) {
cin >> t[i].a >> t[i].b >> t[i].c;
t[i].id = i;
}

sort(t + 1, t + n + 1);

for(int i = 1; i <= n; i++)
if(i != n) cout << t[i].id << " ";
else cout << t[i].id << endl;
}

return 0;
}

POJ.2559 Largest Rectangle in a Histogram (单调栈)

题面

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,…,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

1
2
3
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

1
2
8
4000

Hint

Huge input, scanf is recommended.

分析

题目大意:在一水平线上方有若干个矩形,求包含于这些矩形的并集内部的最大矩形的面积,矩形个数 105\leq 10^{5}

我们现在面临两个问题:

  • 应从哪个位置开始选取所需的矩形并集?
  • 当确定了开始位置时,应向左/右哪个方向延伸,延伸多少?

作为对问题的简化,我们先考虑如下情况:如果矩形高度从左到右单调递增,答案将是多少?

很显然,答案将是以下四种情形之一:

那么,此时如果新增加一个矩形,它的高度比其之前的三个矩形都要低;此时,如果我们想要利用这个矩形以及之前的矩形一同选取一个并集,这个并集的高度一定不会高于新矩形的高度:也就是说,下图中打叉的部分已经对于后续计算没有用处了。那么,我们就可以将新选取的并集独立出来,代替之前用到的所有矩形,放入我们已有的矩形序列之内:此时,矩形序列又重新具有了高度单调性。

因此,我们可以采用单调栈维护矩阵序列:我们存储序列中每一个矩形的高度和宽度,之后扫描所有矩形;每当读入一个新矩形时进行如下操作:

  • 如果当前矩形的高度大于等于栈顶矩形,则直接将当前矩形压入栈顶,宽度为1。
  • 如果当前矩形的高度小于栈顶矩形,则持续将栈顶矩形出栈,直至当前矩形高度大于等于栈顶矩形为止。同时,在这一过程中,累积记录所有出栈矩形的宽度;当出栈完毕后,再将以累积值为宽度、当前矩形高度为高的新矩形压入栈顶。

在扫描结束后,为了防止栈中仍有矩形未被弹出,我们可以增加一个高度为0的矩形 h[n + 1] ,以此简化计算。

注意:此题最终答案会爆int。

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
int h[MAXN];
int s[MAXN], w[MAXN], top;

void push(int hei, int wid);
void pop(int* hei, int* wid);
bool isEmpty();
int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int n = 0;

while(cin >> n && n) {
for(int i = 1; i <= n; i++)
cin >> h[i];
h[n + 1] = 0;

top = 0;
memset(s, 0, sizeof(s));
memset(w, 0, sizeof(w));

ll ans = 0;
for(int i = 1; i <= n + 1; i++) {
if(h[i] >= s[top]) s[++top] = h[i], w[top] = 1;
else {
int outWidth = 0;

while(h[i] < s[top]) {
outWidth += w[top];
ans = max(ans, (long long)s[top--] * outWidth);
}

s[++top] = h[i], w[top] = outWidth + 1;
}
}

cout << ans << endl;
}

return 0;
}

inline void push(int hei, int wid) {
s[++top] = hei;
w[top] = wid;
}

inline void pop(int* hei, int* wid) {
*hei = s[top];
*wid = w[top--];
}

inline bool isEmpty() {
if(top == 0) return true;
else return false;
}

A. An Olympian Math Problem (数论) [2018 ACM-ICPC Nanjing Online Contest]

Description

Alice, a student of grade 66, is thinking about an Olympian Math problem, but she feels so despair that she cries. And her classmate, Bob, has no idea about the problem. Thus he wants you to help him. The problem is:

We denote k!k!:

k!=1×2××(k1)×kk! = 1 \times 2 \times \cdots \times (k - 1) \times k

We denote SS:

S=1×1!+2×2!++S = 1 \times 1! + 2 \times 2! + \cdots +
(n1)×(n1)!(n - 1) \times (n-1)!

Then SSmodulenn is ____________

You are given an integer nn.

You have to calculate SSmodulonn.

Input

The first line contains an integer T(T1000)T(T \le 1000), denoting the number of test cases.

For each test case, there is a line which has an integer nn.

It is guaranteed that 2n10182 \le n\le 10^{18}.

Output

For each test case, print an integer SSmodulonn.

Hint

The first test is: S=1×1!=1S = 1\times 1!= 1, and 11modulo 22 is11.

The second test is: S=1×1!+2×2!=5S = 1\times 1!+2 \times 2!= 5, and 55modulo33 is22.

Sample Input

1
2
3
2
2
3

Sample Output

1
2
1
2

题解

首先,显然有 S=k=1n1kk!=k=1n1((k+1)!k!)=n!1S = \sum\limits_{k=1}^{n-1}k \cdot k! = \sum\limits_{k=1}^{n-1}((k+1)!-k!)=n!-1.

S  mod  nS \; \mathrm{mod} \; n

=(n!1)  mod  n= (n! - 1) \; \mathrm{mod} \; n

$ = (n! + n - 1) ; \mathrm{mod} ; n$

$ = n! ; \mathrm{mod} ; n + (n - 1) ; \mathrm{mod} ; n$

$ = n - 1$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int t = 0;
cin >> t;

while(t--) {
ll n = 0;
cin >> n;
cout << n - 1 << endl;
}

return 0;
}

A.队列Q - WannyFly挑战赛19

题目

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

ZZT 创造了一个队列 Q。这个队列包含了 N 个元素,队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素,QN 表示队尾元素。队列中的元素是 N 的一个全排列。
ZZT 需要在这个队列上执行 P 次操作,操作分两种:
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。
在 P 次操作之后,ZZT 想知道队列中的元素的排列方式,由于他最近很忙,因此需要请你帮他解决这个问题。

输入描述:

1
2
3
4
5
6
7
8
9
10
第一行输入一个正整数 N,表示队列的大小。
第二行输入 N 个正整数,Q1, Q2, Q3, ... ..., QN,Qi 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。
第三行输入一个正整数 P,表示接下来要进行的操作次数。

接下来 P 行,第 i 行输入一个字符串 Si 以及一个正整数 Xi,表示一次操作。
1 ≤ N ≤ 105.
1 ≤ Qi ≤ N.
1 ≤ P ≤ 105.
Si { “FIRST”, “LAST” }.
1 ≤ Xi ≤ 105.

输出描述:

1
输出 N 个正整数,表示 P 次操作之后的队列。

示例1

输入

1
2
3
4
5
6
4
4 2 1 3
3
FIRST 4
LAST 2
LAST 1

输出

1
4 3 2 1

题解

这个题的数据量比较大,用类似插入排序的方法只能过65%的数据,但因为题目给出的数据是n的全排列,因此队列中不会有重复的数据,所以可以另开一个数组维护队列中每个元素的位置,之后要用到某个元素的位置时根据值反查位置。

同时因为移动位置操作开销较大,可开一个较大的数组(大概5e5),并从数组的中部开始存入队列的数据,并维护一个start和end指针来指示数组第一个元素的前一个位置和数组最末元素的后一个位置,每当出现元素移动位置事件时,修改start和end指针的位置,并采用懒惰删除的策略标记数组中原有位置,最后遍历整个队列数组打印队列。时间复杂度O(n+q)。

代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

#define FIRST "FIRST"
#define LAST "LAST"

const int MAXN = 1e5;
int q[MAXN * 5];
int h[MAXN + 100];

int main(){
int n = 0;

while(scanf("%d", &n) != EOF) {
int start = 2e5 - 1;
int end = start + n + 1;

for(int i = 1; i <= n; i++) {
scanf("%d", &q[i + start]);
h[q[i + start]] = i + start;
}

int p =0;
scanf("%d", &p);

char tmp[10]; int x =0;
for(int i = 0; i < p; i++) {
scanf("%s %d", tmp, &x);

if(strcmp(FIRST, tmp) == 0) {
q[start] = q[h[x]];
q[h[x]] = -1;
h[x] = start;
start--;
} else if(strcmp(LAST, tmp) == 0) {
q[end] = q[h[x]];
q[h[x]] = -1.;
h[x] = end;
end++;
}
}

int ok = 0;
for(int p = start + 1; p != end; p++) {
if(q[p] != -1) {
ok ? putchar(' ') : 1;

printf("%d", q[p]);

!ok ? ok = 1 : 1;
}
}
putchar('\n');
}

return 0;
}