原题：Misha, Grisha and Underground 原题大意给一棵树，在给给出3个点s，f，t问s到f与t到f经过相同的点有几个？输出最多的那种sft组合。 算法分析分情况讨论： f是s的祖先，t在f到s的外面 f是s的祖先，t在f到s的路径上 s->lca(f,s)->f，lca(s,t)在s->lca(f,s)上 s->lca(f,s)->f，lca(f,t)在lca(f,s)->f上 另一种取巧的做法是(lca(a,b) + lca(c,b) - lca(a,c))/2 程序代码#include <cstdio> #include <algorithm> #include <vector> using namespace std; #define pb push_back const int maxn=100005; int n, q; int fir[maxn],no[2*maxn],se[2*maxn],st[2*maxn][20],lo[200005],dep[maxn]; bool ...

原题：Okabe and El Psy Kongroo 原题大意从（0,0） 到（k，0），每个点可以到达右上，右，右下这三个点，但必须在c下方，0上方（包括0边界），问最终到达（k，0）有多少种方案。 算法分析dp，因为ci是一条与x轴平行的线段，所以从ai到ai+1的每一次的贡献都是一样的，可以用矩阵加速，c最多为15，所以不会超时 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; struct matrix{ ll val[16][16]; matrix(){memset(val,0,sizeof(val));} matrix operator*(const matrix & rhs)const{ matrix ret; for(int i = 0; i < 16; i++) for(int j = 0; j < 16; j++) for(int k = 0 ...

原题：Okabe and City 原题大意bfs搜索题，从左上角到右下角，必须走在有灯的格子里，如果要去的格子没有灯，可以暂时照亮任意一行或者一列，但必须之前站在原来就是有灯的格子里，同时花费为1，问是否能到达目的地，如果能输出最小花费，否则输出-1。 算法分析每次bfs都是在原始就是有灯的点之间移动（除了终点） 一行或者一列最多被照亮一次 当前点，与下一次可以到达的点的横坐标或纵坐标距离小于等于2 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)); #define pb push_back using namespace std; const int maxn = 10000 + 50; const int MAXN = (1<<30); typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; priority_queue<pii, vector< ...

原题：Exhausted? 原题大意N 个人，M把椅子，每个人都要有椅子坐，第i个人不能做[Li+1,Ri-1]里的椅子，最少要添多少椅子 算法分析贪心，先按左端点(L)排序，尽量先往左边垒，如果左边垒不下就垒右边，在已经垒好的集合里换一个右端点(R)最小的，最终还没有垒的全放在右端点。 程序代码#include <bits/stdc++.h> #define MN 210000 using namespace std; struct na{int l,r;}p[MN]; bool cmpl(na a,na b){return a.l==b.l?a.r>b.r:a.l<b.l;} priority_queue<int,vector<int>,greater<int> > q,_q; int n,m,mmh; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n >> m; mmh ...

原题：Built? 原题大意N个点求最小生成树，任意两点的权值为min(|x1-x2|,|y1-y2|) 算法分析按横坐标和纵坐标分别排序，然后记边，每个点只与相邻的点有关联。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100001; const ll mod = 1e9+7; int n, tot; struct coo { int x, y; int id; }c[maxn]; bool cmp1(coo a, coo b){ return a.x < b.x; } bool cmp2(coo a, coo b){ return a.y < b.y; } int dx[maxn],dy[maxn]; struct Edge{ int u, v; int cost; }e[maxn*2]; bool cmp(Edge a, Edge b){ return a.cost < b.cost ...