6.18总结

省赛排位赛2：

省赛排名赛2 - Virtual Judge

思路：

设两个方程直接解出来就行

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m; 
int main()
{int n, m;int ans1, ans2;cin >> n >> m;ans1 = n - (-3 + sqrt(3 * 3 + 4 * 2 * (n + m))) / 2;ans2 = n - (-3 - sqrt(3 * 3 + 4 * 2 * (n + m))) / 2;if (ans1 <= n && ans2 >= 0) cout << ans1;else cout << ans2;
}

省赛排名赛2 - Virtual Judge
代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
int main()
{int t;cin >> t;while (t--){cin >> n;ll ans = 0;ll nn = n;ll i = 1;while (nn){ans += n / i;i <<= 1ll;nn >>= 1ll;}cout << ans << endl;}return 0;
}

省赛排名赛2 - Virtual Judge

代码：

#include<bits/stdc++.h>
using namespace std;
int a[10000005];
int main()
{int n, p;cin >> n >> p;for (int i = 1; i <= n; i++){cin >> a[i];a[i] += a[i - 1];}int ans = 0;for (int i = 1; i < n; i++){ans = max(ans, (a[i] % p + (a[n] - a[i]) % p));}cout << ans << endl;return 0;
}

省赛排名赛2 - Virtual Judge

思路：

需要得到每个(x,y)下的最大公约数，再找出一定的规律

代码：

#include<bits/stdc++.h>
using namespace std;
long long t, a, b, c, n, ca, cb, cc;
int gcd(int x, int y)
{if (x < y)swap(x, y);if (x % y)return gcd(y, x % y);return y;
}
int main()
{cin >> t;while (t--){cin >> n >> a >> b;c = a * b / gcd(a, b);ca = n / a, cb = n / b, cc = n / c;ca -= cc, cb -= cc;cout << (n + n - ca + 1) * ca / 2 - (1 + cb) * cb / 2 << endl;}return 0;
}

省赛排名赛2 - Virtual Judge

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1000010], n;
int main() {cin >> n;for (int i = 1; i <= n; i++)cin>>a[i], a[i] ^= a[i - 1];ll ans = 0;for (int i = 0, x = (1 << i); i < 32; i++, x <<= 1){int cnt = 0;for (int j = 1; j <= n; j++)if ((a[j] >> i) & 1) cnt++;ans += 1LL * cnt * (n + 1 - cnt) * x;}cout << ans << endl;return 0;
}

省赛排名赛2 - Virtual Judge

思路：

给定一个能达到数据范围的斐波拉契数组，包含所有数据范围内的斐波拉契数，再进行几个特判

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[100];
string check(ll n, ll x, ll y)
{if (x == 1 && y == 1){return "YES";}if (y <= f[n] && y > f[n - 1]){return "NO";}if (y > f[n]){y = y - f[n];}return check(n - 1, y, x);
}
int main()
{ll t, n, x, y;f[0] = 1;f[1] = 1;for (int i = 2; i <= 45; i++)f[i] = f[i - 1] + f[i - 2];cin >> t;while (t--){cin >> n >> x >> y;cout << check(n, x, y) << endl;;}return 0;
}

省赛排名赛2 - Virtual Judge

思路：

01背包问题，就题目改了一下，直接用模板就行

代码：

#include<bits/stdc++.h>
using namespace std;
int h, t, n, a[401], z[401], l[501], dp[401][401];
int main() {cin >> h >> t >> n;for (int i = 1; i <= n; i++){cin >> a[i] >> z[i] >> l[i];}for (int i = 1; i <= n; i++){for (int j = h; j >= a[i]; j--){for (int k = t; k >= z[i]; k--){dp[j][k] = max(dp[j][k], dp[j - a[i]][k - z[i]] + l[i]);}}}cout << dp[h][t];return 0;
}