A.最长不下降子序列
有一个显然的规律：这个序列具有循环节，所以我们根据循环节统计答案即可..
考场写挂的原因：循环节不能只累计一节进行计算..
正确的计算方式：
设单独每个循环节内部所含有的最长不下降子序列的长度为\(len\)..
设在循环节已经有了很多时，每增加一个循环节，答案应该增加\(ans\)..
那么\(ans\)的求法应该是：
\(ans=\) \(len+1\)个循环节的最长不下降子序列的长度\(-\)\(len\)个循环节的最长不下降子序列的长度
然后我们发现所有的\(ans\)都等于 \(1\)
这是通过打表发现的规律，但是也并非没有道理，前面的循环节可以放弃前面的元素然后选择更大的元素..
为了方面，我们可以直接求出\(mod+1\)与\(mod\)个循环节之间的差
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define p() printf("Pass")
#define ll long long int
#define ull unsigned ll
#define re register ll
#define lf double
#define lb lower_bound
#define ub upper_bound
#define mp(x,y) make_pair(x,y)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x);
#define Copy(x,y) memcpy(x,y,sizeof x);
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
inline void write(ll ss)
{
static int stas[35]; int topps=0;
if(ss<0) putchar(‘-‘),ss=-ss;
do{stas[++topps]=ss%10,ss/=10;}while(ss);
while(topps) putchar(stas[topps--]+48); puts("");
}
} using namespace BSS;
const ll N=1320000;
ll m,n,a,b,c,mod,t,st,en,anst;
ll val[N],f[N],vis[N],tmp[N],lsh[N];
inline void Init()
{
n=read();
val[1]=read();
a=read(),b=read(),c=read(),mod=read();
}
inline void Easy_Work()
{
for(re i=2;i<=n;i++)
{
val[i]=((val[i-1]*val[i-1])%mod*a)%mod+(val[i-1]*b)%mod+c%mod;
val[i]%=mod;
}
ll ans=0,temp;
for(re i=1;i<=n;i++)
{
temp=ub(lsh+1,lsh+1+ans,val[i])-lsh;
if(lsh[temp]<=val[i]) lsh[++ans]=val[i];
else lsh[temp]=val[i];
}
printf("%lld\n",ans);
}
inline ll Find_Single()
{
ll cnt=0,temp;
for(re i=1;i<=en;i++) tmp[++cnt]=val[i];
for(re i=1;i<=t*mod;i++) tmp[++cnt]=val[i+en];
for(re i=st,j=1;i<=n;i++,j++) tmp[++cnt]=val[j+en];
ll ans=0;
for(re i=1;i<=cnt;i++)
{
temp=ub(lsh+1,lsh+1+ans,tmp[i])-lsh;
if(lsh[temp]<=tmp[i]) lsh[++ans]=tmp[i];
else lsh[temp]=tmp[i];
}
return ans;
}
inline void Work()
{
for(re i=2;i<=mod*mod;i++)
{
val[i]=((val[i-1]*val[i-1])%mod*a)%mod+(val[i-1]*b)%mod+c%mod;
val[i]%=mod;
}
for(re i=1;i<=mod*mod;i++)
{
if(vis[val[i]])
{
t=i-vis[val[i]];
en=vis[val[i]]-1;
break;
}
vis[val[i]]=i;
}
ll temp=n-en; temp/=t; // temp即为周期个数
st=temp*t+en+1;
ll res=Find_Single();
temp-=mod;
res+=temp;
printf("%lld\n",res);
}
signed main()
{
Init();
if(n<=mod*mod) Easy_Work();
else Work();
// Easy_Work();
return 0;
}
B.完全背包问题
这道题运用了剩余系的思想，从而达到了节约时空的效果，是一个很不错的优化..
然后我们会发现其实这个题对于 \(\leq L\) 的物品可以看作一个非拓扑序的动态转移方程，所以可以建立一个超级源点，然后跑最短路即可..
时间复杂度为\(O(nm · SSSP (V + 1, 2V ))\)
但是对于另外一种方法：
我们会发现所有的环都是不交的，所以这时我们可以选择找到所有与\(S\)相连的顶点中对应边权最小的顶点\(P\)，那么\(S\)到\(P\)的最短路一定就是\(path(S,P)\)，这是我们删掉所有与\(P\)相连的实边，这时环消失，变成了一个拓扑图..
自环直接删了就行..
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define p() printf("Pass")
#define ll long long int
#define ull unsigned ll
#define re register ll
#define lf double
#define lb lower_bound
#define ub upper_bound
#define mp(x,y) make_pair(x,y)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x);
#define Copy(x,y) memcpy(x,y,sizeof x);
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
inline void write(ll ss)
{
static int stas[35]; int topps=0;
if(ss<0) putchar(‘-‘),ss=-ss;
do{stas[++topps]=ss%10,ss/=10;}while(ss);
while(topps) putchar(stas[topps--]+48); puts("");
}
} using namespace BSS;
const ll N=10050;
ll m,n,l,c,mod,lmt,ts,S,tot;
ll v[N],pos[N],dis[N],head[N],vis[N];
ll dp[55][35][N];
inline ll add(ll i,ll j) { return (i%mod+j%mod+mod)%mod; }
inline ll down(ll i,ll j) { return (i%mod-j%mod+mod*mod*mod)%mod; }
struct I { ll u,v,w,nxt; } e[N*6];
inline void Init()
{
n=read(),m=read();
for(re i=1;i<=n;i++) v[i]=read();
sort(v+1,v+1+n); mod=v[1];
n=unique(v+1,v+1+n)-v-1;
l=read(),c=read();
if(v[n]<l) lmt=n+1;
else lmt=lb(v+1,v+1+n,l)-v;
}
inline void Add(ll u,ll v,ll w)
{
e[++ts].u=u;
e[ts].v=v;
e[ts].w=w;
e[ts].nxt=head[u];
head[u]=ts;
}
queue<ll> que;
inline void Spfa()
{
que.push(S); dis[S]=0;
ll now; vis[S]=1;
while(que.size())
{
now=que.front(); que.pop();
for(re i=head[now];i;i=e[i].nxt)
{
// cout<<now<<" "<<e[i].v<<" "<<dis[now]<<" "<<e[i].w<<" "<<dis[e[i].v]<<endl;
if(dis[e[i].v]>=dis[now]+e[i].w)
{
dis[e[i].v]=dis[now]+e[i].w;
if(!vis[e[i].v]) que.push(e[i].v);
vis[e[i].v]=1;
}
}
vis[now]=0;
}
return ;
}
inline void Work()
{
Fill(dp,0x3f); Fill(dis,0x3f);
dp[lmt-1][0][0]=0; long long int w;
for(re i=lmt-1;i<=n;i++)
{
for(re j=0;j<=c;j++)
{
for(re k=0;k<mod;k++)
{
dp[i][j+1][add(k,v[i])]=min(dp[i][j][k]+v[i],dp[i][j+1][add(k,v[i])]);
dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
dp[i+1][j+1][add(k,v[i])]=min(dp[i+1][j+1][add(k,v[i])],dp[i][j][k]+v[i+1]);
// cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<" \n";
}
}
}
S=++tot;
for(re i=0;i<mod;i++) pos[i]=++tot;
for(re k=0;k<mod;k++)
{
for(re i=lmt;i<=n;i++)
{
for(re j=0;j<=c;j++)
{
dis[pos[k]]=min(dis[pos[k]],dp[i][j][k]);
}
}
Add(S,pos[k],dis[pos[k]]);
}
for(re i=0;i<mod;i++)
{
for(re j=1;j<=lmt-1;j++)
{
Add(pos[i],pos[add(i,v[j])],v[j]);
}
}
for(re i=1;i<=lmt-1;i++) Add(S,pos[v[i]%mod],v[i]);
for(re i=1;i<=lmt-1;i++)
{
for(re j=1;j<=lmt-1;j++)
{
Add(pos[v[i]%mod],pos[v[j]%mod],v[j]);
}
}
Spfa();
while(m--)
{
scanf("%lld",&w); //cout<<dis[pos[w%mod]]<<" "<<pos[w%mod]<<endl;
dis[pos[w%(1ll*mod)]]<=w or (!w) ? puts("Yes") : puts("No") ;
}
return ;
}
signed main()
{
// File(0.in,aout);
Init(); Work();
return 0;
}
C.最近公共祖先
算是比较简单的一道了..
对于这种树上的染色问题..绝大部分都是树剖或者LCT套一个线段树吧..
比较妙的一个剪枝，也是考场上唯一没有想到的地方..就是可以选择如果已经将父亲的值传给了自己的兄弟和自己的父亲..那么就不再访问这个点了..
C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define p() printf("Pass")
#define ll long long int
#define ull unsigned ll
#define re register ll
#define lf double
#define lb lower_bound
#define ub upper_bound
#define mp(x,y) make_pair(x,y)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x);
#define Copy(x,y) memcpy(x,y,sizeof x);
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
inline void write(ll ss)
{
static int stas[35]; int topps=0;
if(ss<0) putchar(‘-‘),ss=-ss;
do{stas[++topps]=ss%10,ss/=10;}while(ss);
while(topps) putchar(stas[topps--]+48); puts("");
}
} using namespace BSS;
const ll N=1e5+50;
ll m,n,tot,ts,black;
ll head[N],val[N],flag[N];
ll dep[N],fa[N],dfn[N],rk[N],son[N],top[N],siz[N];
struct I { ll u,v,nxt; } e[N*2];
struct II { ll l,r,lazy,maxn; } tr[N*20];
inline void add(ll u,ll v)
{
e[++ts].u=u;
e[ts].v=v;
e[ts].nxt=head[u];
head[u]=ts;
}
inline void Init()
{
n=read(),m=read();
for(re i=1;i<=n;i++) val[i]=read();
ll u,v;
for(re i=1;i<=n-1;i++)
{
u=read(),v=read();
add(u,v); add(v,u);
}
return ;
}
void dfs1(ll now,ll dad,ll depth)
{
fa[now]=dad; dep[now]=depth+1;
siz[now]=1;
for(re i=head[now];i;i=e[i].nxt)
{
if(dad==e[i].v) continue;
dfs1(e[i].v,now,depth+1);
siz[now]+=siz[e[i].v];
if(siz[son[now]]<siz[e[i].v])
{
son[now]=e[i].v;
}
}
return ;
}
void dfs2(ll now,ll high)
{
dfn[now]=++tot; rk[tot]=now;
top[now]=high;
if(!son[now]) return ;
dfs2(son[now],high);
for(re i=head[now];i;i=e[i].nxt)
{
if(e[i].v==fa[now] or e[i].v==son[now]) continue;
dfs2(e[i].v,e[i].v);
}
return ;
}
inline void spread(ll x)
{
if(tr[x].lazy)
{
tr[x<<1].maxn=max(tr[x<<1].maxn,tr[x].lazy);
tr[x<<1|1].maxn=max(tr[x<<1|1].maxn,tr[x].lazy);
tr[x<<1].lazy=max(tr[x].lazy,tr[x<<1].lazy);
tr[x<<1|1].lazy=max(tr[x].lazy,tr[x<<1|1].lazy);
tr[x].lazy=0;
}
return ;
}
void build(ll x,ll l,ll r)
{
tr[x].l=l; tr[x].r=r;
if(tr[x].l==tr[x].r) return ;
ll mid=(tr[x].l+tr[x].r)>>1;
build(x<<1,l,mid); build(x<<1|1,mid+1,r);
return ;
}
ll query(ll x,ll pos)
{
if(tr[x].l==tr[x].r) return tr[x].maxn;
spread(x);
ll mid=(tr[x].l+tr[x].r)>>1;
if(pos<=mid) return query(x<<1,pos);
else return query(x<<1|1,pos);
}
void update(ll x,ll ql,ll qr,ll w)
{
if(tr[x].l>=ql and tr[x].r<=qr)
{
tr[x].lazy=max(tr[x].lazy,w);
tr[x].maxn=max(tr[x].maxn,w);
return ;
}
spread(x);
ll mid=(tr[x].l+tr[x].r)>>1;
if(ql<=mid) update(x<<1,ql,qr,w);
if(qr>=mid+1) update(x<<1|1,ql,qr,w);
}
inline void Change(ll x)
{
update(1,dfn[x],dfn[x]+siz[x]-1,val[x]);
// flag 记是否给自己的兄弟节点更新父亲的权值.
ll now=x,temp;
while(fa[now] and (!flag[now]))
{
temp=fa[now]; flag[now]=1;
update(1,dfn[temp],dfn[now]-1,val[temp]);
update(1,dfn[now]+siz[now],dfn[temp]+siz[temp]-1,val[temp]);
now=fa[now];
}
return ;
}
inline void Work()
{
build(1,1,n);
dfs1(1,0,1); dfs2(1,1);
char ss[20]; ll u,v,w;
while(m--)
{
scanf("%s",ss+1); u=read();
if(ss[1]==‘Q‘)
{
if(!black) { puts("-1"); continue; }
w=query(1,dfn[u]);
printf("%lld\n",w);
}
if(ss[1]==‘M‘)
{
black=1; Change(u);
}
}
}
signed main()
{
Init();
Work();
return 0;
}