- gf25051 的博客
《咸鱼概要 · 娱乐》灌水
-
gf25051
LV 6
@
2026-4-30 13:54:13
待办：
拦截导弹all
合唱队列all
LIS all
5月19日花广：
http://13030104977.web3v.work/
P1983
P7972
格蕾丝的逃离题解
方法一
暴力搜索
我们分别枚举公主和革命军的速度
60分版本
#include <bits/stdc++.h>
using namespace std;
int d,l,n,a,b,cnt;
int v[500005];
int main() {
cin>>d>>l>>n;
for(int i=1; i<=n; i++) {
cin>>v[i];
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
int g=v[i];
int z=v[j];
if(g<=z){
continue;
}
if(d*z<l*(g-z)){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
但只要我们把int改为long long，就能拿80分
80分版本
#include <bits/stdc++.h>
using namespace std;
long long d,l,n,a,b,cnt;
int v[500005];
int main() {
cin>>d>>l>>n;
for(int i=1; i<=n; i++) {
cin>>v[i];
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
int g=v[i];
int z=v[j];
if(g<=z){
continue;
}
if(d*z<l*(g-z)){
cnt++;
}
}
}
cout<<cnt;
return 0;
}
再加一个sort排序优化一下
90分版本
#include <bits/stdc++.h>
using namespace std;
long long d,l,n,a,b,cnt;
int v[200005];
bool cmp(int x,int y) {
return x<y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>d>>l>>n;
for(int i=1; i<=n; i++) {
cin>>v[i];
}
sort(v+1,v+1+n,cmp);
for(int i=1; i<=n; i++) {
for(int j=1; j<i; j++) {
int g=v[i];
int z=v[j];
if(d*z<l*(g-z)) {
cnt++;
}
}
}
cout<<cnt;
return 0;
}
这就是暴力搜索的极限了
方法二
二分查找
查找第一个>=革命军追上公主的速度，剩余部分累加即可
100分版本
#include <bits/stdc++.h>
using namespace std;
long long d,l,n,a,b,cnt;
int v[200005];
bool cmp(int x,int y) {
return x<y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>d>>l>>n;
for(int i=0; i<n; i++) {
cin>>v[i];
}
sort(v,v+n,cmp);
for(int i=0; i<n; i++) {
int g=v[i];
int need=(g*(d+l))/l+1;
if(need<g+1){
need=g+1;
}
int erfen=lower_bound(v,v+n,need)-v;
cnt+=n-erfen;
}
cout<<cnt;
return 0;
}
冷知识
这道题DXD偷懒了，没有加特判，所以用拓扑排序做的只有80分，不信可以把代码拿去洛谷提交，在洛谷是可以AC的
https://www.bilibili.com/video/BV1S6DABJEmm?t=43.9
https://www.bilibili.com/video/BV138dnBUExF/?spm_id_from=333.337.search-card.all.click
https://www.bilibili.com/video/BV1HkwYzDEg1/?spm_id_from=333.337.search-card.all.click
#include <bits/stdc++.h>
using namespace std;
int n,k,di[10005],fa[10005];
struct xh{
int u,v,w;
}g[10005];
bool cmp(xh a,xh b){
return a.w<b.w;
}
void find(int x){
if(fa[x]!=x){
fa[x]=find(fa[x]);
}
return fa[x];
}
int main() {
cin>>n>>k;
for(int i=1;i<=k;i++){
cin>>di[i];
}
for(int i=1;i<=n;i++){
cin>>g[i].u>>g[i].v>>g[i].w;
}
sort(g+1,g+n+1,cmp);
return 0;
}
std::ostream& operator<<(std::ostream& os, __int128 n) {
if (n == 0) return os << '0';
std::string s;
bool negative = false;
if (n < 0) {
negative = true;
n = -n;
}
while (n > 0) {
s += '0' + (n % 10);
n /= 10;
}
if (negative) s += '-';
std::reverse(s.begin(), s.end());
return os << s;
}
std::istream& operator>>(std::istream& is, __int128& n) {
std::string s;
is >> s;
n = 0;
bool negative = false;
size_t start = 0;
if (s[0] == '-') {
negative = true;
start = 1;
}
for (size_t i = start; i < s.size(); ++i) {
n = n * 10 + (s[i] - '0');
}
if (negative) n = -n;
return is;
}