卡片
小蓝有很多数字卡片，每张卡片上都是数字0 到9。
小蓝准备用这些卡片来拼一些数，他想从1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从1 拼到多少。
例如，当小蓝有30 张卡片，其中0 到9 各3 张，则小蓝可以拼出1 到10，但是拼11 时卡片1 已经只有一张了，不够拼出11。
现在小蓝手里有0 到9 的卡片各2021 张，共20210 张，请问小蓝可以从1拼到多少？
提示：建议使用计算机编程解决问题。
#include <iostream> #include <bits/stdc++.h> using namespace std; int main() { int card[10] = {2021,2021,2021,2021,2021,2021,2021,2021,2021,2021}; int ans = 1; int temp = 0; int temp2 = 0; while(1) { temp = ans; while(temp != 0) { temp2 = temp % 10; card[temp2] --; if(card[temp2] == -1) { cout << ans - 1 << endl; return 0; } temp = temp / 10; } ans ++; } return 0; }
小技巧：用for从1到3500打印，再用word功能的查找功能，哪一个数字小于0了，就往回找。
货物摆放
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有n 箱货物要摆放在仓库，每箱货物都是规则的正方体。
小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆L、W、H 的货物，满足n = L × W × H。
给定n，请问有多少种堆放货物的方案满足要求。
例如，当n = 4 时，有以下6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
请问，当n = 2021041820210418 （注意有16 位数字）时，总共有多少种
方案？
提示：建议使用计算机编程解决问题。
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { set<ll>s; ll n = 2021041820210418; for(ll i = 1; i * i <= n; i ++) { if(n % i == 0) { s.insert(i); s.insert(n / i); } } ll ans = 0; for(auto a : s) { for(auto b : s) { for(auto c : s) { if(a * b * c == n) ans++; } } } cout << ans << endl; return 0; }
扩：set 带有排序 + 去重功能，ACMer必回知识点。
路径
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由2021 个结点组成，依次编号1 至2021。
对于两个不同的结点a, b，如果a 和b 的差的绝对值大于21，则两个结点之间没有边相连；
如果a 和b 的差的绝对值小于等于21，则两个点之间有一条长度为a 和b 的最小公倍数的无向边相连。
例如：结点1 和结点23 之间没有边相连；结点3 和结点24 之间有一条无向边，长度为24；
结点15 和结点25 之间有一条无向边，长度为75。
请计算，结点1 和结点2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; int gcd(int x,int y) { return !y ? x : gcd(y, x % y); } int main() { int f[2022]; memset(f, 0, sizeof f); for(int i = 1;i <= 2021;i++) { for(int j = i + 1; j <= i + 21; j ++) { if(j > 2021) break; if(f[j] == 0) f[j] = f[i] + j * i / gcd(i, j); else f[j] = min(f[j], f[i] + j * i / gcd(i, j)); } } cout << f[2021] << endl; return 0; }
砝码称重
题目描述
你有一架天平和N 个砝码，这N 个砝码重量依次是W1, W2, ... , WN。
请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数N。
第二行包含N 个整数：W1, W2, W3, ... , WN。
对于50% 的评测用例，1 ≤ N ≤ 15。
对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过100000。
输出格式
输出一个整数代表答案。
输入样例
3 1 4 6
输出样例
10
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; int dp[102][100005]={0}; int w[102]; int n; int sum = 0; int main() { scanf("%d",&n); for (int i = 1; i <= n; i++) { scanf("%d",&w[i]); sum += w[i]; } dp[0][0] = 1; for (int i = 1; i <= n; i++) for (int j = 0; j <= sum; j++) dp[i][j] = dp[i - 1][abs(j - w[i])] + dp[i - 1][j + w[i]] +dp[i - 1][j]; int ans = 0; for (int i = 1; i <= sum; i++) if (dp[n][i] != 0) ans++; printf("%d",ans); return 0; }
括号序列
题目描述
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法。
当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列((()，只需要添加两个括号就能让其合法
有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和((()))。
输入格式
输入一行包含一个字符串s，表示给定的括号序列，序列中只有左括号和右括号。
对于40% 的评测用例，|s| ≤ 200。
对于所有评测用例，1 ≤ |s| ≤ 5000。
输出格式
输出一个整数表示答案，答案可能很大，请输出答案除以1000000007
输入样例
((()
输出样例
5
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5005; int f[N][N]; int mod = 1e9 + 7; string s; int n; ll fun() { memset(f, 0, sizeof f); f[0][0] = 1; for (int i = 1; i <= n; i++) { if (s[i - 1] == '(') { for (int j = 1; j <= n; j++) f[i][j] = f[i - 1][j - 1]; } else { f[i][0] = (f[i - 1][1] + f[i - 1][0]) % mod; for (int j = 1; j <= n; j++) f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod; } } for (int i = 0; i <= n; i++) if (f[n][i]) return f[n][i]; return -1; } int main() { cin >> s; n = s.size(); ll x = fun(); reverse(s.begin(), s.end()); for (int i = 0; i < n; i++) { if (s[i] == ')') s[i] = '('; else s[i] = ')'; } ll y = fun(); cout << (x * y) % mod; }
时间显示
题目描述
小蓝要和朋友合作开发一个时间显示的网站。
在服务器上，朋友已经获取了当前的时间，用一个整数表示。
值为从1970 年1 月1 日00:00:00 到当前时刻经过的毫秒数。
现在，小蓝要在客户端显示出这个时间。
小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
输入格式
输入第一行包含正整数T，表示存在T组测试数据，T不超过1000。
接下来T行，每行一个正整数表示时间。时间不超过10^18。
输出格式
输出T行，每行按照如下格式：
输出时分秒表示的当前时间，格式形如HH:MM:SS
其中HH 表示时，值为0 到23，MM 表示分，值为0 到59，SS 表示秒，值为0 到59。
时、分、秒不足两位时补前导0。
输入样例
2 46800999 1618708103123
输出样例
13:00:00 01:08:23
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t, n; scanf("%lld", &t); while(t --) { scanf("%lld",&n); int shi,fen,miao; n /= 1000; n %= 86400; shi = n / 3600; n = n - shi * 3600; fen = n / 60; miao = n - fen * 60; printf("%02d:%02d:%02d\n",shi,fen,miao); // cout << n <<endl; } return 0; }
杨辉三角形
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数N，请你输出数列中第一次出现N 是在第几个数？
输入格式
输入包含T行，表示T组测试数据。T不超过10。
每行输入一个整数N，N不超过10^9。
输出格式
对于每组测试数据输出一行表示答案。
输入样例
2 3 6
输出样例
8 13
#include <iostream> #include <bits/stdc++.h> #include <algorithm> using namespace std; typedef long long ll; int n; ll fun(int a, int b) { ll res = 1; for(int i = a, j = 1; j <= b; i -- ,j ++ ) { res = res * i / j; if(res > n) return res; } return res; } bool check(int k) { ll l = k * 2; ll r = max((ll)n, l); while(l < r) { ll mid = l + r >> 1; if(fun(mid, k) >= n) { r = mid; } else l = mid + 1; } if(fun(r, k) != n) return 0; cout << r * (r + 1) / 2 + k + 1 << endl; return 1; } int main() { scanf("%d", &n); for(int i = 16; i >= 0; i -- ) { if(check(i)) { return 0; } } return 0; }
空间
小蓝准备用256MB 的内存空间开一个数组，数组的每个元素都是32 位二进制整数。
如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256MB 的空间可以存储多少个32 位二进制整数？
#include <iostream> using namespace std; int main() { // 请在此输入您的代码 //1MB=1024KB //1KB=1024B //1B=8b; //B:byte字节 //b:bit比特(1位=1比特) //32位=4B //题解的意思是有多少个32位 //转化成long long避免数据溢出 cout<<(long long)256*1024*1024*8/32; return 0; }
相乘
小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以 1000000007 的余数，会得到不同的数。
小蓝想知道，能不能在 1 至 1000000007 之间找到一个数，与 2021 相乘后 再除以 1000000007 后的余数为 999999999。
如果存在，请在答案中提交这个数； 如果不存在，请在答案中提交 0。
#include <iostream> #include <bits/stdc++.h> #include <algorithm> using namespace std; typedef long long ll; int main() { ll n = 1000000007; ll i = 1; while(1) { if((n * i + 999999999) % 2021 == 0) { cout << ((n * i + 999999999) / 2021); return 0; } i ++; } return 0; }
