咕了一年的补题……
提高组
冒泡排序
令 \(x_i=\sum_{j=1}^{i-1}[x_j>x_i]\)，则 \(k\) 次冒泡排序相当于将所有 \(x_i\) 变成 \(\max\{0,x_i-k\}\)，树状数组维护即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int N=2e5+10;
int a[N],p[N],n;
struct bit
{
int c[N];
void init(){memset(c,0,sizeof(c));}
int query(int x,int ans=0){for(;x;x-=x&-x)ans+=c[x];return ans;}
void modify(int x,int d)
{
if(x==0)return;
for(;x<=n;x+=x&-x)c[x]+=d;
}
}t1,t2;
signed main()
{
// freopen("P6186_1.in","r",stdin);
// freopen("out.txt","w",stdout);
n=read();int m=read();
t1.init();
for(int i=1;i<=n;i++)
{
a[i]=read();
p[i]=t1.query(n)-t1.query(a[i]);
t1.modify(a[i],1);
}
// for(int i=1;i<=n;i++)printf("%d ",p[i]);
// puts("");
t1.init();t2.init();
for(int i=1;i<=n;i++)t2.modify(p[i],p[i]),t1.modify(p[i],1);
for(int i=1;i<=m;i++)
{
int pos=read();
if(pos==1)
{
// puts("haha");
int x=read();
if(a[x]<a[x+1])
{
t2.modify(p[x],-p[x]);t2.modify(p[x+1],-p[x+1]);
t1.modify(p[x],-1);t1.modify(p[x+1],-1);
swap(a[x],a[x+1]);swap(p[x],p[x+1]);
p[x+1]++;
t2.modify(p[x],p[x]);t2.modify(p[x+1],p[x+1]);
t1.modify(p[x],1);t1.modify(p[x+1],1);
}
else
{
// puts("t2.modify");
t2.modify(p[x],-p[x]);t2.modify(p[x+1],-p[x+1]);
// puts("t1.modify");
t1.modify(p[x],-1);t1.modify(p[x+1],-1);
swap(a[x],a[x+1]);swap(p[x],p[x+1]);
p[x]--;
// printf("p[x+1]:%d\n",p[x+1]);
// puts("t2.modify");
t2.modify(p[x],p[x]);t2.modify(p[x+1],p[x+1]);
// puts("t1.modify");
t1.modify(p[x],1);t1.modify(p[x+1],1);
}
// puts("HAHA");
}
else
{
// puts("hehe");
int k=read();
if(k>n){puts("0");continue;}
int cnt=t1.query(n)-t1.query(k),sum=t2.query(n)-t2.query(k);
printf("%lld\n",sum-k*cnt);
// puts("HEHE");
}
}
return 0;
}
序列
咕咕咕
最小环
咕咕咕
普及组
买铅笔
咋写都能过
跑步
反正NOIP不考五边形数
魔法
考虑 \(k=1\) 的情况，设 \(f(x,i,j)\) 表示 \(i\sim j\) 用了 \(k\) 次魔法的最小代价，则：
\[f(1,i,j)=\min_{(u,v,w)\in E}\{f(0,i,u)+f(0,v,j)-w\} \]接下来考虑 \(k\ge 2\) 的情况，有：
\[f(x,i,j)=\min_{u=1}^n\{f(x-1,i,u)+f(1,u,j)\} \]一个经典的矩乘式子，建立矩阵跑快速幂即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int N=110;
int n;
int e[N][N],f[N][N];
struct mat
{
int a[N][N];
mat(){memset(a,0x3f,sizeof(a));}
void init(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=e[i][j];}
mat operator * (const mat &x) const
{
mat ans;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans.a[i][j]=min(ans.a[i][j],a[i][k]+x.a[k][j]);
return ans;
}
};
struct Edge
{
int u,v,w;
Edge(int uu,int vv,int ww){u=uu;v=vv;w=ww;}
Edge(){}
}a[2510];
mat qpow(mat a,int n)
{
mat ans;
ans.init();
while(n)
{
if(n&1)ans=ans*a;
a=a*a;
n>>=1;
}
return ans;
}
signed main()
{
// freopen("P6190_3.in","r",stdin);
memset(e,0x3f,sizeof(e));
n=read();int m=read(),k=read();
for(int i=1;i<=n;i++)e[i][i]=0;
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
e[u][v]=min(e[u][v],w);
a[i]=Edge(u,v,w);
}
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=e[i][j];
for(int k=1;k<=m;k++)
{
int u=a[k].u,v=a[k].v,w=a[k].w;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],e[i][u]+e[v][j]-w);
}
mat x;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)x.a[i][j]=f[i][j];
mat ans=qpow(x,k);
printf("%lld",k==0?e[1][n]:ans.a[1][n]);
return 0;
}