2019.07.08【NOIP提高組】模拟 A 組

T1：這題不難，但要發現一些性質。

首先我們設f[i]表示n=i時的答案，那麼不難推出可以由f[i-i%p[j]]轉移到f[i]，但是這個轉移的複雜度是O(nm)的，需要優化。

我們考慮倒推：既然n能推到n-n%p[i]，那麼我們也可以用k推到k+r（注意要滿足p[i]|k且1<=r<=p[i]）。

進而我們可以發現：設p0為整除k的且在給出範圍中的最大素數，那麼k能推到的範圍就是k+1~k+p0-1，即可以用f[k]去更新f[k+1~k+p0-1]。

由此我們就可以證明f的單調不遞減性。因為如果一個f[j]能更新f[i+1]，那麼f[j]必能更新f[i]，是以f[i]<=f[i+1]，得證。

再進一步，我們發現f是一個分段函數，且相鄰段之間的差為1。這也就是說f從1開始肯定是一段1、一段2、一段3……

既然這樣，那麼我們考慮用目前段的端點l、r來求出下一段的端點l1、r1。首先顯然l1=r+1，而r1=max(i+p0-1),(l<=i<=r)，即r1為l~r能更新到的最遠點。

但是我們如果直接枚舉i進行質因數分解的話會逾時，是以我們可以枚舉給出的素數，然後通過計算出l~r中最大的素數的倍數來求r1。

T2：正解很簡單，但是很巧妙。

首先從左上角開始bfs，求出與左上角顔色相同的聯通塊，然後把聯通塊反色，在做一邊。每次bfs時ans加1，一直bfs到所有有顔色的點都被周遊到為止。

證明很好想，這裡就不多講了。

總結：這一題主要運用到倒推的思想（包括第一題也是）。以後遇到這種十分棘手題可以多考慮一下如何從最後的狀态往前推。

T3：神奇的線頭dp。

我們先轉化一下題目：既然每一個e都要話2的代價去删除它，那麼我們不妨把e全從原序列中去除，然後把每一個e後面的點設為必經點。而線頭dp就是說在一個數軸中要連線使路徑進過一些必經點（太難表達了）。

對于這一道題，設f[i][j]表示第i個點前有一條線直接從它的前面連到後面一個字母為j的位置去的最小代價。

g[i][j]表示第i個點前面有一條直線連到i的後面一個字母為j的位置去，然後從那個位置走到i前面某一個，再從那個“某一個位置”連到一個i後面的字母為k的位置上去的最小代價。

轉移時我們要注意分類讨論j是否等于a[i]的情況，并且在求f[i][j]是如果i是必經點的話就不能直接把i給跳了。

至于初始值，就是f[0][a[1]]=0。而答案就是f[n][c]=1，c為一個不存在的字母（可設為11）.這樣求答案的意思是最後把線連向某個處于最後位置的不存在的字母，這樣做是為了友善求答案。最終ans=f[n][c]+se*2-2。se*2表示的是“每一個e都要話2的代價去删除它”，-2為的是減去連向不存在的字母的代價。

詳細解釋看https://www.cnblogs.com/Itst/p/10339605.html。

最後貼一下代碼（轉移方程有10條，十分複雜）：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define MAXN 70010
#define MAXV 12
using namespace std;

int a[MAXN],bz[MAXN],f[MAXN][MAXV],g[MAXN][MAXV][MAXV],n,se;
char a1[MAXN];
int main()
{
int i,j,k,s;
scanf("%d\n%s",&n,a1);
for(i=1;i<=n;i++)a[i]=a1[i-1]-'a'+1;
for(i=1;i<=n;i++)
	if(a[i-1]==5)bz[i]=1;
s=0;
for(i=1;i<=n;i++)
	if(a[i]!=5){s++;a[s]=a[i];bz[s]=bz[i];}
se=n-s;n=s;
n++;a[n]=11;bz[n]=bz[n-1];
memset(f,0x7f,sizeof(f));
memset(g,0x7f,sizeof(g));
f[0][a[1]]=0;
for(i=1;i<=n;i++)
	for(j=1;j<=11;j++)
	{
		if(j!=a[i]&&bz[i]==0)f[i][j]=min(f[i][j],f[i-1][j]);
		f[i][j]=min(f[i][j],f[i-1][a[i]]+2);
		if(j!=a[i])f[i][j]=min(f[i][j],g[i-1][a[i]][j]);
		f[i][j]=min(f[i][j],g[i-1][a[i]][a[i]]+2);
		for(k=1;k<=11;k++)
		{
			if(j!=a[i])g[i][j][k]=min(g[i][j][k],f[i-1][j]+3);
			g[i][j][k]=min(g[i][j][k],f[i-1][a[i]]+5);
			if(j!=a[i]&&k!=a[i])g[i][j][k]=min(g[i][j][k],g[i-1][j][k]+1);
			if(k!=a[i])g[i][j][k]=min(g[i][j][k],g[i-1][a[i]][k]+3);
			if(j!=a[i])g[i][j][k]=min(g[i][j][k],g[i-1][j][a[i]]+3);
			g[i][j][k]=min(g[i][j][k],g[i-1][a[i]][a[i]]+5);
		}
	}
printf("%d",f[n-1][11]+se*2-2);
}