• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[ARC123]Training

开发技术 开发技术 4小时前 1次浏览

[newcommanddivd[2]{leftlfloor{#1over #2}rightrfloor}
]

壹、题目描述 ¶

传送门 to Atcoder.

贰、题解 ¶

前言

坐在 (sf closestool) 旁边真的绝望了,当你正在做 (B) 时,祂过了 (C);当你看到 (C) 并发现自己不会时,祂过了 (D);当你看到 (D) 并发现自己不会时,你心中只剩下一句话:

夫哀莫大于心死,而人死亦次之。——庄子

然后我看到 (E),发现好像可以搞一搞,然后设计出一个算法,大概证明了一下复杂度可能在 (mathcal O(Tsqrt {max{B_x,B_y}})) 左右(不过证伪了),发现过掉了 😃

赛后 (sf closestool) 也尝试证明,并被我成功带偏,承认复杂度 “正确”。不过第二天早上祂给了我一个 (rm hack) 数据:

200000
1000000000
4 300000 1 299999

1000000000
4 300000 1 299999

1000000000
4 300000 1 299999

1000000000
4 300000 1 299999
...

1000000000
4 300000 1 299999

这样会跑满 (mathcal O(TN)),不过运气好确实也会碰上水数据,比如 (20210719)(A)(mathcal O(3^{20})) 随便跑,(mathcal O(n^{n-1})) 更是让我人傻了……但是可以学到正解的时候还是要钻研啊。

正文

题目让你求

[sum_{i=1}^N[A_X+divd{i}{B_X}=A_Y+divd{i}{B_Y}]
]

这里有一个虚假的做法:

我们可以猜想相交的段不会太多,并且有一个特点,跑得快的函数与跑得慢的函数相差为 (2) 后,两个函数将不会有交,所以,我们可以先使用二分找到跑得快的函数差 (1) 追上跑得慢的函数,然后使用类似分块(实际上要慢得多)的做法,暴力算这些段是否相交,然后就有了一个代码:

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

// #define NDEBUG
#include<cassert>

namespace Elaina{
    #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
    #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
    #define fi first
    #define se second
    #define mp(a, b) make_pair(a, b)
    #define Endl putchar('n')
    #define mmset(a, b) memset(a, b, sizeof a)
    // #define int long long
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    template<class T>inline T fab(T x){ return x<0? -x: x; }
    template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
    template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
    template<class T>inline T readin(T x){
        x=0; int f=0; char c;
        while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
        for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
        return f? -x: x;
    }
    template<class T>inline void writc(T x, char s='n'){
        static int fwri_sta[1005], fwri_ed=0;
        if(x<0) putchar('-'), x=-x;
        do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
        while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
        putchar(s);
    }
}
using namespace Elaina;

int n;
pii a, b;

inline int bisearch(){
	int l=1, r=n, mid, ret=1;
	while(l<=r){
		mid=(l+r)>>1;
		int va=a.fi+(mid/a.se), vb=b.fi+(mid/b.se);
		if(va<vb) r=mid-1;
		else if(va==vb) r=mid-1;
		else if(va==vb+1) ret=mid, r=mid-1;
		else l=mid+1;
	}
	return ret;
}

inline void solve(){
	n=readin(1);
	a.fi=readin(1), a.se=readin(1);
	b.fi=readin(1), b.se=readin(1);
	if(a.fi<b.fi || (a.fi==b.first && a.se<b.se)) swap(a, b);
	// the same
	if(a.fi==b.fi && a.se==b.se)
		return writc(n), void();
	// no crossing
	if(a.fi>b.fi && a.se<=b.se)
		return writc(0), void();
	// the gap is too large
	if(a.fi+(n/a.se)>b.fi+(n/b.se)+2)
		return writc(0), void();
	int l=bisearch(); // find the first position where b+1 == a
	int ans=0;
	for(int r; l<=n; l=r+1){
		r=min(((l/a.se)+1)*a.se, ((l/b.se)+1)*b.se)-1;
		r=min(r, n);
		if(a.fi+(l/a.se)==b.fi+(l/b.se))
			ans+=(r-l+1);
		else if(b.fi+(l/b.se)-(a.fi+(l/a.se))>2)
			break;
	}
	writc(ans);
}

signed main(){
	rep(_, 1, readin(1)) solve();
    return 0;
}

至于它为什么会被上面的数据卡,可以自己想一想原因。

至于官方做法,它也很玄学了,首先

[f(x)oversetDelta=A_X+{xover B_X} \
g(x)oversetDelta=A_Y+{xover B_Y}
]

然后我们再定义 (F(x)=leftlfloor f(x)rightrfloor,G(x)=leftlfloor g(x)rightrfloor),那么问题就变成了

[sum_{i=1}^N[F(i)=G(i)]
]

并且,我们不难发现,当 (F(x)=G(x)) 时,(f(x)-g(x)) 是接近 (0) 的,于是我们可以进行分类讨论:

  • (f(x)<g(x)-1) 时,(F(x)neq G(x))
  • (g(x)-1le f(x)<g(x)) 时,(F(x)in{G(x)-1,G(x)})(可能没有 (G(x)),下同);
  • (g(x)le f(x)<g(x)+1) 时,(F(x)in{G(x),G(x)+1})
  • (f(x)ge g(x)+1) 时,(F(x)neq G(x))

不难发现,只有两段可能存在 (F(x)=G(x)),我们可以只在这两段计算答案,此时我们成功将答案的范围缩小了许多。至于这两段的边界,由于 (f,g) 不涉及下取整,可以很轻易地使用简单不等式的运算解出来。

现在,考虑我们面临的问题是什么:

(xin [L,R)),并且两个函数满足 (F(x)in{G(x),G(x)+1},xin[L,R)),有多少个 (xin Zcap[L,R)) 满足 (F(x)=G(x))

题目有很好的转化:

[sum_{i=L}^{i<R}[F(i)=G(i)]Leftrightarrow left|sum_{i=L}^{i<R}F(i)-sum_{i=L}^{i<R}G(i)right|quadBig(F(i)in{G(i)-1,G(i)}Big)
]

对于另一种情况也是一样。并且绝对值里面的两个 (sum) 可以使用前缀和作差,那么我们最后要求的就是

[sum_{x=1}^{x<n}a+divd{x}{b}
]

至于这个,不用我多说了吧,这甚至可以 (Theta(1)) 计算,简单推式子就行了。

所以复杂度甚至可以达到 (mathcal O(T)).

叁、参考代码 ¶

咕咕咕......

肆、关键之处 ¶

合理缩小答案范围,而在此范围内有很好的性质,那么就可以加以利用了。


程序员灯塔
转载请注明原文链接:[ARC123]Training
喜欢 (0)