Cette question comporte une particularité : les sous-séquences ne sont pas continues **Attention, les sous-séquences peuvent être discontinues, tandis que les sous-chaînes doivent être continues.**Une solution brute évidente existe :

Cliquez pour voir le code``` int dp[N][N],n,p[N],q[N]; int main() { speed(); freopen("in.in","r",stdin); freopen("out.out","w",stdout); cin>>n; for(int i=1;i<=n;i++)cin>>p[i]; for(int i=1;i<=n;i++)cin>>q[i]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if(q[j]%p[i]==0) { dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]); } } } cout<<dp[n][n]<<endl; return 0; }

L'optimisation consiste à utiliser un arbre de segment, et à supprimer une dimension. Il faut également parcourir en ordre inverse pour éviter des mises à jour incorrectes. On pré-traite chaque valeur de $p_i$ pour ses multiples. La complexité est $O(n \log n \log n)$.

Cliquez pour voir le code```
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 2e5+5;
int dp[N],n;
int p[N],q[N];
int posq[N],posp[N];
vector <int> pos[N];
int c[N];
int lowbit(int x){return x&-x;}
int query(int x)
{
	int ans=0;
	if(x<=0)return 0;
	while(x)
	{
		ans=max(ans,c[x]);
		x-=lowbit(x);
	}return ans;
}
void upd(int x,int val)
{
	if(x<=0)return ;
	while(x<=n)
	{
		c[x]=max(c[x],val);
		x+=lowbit(x);
	}
	return;
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i],posp[p[i]]=i;
	for(int i=1;i<=n;i++)cin>>q[i],posq[q[i]]=i;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j+=i)
			if(posq[j])pos[i].pb(posq[j]);
		sort(pos[i].begin(),pos[i].end());
		reverse(pos[i].begin(),pos[i].end());
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int ls=0;
		for(auto v:pos[p[i]])
		{
			int j=v;
			dp[j]=query(j);
			dp[j]=max(query(j-1)+1,dp[j]);
			ans=max(ans,dp[j]);
			upd(j,dp[j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Deux approches possibles, Mo's algorithm (constante légèrement plus élevée)

Cliquez pour voir le code``` #include <bits/stdc++.h> #define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define ll long long #define lid (rt<<1) #define rid (rt<<1|1) // #define endl '\n' #define pb push_back using namespace std; const int N = 2e5+5,mod=1e9+7; int x[N],n,m; int sq,B,st[500],ed[500],b[N],cnt[N],ans[N],cc[N]; struct qu { int l,r,id,bl; bool operator < (const qu& A)const { if(bl==A.bl)return r<A.r; return l<A.l; } }q[N]; void init() { sq=sqrt(n);B=n/sq; for(int i=1;i<=B;i++) { st[i]=ed[i-1]+1;ed[i]=st[i]+sq-1; // cout<<st[i]<<" "<<ed[i]<<endl; } if(ed[B]<n) { B++;st[B]=ed[B-1]+1;ed[B]=n; } } int RES; void add(int d) {

cnt[x[d]]++;
// cout<<cnt[x[d]]<<endl;
RES=max(RES,cnt[x[d]]);
// cout<<res<<endl;

} void del(int d) { cnt[x[d]]--; } int force(int l,int r) { memset(cc,0,sizeof cc); int ans=0; for(int i=l;i<=r;i++)cc[x[i]]++,ans=max(ans,cc[x[i]]); return ans; } int main() { speed(); // freopen("T2.in","r",stdin); // freopen("in.in","r",stdin); // freopen("out.out","w",stdout); cin>>n>>m;

for(int i=1;i<=n;i++)
{
	cin>>x[i];b[i]=x[i];
}
sort(b+1,b+1+n);
int res=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
{
	x[i]=lower_bound(b+1,b+1+res,x[i])-b;
	// cout<<x[i]<<endl;
}
init();
for(int i=1;i<=m;i++)
{
	cin>>q[i].l>>q[i].r;q[i].id=i;
	q[i].bl=(q[i].l-1)/sq+1;
}
sort(q+1,q+1+m);int j=1;int L,R;
// sq=1e9;
for(int i=1;i<=B&&j<=m;i++)
{
	L=ed[i]+1;R=ed[i];RES=0;
	memset(cnt,0,sizeof cnt);
	while(q[j].bl==i)
	{
		if(q[j].r-q[j].l<=sq)
		{
			ans[q[j].id]=force(q[j].l,q[j].r);
			j++;
			continue;
		}
		// cout<<L<<" "<<R<<" "<<q[j].l<<endl;
		L=ed[i]+1;
		while(R<q[j].r)
		{
			++R;
			add(R);
		}
		// cout<<res<<endl;
		ll tmp=RES;
		while(L>q[j].l)
		{
			L--;
			// cout<<L<<endl;
			add(L);
		}
		ans[q[j].id]=RES;
		// cout<<res<<endl;
		RES=tmp;
		while(L<=ed[i])del(L++);
		j++;
	}
}
for(int i=1;i<=m;i++)cout<<-ans[i]<<endl;
return 0;

}

Mo's algorithm

Cliquez pour voir le code```
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 2e5+5;
int n,m,st[500],ed[500],sq,B,x[N],b[N],t[N],cnt[N],aa[N];
struct qu
{
	int l,r,id,bl;
	bool operator < (const qu& A)const
	{
		if(bl!=A.bl)return l<A.l;
		if(bl&1)return r<A.r;
		return r>A.r;
	}
}q[N];
void init()
{
	sq=sqrt(n);B=n/sq;
	for(int i=1;i<=B;i++)
	{
		st[i]=ed[i-1]+1;ed[i]=st[i]+sq-1;
	}
	if(ed[B]<n)
	{
		B++;st[B]=ed[B-1]+1;ed[B]=n;
	}
}
int ans;
inline void del(int x)
{
	if(ans==cnt[b[x]])ans--;
	t[cnt[b[x]]]--;
	if(t[cnt[b[x]]])ans=max(ans,cnt[b[x]]);
	cnt[b[x]]--;
	t[cnt[b[x]]]++;
	ans=max(ans,cnt[b[x]]);
}
inline void add(int x)
{
	t[cnt[b[x]]]--;
	cnt[b[x]]++;
	t[cnt[b[x]]]++;
	ans=max(ans,cnt[b[x]]);
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];b[i]=x[i];
	}
	sort(x+1,x+1+n);
	int res=unique(x+1,x+1+n)-x-1;
	for(int i=1;i<=n;i++)
	{
		b[i]=lower_bound(x+1,x+1+res,b[i])-x;
		// cout<<x[i]<<endl;
	}init();
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;q[i].id=i;
		q[i].bl=(q[i].l-1)/sq+1;
	}
	sort(q+1,q+1+m);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l>q[i].l){add(--l);}
		while(l<q[i].l){del(l++);}
		while(r>q[i].r){del(r--);}
		while(r<q[i].r){add(++r);}
	
		aa[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)cout<<-aa[i]<<endl;
	return 0;
}

T3 Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

**Un chemin simple peut avoir deux définitions : il peut désigner un chemin dans un graphe G(V, E) où les sommets sont tous distincts, ou bien un arc dans Rn, appelé aussi arc simple, qui est une généralisation de l'arc courbe.**Ainsi, un chemin simple dans un sous-arbre est un chemin ne contenant pas d'autre sommet, ne se répétant pas et pouvant traverser deux fils. En utilisant une approche brute-force, on peut obtenir la propriété suivante : un chemin peut être palindrome uniquement si chaque lettre apparaît un nombre pair de fois, sauf une au maximum. Dans ce cas, on peut compresser en binaire. Un état valide est celui où tous les bits sont 0 ou seulement un bit est 1. L'attente est 50pts.

Cliquez pour voir le code``` #include <bits/stdc++.h> #define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define ll long long #define lid (rt<<1) #define rid (rt<<1|1) #define endl '\n' #define pb push_back #define pii pair<int,int> using namespace std; const int N = 5e5+5; int n,ans[N],fa[N];char val[N]; vector edge[N]; map <int,int> len[N]; inline int get(int x) { return 1<<(val[x]-'a'); } inline void dfs(int u) { len[u][0]=0; for(auto to:edge[u]) { dfs(to); ans[u]=max(ans[to],ans[u]); for(auto v:len[to]) { int zt=get(to)^v.first; if(len[u].find(zt)!=len[u].end())ans[u]=max(ans[u],len[u][zt]+v.second+1); if((zt^(zt&-zt))==0)ans[u]=max(ans[u],v.second+1); for(int j=0;j<22;j=-~j) { if(len[u].find(zt^(1<<j))!=len[u].end()) ans[u]=max(ans[u],len[u][zt^(1<<j)]+v.second+1); } } for(auto v:len[to]) len[u][get(to)^v.first]=max(len[u][get(to)^v.first],v.second+1); } } int main() { speed(); // freopen("in.in","r",stdin); // freopen("out.out","w",stdout); cin>>n; for(int i=2;i<=n;i++) { cin>>fa[i]>>val[i]; edge[fa[i]].pb(i); } dfs(1); for(int i=1;i<=n;i++) cout<<ans[i]<<" "; return 0; }

La solution optimale utilise la fusion heuristique. On commence par penser à la solution brute-force : calculer l'état XOR du chemin de x vers 1, puis vérifier si u,v sont valides en effectuant un XOR directement. Une solution est valide si et seulement si son représentation binaire contient un seul 1 ou tous 0. Si u,v sont valides (soit dis_u == dis_v et dis_udis_v a un seul 1), alors la contribution est dep_u + dep_v - 2dep_lca. On stocke dans un tableau book les profondeurs correspondantes à chaque état. En parcourant toutes les sous-arborescences, on vérifie les 23 états possibles. Cela permet d'optimiser de O(23n²) à O(23n log n).

Cliquez pour voir le code```
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 1e6+5;
int fa[N],L[N],R[N],rk[N],dfstot,sz[N],son[N],dis[N],dep[N],n;char val[N];
int ans[N],book[1<<22];//book stocke l'état courant correspondant à la profondeur
vector <int> edge[N];
inline void dfs1(int u)
{
	dep[u]=dep[fa[u]]+1;sz[u]=1;
	L[u]=++dfstot;rk[dfstot]=u;//ordre d'Euler pour faciliter le parcours des fils
	for(auto to:edge[u])
	{
		dis[to]=dis[u]^(1<<(val[to]-'a'));//calculer l'état du chemin
		dfs1(to);
		sz[u]+=sz[to];
		if(sz[to]>sz[son[u]])son[u]=to;
	}
	R[u]=dfstot;
}
inline void dfs2(int u,bool heavy)
{
	for(auto to:edge[u])
	{
		if(to==son[u])continue;
		dfs2(to,0);
		ans[u]=max(ans[u],ans[to]);
	}
	if(son[u])dfs2(son[u],1),ans[u]=max(ans[u],ans[son[u]]);
	if(book[dis[u]])ans[u]=max(ans[u],book[dis[u]]-dep[u]);//mise à jour de la réponse
	for(int j=0;j<22;j++)
		if(book[dis[u]^(1<<j)])ans[u]=max(ans[u],book[dis[u]^(1<<j)]-dep[u]);//vérification de l'état valide
	book[dis[u]]=max(book[dis[u]],dep[u]);//mise à jour de l'état
	for(auto to:edge[u])
	{
		if(to==son[u])continue;
		for(int j=L[to];j<=R[to];j++)
		{
			int id=rk[j];
			if(book[dis[id]])ans[u]=max(ans[u],book[dis[id]]+dep[id]-2*dep[u]);
			for(int k=0;k<22;k++)
				if(book[dis[id]^(1<<k)])ans[u]=max(ans[u],book[dis[id]^(1<<k)]+dep[id]-2*dep[u]);
		}
		for(int j=L[to];j<=R[to];j++)book[dis[rk[j]]]=max(dep[rk[j]],book[dis[rk[j]]]);//préparation pour le prochain fils
	}
	if(!heavy)for(int j=L[u];j<=R[u];j++)book[dis[rk[j]]]=0;
}
int main()
{
	speed();
	// freopen("T3.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i]>>val[i];
		edge[fa[i]].pb(i);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)	
		cout<<ans[i]<<" ";
	return 0;
}

T4 [AGC049D] Séquence convexe

Solution brute-force

Cliquez pour voir le code``` #include <bits/stdc++.h> #define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define ll long long #define lid (rt<<1) #define rid (rt<<1|1) #define endl '\n' #define pb push_back using namespace std; const int N = 1e5+5,mod=1e9+7; ll ans=0;int n,m; unordered_map <int,unordered_map<int,unordered_map<int,unordered_map<int,int>>>> f; inline ll dfs(int now,ll cha,int sum,int ai) { if(sum>m)return 0; if(now==n+1) { // for(int i=1;i<=n;i++)cout<<p[i]<<" "; // cout<<endl; return (m==sum); } if(f[now][cha][sum][ai])return f[now][cha][sum][ai]; ll ans=0; for(int i=0;i<=m-sum;i++) { if(i-ai>=cha) { ans=(ans+dfs(now+1,i-ai,sum+i,i))%mod; } } return f[now][cha][sum][ai]=ans; } int main() { speed(); // freopen("in.in","r",stdin); // freopen("out.out","w",stdout); cin>>n>>m; ll ans=0; for(int i=0;i<=m;i++) { ans=(ans+dfs(2,-1e9,i,i))%mod; } cout<<ans; return 0; }

Les points bonus ont diminué, mais il y a progressé