ARC153
A
直接枚举所有的美丽数即可
#include<bits/stdc++.h>
using namespace std;
vector<int>V;
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
for(int i1=1;i1<=9;i1++)
{
int i2=i1;
for(int i3=0;i3<=9;i3++)
{
for(int i4=0;i4<=9;i4++)
{
for(int i5=0;i5<=9;i5++)
{
int i6=i5;
for(int i7=0;i7<=9;i7++)
{
for(int i8=0;i8<=9;i8++)
{
int i9=i7;
int Nt=(((((((((i1*10)+i2)*10+i3)*10)+i4)*10+i5)*10+i6)*10+i7)*10+i8)*10+i9;
V.push_back(Nt);
}
}
}
}
}
}
//cerr<<V.size()<<endl;
sort(V.begin(),V.end());
int N;
scanf("%d",&N);
printf("%d\n",V[N-1]);
}
B
平衡树搞一下即可
#include<bits/stdc++.h>
#define ls Tree[p].child[0]
#define rs Tree[p].child[1]
using namespace std;
const int MAXN=5e5+5;
struct FHQ_Tree{
int Size;
int cnt;
int child[2];
int val;
int key;
int lazy_roll;
};
vector<int>a,b;
struct FHQ{
FHQ_Tree Tree[MAXN];
int cnt_node=0;
int root;
int New(int val)
{
Tree[++cnt_node].key=rand();
Tree[cnt_node].cnt=1;
Tree[cnt_node].Size=1;
Tree[cnt_node].val=val;
return cnt_node;
}
void push_up(int p)
{
Tree[p].Size=Tree[ls].Size+Tree[rs].Size+Tree[p].cnt;
}
void RL(int p)
{
swap(ls,rs);
Tree[p].lazy_roll^=1;
}
void push_down(int p)
{
if(Tree[p].lazy_roll)
{
// swap(ls,rs);
if(ls)
{
RL(ls);
}
if(rs)
{
RL(rs);
}
Tree[p].lazy_roll=0;
}
}
void Split(int p,int val,int &x,int &y)
{
if(!p)
{
x=0;
y=0;
return;
}
push_down(p);
if(Tree[ls].Size+Tree[p].cnt<=val)
{
x=p;
Split(rs,val-Tree[ls].Size-Tree[p].cnt,rs,y);
}
else
{
y=p;
Split(ls,val,x,ls);
}
push_up(p);
}
int merage(int x,int y)
{
if((!x)||(!y))
{
return x+y;
}
if((Tree[x].key)<(Tree[y].key))
{
push_down(x);
Tree[x].child[1]=merage(Tree[x].child[1],y);
push_up(x);
return x;
}
else
{
push_down(y);
Tree[y].child[0]=merage(x,Tree[y].child[0]);
push_up(y);
return y;
}
}
void insert(int x,int val)
{
int lx,rx;
Split(root,x,lx,rx);
root=merage(merage(lx,New(val)),rx);
return;
}
void roll(int l,int r)
{
int lx,zx,rx;
Split(root,l-1,lx,rx);
Split(rx,r-l+1,zx,rx);
// Tree[zx].lazy_roll^=1;
RL(zx);
root=merage(merage(lx,zx),rx);
return;
}
void print(int p)
{
if(!p)
{
return;
}
push_down(p);
print(ls);
// printf("%d ",);
a.push_back(Tree[p].val);
print(rs);
}
}tree1,tree2;
int n,m,q;
int l,r;
int x,y;
string V[MAXN];
int main()
{
srand(time(0));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
tree1.insert(i-1,i);
}
for(int i=1;i<=m;i++)
{
tree2.insert(i-1,i);
}
for(int i=1;i<=n;i++)
{
cin>>V[i];
}
scanf("%d",&q);
while(q--)
{
scanf("%d %d",&x,&y);
tree1.roll(1,x);
tree1.roll(x+1,n);
tree2.roll(1,y);
tree2.roll(y+1,m);
}
tree2.print(tree2.root);
b=a;
a.clear();
tree1.print(tree1.root);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int Keyi=a[i-1];
int Keyj=b[j-1];
printf("%c",V[Keyi][Keyj-1]);
}
printf("\n");
}
// for(int i=1;i<=n;i++)
// {
// printf("%d ",a[i-1]);
// }
// printf("\n");
// for(int i=1;i<=m;i++)
// {
// printf("%d ",b[i-1]);
// }
}
C
最后一个可以作为调整的,让它是\(-1\),然后这里我们可以尽量让\(+\)的比\(-\)的多即可
然后这里先构造为前面一个比后面刚好小\(1\)
然后有调整,直接对一个后缀\(+\)上一些数,直接看有没有即可
注意\(1e12\)的限制
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int a[MAXN];
long long b[MAXN];
int Sur[MAXN];
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
if(n==1)
{
printf("Yes\n0");
return 0;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==-1)
{
a[i]=0;
}
}
if(a[n]==1)
{
for(int i=1;i<=n;i++)
{
a[i]^=1;
}
}
for(int i=n;i>=1;i--)
{
Sur[i]=Sur[i+1]+(a[i]==1);
}
b[0]=-1e6;
long long D0=0,D1=0;
int f=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)
{
if((Sur[i]>(n-i+1)-Sur[i])&&(!f))
{
f=i;
b[i]=b[i-1]+1;
}
else
{
b[i]=b[i-1]+1;
}
D1+=b[i];
}
else if(a[i]==0)
{
b[i]=b[i-1]+1;
D0+=b[i];
}
}
if(f&&(D0>D1))
{
long long Det=(D0-D1)/(Sur[f]-((n-f+1)-Sur[f]));
for(int i=f;i<=n;i++)
{
b[i]+=Det+1;
if(a[i]==0)
{
D0+=(Det+1);
}
else
{
D1+=(Det+1);
}
}
//printf("fuck\n");
}
//printf("%lld %lld\n",D0,D1);
if(D0>D1&&(!f))
{
printf("No");
}
else
{
long long det=D1-D0;
b[n]+=det;
printf("Yes\n");
for(int i=1;i<=n;i++)
{
printf("%lld ",b[i]);
}
}
}
D
考虑每个\(x\)在第\(i\)位的贡献
可以发现第\(i-1\)位的影响就是它是否进位
如果设\(dp_{i,j}\)为前\(i\)位有\(j\)个进位
然后\(j\)个进位的数是固定的,我们可以直接枚举填的数即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int a[MAXN];
int dp[11][MAXN];
int C[11];
vector<pair<int,int> >V;
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
int Sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int Now=a[i];
for(int j=1;j<=9;j++)
{
Sum+=(Now%10);
Now/=10;
}
}
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
int Mul=1;
for(int ie=1;ie<=9;ie++)
{
for(int j=0;j<=10;j++)
{
C[j]=0;
}
for(int i=1;i<=n;i++)
{
C[(a[i]/Mul)%10]++;
}
V.clear();
for(int i=1;i<=n;i++)
{
V.push_back((make_pair(-(a[i]%Mul),i)));
}
sort(V.begin(),V.end());
for(int i=0;i<=n;i++)
{
if(dp[ie-1][i]!=0x3f3f3f3f)
{
// if(ie==2)
// {
// printf("%d %d----\n",i,C[8]);
// }
for(int j=0;j<=9;j++)
{
int Nr=(j*n);
int Cp=0;
for(int k=0;k<=10;k++)
{
if(j+k>=10)
{
Cp+=C[k];
}
}
Nr=(Nr-9*Cp);
//printf("%d----\n",Nr);
dp[ie][Cp]=min(dp[ie][Cp],dp[ie-1][i]+Nr);
}
}
if(i!=n)
{
int p=V[i].second;
//printf("%d??\n",p);
C[(a[p]/Mul)%10]--;
C[(a[p]/Mul)%10+1]++;
}
}
// for(int i=0;i<=n;i++)
// {
// printf("%d %d %d:::\n",ie,i,dp[ie][i]);
// }
Mul*=10;
}
int Res=0x3f3f3f3f;
for(int i=0;i<=n;i++)
{
Res=min(Res,dp[9][i]);
}
printf("%d\n",Res+Sum);
}
E
注意\(f(X)\)是最小的
如果我们知道了\([L,R]\),然后\(X\)后面那位一定是要填在\(L-1\)或者\(R+1\)
如果填的是\(L-1\),必须满足\((Y_{L-1}\le Y_L)\)
如果填的是\(R+1\),必须满足\(Y_R>Y_L\)(防止重复)
这个区间\(dp\)直接做是\(O(n^2)\)的
不过可以注意到很多状态是用不到的
可以发现如果要转移到\(1\),说明\([1,L]\)必须是个不降的序列
而且\(i\)向右转移的范围是最大的\(R\)使得\([i,R]\)最小的数大于\(i\)
然后可以发现这玩意长得像若干个阶梯状的转移,阶级间的转移是个卷积的形式
#include<bits/stdc++.h>
#define eps 1e-9
using namespace std;
const int MAXN=6e5+5;
const int MOD=998244353;
const int g=3;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int Rev[MAXN*4];
int inv_fac[MAXN];
int fac[MAXN];
int C(int n,int m)
{
if(n<m||m<0)
{
return 0;
}
if(n==m||m==0)
{
return 1;
}
return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD;
}
struct Poly{
vector<int>U;
void NTT(int Limit,int type)
{
int Len=(1<<Limit);
for(int i=0;i<Len;i++)
{
Rev[i]=((Rev[i>>1]>>1)|((i&1)<<(Limit-1)));
}
while(U.size()<Len)
{
U.push_back(0);
}
for(int i=0;i<Len;i++)
{
if(i<Rev[i])
{
swap(U[i],U[Rev[i]]);
}
}
for(int l=1;l<Len;l<<=1)
{
int Wn=Pow(g,(MOD-1)/(l<<1),MOD);
if(type==-1)
{
Wn=inv(Wn,MOD);
}
for(int i=0;i<Len;i+=(l<<1))
{
int W=1;
for(int j=i;j<i+l;j++,W=((long long)W*Wn)%MOD)
{
int Xc=U[j];
int Yc=((long long)U[j+l]*W)%MOD;
U[j]=((long long)Xc+Yc)%MOD;
U[j+l]=((long long)Xc-Yc+MOD)%MOD;
}
}
}
if(type==-1)
{
int Liv=inv(Len,MOD);
for(int i=0;i<Len;i++)
{
U[i]=((long long)U[i]*Liv)%MOD;
}
}
}
};
Poly Mul_NTT(Poly A,Poly B)
{
int N=A.U.size();
int M=B.U.size();
int nox=1;
int Lm=0;
while(nox<=(N+M-2))
{
nox<<=1;
Lm++;
}
A.NTT(Lm,1);
B.NTT(Lm,1);
for(int i=0;i<nox;i++)
{
A.U[i]=((long long)A.U[i]*B.U[i])%MOD;
}
A.NTT(Lm,-1);
while(A.U.size()>(N+M-1))
{
A.U.pop_back();
}
return A;
}
char s[MAXN];
Poly A;
struct Sery{
int l,r,R;
}a[MAXN];
int dp[MAXN][25];
int Lg[MAXN];
int Query(int l,int r)
{
if(l>r)
{
return 0x3f3f3f3f;
}
int k=Lg[r-l+1];
return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
fac[0]=1;
for(int i=1;i<=MAXN-5;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
for(int i=MAXN-5-1;i>=1;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;i++)
{
dp[i][0]=s[i];
Lg[i]=log2(i);
}
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
}
A.U.resize(n+1,0);
int Pi=1;
int Cnt=0;
while(Pi<=n)
{
++Cnt;
a[Cnt].l=Pi;
while((Pi+1<=n)&&(s[Pi]==s[Pi+1]))
{
++Pi;
}
a[Cnt].r=Pi;
int l=Pi;
int r=n;
int Key=Pi;
while(l<=r)
{
int mid=(l+r)>>1;
if(Query(Pi+1,mid)>s[Pi])
{
l=mid+1;
Key=mid;
}
else
{
r=mid-1;
}
}
a[Cnt].R=Key;
if((Pi<=n)&&(s[Pi+1]>s[Pi]))
{
++Pi;
}
else
{
break;
}
}
// printf("%d\n",Cnt);
// for(int i=1;i<=Cnt;i++)
// {
// printf("%d %d %d\n",a[i].l,a[i].r,a[i].R);
// }
Poly B;
B.U.resize(n+1,0);
for(int i=Cnt;i>=1;i--)
{
int Len=a[i].r-a[i].l+1;
for(int j=0;j<=n;j++)
{
B.U[j]=C(j+Len-1,Len-1);
}
A.U[a[i].r]=1;
A=Mul_NTT(A,B);
for(int j=0;j<=n;j++)
{
if(j>=a[i].l&&j<=a[i].R)
{
}
else
{
A.U[j]=0;
}
}
for(int j=a[i].l;j<a[i].r;j++)
{
A.U[j]=1;
}
// printf("%d::\n",i);
// for(int j=0;j<=n;j++)
// {
// printf("%d ",A.U[j]);
// }
// printf("\n");
// for(int j=0;j<=n;j++)
// {
// printf("%d ",B.U[j]);
// }
// printf("\n");
}
printf("%d\n",A.U[n]);
}