卡片
思路:这道题咋一看给人一种挺难的感觉,其实很简单,就是一个数的每位遍历。
#include<iostream> using namespace std; int main() { int a[10] = { 0 }; int t = 0; for (int i = 0; i <= 9; i++) { a[i] = 2021; } for ( t = 1; t <= 9900; t++) { int i = t; while (i > 0) { a[i % 10]--; if (a[i % 10] <= 0) { cout << t << endl; return 0; } i = i/ 10; } } }
答案:3181
直线
两点式直线方程：
(y1-y2) * x +(x2-x1) * y +( x1 * y2 - x2 * y1)=0
思路：先存储所有的坐标 ，遍历所有的坐标组获得直线Ax+By+C=0的A,B,C并使用gcd约分最后再利用set去重，最后再加上垂直于x轴和y轴的数.
#include<iostream> #include<set> using namespace std; typedef pair<double, double> PII; typedef pair<PII, double> PIII; set<PIII> ss; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { for (int x1 = 0; x1 <= 19; x1++) { for (int y1 = 0; y1 <= 20; y1++) { for (int x2 = 0; x2 <= 19; x2++) { for (int y2 = 0; y2 <= 20; y2++) { if (x1 != x2 && y1 != y2) { double a = x2 - x1; double b = y1 - y2; double c = y2 * x1 - x2 * y1; double m = gcd(gcd(a, b), c); ss.insert({ { a / m,b / m }, c / m }); //ss.insert(a); } } } } } cout << ss.size() + 20 + 21; return 0; }
答案:40257
货物摆放
思路:这道题是填空题,直接纯暴力法,不过要稍微优化下,我们可以通过减少for循环或者用缩小循环的范围即可.这道题就是拆解成三个因子(a,b,c),要保持a<=b<=c;可以通过sqrt来缩小循环范围
#include<iostream> using namespace std; #define n 2021041820210418 //n=a*b*c typedef long long ll; int ants = 0; int main() { for (ll a = 1; a * a * a <= n; a++) { if (n % a == 0) { for (ll b = a; a * b * b <= n; b++) { if (n / a % b == 0) { ll c = n / a / b; if (a == b && a == c)ants = 0; else if (a == b || a == c || c == b) ants += 3; else ants += 6; } } } } cout << ants << endl; return 0; }
这个是我在网上看的一种解法,把a,b,c放入到一个集合中,最近几年频繁使用这个set，所以尽可能多练练
#include<iostream> #include<cmath> #include<set> using namespace std; #define n 2021041820210418 //n=a*b*c int ants = 0; typedef long long ll; int main() { ll end = sqrt(n); for (ll a = 1; a <= end; a++) { if (n % a == 0) { ll nn = n / a; ll end1 = sqrt(nn); for (ll b = a; b <= end1; b++) { if (nn % b == 0) { ll c = nn / b; if (c >= b) { set<int> s; s.insert(a); s.insert(b); s.insert(c); if (s.size() == 1)ants += 1; else if (s.size() == 2) ants += 3; else if(s.size()==3) ants += 6; } } } } } cout << ants << endl; return 0; }
答案:2430
路径
思路:这道题直接就用floyd算法跑就行,反正填空题超时也不怕,三层循环等个几十秒就出来了。迪杰斯特拉写着太麻烦了。
#include<iostream> #include<cmath> using namespace std; typedef long long ll; #define INT 0x3f3f3f3f ll Edge[2022][2022]; int gcd(int a, int b)//最大公约数 { if (b == 0) return a; return gcd(b, a % b); } int lcm(int a, int b)//最小公倍数 { int c = a * b; return c / gcd(a, b); } int main() { //初始化 memset(Edge, INT, sizeof(Edge)); for (int i = 1; i <= 2021; i++) { for (int j = 1; j <= 2021; j++) { if (i == j)Edge[i][j] = 0; else { if (abs(i - j) <= 21)//判断差的绝对值是否小于等于21 { Edge[i][j] = lcm(i, j); } } } } //floyd算法核心 for (int k = 1; k <= 2021; k++) { for (int i = 1; i <= 2021; i++) { for (int j = 1; j <= 2021; j++) { if (Edge[i][j] > Edge[i][k] + Edge[k][j]) { Edge[i][j] = Edge[i][k] + Edge[k][j]; } } } } cout << Edge[1][2021]; return 0; }
答案:10266837
空间
思路:
1MB=1024KB 1KB=1024B 1B=8b
- 答案:（（256*1024）*1024）/ 4== 67108864
砝码称重
输入样例
3
1 4 6
输出样例
10
思路:
代码
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 110, M = 200010, B = M / 2; int n, m; int w[N]; bool f[N][M]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin>>w[i], m += w[i]; f[0][B] = true; for (int i = 1; i <= n; i++) { for (int j = -m; j <= m; j++) { f[i][j+B] = f[i - 1][j+B]; if (j - w[i] >= -m) f[i][j+B] |= f[i - 1][j - w[i]+B]; if (j + w[i] <= m)f[i][j+B] |= f[i - 1][j + w[i]+B]; } } int res = 0; for (int j = 1; j <= m; j++) { if (f[n][j + B]) { res++; } } cout<<res<<endl; return 0; }
我还看到一个特别好理解的思路:其时当发现一个重量可以得负数，再和以后的状态做加减转化时，正数减去也能代表负数，
如 有砝码 2 1 3
前俩可以拼凑出的状态 1 2 3 -1，
3 + （-1）和 3 - 1 效果是一样的，所以负的重量状态抛弃掉最后结果也是不变的
#include<iostream> using namespace std; int dp[105][100005]; int main() { int n; cin >> n; dp[0][0] = 1; for (int i = 1;i <= n;i++) { int a;cin >> a; for (int j = 0;j <= 100000;j++) { if (dp[i-1][j]) { dp[i][j] = 1; dp[i][j + a] = 1; dp[i][abs(j - a)] = 1; } } } int ans = 0; for (int i = 1;i <= 100000;i++)if (dp[n][i]) ans++; cout << ans; }
时间显示
输入样例
2
46800999
1618708103123
输出样例
13:00:00
01:08:23
思路:读清题目说的是毫秒，/1000换成秒,因为只要求最后一天的时分秒,所以%24*60*60就是去掉除了最后一天的前面所有天数;剩下的就是求时分秒了,很简单
#include<bits/stdc++.h> using namespace std; int main() { long long int n; cin>>n; n=n/1000; n=n%86400;//去掉除了最后一天的前面的天数;24*60*60 int h,m,s; h=n/3600;//求得最后一天的小时 n=n%3600; m=n/60;//分钟 s=n%60;//秒数 printf("%02d:%02d:%02d",h,m,s); //输出时间常用的形式，不用判断了 return 0; }
