2019.09.08【NOIP提高組】模拟 A 組

T1：這是一道規律題，但是我沒有想出來。

首先我們發現所有的家庭一定是繞圈放置時答案才是最優的，由此我們可以手玩幾個小資料來推出規律。

正解的規律是對于一個正六邊形：我們第一次可以花費1的代價擴充它的一條邊，産生k-1個新的格子（k代表邊長）；第二次可以花費1的代價擴充它的第二條邊，這時會産生新的k個格子；以此類推，第三、第四、第五條邊都是花費1的代價産生k個新的格子，但是第六條邊時花費1的代價産生k+1個新的格子。

是以我們首先找到一個面積不超過n的最大的正六邊形，然後枚舉要擴充它的幾條邊才能容下n個家庭，這樣就可以算出答案了。

代碼如下：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long

ll n,ans;
int main()
{
//freopen("wall.in","r",stdin);
//freopen("wall.out","w",stdout);
ll k,s;
scanf("%lld",&n);
k=1;s=0;
while(3*k*(k-1)+1<=n)k++;k--;
s=3*k*(k-1)+1;ans=6*k;
if(s>=n){printf("%lld",ans);return 0;}
s=s+k-1;ans++;
if(s>=n){printf("%lld",ans);return 0;}
s=s+k;ans++;
if(s>=n){printf("%lld",ans);return 0;}
s=s+k;ans++;
if(s>=n){printf("%lld",ans);return 0;}
s=s+k;ans++;
if(s>=n){printf("%lld",ans);return 0;}
s=s+k;ans++;
if(s>=n){printf("%lld",ans);return 0;}
s=s+k+1;ans++;
if(s>=n){printf("%lld",ans);return 0;}
}
           

T2：這題我當場就想出正解了，但是還有一個細節沒有處理好。

首先我們從f[i]想i連邊，邊權為D[f[i]]-C[i]，然後我們發現整個圖就是一個環套樹。接着我們就可以用類似拓撲的方法搞定樹的答案（即選最大的邊乘上a[f[i]]）。然後一個環上一定要删掉一條邊，那麼我們就選擇删掉收益最小的那一條邊，然後環就變成了一棵樹，用樹的方法處理就好了。

注意：1、自環的情況。

2、我們其實可以把所有的物品取剩隻有1個時再來割環邊，我比賽時就錯了這個地方。

T3：這一題不難，但是考思維。

首先我們枚舉p串，這裡注意p串的長度一定要是n的約數，是以枚舉的複雜度是O(n*logn)的。

接着我們可以取件dp，一開始設f[i][j][k]表示i~j這一個區間，去掉所有完整的串之後剩下的幾個部分比對到p的第k位是否可行。

然後我們又可以發現其實k=(j-i+1)*len（len是p的長度），這個想一想就清楚了。是以現在隻剩下i、j兩維。

接着我們就枚舉l表示k+1位比對的位置，這時又注意到l=j+1+x*len（這個想一想也可以知道為什麼），是以l的枚舉是O(logn)的。

綜上所述，總的時間複雜度是O(n*logn*n^2*logn)=O(n^3*(logn)^2)。有點大，但是優化一下能過。