PORTAL\text{PORTAL}

A - The Number of Even Pairs

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100100 points

Problem Statement

We have N+MN+M balls, each of which has an integer written on it.
It is known that:
The numbers written on NN of the balls are even.
The numbers written on MM of the balls are odd.
Find the number of ways to choose two of the N+MN+M balls (disregarding order) so that the sum of the numbers written on them is even.
It can be shown that this count does not depend on the actual values written on the balls.

Constraints

0≤N,M≤1000≤N,M≤100
2≤N+M2≤N+M
All values in input are integers.

Input

Input is given from Standard Input in the following format:
NN MM

Output

Print the answer.

Sample Input 1

2 1

Sample Output 1

1
For example, let us assume that the numbers written on the three balls are 1,2,41,2,4.
If we choose the two balls with 11and 22, the sum is odd;
If we choose the two balls with 11 and 44, the sum is odd;
If we choose the two balls with 22 and 44, the sum is even.
Thus, the answer is 11.

Sample Input 2

4 3

Sample Output 2

9

Sample Input 3

1 1

Sample Output 3

0

Sample Input 4

13 3

Sample Output 4

81

Sample Input 5

0 3

Sample Output 5

3

Translation

有N+MN+M个球，NN个球上面写着偶数，MM个球上面写着奇数，要从这N+MN+M个球中选取两个球，使得两个球上写的数字的和为偶数，问有多少种选法。

Idea

同奇偶性的两个数相加为偶数，所以答案为Cn2+Cm2C_n^2+C_m^2。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
void solve()
{
	int n,m;
	cin>>n>>m;
	cout<<n*(n-1)/2+m*(m-1)/2<<endl;
}
int main()
{
	solve();
	return 0;
}

B - String Palindrome

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 200200 points

Problem Statement

A string SS of an odd length is said to be a strong palindrome if and only if all of the following conditions are satisfied:
SS is a palindrome.
Let NN be the length of SS. The string formed by the 11-st through ((N−1)/2)((N−1)/2)-th characters of SS is a palindrome.
The string consisting of the (N+3)/2(N+3)/2-st through NN-th characters of SS is a palindrome.
Determine whether SS is a strong palindrome.

Constraints

SS consists of lowercase English letters.
The length of SS is an odd number between 33 and 9999 (inclusive).

Input

Input is given from Standard Input in the following format:
SS

Output

If SS is a strong palindrome, print Yes; otherwise, print No.

Sample Input 1

akasaka

Sample Output 1

Yes
SS is akasaka.
The string formed by the 11-st through the 33-rd characters is aka.
The string formed by the 55-th through the 77-th characters is aka. All of these are palindromes, so SS is a strong palindrome.

Sample Input 2

level

Sample Output 2

No

Sample Input 3

atcoder

Sample Output 3

No

Translation

给一个字符串SS，要求判断该字符串是不是strong palindrome\text {strong palindrome}（条件见英文题面）。

Idea

按题给意思模拟。
用reverse\text {reverse}函数判断是否回文。

Code

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<iostream>
#include<algorithm>
#include<string>
using namespace std;
void solve()
{
	bool flag=1;
	string s;
	cin>>s;
	int len=s.length();
	//串的长度必须为奇数  
	if(len%2==0) flag=0;
	else
	{
		string temp=s;
		reverse(temp.begin(),temp.end());
		//串本身是回文串
		if(temp!=s) flag=0;
		else
		{
			string t;
			//截取前半部分
			int pos=(len-1)/2-1;
			int i;
			for(i=0;i<=pos;i++) t+=s[i];
			string temp=t;
			reverse(t.begin(),t.end());
			if(t!=temp) flag=0;
			else
			{
				string t;
				//截取后半部分
				int pos=(len+3)/2-1;
				for(i=pos;i<s.length();i++) t+=s[i];
				string temp=t;
				reverse(t.begin(),t.end());
				if(t!=temp) flag=0;
			}
		}
	}
	if(flag) puts("Yes");
	else puts("No");
}
int main()
{
	solve();
	return 0;
}

C - Maximum Volume

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 300300 points

Problem Statement

Given is a positive integer LL. Find the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is LL.

Constraints

1≤L≤10001≤L≤1000
LL is an integer.

Input

Input is given from Standard Input in the following format:
LL

Output

Print the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is LL. Your output is considered correct if its absolute or relative error from our answer is at most 10−610^{-6}.

Sample Input 1

3

Sample Output 1

1.000000000000
For example, a rectangular cuboid whose dimensions are 0.80.8, 11, and 1.21.2 has a volume of 0.960.96.
On the other hand, if the dimensions are 11, 11, and 11, the volume of the rectangular cuboid is 11, which is greater.

Sample Input 2

999

Sample Output 2

36926037.000000000000

Translation

长方体的长、宽、高之和为LL，问其最大体积。

Idea

由AM-GM\text{AM-GM}不等式，$\sqrt[n]{\prod\limits_{i=1}^{n}x_i}\leqslant \frac{\sum\limits_{i=1}^{n}x_i}{n}$，当且仅当x1=x2=⋯=xnx_1=x_2=\dots=x_n时取等号。
故$V_{max}=\frac{L}{3}\times\frac{L}{3}\times\frac{L}{3}=\frac{L^3}{27}$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
void solve()
{
	double l;
	cin>>l;
	printf("%.12lf\n",l*l*l/27);
}
int main()
{
	solve();
	return 0;
}

D - Banned K

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 400400 points

Problem Statement

We have NN balls. The ii-th ball has an integer AiA_i written on it.
For each k=1,2,...,Nk=1,2,...,N, solve the following problem and print the answer.
Find the number of ways to choose two distinct balls (disregarding order) from the N−1N−1 balls other than the kk-th ball so that the integers written on them are equal.

Constraints

3≤N≤2×1053≤N≤2×10^5
1≤Ai≤N1≤A_i≤N
All values in input are integers.

Input

Input is given from Standard Input in the following format:
NN
A1A2...ANA_1 A_2 ... A_N

Output

For each k=1,2,..,Nk=1,2,..,N, print a line containing the answer.

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3
Consider the case k=1k=1 for example. The numbers written on the remaining balls are1,2,1,21,2,1,2.
From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.
Thus, the answer for k=1k=1 is 22.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0
No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6
Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5

Translation

给NN个球，第ii个球上印着数字AiA_i。对于每一个ii，要在剩余N−1N-1个数字中选出两个相同的数字；要求对于每一个ii，输出方案数。

Idea

如果要计算从NN个数中选取两个相同数字的方案，就相当简单，只需要计算每一个数字出现的次数cntAicnt_{A_i}，答案即为∑i=1NCcntAi2\sum\limits_{i=1}^{N}C_{cnt_{A_i}}^2。这里的组合数，每种数字应该只计算一次，否则会有冗余，当一个计算过的数字再次遍历到时应当跳过。
对于每一个ii，每次将剩余N−1N-1个数扫一遍显然会TLE\text{TLE}，可以利用Mo’s algorithm\text{Mo's algorithm}的思想，采取加减贡献的策略。

Code

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
#include<iostream>
using namespace std;
const int N=200005;
int a[N];
long long cnt[N];
bool vis[N];
void solve()
{
	int n;
	cin>>n;
	int i;
	long long sum=0;
	for(i=1;i<=n;i++) 
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(i=1;i<=n;i++)
	{
		if(vis[a[i]]) continue;
		//计算全部的贡献
		sum=sum+cnt[a[i]]*(cnt[a[i]]-1)/2;
		//标记访问
		vis[a[i]]=1;
	}
	for(i=1;i<=n;i++)
	{
		//减去所有a[i]的贡献，加上cnt[a[i]]-1个a[i]的贡献 
		printf("%lld\n",sum-cnt[a[i]]*(cnt[a[i]]-1)/2+(cnt[a[i]]-1)*(cnt[a[i]]-2)/2);
	}
}
int main()
{
	solve();
	return 0;
}

E - Dividing Chocolate

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 500500 points

Problem Statement

We have a chocolate bar partitioned into HH horizontal rows and WW vertical columns of squares.
The square (i,j)(i,j) at the i-th row from the top and the jj-th column from the left is dark if Si,jS_{i,j} is 00 and white if Si,jS_{i,j} is 11.
We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.
How many times do we need to cut the bar so that every block after the cuts has KK or less white squares?

Constraints

1≤H≤101≤H≤10
1≤W≤10001≤W≤1000
1≤K≤H×W1≤K≤H×W
Si,jS_{i,j} is 00 or 11.

Input

Input is given from Standard Input in the following format:
HH WW KK
S1,1S1,2...S1,WS_{1,1}S_{1,2}...S_{1,W}
::
SH,1SH,2...SH,WS_{H,1}S_{H,2}...S_{H,W}

Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has KK or less white squares.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2
For example, cutting between the 11-st and 22-nd rows and between the 33-rd and 44-th columns - as shown in the figure to the left - works.
Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0
No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3

Translation

给定一个n×mn×m的01字符矩阵。求最少需要多少次水平或竖直切割，使得切出的每一块都包含不超过ss个1。

Idea

nn的范围很小，可以枚举2n2^{n}种水平切割情况，竖直切割情况则用贪心策略检验。
对于每一种水平切割的方案，按列从左往右贪心，每到一列，水平切割切成的每一块当前的1的个数就会增加该列1的个数，如果至少有一块当前的1的个数超过了ss，便在本列与上一列之间竖直切割一刀，如果仍然超过，那么此种水平切割方案就不可行。对于每种水平切割状态，如果可行就需要更新答案。
时间复杂度O(2nnm)O(2^nnm)。

Code

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<vector>
using namespace std;
const int N=12,M=1003;
int n,m,s;
char G[N][M];
void solve()
{
	cin>>n>>m>>s;
	int i,j,k,o;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>G[i][j];
		}
	}
	//初始化
	int ans=0x3f3f3f3f;
	for(i=0;i<1<<n-1;i++)
	{
		//存水平切割的位置
		vector<int>pos; 
		//设置起点
		pos.push_back(0);
		//枚举每一行是否切割
		for(j=1;j<=n;j++)
		{
			if(i&1<<j-1)
			{
				pos.push_back(j);
			}
		}
		//设置终点
		pos.push_back(n);
		//此水平切割状态当前切割次数
		int now=pos.size()-2;
		/*存水平切割的每一块当前'1'的个数 
		如果向右推进一列，就叠加上该列的'1'的个数*/
		vector<int>cntr(pos.size()-1,0);
		//从左往右贪心 
		for(j=1;j<=m;j++)
		{
			bool ok=1;
			//存第j列水平切割后每一块的个数 
			vector<int>cntc(pos.size()-1,0);
			for(k=0;k<cntr.size();k++)//枚举水平切割的每一块 
			{
				//统计一块中'1'的个数
				for(o=pos[k]+1;o<=pos[k+1];o++)
				{
					cntc[k]+=G[o][j]^48;
				}
				//切割之后还行不通，计算下一种行分割方案 
				if(cntc[k]>s) goto next_condition;
				//需要切割 
				if(cntr[k]+cntc[k]>s) ok=0;
			}
			if(ok) 
			{
				//不需要竖直切割
				for(k=0;k<cntr.size();k++)
				{
					//行的'1'的个数进行叠加
					cntr[k]+=cntc[k]; 
				}
			}
			else
			{
				//多割一刀
				now++;
				//目前所在行‘1’的个数等于该列‘1’的个数
				cntr=cntc;//竖直切割 
			}
		}
		//更新
		ans=min(ans,now);
		next_condition:; 
	}
	cout<<ans<<endl;
}
int main()
{
	solve();
	return 0;
}

Postscipt

一个数据规模较小的维度用二进制压缩枚举，另一个数据规模较大的维度进行贪心策略。

F - Knapsack for All Segments

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 600600 points

Problem Statement

Given are a sequence of NN integers A1,A2,…,ANA_1, A_2, …, A_N and a positive integer SS.
For a pair of integers (L,R)(L,R) such that 1≤L≤R≤N1≤L≤R≤N, let us define f(L,R)f(L,R) as follows:
f(L,R)f(L,R) is the number of sequences of integers (x1,x2,…,xk)(x_1,x_2,…,x_k) such that L≤x1<x2<⋯<xk≤RL≤x_1<x_2<⋯<x_k≤R and Ax1+Ax2+⋯+Axk=SA_{x_1}+A_{x_2}+⋯+A_{x_k}=S.
Find the sum of f(L,R)f(L,R) over all pairs of integers (L,R)(L,R) such that 1≤L≤R≤N1≤L≤R≤N. Since this sum can be enormous, print it modulo 998244353998244353.

Constraints

All values in input are integers.
1≤N≤30001≤N≤3000
1≤S≤30001≤S≤3000
1≤Ai≤30001≤A_i≤3000

Input

Input is given from Standard Input in the following format:
NN SS
A1A2...ANA_1 A_2 ...A_N

Output

Print the sum of f(L,R)f(L,R), modulo 998244353998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

5
The value of f(L,R)f(L,R) for each pair is as follows, for a total of 55.
f(1,1)=0f(1,1)=0
f(1,2)=1f(1,2)=1 (for the sequence (1,2)(1,2))
f(1,3)=2f(1,3)=2 (for (1,2)(1,2) and (3)(3))
f(2,2)=0f(2,2)=0
f(2,3)=1f(2,3)=1 (for (3)(3))
f(3,3)=1f(3,3)=1 (for (3)(3))

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

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

Sample Output 3

152

Translation

给定一个长度为 NN 的数组 AA 和一个正整数 SS ，定义 f(L,R)f(L,R) 为原数组中满足：L≤x1≤x2≤⋯≤xk≤RL\leq x_1\leq x_2\leq\cdots\leq x_k \leq R 并且 Ax1+Ax2+⋯+Axk=SA_{x_1}+A_{x_2}+\cdots + A_{x_k}=S 的子序列数量。求 ∑L=1N∑R=LNf(L,R)\sum\limits^N_{L=1}\sum\limits^N_{R=L}f(L,R) 。

Idea

dp[j]dp[j]表示当前和为 jj 的子序列数量，那么本题的方案数就可以通过 0101 背包的方法转移。考虑新加入一个数字 AiA_i 时的转移，首先对于新加入的元素，我们只需要考虑新加入元素与先前元素构成的新子序列，即只考虑 f(L,R)f(L,R) 右端点变化，这一过程通过 0101 背包转移方案数；然后， f(L,R)f(L,R) 左端点的选择是在 [1,i][1,i] 范围内任意的，因此加入的 AiA_i 对后继的影响是： dp[A[i]]=dp[A[i]]+idp\left[A\left[i\right]\right]=dp\left[A\left[i\right]\right]+i 。

Code

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
#include<iostream>
using namespace std;
const int N=3003;
const int mod=998244353;
int dp[N],A[N];
int ans;
int n,s;
void solve()
{
	int i,j;
	cin>>n>>s;
	for(i=1;i<=n;i++) cin>>A[i];
	for(i=1;i<=n;i++)
	{
		for(j=s;j>=A[i];j--)
		{
			//01背包式的转移 
			dp[j]=(dp[j-A[i]]+dp[j])%mod;
		}
		//可添加 
		if(A[i]<=s) dp[A[i]]=(dp[A[i]]+i)%mod;
		ans=(dp[s]+ans)%mod;
	}
	cout<<ans<<endl;
}
int main()
{
	solve();
	return 0;
}

Postscrip

很多动态规划问题都可以转化为背包模型。