最小的数
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 31 Accepted Submission(s) : 17
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
定义一种正整数集合K，集合中有N个数，集合中元素Ki（1<=i<=N）是包含i个不同质因子的最小的数。因为Ki可能会很大，所以将集合中所有Ki对10^9+7取余。Input
本题只有唯一一组测试数据，第一行给出N，q，表示K的个数以及q次询问。1<=N<=1000，q<=10^5.接下来q行每行一个正整数（64位整数范围内），请判断其对10^9+7取余后，是否在集合K中。
Output
对于每次询问，根据题意输出Yes或NoSample Input
3 3
2
6
33
Sample Output
Yes
Yes
No
思路：因为集合中有n个数（每个数都是由i个不同的质因子组成的最小的数），所以通过素数筛选法选出前n个素数，
因为要是不同的质因子，所以最小的数就是i个相对小的素数相乘，然后把乘积取余放入set中，之后直接查找就好了
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <cmath>
10 #include <cstdio>
11 #include <algorithm>
12 #define N 2225
13 #define M 1000000
14 #define LL __int64
15 #define inf 0x3f3f3f3f
16 #define lson l,mid,ans<<1
17 #define rson mid+1,r,ans<<1|1
18 using namespace std;
19 const LL mod = 1e9 + 7;
20 const double eps = 1e-9;
21 LL num[N];
22 int flag[M];
23 set<LL> s;
24 int main() {
25 cin.sync_with_stdio(false);
26 s.clear();
27 LL n, q;
28 cin >> n;
29 q = 0;
30 memset(flag, 0, sizeof(flag));
31 for (int i = 2; i < M; i++) {
32 if (!flag[i]) {
33 num[q++] = i;
34 if (q == n) {
35 break;
36 }
37 for (int j = i + i; j < M; j += i) {
38 flag[j] = 1;
39 }
40 }
41 }
42 s.insert(num[0]);
43 for (int i = 1; i < n; i++) {
44 num[i] *= num[i - 1];
45 num[i] %= mod;
46 s.insert(num[i]);
47 }
48 cin >> q;
49 while (q--) {
50 cin >> n;
51 n %= mod;
52 if (s.find(n) != s.end()) {
53 cout << "Yes" << endl;
54 }
55 else {
56 cout << "No" << endl;
57 }
58 }
59 return 0;
60 }
不安全字符串
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 15 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
集训十分无聊，于是boss发明了一个“益智”游戏——假设有一段仅由U和L构成的字符串，我们定义当连续的U的个数大于等于三的时候，这个字符串是不安全的。现告诉你字符串的长度n,请你算出能够生成多少个不安全字符串。Input
输入有多组，每组仅输入一个n，代表字符串的长度,当n等于0的时候输入结束。（4<=n<=30）Output
输出可生成的不安全字符串的个数。Sample Input
4
5
0
Sample Output
3
8
思路：递推吧，因为每一个情况都是由前一个情况转变过来的，所以用一个dp数组去存每个情况相应的值，每一层的意思如下：（i为当前序列的长度）
dp[i][0]没有三个连续U的序列最右边为L
dp[i][1]没有三个连续U的序列最右边有一个U
dp[i][2]没有三个连续U的序列最右边有两个连续的U
dp[i][3]有三个连续的U的序列
结合每个情况可以发现
- dp[i][0]可以由dp[i-1][0]+dp[i-1][1]+dp[i-1][2]转变过来，因为前一状态只要不是有了3个连续的U的序列，在最右边加一个L就可以形成
- dp[i][1]可以由dp[i - 1][0]转变过来，因为只能是在最右边没有U的序列加上个U形成
- dp[i][2]可以由dp[i - 1][1]转变过来，因为只能是在最右边有一个U的序列加上个U形成
- dp[i][3]可以由dp[i - 1][3] * 2 + dp[i - 1][2]转变过来，因为如果原本就是有连续3个U的序列最右边加上什么都是该情况，然后也可以在最右边有两个U的序列加上个U形成
结合上面的思路就能写出这题了
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <cmath>
10 #include <cstdio>
11 #include <algorithm>
12 #define N 35
13 #define M 1000000
14 #define LL __int64
15 #define inf 0x3f3f3f3f
16 #define lson l,mid,ans<<1
17 #define rson mid+1,r,ans<<1|1
18 using namespace std;
19 const LL mod = 1e9 + 7;
20 const double eps = 1e-9;
21 LL dp[N][4];
22 void init() {
23 dp[1][0] = 1;
24 dp[1][1] = 1;
25 dp[1][2] = 0;
26 dp[1][3] = 0;
27 for (int i = 2; i <= 37; i++) {
28 dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2];
29 dp[i][1] = dp[i - 1][0];
30 dp[i][2] = dp[i - 1][1];
31 dp[i][3] = dp[i - 1][3] * 2 + dp[i - 1][2];
32 }
33 }
34 int main() {
35 cin.sync_with_stdio(false);
36 int n;
37 init();
38 while (cin >> n&&n) {
39 cout << dp[n][3] << endl;
40 }
41 return 0;
42 }
壮壮的数组
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 32 Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
A,B,C为三个元素个数为n的数组，A={a1,a2,a3...an},B={b1,b2,b3...bn},C={c1,c2,c3...cn};已知A、B数组，而且有ci等于ai或bi（1<=i<=n），毫无疑问，C数组有很多种组合。
但是zz不希望C数组全由A数组或者B数组组成，每一种组合都有一个K值，K=c1*c2*c3*...*cn。
现在需要你求出每一种组合对应的K值，并将它们加起来的结果。这个结果可能会很大，请将答案对1e9+7取模。
例如A={1,2,3} B={2,2,4}。
C数组可能为{a1,b2,b3} {b1,a2,b3} {b1,b2,a3} {a1,a2,b3} {a1,b2,a3} {b1,a2,a3}
K值分别为8，16，12，8，6，12，所以你应该输出62。
大量输入，建议使用scanf
Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(1<=n<=100000)，表示A,B,C数组元素个数，第二行有n个数据表示a1 a2 a3...an，第三行有n个数据表示b1 b2 b3...bn，(1<=ai,bi<=1e9)。处理到文件的结束。Output
对于每个测试实例，输出一行数据表示问题的答案，请将答案对1e9+7取模。Sample Input
3
1 2 3
2 2 4
1
3
4
Sample Output
62
0
思路：数学题目，因为c序列是由a，b序列中的数构成的，每一位不是选a[i]，就是选b[i]，但是因为数据量比较大所以不能直接模拟去写，举个例子：
A序列：a1 a2
B序列：b1 b2
C序列：(1)a1 b2 (2)a2 b1
K值得总和：a1 * b2+a2 * b1
(a1+b1) * (a2+b2) = a1 * a2+a1 * b2+b1 * a2+b1 * b2
K=(a1+b1) * (a2+b2)-(a1 * a2+b1 * b2)（因为不让全为A或者B）
所以可以通过这个方式计算出K的值
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <cmath>
10 #include <cstdio>
11 #include <algorithm>
12 #define N 100010
13 #define M 1000000
14 #define LL __int64
15 #define inf 0x3f3f3f3f
16 #define lson l,mid,ans<<1
17 #define rson mid+1,r,ans<<1|1
18 using namespace std;
19 const LL mod = 1e9 + 7;
20 const double eps = 1e-9;
21 LL a[N], b[N];
22 int main() {
23 cin.sync_with_stdio(false);
24 int n;
25 LL sum, ans, cnt;
26 while (cin >> n) {
27 ans = 1;
28 for (int i = 0; i < n; i++) {
29 cin >> a[i];
30 ans *= a[i];
31 ans %= mod;
32 }
33 cnt = 1;
34 for (int i = 0; i < n; i++) {
35 cin >> b[i];
36 cnt *= b[i];
37 cnt %= mod;
38 }
39 sum = 1;
40 for (int i = 0; i < n; i++) {
41 sum *= (a[i] + b[i]);
42 sum %= mod;
43 }
44 sum = (sum + mod - ans + mod - cnt) % mod;
45 cout << sum << endl;
46 }
47 return 0;
48 }
涛涛的Party
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 31 Accepted Submission(s) : 16
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
涛神因为极强，并且特别帅，所以拥有很多美女的联系方式，每个美女都有自己的食量以及魅力值，大家都知道，物以类聚，人以群分，朋友的朋友就是自己的朋友，所以美女一般都是有自己的美女朋友圈，而且这些美女特别团结，如果她的朋友有没有被邀请的她就不会答应邀请。涛涛想办一个party，但是他只准备了w kg的食物，他想获得最大的美女魅力值，不知道怎么邀请美女，于是他去问你，你能告诉他，他能获得的美女魅力数是多少吗Input
数据有多组，第一行输入n,m和w(1≤n≤1000,0≤m≤min(n*(n-1)/2,10^5),1≤w≤1000)；第二行输入n个整型变量w1,w2,...,wn(1≤wi≤1000)代表美女i的食量；第三行输入n个整型变量b1,b2,...,bn(1≤bi≤106)代表美女i的魅力值；接下来的m行输入两个数x和y(1≤xi,yi≤n,xi≠yi),代表x和y是朋友Output
输出涛涛能获得的最大魅力值Sample Input
3 1 5
3 2 5
2 4 2
1 2
4 2 11
2 4 6 6
6 4 2 1
1 2
2 3
Sample Output
6
1
思路：就是并查集+01背包，因为他必须要是一个朋友圈的人参加才会去，并且朋友的朋友就是自己的朋友，
所以通过并查集去得到这个朋友圈，把这个朋友圈中的所有美女的食量和魅力值都叠加起来，求01背包就好了
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <cmath>
10 #include <cstdio>
11 #include <algorithm>
12 #define LL long long
13 #define N 1100
14 #define M 50010
15 #define inf 0x3f3f3f3f
16 using namespace std;
17 const LL mod = 1e9 + 7;
18 const double eps = 1e-9;
19 int pre[N];
20 LL dp[N];
21 struct node {
22 int w, b;
23 }people[N];
24 map<int,node>quan;
25 int n, m, w;
26 void init() {
27 for (int i = 0; i <= n; i++) {
28 pre[i] = i;
29 }
30 quan.clear();
31 memset(dp, 0, sizeof(dp));
32 }
33 int find(int x) {
34 if (pre[x] == x) {
35 return x;
36 }
37 return pre[x] = find(pre[x]);
38 }
39 void add(int a, int b) {
40 int aa = find(a);
41 int bb = find(b);
42 if (aa != bb) {
43 pre[aa] = bb;
44 }
45 }
46 bool cmp(node a, node b) {
47 if (a.w == b.w) {
48 return a.b > b.b;
49 }
50 return a.w < b.w;
51 }
52 int main() {
53 cin.sync_with_stdio(false);
54 int a, b;
55 while (cin >> n >> m >> w) {
56 init();
57 for (int i = 1; i <= n; i++) {
58 cin >> people[i].w;
59 }
60 for (int i = 1; i <= n; i++) {
61 cin >> people[i].b;
62 }
63 for (int i = 0; i < m; i++) {
64 cin >> a >> b;
65 add(a, b);
66 }
67 for (int i = 1; i <= n; i++) {
68 if (quan.find(find(i)) == quan.end()) {
69 quan[pre[i]].w = 0;
70 quan[pre[i]].b = 0;
71 }
72 quan[pre[i]].w += people[i].w;
73 quan[pre[i]].b += people[i].b;
74 }
75 for (map<int, node>::iterator it = quan.begin(); it != quan.end();it++) {
76 node now = it->second;
77 for (int i = w; i >= now.w; i--) {
78 dp[i] = max(dp[i], dp[i - now.w] + now.b);
79 }
80 }
81 cout << dp[w] << endl;
82 }
83 return 0;
84 }
手机信号
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 13 Accepted Submission(s) : 10
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
现在在市面上流传了一款功能极简的手机，在手机上用一个 7×7 的显示屏来显示手机信号，每个区块能显示一个字符。满信号的时候显示如下：+-----+
|- 4G|
|-- |
|--- |
|---- |
|-----|
+-----+
（杭电描述区块对字宽的设定不统一，正确显示请看输出样例）
每一格信号（第i(1≤i≤5) 格信号有 i个-）代表 20% 的信号强度，不足一格信号的部分不显示。同时会在右上角显示当前的网络传输模式。在信号强度不低于 90% 的时候显示4G；当信号低于 90%、不低于 60% 的时候显示3G；否则显示E。
对于给定的当前信号强度 d%，输出信号的 7×7 像素的图案。
Input
输入一个整数 d(0≤d≤100)，表示信号强度。Output
按照题目要求输出，每行末尾不要输出多余的空白字符。Sample Input
0
65
Sample Output
+-----+
| E|
| |
| |
| |
| |
+-----+
+-----+
|- 3G|
|-- |
|--- |
| |
| |
+-----+
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <algorithm>
6 #define N 310
7 #define inf 0x3f3f3f3f
8 using namespace std;
9 int main() {
10 int n;
11 cin.sync_with_stdio(false);
12 while (cin >> n) {
13 cout << "+-----+" << endl;
14 if (n < 20) {
15 cout << "| E|\n| |\n| |\n| |\n| |\n+-----+" << endl;
16 }
17 else if (n < 40) {
18 cout << "|- E|\n| |\n| |\n| |\n| |\n+-----+" << endl;
19 }
20 else if (n < 60) {
21 cout << "|- E|\n|-- |\n| |\n| |\n| |\n+-----+" << endl;
22 }
23 else if (n < 80) {
24 cout << "|- 3G|\n|-- |\n|--- |\n| |\n| |\n+-----+" << endl;
25 }
26 else if (n < 90) {
27 cout << "|- 3G|\n|-- |\n|--- |\n|---- |\n| |\n+-----+" << endl;
28 }
29 else if (n < 100) {
30 cout << "|- 4G|\n|-- |\n|--- |\n|---- |\n| |\n+-----+" << endl;
31 }
32 else {
33 cout << "|- 4G|\n|-- |\n|--- |\n|---- |\n|-----|\n+-----+" << endl;
34 }
35 }
36 return 0;
37 }
涛神的城堡
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 55 Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
涛神有一个城堡给游客参观，涛神特别的强壮，涛神的强壮值是strong，每个游客也有自己的强壮值，涛神为了赚钱，他会选取多个区间去打劫别人，所以如果比涛神弱的，他就要收取他们的强壮值的差值，但是还是有比涛涛强壮的，所以涛涛打劫那个人的话，涛涛要给那个人他们的强壮值的差值，所以涛涛可以选择打不打劫那个区间的人，（人是可以重复打劫的，区间不行）涛涛最多能赚多少钱呢？Input
第一行给你三个整型变量n,m,strong(1≤n,m≤10000,1≤strong≤200),第二行给你n个人的强壮值a1,a2,...,an(1≤ai≤200).
接下来m行给你两个整型变量l,r(1≤li≤ri≤n),代表区间里包括了第l个游客到第r个游客,涛涛可以选择打不打劫这个区间
Output
输出涛涛可以打劫到的最多的钱Sample Input
5 4 10
9 12 9 7 14
1 2
4 5
3 4
1 4
Sample Output
7
思路：就是一个前缀和的想法，先把涛涛对于每个人能得到多少钱或者失去多少钱预处理出来，然后通过前缀和就可
以得到每个区间能的得到或者失去多少钱，moneysum[l~r]=sum[r]-sum[l-1]。然后做一个贪心操作，把能获得钱的区
间取出来，要付钱的区间去掉，这样就是涛涛能获得的最大的钱数
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <cmath>
10 #include <cstdio>
11 #include <algorithm>
12 #define LL long long
13 #define N 11000
14 #define M 50010
15 #define inf 0x3f3f3f3f3f3f3f3f
16 using namespace std;
17 const LL mod = 1e9 + 7;
18 const double eps = 1e-9;
19 int num[N];
20 int main() {
21 cin.sync_with_stdio(false);
22 int n, m;
23 int strong;
24 int a, b, c;
25 while (cin >> n >> m >> strong) {
26 num[0] = 0;
27 for (int i = 1; i <= n; i++) {
28 cin >> num[i];
29 num[i] = strong - num[i];
30 num[i] += num[i - 1];
31 }
32 int sum = 0;
33 for (int i = 0; i < m; i++) {
34 cin >> a >> b;
35 c = num[b] - num[a - 1];
36 if (c > 0) {
37 sum += c;
38 }
39 }
40 cout << sum << endl;
41 }
42 return 0;
43 }
dada的GCD
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 23 Accepted Submission(s) : 13
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
C语言都学过了怎么计算两个数的最大公约数，而一段区间[L,R]的GCD即这段区间所有数的最大公约数。现在给你一串长度为n的序列，如果对于序列的任意子区间[L,R]，都有这段区间的gcd>=2，那么这段序列就叫做dada的GCD序列。n<=10^4
序列的每个数小于10^9
Input
第一行有一个整数t，代表t组数据每组输入有一个正整数n，
随后一行n个正整数。
大量输入，使用cin的同学请关闭stdio同步
Output
如果是dada的GCD序列，就输出Yes，反之输出NoSample Input
2
3
2 6 4
3
4 6 9
Sample Output
Yes
No
思路：因为问你一个序列的任意区间的gcd是不是大于等于2，因为是任意区间，所有其实只有整个序列的gcd是大于等于2的时候任意区间的gcd是大于等于2的
1 #include <iostream>
2 #include <cstring>
3 #include <string>
4 #include <queue>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <stack>
9 #include <cmath>
10 #include <cstdio>
11 #include <algorithm>
12 #define N 100010
13 #define M 1000000
14 #define LL __int64
15 #define inf 0x3f3f3f3f
16 #define lson l,mid,ans<<1
17 #define rson mid+1,r,ans<<1|1
18 using namespace std;
19 const LL mod = 1e9 + 7;
20 const double eps = 1e-9;
21 LL num[N];
22 LL gcd(LL a, LL b) {
23 return b == 0 ? a : gcd(b, a%b);
24 }
25 int main() {
26 cin.sync_with_stdio(false);
27 int n, T;
28 cin >> T;
29 while (T--) {
30 cin >> n;
31 for (int i = 0; i < n; i++) {
32 cin >> num[i];
33 }
34 if (n == 1) {
35 if (num[0] >= 2) {
36 cout << "Yes" << endl;
37 }
38 else {
39 cout << "No" << endl;
40 }
41 }
42 else {
43 LL ans = gcd(num[0], num[1]);
44 for (int i = 2; i < n; i++) {
45 ans = gcd(ans, num[i]);
46 }
47 if (ans >= 2) {
48 cout << "Yes" << endl;
49 }
50 else {
51 cout << "No" << endl;
52 }
53 }
54 }
55 return 0;
56 }