A洛谷P10999 [蓝桥杯 2024 省 Python B] 穿越时空之门
考了进制
#include<iostream>
#define int long long
using namespace std;
int ans;
int a(int x){int res = 0;while(x){res += x % 2;x /= 2;}return res;
}
int b(int x){int res = 0;while(x){res += x % 4;x /= 4;}return res;
}
signed main(){for(int i = 1; i <= 2024; i++){if(a(i) == b(i))ans++;}cout << ans << endl;return 0;
}B洛谷P11042 [蓝桥杯 2024 省 Java B] 类斐波那契循环数
#include<iostream>
#include<vector>
using namespace std;
/*
bool check(int x){string s = to_string(x);int len = s.size();vector<int> a(len);for(int i = 0; i < len; i++){a[i] = s[i] - '0';}while(1){int t = 0;for(int i = a.size() - len; i < a.size(); i++){t += a[i];}if(t > 1e7)return false;if(t == x)return true;a.push_back(t); }
}*/
signed main(){/*for(int i = 1e7; i >= 0; i--){if(check(i))cout << i << endl;}*/cout << 7913837 << endl;return 0;
}C洛谷P9240冶炼金属
#include<iostream>
using namespace std;
int n;
const int N = 10010;
int a, b;
int ans[N][2];//ans[i][0]为最小值ans[i][1]为最大值
int main(){cin >> n;int minn = 0, maxx = 0x3f3f3f3f;for(int i = 1; i <= n; i++){int a, b; cin >> a >> b;ans[i][1] = a / b;ans[i][0] = (a / (b + 1)) + 1;minn = max(minn, ans[i][0]);maxx = min(maxx, ans[i][1]);}cout << minn << " " << maxx << endl;return 0;
}D洛谷P5440 【XR-2】奇迹
一道模拟题
单词筛质数
bool is_prime(int x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0)return 0;
}
return 1;
}快
多次欧式筛快。
#include<iostream>
using namespace std;
int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int d[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int a[200], ans[1000010];
bool is_prime(int x){for(int i = 2; i <= x / i; i++){if(x % i == 0)return 0;}return 1;
}
int main(){int cnt = 0;for(int i = 1; i <= 12; i++){//月ifor(int j = 1; p[j] <= d[i - 1]; j++){//天数p[j] if(is_prime(100 * i + p[j]))a[++cnt] = 100 * i + p[j];} }int t = 0;for(int i = 1; i <= 9999; i++){//年i for(int j = 1; j <= cnt; j++){//符合的月日if(is_prime(10000 * i + a[j]))ans[++t] = 10000 * i + a[j];}}//特判闰年 for(int i = 4; i <= 9999; i += 4){//年i if(i % 100 != 0 || i % 400 == 0){if(is_prime(i * 10000 + 229))ans[++t] = i * 10000 + 229;}}int n; cin >> n;while(n--){int res = 0;char s[10]; cin >> (s + 1);for(int i = 1; i <= t; i++){//枚举t个符合的数int now = ans[i], flag = 1;for(int j = 8; flag && j; j--, now /= 10){if(s[j] != '-' && s[j] - '0' != now % 10){flag = 0;} }if(flag)res++;}cout << res << endl;} return 0;
}E洛谷P1441 砝码称重
dfs暴力得百分之60分
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 25;
int a[N];
bool flag[N], vis[100010];
int res, ans;
int gett[N];
void dfs1(int x, int sum){if(sum > 0 && !vis[sum]){ans++;vis[sum] = true;}if(x > n)return;for(int i = x; i <= n; i++){if(!flag[i]){dfs1(i + 1, sum + a[i]); }}
}
void dfs(int x, int cnt){//x为当前砝码，cnt为去掉的个数 if(cnt > m)return;if(x > n){if(cnt == m){ans = 0;memset(vis, 0, sizeof(vis));dfs1(1, 0);res = max(res, ans);}return;}flag[x] = true;dfs(x + 1, cnt + 1);flag[x] = false;dfs(x + 1, cnt);
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];dfs(1, 0);cout << res << endl;return 0;
} 下面进行dp优化
#include<bits/stdc++.h>
using namespace std;
int n, m;
const int N = 25;
int a[N];
bool flag[N], f[2010];
int res, ans;
void dp(){memset(f, 0, sizeof(f));f[0] = true; int sum = 0;ans = 0;for(int i = 1; i <= n; i++){if(flag[i])continue;for(int j = sum; j >= 0; j--){if(f[j] && !f[j + a[i]])f[j + a[i]] = true, ans++;}sum += a[i];}res = max(res, ans);
}
void dfs(int x, int cnt){//x为当前砝码，cnt为去掉的个数 if(cnt > m)return;if(x > n){if(cnt == m){dp();}return;}flag[x] = true;//抛弃 dfs(x + 1, cnt + 1);flag[x] = false;dfs(x + 1, cnt);
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++)cin >> a[i];dfs(1, 0);cout << res << endl;return 0;
} F洛谷P2088 果汁店的难题
#include<bits/stdc++.h>
using namespace std;
int k, n;
const int N = 110;
int a[N];
set<int>machines;//正在使用的果汁机
int main(){cin >> k >> n;for(int i = 1; i <= n; i++)cin >> a[i];int ans = 0;for(int i = 1; i <= n; i++){if(machines.find(a[i]) != machines.end())continue;//机器中有这类果汁，直接使用if(machines.size() < k)machines.insert(a[i]);//如果有空闲的果汁机，直接使用else{int first = -1, mach = -1;for(auto machine : machines){int next = 0x3f3f3f3f;for(int j = i + 1; j <= n; j++){//找到最后使用的果汁 if(a[j] == machine){next = j;break;}}if(next > first){first = next;mach = machine;}}machines.erase(mach);machines.insert(a[i]);ans++;} }cout << ans << endl;return 0;
} G洛谷P1982 [NOIP 2013 普及组] 小朋友的数字
前置知识洛谷P1115最大子段和
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 20005;
int a, b;
int ans = INT_MIN;
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a;
if(i == 1)b = a;
else b = max(a, a + b);
ans = max(ans, b);
}
cout << ans << endl;
return 0;
}
不优化：爆long long
#include<bits/stdc++.h>
using namespace std;
int n, p, a;
signed main(){cin >> n >> p >> a;//a是第一个数据if(n < 2){//特判只有一个数据 cout << a % p << endl;return 0; } long long su = max(a, 0);//最大子段和的辅助变量 long long maxx = a;//当前的最大子段和也就是特征值 long long maxn = a * 2;//存储分数fe[n]的变量for(int i = 2; i < n; i++){//最后一个对答案没贡献不读 int c; cin >> c; su += c;maxx = max(maxx, su);//最大子段和 maxn += max(maxx, (long long)0);//得分 su = max(su, (long long)0);//保证不为负，如果为负就不要前面的了，到后面+=c只要后面那个 } cout << max((long long)a, maxn) % p << endl;//如果都是负的那就是a啦 return 0;
} 优化有点难，先过了。
H洛谷P11659 小夫
太难了，跳过。