Noip模拟93 2021.11.9
这样的话我觉得我已经改完题了（逃）
所以在所有人都很颓废的情况下写一下题解
T1 NOIP2018
比较明显的二分，重点是考场上不会卡精度，再加上不会\(O(1)check\)，于是只拿到了\(40\)，苦苦
二分\(check\)可以\(O(1)\)，整一个关于\(x\)的二次函数计算最小值是否合法即可，\(x\)表示第一种货币换了几个
那么另一种货币换了\(mid-x\)个，列出等差数列求和公式然后爆蒜出一元二次不等式系数即可
注意特判超过边界的不合法情况，还挺多的，不过可以通过他给的大测试点调出来，自己看一下计算式的值即可
然后就是二分边界搞到\(\sqrt{x}\)即可，因为二次函数有\(x^2\)项所以最大值不会超过\(\sqrt{x}\)
money
#include
#define int __int128
using namespace std;
namespace AE86{
FILE *wsn;
auto read=[](){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
}using namespace AE86;
typedef long double D;
int q,a,b,c,d,x;
inline bool check(int mid){
D A=b+d;
D B=2*a-b-2*c-2*d*mid+d;
D C=2*c*mid+d*mid*mid-d*mid-2*x;
D X=floor(1.0*(-B)/(2*A)+0.5);
// write(A,' ');write(B,' ');write(C);write(X);
if(X<=mid&&X>=0) return A*X*X+B*X+C<=0;
else if(X>mid) return A*mid*mid+B*mid+C<=0;
else return C<=0;
}
auto solve=[](){
a=read();b=read();c=read();d=read();x=read();
if(a>x&&c>x) return puts("0"),void();
int l=1,r=2e9,ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
write(ans);
};
namespace WSN{
inline short main(){
wsn=freopen("money.in","r",stdin);
wsn=freopen("money.out","w",stdout);
q=read();while(q--)solve();
return 0;
}
}
signed main(){return WSN::main();}
T2 CSP2019
咕咕咕
T3 CSP2020
行吧，又改出来一个这个，但是考场上是肯定不可能想出来的
在值较小的时候数位\(dp\)，因为这个时候没有规律
值域大的时候发现最后答案一定是最后跟着一串\(9\)因为这个时候\(n^3\)和\(n^4\)的差距已经非常恐怖了
于是我们只需要找到把一串\(9\)里面的几个换成\(8\)，前面多加几个\(1\)可以凑出第\(n^4\)个就行
number
#include
#define int long long
using namespace std;
int n,mod,ans[1001],dp[1001][8001];
bool ok;
inline int dfs(int x,int rem,int rk,bool up){
if(0<=dp[x][rem]&&dp[x][rem]<=rk) return dp[x][rem];
if(!rem){if(!rk) ok=true;return dp[x][rem]=1;}
if(ok) return 0;
if(!x) return dp[x][rem]=0;
int sum=0,tmp=0;
for(int i=up;i<=min(9ll,rem);i++){
ans[x]=i;
tmp=dfs(x-1,rem-i,rk,0);
if(ok) return 0;
rk-=tmp; sum+=tmp;
}
return dp[x][rem]=sum;
}
auto solve_small=[](int x){
int as=0,lim=0,rk=x*x*x*x-1; ok=false;
while(!ok){
memset(ans,0,sizeof(ans));
int tmp=dfs(++lim,x*x*x,rk,1);
rk-=tmp;
}
for(int i=lim;i;i--) as=(as*10+ans[i])%mod;
printf("%lld ",as);
};
auto qmo=[](int a,int b,int ans=1){
for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
return ans;
};
auto solve_big=[](int x){
int rk=x*x*x*x-1,num=x*x*x,bit,i,j;
rk-=num/9; num+=2; bit=num/9;
(num%9)?ans[0]=num%9:ans[0]=9;
for(i=1;i<=bit;i++){
if(rk<=bit-i+1) break;
rk-=bit-i+1;
} j=i+rk-1;
int as=(qmo(10,bit)*(ans[0]+1)%mod+mod-1+mod-qmo(10,bit-i)-qmo(10,bit-j)+mod)%mod;
printf("%lld ",as);
};
namespace WSN{
inline short main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%lld%lld",&n,&mod);memset(dp,-1,sizeof(dp));
for(int t=1;t<=min(12ll,n);t++)solve_small(t);
for(int t=13;t<=n;t++)solve_big(t); puts("");
return 0;
}
}
signed main(){return WSN::main();}
T4 NOIP2021
菇菇菇