XP05-01 DAY03
2025-08-14 22:05:54
发布于：浙江
觉得自己不应该来XP05....我学完XP04就应该滚回家了。
今天需要做一些补题。
详细：
Emiya家的饭
略：
最佳拍照地点
射箭比赛
跳题
题目：最佳拍照地点链接描述
这个最佳拍照地点，说实话我觉得不应该错啊。
毕竟我在XP04的时候已经遇到过一次了。
已经超过全班99%的人。
但是因为XP04的时候，没有好好听讲，导致忘记开，下次要吸取教训，牢记不开见祖宗。
但是开了ll后，只拿了，主要是因为超时。
所以尝试使用某些二分，寻找最接近的。
神秘的错误代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll k[N];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>k[i];
}
for(int i=1;i<=m;i++){
ll a,b,c;
cin>>a>>b>>c;
int idx1=upper_bound(k+1,k+1+n,b)-k;
if(idx1>n){
idx1=n;
}
int idx=(abs(k[idx1]-b)>abs(k[idx1-1]-b))?idx1-1:idx1;
if((b-k[idx])*(b-k[idx])-4*a*c<0){
cout<<"YES\n"<<k[idx]<<'\n';
}else cout<<"NO\n";
}
}
int main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
这是正确的解法：（错因：二分没有排序）
sort(k+1,k+1+n);
再来看一下神秘的跳题：链接描述
从理论上而言，这道题目的思路其实很难想。
不过这类题目遇到过一次后，就会简单很多。
观察发现，做完/放弃这道题目后，它的下一题（一般）并不是直接可以去的。
或者说它们（一般）不是相邻的。
可以联想到（第一次基本不可能直接联想到，这种思路诡异的题目都是见过一次后，下一次再见到才有思路的）图，然后因为发现从A题想要跳到B题，是需要“代价”的，代价就是题目A的分数。
简单来说，放弃题目A就可以获得题目B的分数。
那么图中就会多出一条连接点A和点B的，权值为的单向边。
而且对于点A来说，它还与的点有着一条权值为的单向边。
（因为做出题目A后，可以去选择编号小于A的题目做）。
最后一道题目的位置可能在任意地点。
然后可以想一想图上有关的，求消耗最小（题目得分最大）的算法。
无负权边的那种。
Dijkstra.
好的，那么到这基本就通了，可以开始写代码了。
然后有一个神秘小代码：
typedef pair<ll,ll>pll;
一点用都没有。
正确代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
ll a[N];
ll b[N];
ll dis[N];
bool ok[N];
struct Node{
ll z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>q;
vector<Node>v[N];
ll pre[N];
//typedef pair<ll,ll>pll;
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
//初始化。
v[i].clear();
dis[i]=1e18;
ok[i]=false;
}
for(int i=1;i<=n;i++)cin>>a[i],pre[i]=pre[i-1]+a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++){
v[i].push_back({i-1,0});
v[i].push_back({b[i],a[i]});
}
//Dij
dis[1]=0;
//全部从第一题开始。
// priority_queue<pll,vector<pll>,greater<pll>>q;
//小根堆
q.push({1,0});
//路程，地点。
while(!q.empty()){
ll now=q.top().z;
q.pop();
if(ok[now])continue;
ok[now]=1;
for(int i=0;i<v[now].size();i++){
int to=v[now][i].z;
int len=v[now][i].q;
if(dis[to]>dis[now]+len){
dis[to]=dis[now]+len;
q.push({to,dis[to]});
//dis[to]=dis[now]+len;
}
}
}
ll mx=-2e18;
for(int i=1;i<=n;i++){
mx=max(mx,pre[i]-dis[i]);
}
cout<<mx<<endl;
}
int main(){
int t;
cin>>t;
while(t--)solve();
return 0;
}
然后就是神秘的射箭比赛：链接描述
首先，观察测试数据范围可以发现，你可以通过一些神秘小暴力拿到20。
对于测试点三-六，你也可以通过某些神秘的小函数进行一些高级的暴力。
接下来的分数就需要一些小智慧了。
进行神秘的数字哈希+异或前缀和+神秘STL+神秘随机数（不知道是不是这么叫的，名字都是我自己取的）。
然后，你需要认识一个神秘随机数生成器：茅台19937：
mt19937_64 rng(time(0));
至于它到底是如何使用的，直接看一下正确代码中的使用方式即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ull;
const int N=2e5+5;
ull a[N];//击中每个目标的得分
mt19937_64 rng(time(0));
ull pre[N];
void solve(){
int n,q;
cin>>n>>q;
map<ull,ull>mp;
for(int i=1;i<=n;i++){
cin>>a[i];
if(!mp.count(a[i])){
mp[a[i]]=rng();
}
pre[i]=pre[i-1]^mp[a[i]];
}
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
if(pre[r]^pre[l-1])cout<<"NO\n";
else cout<<"YES\n";
}
}
int main(){
int T;
cin>>T;
while(T--)solve();
}
然后，这边对这道题目为什么这么写进行一点点解释：
如果说，想要让这个警长平局的话（不可能赢），需要满足条件：
这个区间内所有的数字数量都是偶数。
关于判断偶数，可以进行联想：想到异或。
想同为0，先异为1。
所以说，如果在某个区间内的数全部都是偶数，那么它们异或起来就是0.
有帮助，赞一个