noip2023+ 模拟二

非常好模拟，爱来自东辰。

A. 基于 1 的算术（add）

题目简介

设，给定，现在有一个数初始为，若将加减的代价为，求出将变成的最小代价。

数据范围：

首先不考虑减操作，那么这是一个类十进制拆分，但这种方案显然不一定最优。

具体来讲，对于，我们可以是，代价，但我们同样可以写成，代价。

具体来讲，如果现在我们涉及了一个操作是，直接加的代价是，而我们调整后可以将其代价转化为，容易发现这个转移无序且不独立，所以不怎么好转移。

题解考虑从高位到低位贪心，设对于第位需要使用个，使得，直接设，那么只需要考虑：

减去个；
减去个。

然后我们用拼出一个即可。

然后发现一共就那么多种选择，所以直接即可，时间复杂度。

titie:AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char c){ putchar(c); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>=y?x=y,1:0; }
template<class T>
inline T abs(T x){ return x<0?-x:x; }
const int MAXN=1e3+10;
ll N;
std::vector<ll>vec;
ll Dfs(int pos,ll n)
{
	if(pos<0) return 0;
	ll l=Dfs(pos-1,n%vec[pos])+(n/vec[pos])*(pos+1);
	ll r=Dfs(pos-1,abs(n%vec[pos]-vec[pos])%vec[pos])+(n/vec[pos]+(n%vec[pos]!=0))*(pos+1);
	return std::min(l,r);
}
int main()
{
	freopen("add.in","r",stdin);
	freopen("add.out","w",stdout);
	read(N);
	vec.push_back(1);
	for(int i=1;i<=16;++i) vec.push_back(vec.back()*10+1);
	write(Dfs(16,N));
	return 0;
}
/*

*/

B. 逃离（car）

题目简介

有一根的数轴，其中有很多个方块，第个方块占地（这意味着可能存在的情况），有一个向右匀速运动的初速度。

在一定时间内，如果方块满足了，那么两个方块会合并，会变成。

现在你有次机会，可以选择一个方块使其速度加（同一个方块可以被多次选择），最小化所有方块满足的时间。

小数点精确位。

数据范围：

考虑一手，那么我们不需要考虑加速的问题，直接算答案。

显然最后一辆车是决定答案的关键（我们设其为按照位置排好序的第辆车），

那么我们可以将前面的车的终点向后移，具体来讲，对于第辆车，其对答案贡献当且仅当，也就是它需要给后面的车留下空间越过。

每辆车都需要满足上面的约束，才能保证保证最后一辆车离开桥时没有车辆重叠，进一步地，我们发现，如果后车追赶上了前车，那么它的速度将变的和前车相同，此时，后车和前车将同时到达上述条件约束的位置，在此过程中，后车发生了速度改变，但前车始终保持匀速！

所以，实际上，我们不需要考虑接轨之后的变速问题，只需要对取即可。

时间复杂度，还可以通过的那个的。

基于部分分改造的做法官方题解

事实上，这个答案连续且单调，意味着如果合法，那么对于肯定都合法。

所以我们值域二分，用上述方法判断加速的次数是否，也就是通过时间算速度即可。

时间复杂度。但是好像爆精度了，有一个点过不去。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x*=t?-1:1;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char c){ putchar(c); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Int=__int128_t;
using Pir=std::pair<double,double>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=3e5+10;
const int S=500000;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const long double eps=1e-6;
int N,M,K;
Int T;
struct Car
{
	Int l,r,v;
	bool operator<(const Car &x) const { return l<x.l; }
}Cr[MAXN];
Int Len[MAXN];
inline bool check(double x)
{
	int cnt=0;
	for(int i=1;i<=N;++i)
	{
		long double nxtv=(long double)1.0*Len[i]/x;
		cnt+=std::ceil((long double)1.0*std::max((long double)0,nxtv-Cr[i].v)/K);
	}
	return cnt<=M;
}
int main()
{
	// freopen("car.in","r",stdin);
	// freopen("car.out","w",stdout);
	read(N,T,M,K);T*=S;K*=S;
	for(int i=1;i<=N;++i) read(Cr[i].l,Cr[i].r,Cr[i].v),Cr[i].l*=S,Cr[i].r*=S,Cr[i].v*=S;
	std::sort(Cr+1,Cr+N+1);
	Int sum=0;
	long double l=0,r=0;
	for(int i=1;i<=N;++i)
	{
		Len[i]=T+sum-Cr[i].l;
		sum+=Cr[i].r-Cr[i].l;
		checkMax(r,(long double)1.0*Len[i]/Cr[i].v);
	}
	while(r-l>eps)
	{
		long double mid=(l+r)/2;
		if(check(mid)) r=mid-eps;
		else l=mid+eps;
	}
	printf("%.3Lf",l+0.0000625);
	return 0;
}
/*

*/

后面那个 +0.0000625 是面向数据编程。

我们可以知道是哪一辆车取了作为答案上界，所以当时，我们只可能修改这一辆车。更新之后再求一遍答案即可。

然后扩展到很大的情况，这个更新以及加速，所以我们有一个的做法，现在考虑优化。

那么我们直接用堆维护，开一个动态的 std::priority_queue 即可。时间复杂度。

出题人代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
const int N = 3e5+5;
int n,t,m,k;
// 结构体，记录车辆信息
struct node
{
	/*
	l:题目中的l
	len：车辆长度
	v:车辆初始速度
	*/
	int l,len,v,s;
	double tim;
	// 为堆重载小于运算符，默认大根堆，将用时最长的放在堆顶
	friend bool operator <(node x,node y){return x.tim < y.tim;}
}a[N];
priority_queue<node> q;
//定义排序比较规则，按照车辆位置排序
bool cmp(node x,node y){return x.l < y.l;}
//快速读入函数
inline int rd()
{
	char c;int f = 1;
	while(!isdigit(c = getchar()))if(c=='-')f = -1;
	int x = c-'0';
	while(isdigit(c = getchar()))x = x*10+(c^48);
	return x*f;
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	n = rd();t = rd();m = rd();k = rd();
	for(int i = 1;i <= n;i++)
	{
		int l = rd(),r = rd(),v = rd();
		a[i] = {l,r-l,v};
	}
	sort(a+1,a+n+1,cmp);
	int sum = 0;
	for(int i = 1;i <= n;i++)
	{
		//计算每辆车的约束条件
		a[i].s = t+sum-a[i].l;a[i].tim = a[i].s*1.0/a[i].v;
		q.push(a[i]);sum += a[i].len;
	}
	//使用加速器，利用优先队列辅助运算
	while(m--)
	{
		node now = q.top();q.pop();
		//注意整型变量参与浮点运算时的细节
		now.v += k;now.tim = now.s*1.0/now.v;
		q.push(now);
	}
	//此时所有车满足约束的最长用时即为答案
	printf("%.3f",q.top().tim);
	return 0;
}

C. 南斯拉夫（yugo）

不改，看出题人怎么说。

D. 数数（count）

题目简介

给定一个长度为的序列和，求出所有有序数对满足：

$a_i^2+a_i+a_j^2\equiv a_i\cdot a_j\pmod p$

数据范围：，且是质数。

非常好的诈骗题。

考虑拆分式子，受到做法的鉴，所以我们不考虑下标，直接考虑值。也就是哈希之后再计算。

$a_i^2+a_i+a_j^2\equiv a_i\times a_j\pmod p$

我们设，那么有：

$\begin{align} (x-1)^2+(x-1)+y^2&\equiv\nonumber(x-1)y\pmod p\\ x^2-x+y^2&\equiv\nonumber xy-y\\ x^2-xy+y^2&\equiv\nonumber x-y\\ \end{align}$

式子两侧同时乘以，因为有，所以。

$\begin{align} x^3+y^3&\equiv\nonumber x^2-y^2\pmod p\\ x^3-x^2&\equiv\nonumber -(y^3+y^2)\pmod p \end{align}$

所以我们用两个哈希分别维护和的值就可以了。

时间复杂度。

AC Code

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
int N,P,a[MAXN];
std::map<ll,ll>HashI,HashJ;
ll ans;
int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	read(N,P);
	for(int i=1;i<=N;++i)
	{
		ll x;read(x);a[i]=x;
		ll nxt2=(-x*x%P*(x+1)%P+P)%P;
		ll nxt1=(x+1)*(x+1)%P*x%P;
		// write(nxt1,' ',nxt2,'\n');
		ans+=HashI[nxt1]+HashJ[nxt2];
		++HashI[nxt2],++HashJ[nxt1];
	}
	write(ans);
	return 0;
}
/*

*/

在原式中同时乘以也可以达到同样的效果。