有限小数
证明过程很巧妙,尽在Y总视频中。链接
看到有一个很好的题解,推荐一下。链接
#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int t; scanf("%lld", &t);
while(t --)
{
int p, q, b; scanf("%lld %lld %lld", &p, &q, &b);
int d = gcd(p, q);
q /= d;
while(q > 1){
int d = gcd(q, b);
if(d == 1) break;
while(q % d == 0) q /= d;
}
if(q > 1) puts("NO");
else puts("YES");
}
}
耍杂技的牛
贪心思想 好题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 5;
PII a[N];
int main()
{
int n;
scanf("%d", &n);z
for(int i = 0; i < n; i ++ )
{
int x, y;
scanf("%d %d", &x, &y);
a[i].first = x + y;
a[i].second = y;
}
sort(a, a + n);
ll res = -1e18, sum = 0;
for(int i = 0; i < n; i ++ )
{
sum -= a[i].second;
res = max(res, sum);
sum += a[i].first;
}
cout << res << endl;
return 0;
}
聪明的质检员
二分+前缀和,搞定。视频
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, m;
LL S;
int w[N], v[N];
int l[N], r[N];
int cnt[N];
LL sum[N];
LL get(int W)
{
for (int i = 1; i <= n; i ++ )
if (w[i] >= W)
{
sum[i] = sum[i - 1] + v[i];
cnt[i] = cnt[i - 1] + 1;
}
else
{
sum[i] = sum[i - 1];
cnt[i] = cnt[i - 1];
}
LL res = 0;
for (int i = 0; i < m; i ++ ) res += (cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
return res;
}
int main()
{
scanf("%d%d%lld", &n, &m, &S);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &w[i], &v[i]);
for (int i = 0; i < m; i ++ ) scanf("%d%d", &l[i], &r[i]);
int l = 0, r = 1e6 + 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (get(mid) >= S) l = mid;
else r = mid - 1;
}
printf("%lld\n", min(abs(get(r) - S), abs(S - get(r + 1))));
return 0;
}
作者:yxc
链接:https://www.acwing.com/solution/content/3045/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
借教室
用一个数组,表示每天要用的教室个数。用、二分差分来优化,搞定。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];
bool check(int k)
{
for (int i = 1; i <= n; i ++ ) b[i] = r[i];
for (int i = 1; i <= k; i ++ )
{
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
}
LL res = 0;
for (int i = 1; i <= n; i ++ )
{
res += b[i];
if (res < 0) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &r[i]);
for (int i = n; i; i -- ) r[i] -= r[i - 1];
for (int i = 1; i <= m; i ++ ) scanf("%d%d%d", &d[i], &s[i], &t[i]);
int l = 1, r = m;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (check(r))
{
puts("-1");
printf("%d\n", r);
}
else puts("0");
return 0;
}
作者:yxc
链接:https://www.acwing.com/solution/content/3045/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。