T1:线性DP，求最长不下降子序列优化（cdp，树状数组）
T2：断环为链，结论
T3：序列上区间统计答案，线段树维护
T4：咕了，矩阵乘法+分治优化，我就打个暴力
T1：给你一个长度n的序列A(n<=5e5,ai<=1e9),求把A中数删除若干个后按照原顺序排列得到B，sigma[Bi==i]的最大值。
考虑合法的这样的B应该满足的条件：
\((1)i<j(2)ai<aj(3)aj-ai<=j-i[因为只能删除数，不能加数]\)
\(dp[i]\):表示选i数的最长不下降子序列，以\(ai-i\)为依据，找1~i-1里面满足条件而且aj<ai的数转移。\(O(n^2)\)
考虑优化，因为有ai<aj的限制，所以不好优化，考虑按照某种顺序排序省略一个限制，发现只要aj-ai>0+(3),(1)一定满足，所以按照ai升序，然后依据（3）Dp，注意相等情况特殊拿出来一起转移。\(O(nlogn)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define _f(i,a,b) for(register int i=a;i<=b;++i)
#define f_(i,a,b) for(register int i=a;i>=b;--i)
#define chu printf
#define ll long long
#define rint register int
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
const int N=5e5+100;
/*
三维偏序：
第一维度：顺序保证
第二：sort
第三：树状数组
加入的元素最多5e5个，值域一样
*/
int n,A[N];//<=mx是最大值域
struct node
{
int a,b;
inline bool operator<(const node&U)const
{
return a<U.a;
}
}e[N];
int tot,dp[N],low[N];
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=re();
_f(i,1,n)
{
A[i]=re();
if(A[i]<=i)
{
e[++tot].a=A[i],e[tot].b=i-A[i];
}
}
_f(i,1,tot)low[i]=1e9;
sort(e+1,e+1+tot);int cot=0;
//chu("tot:%d\n",tot);
for(int i=1;i<=tot;++i)
{
int l=i;
while(i<tot&&e[i].a==e[i+1].a)++i;
int r=i;
//l--r去找前面
_f(j,l,r)
dp[j]=upper_bound(low+1,low+1+tot,e[j].b)-1-low+1;
_f(j,l,r)
low[dp[j]]=min(e[j].b,low[dp[j]]);
}
_f(i,1,tot)dp[0]=max(dp[0],dp[i]);
chu("%d",dp[0]);
return 0;
}
/*
5
1 1 2 5 4
*/
T2:一个环，n个点按顺时针排列，sigma(ai)=n,把i位置的数运到j位置（顺时针），需要\(dis(i,j)^2\)的花费，每次只运1单位的值，每个值不重复运输，求最少花费，使得任意ai=1。(n<=1e5)
猜测一定存在一个最优方案使得有断点没有值运输。\(x^2 + y^2 < (x+y)^2\)
枚举断点，然后直接算方案。\(O(n^2)\)
正解：
贪心地想，如果让dis尽量小，就是移动的步数尽量少，考虑hi=ai-1,就是这个点要运出去多少，想象成流水，从最高的地方流，平均地流下去，一定会比中间有一个凸起来的地方要dis更少（平方嘛，尽量“步子越碎”越好），所以找到这段峰值的起点，然后就是最优的起点，如果多个峰值等效,因为最大子段和值>=0,在每个子段内部如果都有峰值那么一定不会彼此流。最大子段和一定可以控制len<=n,因为一个完整区间sum==0.
笑死了，什么贪心，结果唯一，只要合法，一定最优，___0;移动不合法，___1移动等效。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define _f(i,a,b) for(register int i=a;i<=b;++i)
#define f_(i,a,b) for(register int i=a;i>=b;--i)
#define chu printf
#define ll long long
#define rint register int
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
#define int ll
const int N=1e5+100;
int h[N<<1],pos[N<<1],wat[N<<1],top,n,mx,meng[N<<1];
int sum1[N<<1];
ll ans;
inline int find_ans(int l,int r)
{
//if(h[l]<mx)return;
_f(i,l,r)
{
if(sum1[r]-sum1[i-1]>r-i+1)
{
return 0;
}
}
//chu("find:%d--%d\n",l,r);
ll nas=0;top=0;
_f(i,l,r)
{
wat[i]=h[i];
if(h[i])//如果有水
pos[++top]=i;//,chu("posadd:%d\n",pos[top]);//留着用,但是还要知道位置？因为算距离
}
f_(i,r,l)//考虑把这里弄到水的花费
{
if(wat[i])
{
--top;//一定是自己的水
continue;//有水不管
}
nas+=pow(i-pos[top],2);
--wat[pos[top]];++wat[i];
if(!wat[pos[top]])--top;
}
//_f(i,l,r)chu("%d",wat[i]);chu("\n");
ans=min(ans,nas);
return 1;
}
signed main()
{
freopen("barn.in","r",stdin);
freopen("barn.out","w",stdout);
n=re();
ans=1e18;
_f(i,1,n)
{
h[i]=h[i+n]=re();
meng[i]=h[i]-1;
meng[i+n]=h[i]-1;
// mx=max(h[i],mx);
}
int maxn=-1e9,pos=1,pre=1,sum=0;
_f(i,1,n<<1)
{
// chu("meng[%d]:%d\n",i,meng[i]);
sum=sum+meng[i];
if(sum<0)sum=0,pre=i+1;
if(sum>maxn)
{
maxn=sum;pos=pre;
}
}
// chu("pre:%d\n",pos);
_f(i,1,n<<1)sum1[i]=sum1[i-1]+h[i];
find_ans(pos,pos+n-1);
chu("%lld",ans);
return 0;
}
/*
枚举断点，然后计算答案。
10
1
0
0
2
0
0
1
2
2
2
*/
T3:定义mex(i,j)是区间[i,j]的没在ai~aj出现过的最小自然数，求n的子区间mex和。n<=1e5
线段树二分可以树外二分，找到最左边的mex>s[i]的位置pos，在pos~nxt[s[i]]-1中间就是会被影响的数。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define _f(i,a,b) for(register int i=a;i<=b;++i)
#define f_(i,a,b) for(register int i=a;i>=b;--i)
#define chu printf
#define ll long long
#define rint register int
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
const int N=2e5+100;
ll sum[N<<2];int mi[N<<2];
int s[N],Mex[N],vis[N],n,pos[N],nxt[N],tag[N<<2];
ll sm;
#define lson (x<<1)
#define rson (x<<1|1)
inline void push_up(int x)
{
mi[x]=min(mi[lson],mi[rson]);
sum[x]=sum[lson]+sum[rson];
}
inline void push_down(int x,int l,int r)
{
if(tag[x]==-1)return;
int mid=(l+r)>>1;
tag[lson]=tag[rson]=tag[x];
mi[lson]=mi[rson]=tag[x];
sum[lson]=(ll)(mid-l+1)*mi[lson];
sum[rson]=(ll)(r-mid)*mi[rson];
tag[x]=-1;
}
inline void build(int x,int l,int r)
{
tag[x]=-1;
if(l==r)
{
//chu("build(%d):%d\n",x,Mex[l]);
sum[x]=mi[x]=Mex[l];return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
push_up(x);
}
inline void insert(int x,int l,int r,int L,int R,int val)
{
if(L<=l&&r<=R)
{
tag[x]=mi[x]=val;sum[x]=(ll)(r-l+1)*val;
// chu("insert:%d:%d\n",x,val);
return;
}
push_down(x,l,r);
int mid=(l+r)>>1;
if(L<=mid)insert(lson,l,mid,L,R,val);
if(R>mid)insert(rson,mid+1,r,L,R,val);
push_up(x);
}
inline int query(int x,int l,int r,int pos)
{
if(l==r)return mi[x];
int mid=(l+r)>>1;
push_down(x,l,r);
if(pos<=mid)return query(lson,l,mid,pos);
return query(rson,mid+1,r,pos);
}
inline ll query2(int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
//push_down(x,l,r);
// chu("(x:%d)query:%d--%d:%d\n",x,l,r,sum[x]);
return sum[x];
}
int mid=(l+r)>>1;ll ans=0;
push_down(x,l,r);
if(L<=mid)ans+=query2(lson,l,mid,L,R);
if(R>mid)ans+=query2(rson,mid+1,r,L,R);
return ans;
}
int main()
{
freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
n=re();int mx=0;
_f(i,1,n)
{
s[i]=re();
if(s[i]<n)
{
vis[s[i]]=1;
}
while(vis[mx])++mx;
Mex[i]=mx;
// chu("Mex[%d]:%d\n",i,mx);
}
//nxt[n]=n+1;//这个位置的数下一次出现
f_(i,n,1)
{
if(s[i]<n)
{
if(!pos[s[i]])nxt[i]=n+1,pos[s[i]]=i;
else nxt[i]=pos[s[i]],pos[s[i]]=i;
}
}
build(1,1,n);
_f(i,1,n)
{
sm+=query2(1,1,n,i,n);
//chu("addsm:%d\n",sm);
if(s[i]<n)//此时删除可能有影响
{
int l=i+1,r=nxt[i]-1;
int nas=-1;
//chu("l:%d r:%d\n",l,r);
while(l<=r)
{
int mid=(l+r)>>1;
//chu("query:(%d)%d\n",mid,query(1,1,n,mid));
if(query(1,1,n,mid)>s[i])r=mid-1,nas=mid;
else l=mid+1;
}
if(nas!=-1)insert(1,1,n,nas,nxt[i]-1,s[i]);//chu("add get(%d--%d):%d\n",nas,nxt[i]-1,s[i]);
}
}
chu("%lld",sm);
return 0;
}
/*
3
0 1 3
*/
暴力：
50tps：
ai的值域是1e9，一看就不好用vis标记访问，那肯定是\(n^3\)枚举区间然后标记然后没准用个set维护第几小的值？T飞了......发现
有用的a只当< n,因为最多n个连续值域0~n-1，mex最多n，所以只标记这些就行。
18tps：
当ai唯一，从小到大枚举0~n-1的每个数出现位置，然后拓展[l,r]区间，每次计算贡献。需要注意对于0 2 1这种，2在1里面，1不能统计贡献，需要留给2，但是这样很麻烦，所以我对每个数都加上1次贡献，如果有包含，因为次数累加，所以恰好是这个数的贡献。【妙！%%%所有大佬】
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
const int maxn = 200005;
int n, a[maxn], pos[maxn];
bool vis[maxn];
void solve(){
for(int i = 1; i <= n; ++i)if(a[i] < n)pos[a[i]] = i;
ll ans = 0; int lp = n, rp = 0;
for(int mex = 0; mex < n; ++mex){
if(!pos[mex])break;
rp = max(rp, pos[mex]);
lp = min(lp, pos[mex]);
ans += 1ll * lp * (n - rp + 1);
}
printf("%lld\n",ans);
// cerr << "solve" << endl;
}
int main(){
freopen("mex.in","r", stdin);
freopen("mex.out","w",stdout);
n = read();
for(int i = 1; i <= n; ++i)a[i] = read();
bool f = 1;
for(int i = 1; i <= n; ++i){
if(a[i] < n){
if(vis[a[i]]){
f = 0; break;
}
vis[a[i]] = 1;
}
}
if(f){
solve();
return 0;
}
ll ans = 0;
for(int l = 1; l <= n; ++l){
int mex = 0;
for(int i = 0; i < n; ++i)vis[i] = 0;
for(int r = l; r <= n; ++r){
if(a[r] < n){
vis[a[r]] = 1;
while(vis[mex])++mex;
}
ans += mex;
}
}
printf("%lld\n",ans);
return 0;
}
T4:给出一个有向图，求长度<k的环个数。
矩阵乘法的一般意义。a[i][j]代表从i到j的路径数，加上对角线就行。注意初始化矩阵对角线。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define _f(i,a,b) for(register int i=a;i<=b;++i)
#define f_(i,a,b) for(register int i=a;i>=b;--i)
#define chu printf
#define ll long long
#define rint register int
#define ull unsigned long long
inline ll re()
{
ll x=0,h=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')h=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*h;
}
const int N=0;
int k,mod,n;
char s[45];
struct Tiger
{
int a[45][45];
Tiger()
{
memset(a,0,sizeof(a));
}
Tiger operator*(const Tiger&A)const
{
Tiger res;
_f(i,1,n)
_f(j,1,n)
_f(k,1,n)
res.a[i][j]=((ll)res.a[i][j]+(ll)a[i][k]*A.a[k][j]%mod)%mod;
return res;
}
}mp[2];
int main()
{
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
n=re();
_f(i,1,n)
{
scanf("%s",s+1);
_f(j,1,n)
if(s[j]=='Y')mp[0].a[i][j]=1;
}
k=re(),mod=re();
_f(i,1,n)mp[1].a[i][i]=1;
int ans=0;
//_f(i,1,n)
// ans+=mp[1].a[i][i];
_f(i,1,k-1)//只需要*(k-1)次
{
mp[1]=mp[0]*mp[1];
_f(j,1,n)ans=((ll)ans+(ll)mp[1].a[j][j])%mod;
}
chu("%d",ans);
return 0;
}
/*
4
NYNY
NNYN
YNNN
YNNN
6
100
*/