2025年7月28日训练日志

1952. 三除数 - 力扣（LeetCode）

方法一：直接从1遍历到sqrt(n)；

方法二：找出质因子，个数为2且总和为3的就是，因为要保证只有三个因数，其中一个数是1，另一个数是它本身，那剩下那个只能是质因子。

class Solution {
public:bool isThree(int n) {int num = n;vector<int>a(10005,0);a[1]++;for(int i=2;i*i<=num;i++){while(num%i==0){a[i]++;num/=i;}}if(num > 1) a[num]++;int cnt = 0,sum = 0;for(int i=1;i<=n;i++){if(a[i]){sum+=a[i];cnt++;}}if(cnt == 2 && sum == 3) return 1;else return 0;}
};

914. 卡牌分组 - 力扣（LeetCode）

 对每个数的个数计算最大公约数，如果最后结果大于等于2的话就可以分组

class Solution {int a[10005];
public:bool hasGroupsSizeX(vector<int>& deck) {for(int num : deck){a[num]++;}int x = -1;for(int i=0;i<=10000;i++){if(a[i]){if(x==-1){x = a[i];}else{x = __gcd(x,a[i]);}}}if(x>=2) return true;else return false;}
};

Problem - 2126D - Codeforces

贪心，按左区间排序，因为题目确保了re>=l，然后依次遍历求最大值 

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;void solve() {int n, k;cin >> n >> k;vector<pair<int, pair<int, int>>> a(n);for (int i = 0; i < n; i++) {int l, r, re;cin >> l >> r >> re;a[i] = {l, {r, re}};}sort(a.begin(), a.end());int cur = k;for(int i=0;i<n;i++){if(a[i].first > cur) break;cur = max(cur,a[i].second.second);}cout<<cur<<endl;
}signed main() {FASTint t = 1;cin >> t;while (t--)solve();return 0;
}

 Problem - 2126C - Codeforces

因为每次都要往更高的楼层传送，因此直接用set来存数据，然后进行遍历模拟一遍就可以了 

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define FAST ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int MOD = 1e9+7;
const int mod = 998244353;
using namespace std;void solve(){int n,k;cin>>n>>k;set<int>st;int nh;for(int i=0;i<n;i++){int h; cin>>h;if(i == k-1) nh = h;//现在的高度st.insert(h);}int t = 1;//水位，初始水位为1for(auto h : st){if(h > nh){//如果高度大于他现在的高度int cz = h - nh;//高度差if(t + cz <= nh + 1){//如果水位加上高度差值小于等于当前的高度+1的话nh = h;t+=cz;}else{cout<<"NO"<<endl;return ;}}}cout<<"YES"<<endl;
}signed main() {FASTint t = 1;cin>>t;while(t--)solve();return 0;
}

 Problem - 2124B - Codeforces

 做操作的地方只可能从第一个开始或者从第二个开始，因此只需要分别算出求最小值就可以

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define FAST ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
using namespace std;void solve(){int n; cin>>n;int a[n];for(int i=0;i<n;i++) cin>>a[i];int ans = min(a[0]*2,a[0] + a[1]);cout<<ans<<endl;
}signed main() {FASTint t = 1;cin>>t;while(t--)solve();return 0;
}