题解思路 用状态压缩dp 0表示未消失 1表示已经消失 题目代码 #include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 12, M = 1 << 10; int n; int a[N][N], f[M]; int main() { memset(a, 0, sizeof a); while (cin >> n && n) { for (i...

题目链接 滑雪与时间胶囊 题目思路 要先用dfs把从1能到的点筛选出来, 加边的时候不要else if 因为当H[a] == H[b]的时候, 是双向边然后用Kruskal算法求解 代码实现 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 10, M = 3e6 + 10; int e[M], ne[M], h[N], idx; int p[N], H[N]; int n, m; LL cnt, res; bool vis[N]; struct...

题目链接 挖沟 代码实现 #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, M = 5e5 + 10; struct Edge { int u, v, w; bool operator < (const Edge &W)const { return w < W.w; } }edge[M]; int p[N]; int n, m; int find(int a) { if (p[a] != a) p[a] = ...

题目链接 追债之旅 题目思路 用 dist[N][K] 来记录第几天到达第几个点, 用dijkstra算法来求值最后遍历 dist[n][i] 求最小值 代码实现 #include <bits/stdc++.h> using namespace std; typedef pair<int, pair<int, int> > PII; const int N = 1010, M = 20010; int e[M], ne[M], w[M], h[N], idx, dist[N][20]; int n, m, k, a[N], s[N], res; bo...

伪邻接表 struct ty{ int t,next; }edge[Max]; void insertedge(int x,int y) { edge[++m].t=y; edge[m].next=head[x]; head[x]=m; }

题目链接 拦截导弹 题目思路 第一问dp求解第二问dilworth定理Dilworth定理简单来说： 一个序列的最长递增子序列的长度 等于 这个序列的最长不递增（包含递减和相等）子序列的个数和； 相反， 一个序列的最长递减子序列的长度 等于 这个序列的最长不递减（包含递增和相等）子序列的个数和； 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=1e5; int a[Max],num=0,dp[Max],ans=0; int main() { while(cin>>a[++num]);...

题目链接 开心的金明 题目思路 01背包问题，把+v[i]换成了+v[i]*w[i] 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=30; int v[Max],w[Max]; int dp[Max][30005]; int main() { int n,m; cin>>m>>n; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i...

题目链接 过河卒 题目思路 动态规划，把原问题分解成子问题，找动态方程 代码实现 #include<bits/stdc++.h> #define int long long using namespace std; int dr[8][2]={{2,1},{2,-1},{-1,2},{1,-2},{-2,-1},{-1,-2},{1,2},{-2,1}}; const int Max=30; int n,m,x,y; int dp[Max][Max],mp[Max][Max]; signed main() { cin>>n>>m>>x&g...

题目链接 maze 题目思路 优先队列排列时间，bfs找最短时间 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=301; int n,m,q,sx,sy,ex,ey; int mp[Max][Max],vis[Max][Max]; struct Node{ int x,y,tm; bool operator < (const Node b) const{ return tm>b.tm; } }; int dr[4][2]={{1,0},{-1,0},...

const int Max=1e5; int fa[Max]; //父亲集合 int find(int a) { return fa[a]==a ? a:fa[a]=find(fa[a]); } //寻找 void merge(int a,int b) { int x=find(a),y=find(b); if(x!=y) fa[x]=y; } //合并集合

#include<bits/stdc++.h> using namespace std; #define ll long long bool check() { } int main() { ll l=0,r=1e9;//l 和 r是实际范围 while(l<r) { ll mid=(l+r+1)>>1; if(check()) l=mid; else r=mid-1; } return 0; }

const int Max=1e5; int vis[Max],prime[Max]; void Prime() { memset(vis,0,sizeof(vis)); memset(prime,0,sizoef(prime)); for(int i=2;i<Max;i++) { if(!vis[i]) prime[++prime[0]]=i; for(int j=1;j<=prime[0]&&prime[j]*i<Max;j++) { vis[i*pri...

题目链接 小木棍 题目思路 dfs的思想需要学习，努力剪枝减小时间复杂度当第一个木棍尝试dfs无法拼成后，直接break当最后一个尝试dfs无法拼成后，直接breaka[i]不行的话，等于a[i]的也不行 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=100; int n,nmax,sum,a[Max],vis[Max]; bool cmp(int a,int b) { return a>b; } bool dfs(int num,int len,int rest,int now) { ...

题目链接 建筑抢修 题目思路 和会议问题相似，先把结束时间从小到大排序，再用最大堆维护，比较前面维修所需时间与后面所需维修时间，从而实现贪心最大化 代码实现 #include<bits/stdc++.h> using namespace std; const int Max=1e6; struct node{ int t1,t2; }a[Max]; priority_queue<int,vector<int>,less<int> >q; bool cmp(node a,node b) { if(a.t2==b.t2) ...