D:飞机降落（全排列）

#include<iostream>
#include<cstring>
using namespace std;const int N = 12;
int n;
struct node{int t, d, l;  //t为此飞机的最早降落时间 d为盘旋时间 l为降落所需时间
}p[N];
bool st[N];//DFS求全排列模型
bool dfs(int u, int last){if(u == n) return true;for(int i = 0; i < n; i ++ ){int t = p[i].t, d = p[i].d, l = p[i].l;if(st[i]) continue;if(t + d >= last){  //最晚降落时间t+d大于等于上一层的降落结束时刻st[i] = true;if(dfs(u + 1, max(last, t) + l)) return true; //当前层的最早降落结束时刻为max(last,t)+lst[i] = false;}}return false;
}int main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T; cin >> T;while(T -- ){cin >> n;for(int i = 0; i < n; i ++ ){int t, d, l; cin >> t >> d >> l;p[i] = {t, d, l};}memset(st, 0, sizeof(st));cout << (dfs(0, 0) ? "YES" : "NO") << endl;}return 0;
}

E:接龙数列（最长上升子序列）

要求使得数列变成接龙数列的最少删除个数，相当于求该数列的最长接龙子数列的长度，用总长度减去最长接龙长度即为最少删除个数。

定义dp[i][j]为前i个数中，以数字j结尾的最长接龙数列的长度。

设第i个数的首位数字是a，末位数字是b。则dp[i]中相对于dp[i−1]
可能发生变化的只有dp[i][b]

, 因为第i个数只可能加到一个以a结尾的接龙数列中，使得这个接龙数列长度加1并且结尾数字变成b.

所以状态转移方程为dp[i][b] = max(dp[i - 1][b], dp[i - 1][a] + 1)

而显然第一维可以优化掉。

#include <bits/stdc++.h>
using namespace std;
int dp[10];int main () {int n, mx = 0; cin >> n;for (int i = 0; i < n; i ++) {string s; cin >> s;int a = s[0] - '0', b = s.back() - '0';dp[b] = max(dp[b], dp[a] + 1), mx = max(mx, dp[b]);}cout << n - mx << endl;return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],dp[N];
int t[11];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;dp[i]=1;a[i]=x%10;while(x>9)x/=10;b[i]=x;
}int maxx=0;for(int i=1;i<=n;i++)
{dp[i]=max(dp[i],t[b[i]]+1);t[a[i]]=max(t[a[i]],dp[i]);maxx=max(dp[i],maxx);
}cout<<n-maxx;
}

F:岛屿个数（双重bfs）

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m;
string a[N];
bool v[N][N],use[N][N];
int dx[]={-1,1,0,0,-1,-1,1,1},dy[]={0,0,-1,1,-1,1,-1,1};
void bfs_col(int x,int y)//染色 
{v[x][y]=1;queue<int>qx,qy;qx.push(x),qy.push(y);while(!qx.empty()){x=qx.front(),y=qy.front();qx.pop(),qy.pop();for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<0||xx>=n||yy<0||yy>=m||v[xx][yy]||a[x][y]=='0')continue;v[xx][yy]=1;qx.push(xx),qy.push(yy);}}
}
bool bfs_out(int x,int y)//判断能否出去 
{for(int i=0;i<n;i++)for(int j=0;j<m;j++)use[i][j]=0;queue<int>qx,qy;qx.push(x),qy.push(y);use[x][y]=1;while(!qx.empty()){x=qx.front(),qx.pop();y=qy.front(),qy.pop();if(x==0||x==n-1||y==0||y==m-1)return true;for(int i=0;i<8;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<0||xx>=n||yy<0||yy>=m||a[xx][yy]=='1'||use[xx][yy])continue;qx.push(xx),qy.push(yy),use[xx][yy]=1;}}return false;	
}
void solve()
{cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];for(int j=0;j<m;j++)v[i][j]=0;	}int ans=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++)if(!v[i][j]&&a[i][j]=='1'){bfs_col(i,j);if(bfs_out(i,j))ans++;}}cout<<ans<<endl;
}
int main()
{int T;cin>>T;while(T--)solve();return 0;
}

H:整数删除（堆+双链表）

感觉是比较典的题目，用优先队列维护，存入值和下标，再用一个数组cnt累计每个下标增加的和，当弹出最小的值下标为 i 时，如果此时cnt[i]不等于0，说明它实际的值需要加上cnt[i]，我们将其增加后再放回优先对列，注意需要清空cnt[i]。如果此时cnt[i]等于0，那我们就成功弹出当前最小元素，这时需要将其前一个元素和后一个元素值增加，我们需要模拟链表去记录每个元素的前后元素是谁，pre[i]表示下标为i的上一个元素是谁，ne[i]表示下标为 i 的下一个元素是谁，直到堆的元素个数只剩n-k时结束循环。不难想象，堆元素的出入次数是线性的。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long LL;
typedef pair<LL,int> PII;
LL cnt[N]; 
int pre[N],ne[N];
int n,k;
void solve()
{priority_queue<PII,vector<PII>,greater<PII>>q;cin>>n>>k;for(int i=1;i<=n;i++){LL v;cin>>v;q.push({v,i});pre[i]=i-1;ne[i]=i+1;}int g=n-k;while(q.size()>g){auto p=q.top();q.pop();LL v=p.first,i=p.second;if(cnt[i]){q.push({v+cnt[i],i});cnt[i]=0;}else{int l=pre[i],r=ne[i];cnt[l]+=v;cnt[r]+=v;pre[r]=l;ne[l]=r;}}vector<LL> a(n+1);for(int i=0;i<g;i++){auto p=q.top();q.pop();a[p.second]=p.first+cnt[p.second];}for(int i=1;i<=n;i++)if(a[i])cout<<a[i]<<" ";
}
int main()
{solve();return 0;
}