C - 1, 2, 3 - Decomposition
给定 \(n\)，找到最小的 \(k\) 使得存在 \(\{a_k\}\) 满足：
-
\(a_i\) 之和为 \(n\)。
-
\(a_i\) 在十进制下的每个数位均为 \(1,2,3\)。
\(T\le 1000\)，\(1\le n\le 10^{18}\)。
我怎么做出来这个题的？
我们考虑对每个答案 \(ans\) 检查 \(\operatorname{check}(n,ans)\)，表示能不能用 \(ans\) 个数组出 \(n\)。
我们来处理 \(\operatorname{check}(x,m)\)。
首先比较显然的：若 \(x<m\)，不合法；若 \(x\in[m,3m]\)，合法，我们用若干 \(1,2,3\) 组合即可。
这之后，然后就会有位数 \(>1\) 的数。易知当前最低位的数位之和模 \(10\) 一定为 \(x\bmod 10\)，我们枚举 \(i=10k+(x\bmod 10)\)，\(i\in[x\bmod 10+10\times[x\bmod 10<m],3m]\)（这个范围是显然的），枚举位数 \(>1\) 的数的个数 \(j\)，检查 \(\operatorname{check}(\dfrac{x-i}{10},j)\)，若存在任意一个合法，\(\operatorname{check}(x,m)\) 就是合法的。
跑的非常快。实际上，\(ans\) 的最大值是 \(5\)，这为暴力算法提供了保证。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
ll n;
bool check(ll x,int m){
if(x<m)return false;
if(x>=m&&x<=3*m)return true;
bool fl=false;
for(int j=0;j<=m;j++)
for(int i=x%10+(x%10<m?10:0);i<=3*m;i+=10)
if(check((x-i)/10,j))return true;
return false;
}
void solve(){
cin>>n;int ans;
for(ans=1;!check(n,ans);ans++);
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}
D - Inc, Dec - Decomposition
给出 \(\{a_n\}\)，考虑 \(\{b_n\}\) 和 \(\{c_n\}\) 满足：
-
\(\forall i\in[1,n]\)，\(a_i=b_i+c_i\)。
-
\(b_i\) 单调不降。
-
\(c_i\) 单调不升。
试最小化 \(\sum_{i=1}^{n} (|b_i|+|c_i|)\)。
\(n\le 2\times 10^5\)，\(-10^8\le a_i\le 10^8\)。
贪心结论：若 \(a_i>a_{i+1}\)，有 \(b_{i+1}=b_i,c_{i+1}=c_i+a_{i+1}-a_i\)。否则 \(c_{i+1}=c_i,b_{i+1}=b_i+a_{i+1}-a_i\)。
这似乎是十分显然的。
考虑令 \(b_1=x,c_1=a_1-x\)，接着我们可以将所有 \(b_i\) 和 \(c_i\) 用 \(x\) 表示出来。
然后呢？你发现就是一堆点到某个点的距离和的最小值，我们取中位数即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 200010
using namespace std;
ll read(){
ll x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n;ll a[N];
ll B,C,s[N<<1];int m;
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
B=a[1],C=0;
s[++m]=B,s[++m]=C;
for(int i=1;i<n;i++){
ll x=a[i+1]-a[i];
(x>=0)?B+=x:C-=x;
s[++m]=B,s[++m]=C;
}
sort(s+1,s+1+m);
ll ans=0;
for(int i=1;i<=m;i++)
ans+=abs(s[i]-s[n]);
printf("%lld\n",ans);
return 0;
}
E - Training
给出 \(n,A_X,B_X,A_Y,B_Y\)，求：
\[\sum_{i=1}^{n}[A_X+\lfloor\frac{i}{B_X}\rfloor=A_Y+\lfloor\frac{i}{B_Y}\rfloor] \]\(T\le 2\times 10^5\)，\(1\le n\le 10^9\)，\(1\le A_X,B_X,A_Y,B_Y\le 10^6\)。
假设 \(B_X\le B_Y\)。
设 \(f(x)=A_X+\frac{x}{B_X}\)，\(g(x)=A_Y+\frac{x}{B_Y}\)，\(F(x)=\lfloor f(x)\rfloor\)，\(G(x)=\lfloor g(x)\rfloor\)，条件即 \([F(x)=G(x)]\)。
\(B_X=B_Y\) 是简单的。然后我们考虑 \(f(x)-g(x)\) 这条斜率 \(>0\) 的直线。
若 \(F(x)=G(x)\) 显然有 \(f(x)-g(x)\in (-1,1)\)。那么：
-
\(f(x)-g(x)\in(-1,0]\)，\(F(x)-G(x)\in\{-1,0\}\)。
-
\(f(x)-g(x)\in(0,1]\)，\(F(x)-G(x)\in\{0,1\}\)。
我们只考虑第一种。
我们二分出 \(f(x)-g(x)\in(-1,0]\) 的区间 \([l,r]\)，然后你发现求 \(\displaystyle \sum_{i=l}^{r}F(x)-G(x)\) 就能算出 \(-k\) 了。这个东西你可以随便写个前缀和，闲的慌也能写类欧。
但是代码实现感觉好难写。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
ll f(ll a,ll b,ll c,ll n){
if(n<0)return 0;
if(!a||!n)return (n+1)*(b/c);
ll A=a/c,B=b/c;
if(A||B)return n*(n+1)/2*A+B*(n+1)+f(a%c,b%c,c,n);
ll M=(a*n+b)/c;
return M*n-f(c,c-b-1,a,M-1);
}
ll calc(ll a,ll b,ll c,ll l,ll r){
return f(a,b,c,r)-f(a,b,c,l-1);
}
ll n,a,b,c,d;
void solve(){
n=read(),a=read(),b=read(),c=read(),d=read();
if(b>d)swap(a,c),swap(b,d);
ll l=1,r=n,mid;
ll p1=-1,p2=n+1,p3=-1;
while(l<=r){
mid=(l+r)>>1;
if(mid*(d-b)>b*d*(c-a-1))r=mid-1,p1=mid;
else l=mid+1;
}
if(p1==-1)return puts("0"),void();
l=p1,r=n;
while(l<=r){
mid=(l+r)>>1;
if(mid*(d-b)>b*d*(c-a))r=mid-1,p2=mid;
else l=mid+1;
}
l=p2,r=n;
while(l<=r){
mid=(l+r)>>1;
if(mid*(d-b)<=b*d*(c-a+1))l=mid+1,p3=mid;
else r=mid-1;
}
if(p3==-1)p3=p2-1;
ll ans=0,k=calc(1,c*d,d,p1,p2-1)-calc(1,a*b,b,p1,p2-1);
ans+=p2-p1-k;
k=calc(1,a*b,b,p2,p3)-calc(1,c*d,d,p2,p3);
ans+=p3-p2+1-k;
printf("%lld\n",ans);
}
int main(){
int T=read();
while(T--)solve();
return 0;
}