D:飞机降落（全排列）
#include#includeusing 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 = 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 > t >> d >> l;p[i] = {t, d, l};}memset(st, 0, sizeof(st));cout <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 using namespace std;int dp[10];int main () {int n, mx = 0; cin >> n;for (int i = 0; i > 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;}#includeusing 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>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）
#includeusing 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;queueqx,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=n||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;queueqx,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=n||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>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++;}}coutT;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时结束循环。不难想象，堆元素的出入次数是线性的。
#includeusing namespace std;const int N=5e5+10;typedef long long LL;typedef pair PII;LL cnt[N]; int pre[N],ne[N];int n,k;void solve(){priority_queue<PII,vector,greater>q;cin>>n>>k;for(int i=1;i>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 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<