中间停了一段时间
回家休息几天以及一部分老师布置的暑假作业
8.29
P3389 【模板】高斯消元法
这不就是线性代数里面的解线性方程组么
原来这个叫高斯消元
逐项遍历
每次找非0，然后把这一行交换到对角的位置
然后和其他方程组进行加减消元，使得这一项的系数都为0
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 110;
double a[N][N];
int n;int main()
{scanf("%d", &n);_for(i, 1, n)_for(j, 1, n + 1)scanf("%lf", &a[i][j]);_for(j, 1, n){int p = j; //注意从i开始 上面的不能动了 找一个系数非0的行 while(!a[p][j] && p <= n) p++;if(p == n + 1) //找不到无解{puts("No Solution");return 0;}swap(a[p], a[j]); //交换到对角的位置_for(i, 1, n) //消元if(i != j){double t = a[i][j] / a[j][j];_for(k, 1, n + 1) a[i][k] -= t * a[j][k];}}_for(i, 1, n) printf("%.2f\n", a[i][n + 1] / a[i][i]);return 0;
}P4035 [JSOI2008]球形空间产生器（高斯消元）
列个个方程，作差可得线性方程组
然后高斯消元即可
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 15;
double a[N][N], p[N][N];
int n;void build()
{scanf("%d", &n);_for(i, 1, n + 1)_for(j, 1, n)scanf("%lf", &p[i][j]);_for(i, 1, n)_for(k, 1, n) {double x1 = p[i][k], x2 = p[i + 1][k];a[i][k] = 2 * (x2 - x1);a[i][n + 1] += x2 * x2 - x1 * x1;}
}void Gauss()
{_for(j, 1, n){int p = j; while(!a[p][j] && p <= n) p++;swap(a[p], a[j]); _for(i, 1, n) if(i != j){double t = a[i][j] / a[j][j];_for(k, 1, n + 1) a[i][k] -= t * a[j][k];}}_for(i, 1, n) printf("%.3f ", a[i][n + 1] / a[i][i]);
}int main()
{build();Gauss();return 0;
}P4111 [HEOI2015]小 Z 的房间（矩阵树定理 + 行列式计算）
这题看了半天思路，看了题解原来是矩阵树定理模板题……
有时不要死磕一道题太久，可能是没学过的算法
首先可以转化成图，打破一个墙看作连上一条边，两两之间只有一条道路说明是树
所以就转化成无向图的生成树计数问题
用到矩阵树定理，这是一个结论
方法是构造一个矩阵，点数是n的话，就构造一个n * n的矩阵
a[i][i]的值为点i的度数
a[i][j]就是i与j有多少条直接相连的边的相反数
这样的矩阵去掉任意一行和一列，其行列式的值就是答案
怎么求行列式的值呢
转化成对角矩阵来求
怎么转化成对角矩形
需要一列一列来消使得为0，方法是辗转相除法，可以看代码
不要看到紫题就畏惧，很多题就是高级算法的应用罢了，并没有很高的思维难度
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 1e9;
const int N = 15;
int id[N][N], cnt, n, m;
ll a[N * N][N * N];
char s[N][N];void add(int x, int y) { a[x][x]++; a[y][y]++; a[x][y]--; a[y][x]--; }int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%s", s[i] + 1);_for(i, 1, n)_for(j, 1, m)if(s[i][j] == '.')id[i][j] = ++cnt;_for(i, 1, n)_for(j, 1, m){if(s[i][j] == '.' && s[i][j + 1] == '.') add(id[i][j], id[i][j + 1]);if(s[i][j] == '.' && s[i + 1][j] == '.') add(id[i][j], id[i + 1][j]);}ll ans = 1;cnt--;_for(j, 1, cnt - 1)_for(i, j + 1, cnt)while(a[i][j]){ll t = a[j][j] / a[i][j];_for(k, 1, cnt) a[j][k] = (a[j][k] - t * a[i][k]) % mod;_for(k, 1, cnt) swap(a[i][k], a[j][k]);ans *= -1;}_for(i, 1, cnt) ans = ans * a[i][i] % mod;printf("%lld\n", (ans + mod) % mod);return 0;
}8.30
P2447 [SDOI2010]外星千足虫（高斯消元解异或方程组）
又是新的知识点
首先要进行一个转化，我自己想的时候不知道怎么处理这个奇偶
方法是转化成异或，把奇偶转化成异或
那么这道题就成了解异或方程组了
方法是高斯消元，思想和解线性方程组类似
但是注意n个方程不一定能解出n个未知数
在解的时候，每次是寻找最靠上的不为0的系数，这个时候其实就是贪心策略，满足了题目要求的最少的方程数
然后因为只涉及0和1，所以可以用bitset优化，常数大大优化，大概是除以32
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e3 + 10;
bitset<N> b[N];
int n, m, ans, flag;void Gauss()
{_for(j, 1, n){int p = j;while(!b[p][j] && p <= m) p++;if(p == m + 1) { flag = 1; return; }ans = max(ans, p);swap(b[p], b[j]);_for(i, 1, m)if(i != j && b[i][j])b[i] ^= b[j];}
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, m)_for(j, 1, n + 1){int x; scanf("%1d", &x);b[i][j] = x;}Gauss();if(flag) puts("Cannot Determine");else{printf("%d\n", ans);_for(i, 1, n) puts(b[i][n + 1] ? "?y7M#" : "Earth");}return 0;
}P3810 【模板】三维偏序（陌上花开）（cdq分治）
学一学cdq分治
这题是三维偏序
首先对数组排序保证第一维
然后用类似归并排序的方法，对当前的区间的左右区间分别对第二维进行排序
这样前两维的都满足了
然后就用两个指针遍历两个区间就可以了，注意要清空树状数组
注意有相同的元素，而这时cdq分治只处理左区间对右区间的贡献
所以要合并相同的元素
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int M = 2e5 + 10;
const int N = 1e5 + 10;
struct node
{int a, b, c, cnt, ans;
}t[N], s[N];
int f[M], k[N], m, n;int lowbit(int x) { return x & -x; }void add(int x, int p)
{for(; x <= m; x += lowbit(x))f[x] += p;
}int sum(int x)
{int res = 0;for(; x; x -= lowbit(x))res += f[x];return res;
}bool cmp1(node x, node y)
{if(x.a != y.a) return x.a < y.a;if(x.b != y.b) return x.b < y.b;return x.c < y.c;
}bool cmp2(node x, node y)
{if(x.b != y.b) return x.b < y.b;return x.c < y.c;
}void cdq(int l, int r)
{if(l == r) return;int mid = l + r >> 1;cdq(l, mid); cdq(mid + 1, r);sort(s + l, s + mid + 1, cmp2);sort(s + mid + 1, s + r + 1, cmp2);int i = l, j = mid + 1;for(; j <= r; j++){while(s[i].b <= s[j].b && i <= mid){add(s[i].c, s[i].cnt);i++;}s[j].ans += sum(s[j].c);}_for(t, l, i - 1) add(s[t].c, -s[t].cnt); //注意这里清空不是整个左区间，左区间未必遍历完
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%d%d%d", &t[i].a, &t[i].b, &t[i].c);sort(t + 1, t + n + 1, cmp1);int same = 0, p = 0;_for(i, 1, n){same++;if(t[i].a != t[i + 1].a || t[i].b != t[i + 1].b || t[i].c != t[i + 1].c){s[++p] = t[i];s[p].cnt = same;same = 0;}}cdq(1, p);_for(i, 1, p) k[s[i].ans + s[i].cnt - 1] += s[i].cnt;_for(i, 0, n - 1) printf("%d\n", k[i]);return 0;
}P3157 [CQOI2011]动态逆序对（cdq分治）
这题要转化一下
把删去的时间看作一维，这样就有3个维度，转化成三维偏序问题
其实就是求每一次删除少了多少个逆序对
也就是用cdq分治求出每一个数的贡献，这样来统计答案
那么把时间当作一维，一个数删除所产生的贡献是在它前面且大于大且时间大于它
或者在它后面且小于它且时间大于它
这就是三维偏序问题了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
struct node
{int val, time, ans;
}a[N];
int f[N], id[N], n, m;int lowbit(int x) { return x & -x; }void add(int x, int p)
{for(; x <= n; x += lowbit(x))f[x] += p;
}int sum(int x)
{int res = 0;for(; x; x -= lowbit(x))res += f[x];return res;
}bool cmp1(node x, node y) { return x.val < y.val; }
bool cmp2(node x, node y) { return x.val > y.val; }
bool cmp3(node x, node y) { return x.time < y.time; }void cdq(int l, int r)
{if(l == r) return;int mid = l + r >> 1;cdq(l, mid); cdq(mid + 1, r);sort(a + l, a + mid + 1, cmp1);sort(a + mid + 1, a + r + 1, cmp1);int i = l, j = mid + 1;for(; i <= mid; i++){while(a[j].val <= a[i].val && j <= r){add(a[j].time, 1);j++;}a[i].ans += sum(m + 1) - sum(a[i].time);}_for(k, mid + 1, j - 1) add(a[k].time, -1);sort(a + l, a + mid + 1, cmp2);sort(a + mid + 1, a + r + 1, cmp2);i = l, j = mid + 1;for(; j <= r; j++){while(a[j].val <= a[i].val && i <= mid){add(a[i].time, 1);i++;}a[j].ans += sum(m + 1) - sum(a[j].time);}_for(k, l, i - 1) add(a[k].time, -1);
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) {scanf("%d", &a[i].val);id[a[i].val] = i;a[i].time = m + 1;}_for(i, 1, m){int x; scanf("%d", &x);a[id[x]].time = i;}ll res = 0;_for(i, 1, n){res += sum(n) - sum(a[i].val);add(a[i].val, 1);}memset(f, 0, sizeof f);cdq(1, n);sort(a + 1, a + n + 1, cmp3);_for(i, 1, m){printf("%lld\n", res);res -= a[i].ans;}return 0;
}8.31
hdu 7101（双指针）
补一下ccpc网络赛的题目
首先就是求1到12的lcm，然后注意对于一个单词，一个字母要出现一次就总的串就有n个
还要注意是两倍的循环
所以字符的总长度是lcm * n * 2
然后注意到范围越大肯定越优，满足单调性，所以可以用双指针
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 110;
int cnt[30], p[N], n, m;
string s[N];int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }int main()
{int T; cin >> T;while(T--){memset(p, 0, sizeof p);memset(cnt, 0, sizeof cnt);int sum = 1;cin >> n;_for(i, 1, n) {cin >> s[i];sum = lcm(sum, s[i].size());}sum *= 2 * n;string str;_for(t, 1, sum / n)_for(i, 1, n){str.push_back(s[i][p[i]]);p[i] = (p[i] + 1) % s[i].size();}m = 0;_for(i, 1, n)for(auto x: s[i])if(++cnt[x - 'a'] == 1)m++;memset(cnt, 0, sizeof cnt);int l = 0, r = -1, cur = 0, ans = 1e9;while(l < sum){while(cur != m){if(++r == sum) break;if(++cnt[str[r] - 'a'] == 1) cur++;}if(r == sum) break;ans = min(ans, r - l + 1);if(--cnt[str[l] - 'a'] == 0) cur--;l++;}printf("%d\n", ans);}return 0;
}hdu 7108（前缀和）
用前缀和转化一下 遇到U就加1 遇到D就减一
那么如果一个区间端点的值相同就ok了
那就弄两个前缀和，每一个位置是一个二元组
用map统计就行
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int a[N], b[N], n;
map<pair<int, int>, int> mp;
string s;int main()
{int T; cin >> T;while(T--){cin >> n >> s;s = " " + s;_for(i, 1, n){a[i] = a[i - 1];b[i] = b[i - 1];if(s[i] == 'U') a[i]++;if(s[i] == 'D') a[i]--;if(s[i] == 'L') b[i]++;if(s[i] == 'R') b[i]--;}long long ans = 0;mp.clear();_for(i, 0, n){ans += mp[make_pair(a[i], b[i])];mp[make_pair(a[i], b[i])]++;}printf("%lld\n", ans);}return 0;
}hdu 7111
这题很骚
我当时卡在不知道怎么迅速找出最大的m mod p
正解是反过来考虑，考虑一个数x最远能转移到多少
一个数如果是某些模数的倍数
比如p
那么x可以转移到[x + 1, x + p - 1]
可以求出每一个数最远可以转移到的距离，标记一下
之后逆序遍历，把标记取min，就可以求出每个数最往前可以从哪里转移过来
这样就可以求所有的答案了
求最大素因子可以直接枚举质数的倍数，复杂组nloglogn
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef unsigned long long ull;
const int N = 2e6 + 10;
int ans[N], maxp[N], k[N], p[N], pre[N], n, m;
ull f[N];int main()
{f[0] = 1;_for(i, 1, 2e6) f[i] = f[i - 1] * 23333;int T; scanf("%d", &T);while(T--){memset(maxp, 0, sizeof maxp);memset(k, 0x3f, sizeof k);scanf("%d%d", &n, &m);_for(i, 1, m) scanf("%d", &p[i]);_for(i, 1, m)for(int j = p[i]; j <= n; j += p[i])maxp[j] = max(maxp[j], p[i]);_for(i, 1, n)if(maxp[i]){int t = min(i + maxp[i] - 1, n);k[t] = min(k[t], i);}ull LCM = 1;_for(i, 1, m){LCM *= p[i];if(LCM >= n + 1) {LCM = n + 1;break;}}_for(i, LCM, n) ans[i] = 0;int mi = 1e9;for(int i = LCM - 1; i >= 1; i--){mi = min(mi, k[i]);pre[i] = mi;}int mx = 0;_for(i, 1, m) mx = max(mx, p[i]);_for(i, 1, mx - 1) ans[i] = 1;_for(i, mx, LCM - 1) ans[i] = ans[pre[i]] + 1;ull res = 0;_for(i, 1, n) res += ans[i] * f[n - i];printf("%llu\n", res);}return 0;
}9.2
昨天打了积分赛
hdu 1299（约数个数）
做过类似的题目，但比赛中没做出来
卡在一开始的推公式这里，没有想到要令y = n + k
理解为往n靠吧，因为输入只有n
之后可以推出x = n * n / k + n
所以答案就是n的平方的约数个数
求约数个数就质因数分解，然后幂次加1相乘
注意质因数分解只用预处理根号n内的质数，如int范围内预处理1e5就行了
如果有大于1e5的质数，最后一定是单独剩下一个大质数，特判一下就好了
平方就照常按照n来处理，然后幂次全部乘以2就行
#include <cstdio>
#include <vector>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
vector<int> p;
bool vis[N];
int n;void get_prime()
{_for(i, 2, 1e5){if(!vis[i]) p.push_back(i);for(int x: p){if(x * i > 1e5) break;vis[x * i] = 1;if(i % x == 0) break;}}
}int main()
{get_prime();int T, kase = 0; scanf("%d", &T);while(T--){scanf("%d", &n);ll ans = 1;for(int x: p)if(n % x == 0){int cnt = 0;while(n % x == 0){cnt++;n /= x;}ans *= cnt * 2 + 1;}if(n > 1) ans *= 3;printf("Scenario #%d:\n", ++kase);printf("%lld\n\n", (ans + 1) / 2);}return 0;
}9.3
P4170 [CQOI2007]涂色（区间dp）
区间dp很套路化，这种区间合并的可以用区间dp
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 60;
int dp[N][N], n;
char s[N];int main()
{scanf("%s", s + 1);n = strlen(s + 1);_for(i, 1, n) dp[i][i] = 1;_for(len, 2, n)_for(i, 1, n){int j = i + len - 1;if(j > n) break;dp[i][j] = 1e9;_for(k, i, j - 1){if(s[k] == s[k + 1] || s[i] == s[j]) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] - 1);else dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);}}printf("%d\n", dp[1][n]);return 0;
}