A 工作时长
题意：若干条打卡记录字符串（年月日时分秒格式），保证打卡记录相邻。求该年工作时长。
思路：对字符串处理，转换格式为秒数，排序后相邻相减求和。
总结：2月有29天的情况要被4整除，如果能被100整除的话，一定要被400整除。
struct Data{
int month;//5
int day; //8
int hour; //11
int minute; //14
int second; //17
long long cur = 0;
};
array<int, 13> days{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void solve(){
/*
for (int i = 1; i < 13; ++i){
days[i] += days[i - 1];
}
string s;
vector<long long> a;
while (getline(cin, s) && s != "!"){
Data data;
data.month = stoi(s.substr(5, 2));
data.day = stoi(s.substr(8, 2));
data.hour = stoi(s.substr(11, 2));
data.minute = stoi(s.substr(14, 2));
data.second = stoi(s.substr(17, 2));
cout << data.month << " " << data.day <<" " << data.hour << " " << data.minute << " "<<data.second << endl;
data.cur = (((days[data.month - 1] + data.day) *24 + data.hour) * 60 + data.minute) * 60 + data.second;
a.push_back(data.cur);
}
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 1; i < a.size(); i += 2){
ans += a[i] - a[i - 1];
}
cout << ans << '\n';*/
cout << 5101913 << '\n';
}
B 与或异或
题意：给定一个倒三角输入电路，点代表数值，边代表运算方式（有xor， or， and），第一层有5个节点，最后一层只有一个节点，问最后运算的结果为1的运算方式有多少种？第一层的输入已经确定。
思路：一共10次运算，每次3个符号，时间复杂度为O(3 ^ 10)，直接dfs按行暴力，行满后换层，到最后一层是结果。
总结：记得之前比赛的时候，是程序跑了好多次，每跑一次存储一次中间结果，一直到最后一层。只能说之前做题太少了，不懂dfs的优雅。
array<int, 5> d{5, 4, 3, 2, 1};
void solve(){
// vector<array<int, 5>> a(5);
// a[0] = {1, 0, 1, 0, 1};
// long long ans = 0;
// function<void(int, int)> dfs = [&](int x, int y){
// if (x == 5){
// ans += (a[4][0] == 1);
// return;
// }
// if (y == d[x]){
// dfs(x + 1, 0);
// }
// else{
// a[x][y] = a[x - 1][y] ^ a[x - 1][y + 1];
// dfs(x, y + 1);
// a[x][y] = a[x - 1][y] & a[x - 1][y + 1];
// dfs(x, y + 1);
// a[x][y] = a[x - 1][y] | a[x - 1][y + 1];
// dfs(x, y + 1);
// }
// };
// dfs(1, 0);
// cout <<ans << '\n';
cout << 30528 << '\n';
}
C 翻转
题意：给定长度为n的字符串s和t，问s最少多少次操作可以变成t。如果s中存在101,010,则可以进行变换：111, 000。
思路：考虑贪心策略，首先如果首尾不相等肯定不行，然后一次遍历，如果当前某个节点需要变换，但是跟后面的相等不能变换，那么就无解了，因为后面跟当前相等，后面也不能变换。 如果跟前面相等，那么也无解了，因为如果前面没变过，那么直接无解。 如果前面变过，那么当前如果先变，前面就没法变了。
总结：贪心的算法很简单，但是正确性的证明确实需要时间，下次可以先把代码交上去，如果时间充裕再来证明正确性。
void solve(){
string s, t;
cin >> t >> s;
if(s[0] != t[0] || s.back() != t.back()){
cout << "-1\n";
return;
}
int ans = 0;
int n = int(s.size());
for (int i = 1; i < n - 1; ++i){
if (s[i] != t[i] && s[i - 1] != s[i] && s[i + 1] != s[i]){
ans ++;
}
else if (s[i] != t[i]){
cout << -1 << '\n';
return;
}
}
cout << ans << '\n';
}
D 阶乘的和
题意：n个数，问能满足对每个数的阶乘求和后，最大的满足条件的m是多少？m!必须是n个数求和后的因子。
思路：首先，m一定是所有的数里面最小的数的因子，因为每个数都包含了最小的数的阶乘。那么考虑m + 1呢？如果n个数里面为m的数量，刚好可以被m+1整除，那么若干个m的阶乘的和，就可以转换为若干个m+1的阶乘的和。 比如6个2的阶乘是2个3的阶乘。
总结：涉及到数学推导，需要一步一步分析。。这种类型见的少。
void solve(){
int n;
cin >> n;
map<int, int> mapp;
for (int i = 0; i < n; ++i){
int t;
cin >> t;
mapp[t] ++;
}
int ans = 1;
for (auto&[x, y] : mapp){
if (y % (x + 1) == 0){
if (mapp.count(x + 1)){
mapp[x + 1] += (y / (x + 1));
}
else {
mapp[x + 1] = (y / (x + 1));
}
}
else{
ans = x;
break;
}
}
cout << ans << '\n';
}
E 公因数匹配
题意：n个数，gcd(a[i], a[j]) 大于1的最小的有序对i和j。
思路：暴力骗分gcd几行代码搞定。 或者O(n)*log(n)的暴力质因子分解，使用map记录上一次该质因子出现的位置。在所有有序对中找出最小的一个。为了提高效率，使用欧拉筛先筛出质因子，降低质因子分解的时间复杂度。
总结：没注意第一个找到的有序对可能不是最小的有序对。没注意对所有有序对进行存储并排序的算法可能会MLE。经过分析，先欧拉筛再分解的时间复杂度可能接近O(n)级别，与O(n * sqrt(n))比大幅降低。 特别是如果在数很大的情况下，不能使用暴力分解。
这里欧拉筛的代码写错了，如果当前的i是prime的倍数的时候，在记录完当前的i * prime就该break了，因为再往下就不是最小质因子推出来的合数了。比如i = 4, prime = 2,如果再往下那么就是4 * 3 = 12，但是12应该由它的最小质因子2 * 6来标记。
bitset<10000000> bs;
vector<int> prime_values;
void sievePrimes(){
bs.set();
bs[0] = bs[1] = 0;
for (int i = 2; i <= 1e6; ++i){
if (bs[i]){
prime_values.push_back(i);
}
for (const auto& prime : prime_values){
if (1ll * prime * i > 1e6){
break;
}
bs[prime * i] = 0;
}
}
}
inline bool changeMin(pair<int, int>& a, pair<int, int> b) {
if (b.first < a.first){
return a = b, true;
}
else if (a.first == b.first && b.second < a.second){
return a = b, true;
}
return false;
}
void solve(){
sievePrimes();
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i){
cin >> a[i];
}
map<int, int> mapp;
//vector<pair<int, int>> ans;
pair<int, int> ans{1e9, 1e9};
for (int i = 0; i < n; ++i){
for (const auto& prime : prime_values){
if (1ll * prime * prime > a[i]){
break;
}
if (a[i] % prime == 0){
if (mapp.count(prime)){
// ans.push_back({mapp[prime], i});
changeMin(ans, {mapp[prime], i});
}
else{
mapp[prime] = i;
}
}
while (a[i] % prime == 0){
a[i] /= prime;
}
}
if (a[i] > 1){
if (mapp.count(a[i])){
//ans.push_back({mapp[a[i]], i});
changeMin(ans, {mapp[a[i]], i});
}
else{
mapp[a[i]] = i;
}
}
}
// sort(ans.begin(), ans.end(), [&](pair<int, int>& a, pair<int, int>& b){
// return a.first != b.first ? a.first < b.first : a.second < b.second;
// });
cout << ans.first + 1 << " " << ans.second + 1 << '\n';
}
F 奇怪的数
题意：给定n和m，求奇数位上为奇数，偶数位上为偶数，且连续5位数的和不超过m的数有多少个。
思路：数位dp？感觉不太像，数位dp的n一般都是十几。 可以用递推，记录后4位的方案数，推出新的后4位的方案数。
总结：加了剪枝，细节压缩到极致，最后的时间复杂度是pow(5, 5) * n = 6e8，最后4个点TLE过不去。暂时写不出更好的算法，先贴上去。
long long dp[2][11][11][11][11];
vector<array<int, 5>> nums{{0, 2, 4, 6, 8}, {1, 3, 5, 7, 9}};
constexpr int mod = 998244353;
void solve(){
int n, m;
cin >> n >> m;
memset(dp, 0ll, sizeof(dp));
for (int a = 0; a < 5; ++a){
for (int b = 0; b < 5; ++b){
for (int c = 0; c < 5; ++c){
for (int d = 0; d < 5; ++d){
for (int e = 0; e < 5; ++e){
if (nums[1][a] + nums[0][b] + nums[1][c] + nums[0][d] + nums[1][e] <= m){
dp[0][nums[0][b]][nums[1][c]][nums[0][d]][nums[1][e]] ++;
}
}
}
}
}
}
long long ans = 0;
int cur = 1;
for (int i = 6; i <= n; ++i){
int parity = (i & 1);
int sum = 0;
for (auto& a : nums[parity]){
sum += a;
for (auto& b : nums[!parity]){
sum += b;
for (auto& c : nums[parity]){
sum += c;
for (auto& d : nums[!parity]){
sum += d;
for (auto& e : nums[parity]){
if (sum + e <= m){
dp[cur][b][c][d][e] += dp[cur ^ 1][a][b][c][d];
dp[cur][b][c][d][e] %= mod;
}
}
}
}
}
}
cur ^= 1;
memset(dp[cur], 0ll, sizeof(dp[cur]));
}
int parity = (n & 1);
for (auto& b : nums[!parity]){
for (auto& c : nums[parity]){
for (auto& d : nums[!parity]){
for (auto& e : nums[parity]){
ans += dp[cur ^ 1][b][c][d][e];
ans %= mod;
}
}
}
}
cout << ans << '\n';
}
//慢慢补题
标签：prime,14,int,C++,++,mapp,ans,省赛,first From： https://www.cnblogs.com/yxcblogs/p/18107730