早上藍橋杯大寄，算是交了300元買了件T恤qaq

1.簽到：https://ac.nowcoder.com/acm/contest/83687/A

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int main()
{int a,b;cin>>a>>b;if(a==b) cout<<"p";else{if(a<b){if(a==1&&b==3) cout<<"b";else cout<<"a";}else{if(a==3&&b==1) cout<<"a";else cout<<"b";}}
}

2.貪心：https://ac.nowcoder.com/acm/contest/83687/B

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{cin>>a>>b;cout<<min(min(a+5*b,5*a+3*b),11*a);
}

3.DP以及優化（妙題）：https://ac.nowcoder.com/acm/contest/83687/E

我們令dp[i]表示1--i最少刪多少次，易得狀態轉移方程：

dp[i]=min(dp[j-1]+1)(a[i]==a[j])

但是復雜度還是超了，于是我們維護最小值，令mn[i]表示值為i時的位置的前一個的dp的最小值。

于是dp[i]=mn[i]+1,現在我們考慮維護mn，假如一個值是第一次出現也就是mn[i]為無窮，那么此時i給mn帶來的影響也就是當后面的出現i時，它可以作為一段被刪的區間+1（但是前提是dp[i-1]要有解，否則也是白搭），而假如不是第一次出現，那么它的影響也就是優化當前的mn。

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500010],dp[500010],mn[500010];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];memset(dp,-1,sizeof(dp));memset(mn,0x3f,sizeof(mn));dp[0]=0;for(int i=1;i<=n;i++){if(mn[a[i]]!=0x3f3f3f3f) dp[i]=mn[a[i]]+1;if(dp[i-1]==-1) continue;if(mn[a[i]]==0x3f3f3f3f){mn[a[i]]=dp[i-1];}else{mn[a[i]]=min(mn[a[i]],dp[i-1]);}}cout<<dp[n];
}

4.曼哈頓距離轉化成切比雪夫距離：https://ac.nowcoder.com/acm/contest/83687/F

先看公式：

這樣就可以轉換成類似于激光炸彈的題了，但是有幾點注意：

1.轉換后的圖上有幾個點是原圖上沒有的，我們需要去驗證。

2.會出現負數，要進行平移。

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
const int NN=6004;
int f[NN][NN];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int x,y,r;scanf("%d%d%d",&x,&y,&r);int nx=x+y,ny=x-y+3000;f[max(1,nx-r)][max(1,ny-r)]^=1;f[min(6000,nx+r+1)][max(1,ny-r)]^=1;f[max(1,nx-r)][min(6000,ny+r+1)]^=1;f[min(6000,nx+r+1)][min(6000,ny+r+1)]^=1;}int ans=0;for(int i=1;i<=6000;i++){for(int j=1;j<=6000;j++){f[i][j]=f[i-1][j]^f[i-1][j-1]^f[i][j-1]^f[i][j];int x=(i+j-3000)/2,y=(i-j+3000)/2;if(f[i][j]&&((i+j)%2==0)&&x>0&&x<=n&&y>0&&y<=n) ans++;}}cout<<ans;
}