1.P1473 [USACO2.3] 零的数列 Zero Sum
题目描述
请考虑一个由 1 到 N 的数字组成的递增数列：1,2,3,…,N。
现在请在数列中插入 + 表示加，或者 - 表示减， （空格） 表示空白（例如 1-2 3 就等于 1-23），来将每一对数字组合在一起（请不要在第一个数字前插入符号）。
计算该表达式的结果并判断其值是否为 0。 请你写一个程序找出所有产生和为零的长度为N的数列。
输入格式
单独的一行表示整数 N（3≤N≤9）。
输出格式
按照 ASCII码的顺序，输出所有在每对数字间插入 +，-， （空格） 后能得到结果为零的数列。
输入输出样例 #1
输入 #1
输出 #1
1
2
3
4
5
6
| 1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
|
说明/提示
翻译来自NOCOW
USACO 2.3
今日题解：
利用递归构造出所有的可能情况，利用token的转化计算sum。如果已到末尾，需要额外添加一个符号来触发token的转化。
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;
using ll = long long;
vector<string> results;
int N;
void dfs(int idx, string expr) {
if(idx>N) {
int sum=0;
string token="";
int sign=1;
for(char c : expr + '+') {
if(c=='+' || c=='-') {
if(!token.empty()) {
sum+= sign*stoi(token);
token.clear();
}
(c=='+') ? sign=1 : sign=-1;
} else if(c!=' ') {
token+=c;
}
}
if(sum==0) {
results.push_back(expr);
}
return;
}
dfs(idx+1, expr + "+" + to_string(idx));
dfs(idx+1, expr + "-" + to_string(idx));
dfs(idx+1, expr + " " + to_string(idx));
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>N;
dfs(2,"1");
sort(result.begin(), result.end());
for(string expr: results) {
cout<<expr<<'\n';
}
return 0;
}
|
2.P8649 [蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 N 的数列，A1,A2,⋯A**N，如果其中一段连续的子序列 A**i,A**i+1,⋯A**j(i≤j) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K (1≤N,K≤105)。
以下 N 行每行包含一个整数 A**i (1≤A**i≤105)。
输出格式
输出一个整数，代表 K 倍区间的数目。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
时限 2 秒, 256M。蓝桥杯 2017 年第八届
今日题解
理解同余定理，如果两个不同位置的前缀和模k的结果一样，那么他们构成的区间和一定为k的倍数，新出现的同余数可以与前面所有同余数的数分别构成区间，即直接加上其出现次数即可。
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
| #include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin>>n>>k;
vector<int> A(n);
for(int i=0;i<n;++i) {
cin>>A[i];
}
unordered_map<int, int> cnt;
cnt[0]=1;
ll ans=0;
ll pre=0;
for(int i=0;i<n;++i) {
pre=(pre+A[i]) % k;
if(cnt.find(pre) != cnt.end()) {
ans+=cnt[pre];
}
cnt[pre]++;
}
cout<<ans;
return 0;
}
|
3.P4310 绝世好题
题目描述
给定一个长度为 n 的数列 a**i，求 a**i 的子序列 b**i 的最长长度 k，满足 b**i&b**i−1=0，其中 2≤i≤k， & 表示位运算取与。
输入格式
输入文件共 2 行。 第一行包括一个整数 n。 第二行包括 n 个整数，第 i 个整数表示 a**i。
输出格式
输出文件共一行。 包括一个整数，表示子序列 b**i 的最长长度。
输入输出样例
输入 #1
输出 #1
说明/提示
对于100%的数据，1≤n≤100000，a**i≤109。
今日题解
可以直接暴力解,类似于最长上升子序列O(n^2)。
优化：发现新添加的数,
只能由:
在同一二进制位上 , 同为1的数转移而来
所以找到最长连续同2进制位为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
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
int dp[32] = {0};
int maxLength = 0;
for (int i = 1; i <= n; i++) {
int currentNumber;
cin >> currentNumber;
int currentLength = 1;
for (int bit = 0; bit <= 30; bit++) {
if ((1 << bit) & currentNumber) {
currentLength = max(dp[bit] + 1, currentLength);
}
}
for (int bit = 0; bit <= 30; bit++) {
if ((1 << bit) & currentNumber) {
dp[bit] = max(dp[bit], currentLength);
}
}
maxLength = max(maxLength, currentLength);
}
cout << maxLength;
return 0;
}
|
4.P2036 [COCI 2008/2009 #2] PERKET
题目描述
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
输入格式
第一行一个整数 n，表示可供选用的食材种类数。
接下来 n 行，每行 2 个整数 s**i 和 b**i，表示第 i 种食材的酸度和苦度。
输出格式
一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
输入输出样例
输入 #1
输出 #1
输入 #2
输出 #2
输入 #3
输出 #3
说明/提示
数据规模与约定
对于 100% 的数据，有 1≤n≤10，且将所有可用食材全部使用产生的总酸度和总苦度小于 1×109，酸度和苦度不同时为 1 和 0。
说明
今日题解
利用二进制位的01来表示选不选，以达到枚举所有子集的可能。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> s(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> s[i] >> b[i];
}
int ans = INT_MAX;
for (int mask = 1; mask < (1 << n); ++mask) {
int total_s = 1, total_b = 0;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
total_s *= s[i];
total_b += b[i];
}
}
ans = min(ans, abs(total_s - total_b));
}
cout << ans << '\n';
return 0;
}
|
5.P1464 Function
题目描述
对于一个递归函数 w(a,b,c)
- 如果 a≤0 或 b≤0 或 c≤0 就返回值 1。
- 如果 a>20 或 b>20 或 c>20 就返回 w(20,20,20)
- 如果 a<b 并且 b<c 就返回 w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)。
- 其它的情况就返回 w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)
这是个简单的递归函数，但实现起来可能会有些问题。当 a,b,c 均为 15 时，调用的次数将非常的多。你要想个办法才行。
注意：例如 w(30,−1,0) 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。
输入格式
会有若干行。
并以 −1,−1,−1 结束。
输出格式
输出若干行，每一行格式：
注意空格。
输入输出样例
输入 #1复制
输出 #1复制
1
2
| w(1, 1, 1) = 2
w(2, 2, 2) = 4
|
说明/提示
数据规模与约定
保证输入的数在 [−9223372036854775808,9223372036854775807] 之间，并且是整数。
保证不包括 −1,−1,−1 的输入行数 T 满足 1≤T≤105。
今日题解
记忆化存储
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<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<vector<ll>>> dp(21, vector<vector<ll>>(21, vector<ll>(21, -1)));
ll w(ll a,ll b, ll c) {
if(a<=0||b<=0||c<=0) {
return 1;
}
if(a>20||b>20||c>20)return w(20, 20, 20);
if(dp[a][b][c] != -1)return dp[a][b][c];
if(a<b && b<c) {
dp[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
}
else {
dp[a][b][c] = w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1,b-1,c-1);
}
return dp[a][b][c];
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll a, b, c;
while(cin>>a>>b>>c) {
if(a==-1&&b==-1&&c==-1) {
break;
}
else {
cout<<"w("<<a<<", "<<b<<", "<<c<<") = "<<w(a, b, c)<<'\n';
}
}
return 0;
}
|
