#include <iostream> #include <cstring> using namespace std; const int N = 1010; int n; int h[N], e[N], ne[N], idx; int si[N];//每个节点对应的子树大小 int mi = 1e9, id;//mi表示最大子树中的最小子树 id表示重心编号 void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;} //求出每个节点对应的子树大小和父子关系 int dfs(int x, in...

#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 10010, M = 2e5 + 10; int n, m, s, t; int h1[N], e1[M], ne1[M], idx1; int h2[N], e2[M], ne2[M], idx2; bool st[N]; int d[N]; void add(int a, int b) { e1[idx1] = b, ne1[idx1] = h1[a], h1[a] = id...

#include <iostream> #include <cstring> #include <queue> #include <vector> using namespace std; const int N = 1e5 + 10; int n, m; int h[N], e[N], ne[N], idx; int din[N]; vector<int> ans; template<class T> inline void read(T& res) { char ch; bool flag = false; w...

矩阵快速幂模板题 #include <iostream> using namespace std; const int N = 110; int n, m, p; int a[N][N], b[N][N], c[N][N]; int main() { cin >> n >> m; for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) cin >> a[i][j]; cin >> p; for (int i = 0; i < m; i ++) for (in...

思路： 由于数据范围过大，所以递推已经无法满足要求，尝试将递推式的运算转换为矩阵的运算 用 fif_ifi​ 来表示斐波那契数列的第 iii 项 递推式：fi=1×fi−1+1×fi−2f_i = 1\times f_{i-1} + 1 \times f_{i-2}fi​=1×fi−1​+1×fi−2​ 矩阵运算：F=(f1f2)(0111)1=(f2f3)F=\begin{pmatrix} f_1 & f_2 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} ^ 1= \begin{pmatrix} ...

没有思路直接上代码 #include <iostream> #include <cstdio> #define lson u << 1 #define rson u << 1 | 1 using namespace std; const int N = 1e5 + 10; int n, m; int a[N]; struct Node { int l, r; int lazy;//0表示全变0 1表示全变1 2表示全变取反 -1表示什么都不干 int sum[2], ma[2], pre[2], suf[2]; //sum[i]总共用多少个i m...

x, y, d = 0, 0, 0 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] n = int(input()) a = [[0] * n for _ in range(n)]#必须要改变一下定义数组的方式 for i in range(1, n * n + 1): a[x][y] = i tx, ty = x + dx[d], y + dy[d] if tx < 0 or tx >= n or ty < 0 or ty >= n or a[tx][ty] != 0: d = (d + 1) % 4 tx, ty = x + dx[d],...

#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10, INF = 0x3f3f3f3f; int n, m; int f[N];//f[i]表示跳到i号石板上所需的最小次数 int main() { cin >> n >> m; memset(f, 0x3f, sizeof f); f[n] = 0; for (int i = n; i <= m; i ++) { if (f[i] == INF) continue;//可写可不写 for (int j = 2; j ...

Mr. Young's Picture Permutations #include <iostream> #include <cstring> using namespace std; const int N = 31; typedef long long LL; int n; int s[10]; LL f[N][N][N][N][N];//光看样例应该也能猜到会爆int //f[s1][s2][s3][s4][s5]表示第i排放了第si个人时的合影方案数量 int main() { while (~scanf("%d", &n) && n) ...

牛牛的最美味和最不美味的零食 #include <iostream> using namespace std; const int N = 1e6 + 10, INF = 0x3f3f3f3f; int n, m, a[N]; struct Node { int l, r; int cnt, ma, mi; }tr[N << 2]; template <class T> inline void read(T &res) { char ch; bool flag = false; while((ch = getchar()) < '0' || c...

区间和 结构体 #include <iostream> using namespace std; const int N = 1e6 + 10; typedef long long LL; struct Node { int l, r; LL sum; }tr[N * 4];//线段树一般要开4倍数组 int n, m, a[N]; //通过两个子节点来相应调整父节点 void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } //建树 void build(int u, i...

[ZJOI2007]矩阵游戏 #include <iostream> #include <cstring> using namespace std; const int N = 210; int n; bool g[N][N], st[N]; int match[N]; bool find(int x) { for(int i = 1; i <= n; i ++) { if(g[x][i] && !st[i]) { st[i] = true; if(!match[i] || find(match[i])) { match[i] = x; retur...

题目数据太水了也，pushdown写错也能过，pushdown按理来说应该先乘后加的，没想到先加后乘居然也能过，贴一组样例 他人提交里面的代码慎用，有些连我这组样例都过不去，不要拿过来就用 5 6 1 2 3 4 5 1 1 5 2 1 5 3 1 5 2 4 1 5 2 1 1 4 2 2 3  先加后乘算出来是 15 55 40 596  这明显是错的 正确结果应该是先乘后加 15 55 28 100  本题的难点就在于pushdown  结构体 #include <iostream> #define ls u << 1 #define rs u << ...