最小的数

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或No

Sample Input

3 3

2

6

33

Sample Output

Yes

Yes

No


思路：因为集合中有n个数（每个数都是由i个不同的质因子组成的最小的数），所以通过素数筛选法选出前n个素数，
因为要是不同的质因子，所以最小的数就是i个相对小的素数相乘，然后把乘积取余放入set中，之后直接查找就好了
 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 #define N 2225

 #define M 1000000

 #define LL __int64

 #define inf 0x3f3f3f3f

 #define lson l,mid,ans<<1

 #define rson mid+1,r,ans<<1|1

 using namespace std;

 const LL mod = 1e9 + ;

 const double eps = 1e-;

 LL num[N];

 int flag[M];

 set<LL> s;

 int main() {

     cin.sync_with_stdio(false);

     s.clear();

     LL n, q;

     cin >> n;

     q = ;

     memset(flag, , sizeof(flag));

     for (int i = ; i < M; i++) {

         if (!flag[i]) {

             num[q++] = i;

             if (q == n) {

                 break;

             }

             for (int j = i + i; j < M; j += i) {

                 flag[j] = ;

             }

         }

     }

     s.insert(num[]);

     for (int i = ; i < n; i++) {

         num[i] *= num[i - ];

         num[i] %= mod;

         s.insert(num[i]);

     }

     cin >> q;

     while (q--) {

         cin >> n;

         n %= mod;

         if (s.find(n) != s.end()) {

             cout << "Yes" << endl;

         }

         else {

             cout << "No" << endl;

         }

     }

     return ;

 }

不安全字符串

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的序列

结合每个情况可以发现

  1. dp[i][0]可以由dp[i-1][0]+dp[i-1][1]+dp[i-1][2]转变过来，因为前一状态只要不是有了3个连续的U的序列，在最右边加一个L就可以形成
  2. dp[i][1]可以由dp[i - 1][0]转变过来，因为只能是在最右边没有U的序列加上个U形成
  3. dp[i][2]可以由dp[i - 1][1]转变过来，因为只能是在最右边有一个U的序列加上个U形成
  4. dp[i][3]可以由dp[i - 1][3] * 2 + dp[i - 1][2]转变过来，因为如果原本就是有连续3个U的序列最右边加上什么都是该情况，然后也可以在最右边有两个U的序列加上个U形成

结合上面的思路就能写出这题了

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 #define N 35

 #define M 1000000

 #define LL __int64

 #define inf 0x3f3f3f3f

 #define lson l,mid,ans<<1

 #define rson mid+1,r,ans<<1|1

 using namespace std;

 const LL mod = 1e9 + ;

 const double eps = 1e-;

 LL dp[N][];

 void init() {

     dp[][] = ;

     dp[][] = ;

     dp[][] = ;

     dp[][] = ;

     for (int i = ; i <= ; i++) {

         dp[i][] = dp[i - ][] + dp[i - ][] + dp[i - ][];

         dp[i][] = dp[i - ][];

         dp[i][] = dp[i - ][];

         dp[i][] = dp[i - ][] *  + dp[i - ][];

     }

 }

 int main() {

     cin.sync_with_stdio(false);

     int n;

     init();

     while (cin >> n&&n) {

         cout << dp[n][] << endl;

     }

     return ;

 }

壮壮的数组

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的值

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 #define N 100010

 #define M 1000000

 #define LL __int64

 #define inf 0x3f3f3f3f

 #define lson l,mid,ans<<1

 #define rson mid+1,r,ans<<1|1

 using namespace std;

 const LL mod = 1e9 + ;

 const double eps = 1e-;

 LL a[N], b[N];

 int main() {

     cin.sync_with_stdio(false);

     int n;

     LL sum, ans, cnt;

     while (cin >> n) {

         ans = ;

         for (int i = ; i < n; i++) {

             cin >> a[i];

             ans *= a[i];

             ans %= mod;

         }

         cnt = ;

         for (int i = ; i < n; i++) {

             cin >> b[i];

             cnt *= b[i];

             cnt %= mod;

         }

         sum = ;

         for (int i = ; i < n; i++) {

             sum *= (a[i] + b[i]);

             sum %= mod;

         }

         sum = (sum + mod - ans + mod - cnt) % mod;

         cout << sum << endl;

     }

     return ;

 }

涛涛的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背包就好了
 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 #define LL long long

 #define N 1100

 #define M 50010

 #define inf 0x3f3f3f3f

 using namespace std;

 const LL mod = 1e9 + ;

 const double eps = 1e-;

 int pre[N];

 LL dp[N];

 struct node {

     int w, b;

 }people[N];

 map<int,node>quan;

 int n, m, w;

 void init() {

     for (int i = ; i <= n; i++) {

         pre[i] = i;

     }

     quan.clear();

     memset(dp, , sizeof(dp));

 }

 int find(int x) {

     if (pre[x] == x) {

         return x;

     }

     return pre[x] = find(pre[x]);

 }

 void add(int a, int b) {

     int aa = find(a);

     int bb = find(b);

     if (aa != bb) {

         pre[aa] = bb;

     }

 }

 bool cmp(node a, node b) {

     if (a.w == b.w) {

         return a.b > b.b;

     }

     return a.w < b.w;

 }

 int main() {

     cin.sync_with_stdio(false);

     int a, b;

     while (cin >> n >> m >> w) {

         init();

         for (int i = ; i <= n; i++) {

             cin >> people[i].w;

         }

         for (int i = ; i <= n; i++) {

             cin >> people[i].b;

         }

         for (int i = ; i < m; i++) {

             cin >> a >> b;

             add(a, b);

         }

         for (int i = ; i <= n; i++) {

             if (quan.find(find(i)) == quan.end()) {

                 quan[pre[i]].w = ;

                 quan[pre[i]].b = ;

             }

             quan[pre[i]].w += people[i].w;

             quan[pre[i]].b += people[i].b;

         }

         for (map<int, node>::iterator it = quan.begin(); it != quan.end();it++) {

             node now = it->second;

             for (int i = w; i >= now.w; i--) {

                 dp[i] = max(dp[i], dp[i - now.w] + now.b);

             }

         }

         cout << dp[w] << endl;

     }

     return ;

 }

手机信号

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|

|--   |

|---  |

|     |

|     |

+-----+

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <algorithm>

 #define N 310

 #define inf 0x3f3f3f3f

 using namespace std;

 int main() {

     int n;

     cin.sync_with_stdio(false);

     while (cin >> n) {

         cout << "+-----+" << endl;

         if (n < ) {

             cout << "|    E|\n|     |\n|     |\n|     |\n|     |\n+-----+" << endl;

         }

         else if (n < ) {

             cout << "|-   E|\n|     |\n|     |\n|     |\n|     |\n+-----+" << endl;

         }

         else if (n < ) {

             cout << "|-   E|\n|--   |\n|     |\n|     |\n|     |\n+-----+" << endl;

         }

         else if (n < ) {

             cout << "|-  3G|\n|--   |\n|---  |\n|     |\n|     |\n+-----+" << endl;

         }

         else if (n < ) {

             cout << "|-  3G|\n|--   |\n|---  |\n|---- |\n|     |\n+-----+" << endl;

         }

         else if (n < ) {

             cout << "|-  4G|\n|--   |\n|---  |\n|---- |\n|     |\n+-----+" << endl;

         }

         else {

             cout << "|-  4G|\n|--   |\n|---  |\n|---- |\n|-----|\n+-----+" << endl;

         }

     }

     return ;

 }

涛神的城堡

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]。然后做一个贪心操作，把能获得钱的区

间取出来，要付钱的区间去掉，这样就是涛涛能获得的最大的钱数

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 #define LL long long

 #define N 11000

 #define M 50010

 #define inf 0x3f3f3f3f3f3f3f3f

 using namespace std;

 const LL mod = 1e9 + ;

 const double eps = 1e-;

 int num[N];

 int main() {

     cin.sync_with_stdio(false);

     int n, m;

     int strong;

     int a, b, c;

     while (cin >> n >> m >> strong) {

         num[] = ;

         for (int i = ; i <= n; i++) {

             cin >> num[i];

             num[i] = strong - num[i];

             num[i] += num[i - ];

         }

         int sum = ;

         for (int i = ; i < m; i++) {

             cin >> a >> b;

             c = num[b] - num[a - ];

             if (c > ) {

                 sum += c;

             }

         }

         cout << sum << endl;

     }

     return ;

 }

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，反之输出No

Sample Input

2

3

2 6 4

3

4 6 9

Sample Output

Yes

No

思路：因为问你一个序列的任意区间的gcd是不是大于等于2，因为是任意区间，所有其实只有整个序列的gcd是大于等于2的时候任意区间的gcd是大于等于2的

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 #include <cmath>

 #include <cstdio>

 #include <algorithm>

 #define N 100010

 #define M 1000000

 #define LL __int64

 #define inf 0x3f3f3f3f

 #define lson l,mid,ans<<1

 #define rson mid+1,r,ans<<1|1

 using namespace std;

 const LL mod = 1e9 + ;

 const double eps = 1e-;

 LL num[N];

 LL gcd(LL a, LL b) {

     return b ==  ? a : gcd(b, a%b);

 }

 int main() {

     cin.sync_with_stdio(false);

     int n, T;

     cin >> T;

     while (T--) {

         cin >> n;

         for (int i = ; i < n; i++) {

             cin >> num[i];

         }

         if (n == ) {

             if (num[] >= ) {

                 cout << "Yes" << endl;

             }

             else {

                 cout << "No" << endl;

             }

         }

         else {

             LL ans = gcd(num[], num[]);

             for (int i = ; i < n; i++) {

                 ans = gcd(ans, num[i]);

             }

             if (ans >= ) {

                 cout << "Yes" << endl;

             }

             else {

                 cout << "No" << endl;

             }

         }

     }

     return ;

 }

最新文章

  1. Zookeeper API for JAVA实战与应用
  2. 让Java和MySQL连接起来
  3. Android中各组件的生命周期
  4. jquery ajax跨域请求详解
  5. vxworks 实时操作系统
  6. SQL Server2008新特性Filesteam的使用
  7. dedecms织梦导航栏二级菜单的实现方法
  8. urllib模块 | Python 2.7.11
  9. 安装TensorFlow的步骤
  10. python词云的制作方法
  11. Kafka Consumer
  12. 如何将Drawable转为Bitmap？
  13. tomcat多端口配置
  14. 面试神体验之:get和post的区别
  15. Ubuntu 16.04 安装 JDK 1.8
  16. 机器学习入门-文本数据-构造Tf-idf词袋模型(词频和逆文档频率) 1.TfidfVectorizer(构造tf-idf词袋模型)
  17. html标签简介（常用）
  18. Linux下DNS服务器配置
  19. CSS3基础知识（一）
  20. python学习之老男孩python全栈第九期_数据库day002 -- 作业 (数据库为day001创建的数据库)

热门文章

  1. kafka2 简单介绍
  2. 使用SBT构建Scala应用【转载】
  3. python中的0,None,False,空容器
  4. Linux下Nginx安装
  5. Django 框架 基本知识
  6. 【Java】-NO.16.EBook.4.Java.1.012-【疯狂Java讲义第3版 李刚】- Swing
  7. Ubuntu16.04源的问题
  8. servlet的请求转发与重定向
  9. 如何控制TextBox的最打输入字符的长度
  10. sqlserver中查询表字段的sql语句