#include <bits/stdc++.h> #define LL long long using namespace std; const int mod=1e9+7; LL f[305][305]; int main(){ int n, m; scanf("%d%d", &n, &m); f[0][0]=1; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ f[i][j]=f[i-1][j]+f[i-1][j-1]*(m-j+1...

题目链接：https://ac.nowcoder.com/acm/contest/4912/A思路：我们知道一定是断开直径上的边，不然最长航道就是直径了；如图：1-6是直径 #include <bits/stdc++.h> #define LL long long using namespace std; struct E{ int to, w; E(int a, int b){ to=a; w=b; } }; vector<E> e[1000005], Edge[1000005]; int k, d, pos1, pos2;...

题目链接：http://115.236.49.52:83/contest/1351A题:题解：假设n是奇数。n如果是偶数，翻转90度就可以了。 B题： #include <bits/stdc++.h> using namespace std; #define LL long long vector<vector<int> > v(50005); int a[50005]; LL f[50005][1005]; LL ans=0; void DFS(int u, int fa){ f[u][a[u]]=max(f[u][a[u]], 0ll);...

思路：分组背包，f[i][j]:前i组选择价值为j的方案数。 #include <bits/stdc++.h> #define LL long long using namespace std; int a[105][105]; LL f[105][10005]; int main(){ int n, k, m; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++){ scanf("%d", &a[i][0]); for(...

思路：可以证明n=X+m(X-1)+1 (m>=0),如果除去a[1].那么就是X+m(X-1)个数。因为每X个X^t的和=X^(t+1)，然后再从m(X-1)个中拿出X-1个数和X^(t+1)合成X^(t+2)一直到合成只有一个数X^(t+m+1)。t可以任意取。 #include <bits/stdc++.h> #define LL long long using namespace std; vector<int> v; int main(){ int n, x; scanf("%d%d", &n, &x); int m=(...

题意：有一棵树，有n个节点。让你分成n/2对。所有对之间的距离和最小。思路：我们尽量让每条边不重复经过。那么对于一棵子树v。和他的父亲节点u。还有之间的边权w。如果siz[u]%2==1那么v就和u连。ans+=w。如果siz[u]%2==0那么v和自己的子树连过了。不加w的贡献。 #include <bits/stdc++.h> using namespace std; #define LL long long vector<vector<pair<int , LL> > > v(10005); LL ans=0; int DFS(int ...

题目链接：https://ac.nowcoder.com/acm/contest/4853/E思路：树上启发式合并 #include <bits/stdc++.h> using namespace std; #define LL long long typedef pair<LL, LL> pll; LL n, k, a[100005]; vector<vector<int> > v(100005); map<int , pll > mp[100005];//子树到当前点距离 数量 权值 LL d[100005];//距离偏移 L...

#include<bits/stdc++.h> #define LL long long using namespace std; struct node{ LL to, w; }; vector<vector<node> > v(100005); LL f[100005]; void dfs(int u, int fa){ if(v[u].size()==1&&v[u][0].to==fa){ f[u]=1ll<<60; return ; } for(auto ...

题目链接：https://ac.nowcoder.com/acm/contest/82/B #include<bits/stdc++.h> #define LL long long using namespace std; LL a[1000005], s[1000005]={0}, f[1000005][25]; int main(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); for(int i=1; i<=n; i++){ scanf("...

思路一：树上倍增 //我们讲一讲这个是怎么逼近 //可以证明f[u][0]一定是f[father[u]][i]购买路径上的节点 //把一个查询作为一个节点。那么最后就是看从查询的u节点开始能最多跳多少次，并且不超过v节点。 //往上倍增寻找第一个比a[u]大的节点下面那个节点(他的父亲就是第一个比a[u]大的节点); int x=fa; for(int i=20; i>=0; i--){ //找到<=a[u]的第一个节点。那么这个节点肯定处于f[x][i]~f[x][i-1] //从f[x][i-1]开始区间长度为i-1。继续逼近 if(f[x][i]&...

单调队列的模板题。 #include <bits/stdc++.h> using namespace std; int a[1000010]; int q[1000010]; int main() { int n, k; scanf("%d%d", &n, &k); for(int i=1; i<=n; i++) scanf("%d", &a[i]); int l=1, r=0; for(int i=1; i<=n; i++){ while(l<=r&&q[l]+k&...

题目链接：https://ac.nowcoder.com/acm/contest/4853/D思路： #include <bits/stdc++.h> using namespace std; #define ll long long ll extend_gcd(ll a,ll b,ll&x,ll&y) { if(!b) { x = 1; y = 0; return a; } ll xt = 0, yt = 0; ll d = extend_gcd(b, a % b, xt, yt)...

题目链接：https://ac.nowcoder.com/acm/contest/4853/C #include <bits/stdc++.h> using namespace std; #define LL long long const int mod=1e9+7; char s[100005]; LL f[1005][1005], g[30]={0}; int main() { int n, k; scanf("%d%d", &n, &k); scanf("%s", s+1); f...

题目链接：https://www.luogu.com.cn/problem/P3332思路：我们区间修改用一个线段树维护就可以了。 #include <bits/stdc++.h> using namespace std; #define LL long long #define mid (l+r>>1) LL a[200000+10], sum[50000*4+10], laz[50000*4+10], rec[50000*4+10]; void BT(LL i, LL l, LL r){ sum[i]=laz[i]=rec[i]=0; if(l==...