A.
考虑按块来计算
如果这个块在两边，那么除了与这个块相邻的那一个数与这个块的数不同（一个块里的数都是一样的），其他位置上的数任选
若这个块在中间，那么与这个块相邻的左右两个数与这个块的数不同，其他位置上的数任选
块的大小从1-n，每个块可选数字为10种，相邻数可选数字为9种，其他位置可选10种
ll n,pw[N];
int main(){
cin>>n,pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*10%mod;
for(int i=1;i<=n;i++){
if(i==n)puts("10");
else cout<<(pw[n-i]*18+(n-i-1)*pw[n-i-1]*81)%mod<<" ";
}
return 0;
}
B.
提炼本质，打破所给题意限制的好题
题目说数组a非降序，数组b非递增，但这只是数组位置的要求
数组里的元素可以由其他方式得到和计算，最后按要求放进数组即可
我们把数组元素全拿出来
据题意，易得数组a的最大值小于b的最小值，那么也就是由2m个数组成一个非降序（相当于把b数组反转，也就成了非递增）
也就是说，值域是1-n，数量是2m，可重复取，组成一个非降序有多少种方式
如此考虑：有n个盒子，编号为1-n，然后我们把2m个小球扔向这n个盒子，最后我们从1-n遍历，第i个盒子里有几个小球就把几个盒子编号放入序列，易得这一定是非降序的
再想：我们把每个盒子都放入一个球，也就是现在小球数量有2m+n个，那么就有2m+n-1个空隙，选出n-1个空隙把它们分成n份，至此问题解决
ll fac[N],inv[N];//阶乘数组，阶乘的逆元数组
const ll mod=1e9+7;//是质数的模数
ll power(ll x,ll y){//快速幂
ll ans=1;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
void init(){
fac[0]=1;//0的阶乘是1
inv[0]=power(1,mod-2);//1的逆元
for(ll i=1;i<N;i++){
fac[i]=i*fac[i-1]%mod;//递推求阶乘
inv[i]= power(fac[i],mod-2);//递推求阶乘的逆元
}
}
ll C(ll x,ll y){
if(x<y)return 0;//c下方的数比上方的数大，否则不合法
return fac[x]*inv[y]%mod*inv[x-y]%mod;//把除法变成逆元的乘法
}
void solve() {
int n,m;cin>>n>>m;
init();
cout<<C(2*m+n-1,n-1);
}
C.
这样想：当第i个格子是有威胁的，那么它的花费是3，因为我先走过它去解除威胁，再跑回去接士兵，再走过这个格子
第i个格子没有威胁，花费是1，我直接带着士兵走
用差分做，陷阱+1，机关-1，当前缀和为0时花费为1，不为0花费为3
int m,n,k,t;
int a[N];
int l[N],r[N],d[N],vi[N];
bool check(int x){
int jd=a[x];
for(int i=1;i<=k;i++){
if(d[i]>jd){
vi[l[i]]++;
vi[r[i]+1]--;
}
}
int sum=0;
for(int i=1;i<=n+1;i++){
vi[i]=vi[i]+vi[i-1];
if(vi[i]!=0)sum+=3;
else sum+=1;
}
if(sum<=t)return 1;
return 0;
}
bool cmp(int x,int y){
return x>y;
}
void solve() {
cin>>m>>n>>k>>t;
for(int i=1;i<=m;i++)cin>>a[i];
for(int i=1;i<=k;i++)cin>>l[i]>>r[i]>>d[i];
sort(a+1,a+1+m,cmp);
int l_=1,r_=m,mid;
int ans=0;
while(l_<=r_){
mid=(l_+r_)/2;
memset(vi,0,sizeof(vi));
if(check(mid)){
ans=max(mid,ans);
l_=mid+1;
}else r_=mid-1;
}
cout<<ans<<endl;
}