日常吐槽：最近比赛都是1到2道签到题加两道难度不等的好题，让人既不会消化不良也不会吃不饱，还挺享受的。（毕竟我不想回家做作业）咳我热爱OI
JZOJ 2019.01.27【NOIP提高组】模拟 B 组
-
5230 队伍统计
Description现在有n个人要排成一列，编号为1->n 。但由于一些不明原因的关系，人与人之间可能存在一些矛盾关系，具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐，最多不能违背k条矛盾关系（即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面）。问有多少合法的排列。答案对10^9+7取模。
Input
输入文件名为count.in。 第一行包括三个整数n,m,k。 接下来m行，每行两个整数u,v,描述一个矛盾关系(u,v)。 保证不存在两对矛盾关系(u,v),(x,y)，使得u=x且v=y 。
Output
输出文件名为count.out。 输出包括一行表示合法的排列数。
Sample Input
输入1：4 2 11 34 2输入2：10 12 32 66 101 74 16 12 47 61 410 410 95 98 10
Sample Output
输出1：18输出2：123120
Data Constraint对于30%的数据，n<=10
对于60%的数据，n<=15
对应100%的数据，n,k<=20,m<=n*(n-1)，保证矛盾关系不重复。
思路
通过数据范围可以想到状压，从前往后逐个确定排列。设?[?][?]表示当前选了?集合这些人，? 表示违反了多少矛盾关系。 暴力的转移复杂度是?(2 ?? 2?)。可以发现因为矛盾关系没有重复的，设 ???[?] 表示 要排在?后面的人的集合，那么每次只要求出? & ???[?]的1的个数（可预处理）就能快速更新?了，复杂度?(2^???)。
代码
#include#include using namespace std;int n, m, p, ans = 0, q[21], f[1048580][21], g[1048580], a[21], power[21];const int P = (int)1e9 + 7;void dfs(int x, int y, int z){ if (z > n) return; g[x] = y; dfs(x, y, z + 1); dfs(x + power[z], y + 1, z + 1);}int main(){ freopen("count.in", "r", stdin); freopen("count.out", "w", stdout); scanf("%d%d%d", &n, &m, &p); power[0] = 1; for (int i = 1; i <= n; i++) power[i] = power[i - 1] * 2; dfs(0, 0, 0); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); a[v] |= power[u - 1]; } f[0][0] = 1; for (int s = 1; s < power[n]; s++) for (int i = 1; i <= n; i++) if (power[i - 1] & s) for (int j = g[a[i] & s]; j <= p; j++) f[s][j] = (f[s][j] + f[s - power[i - 1]][j - g[a[i] & s]]) % P; for (int i = 0; i <= p; i++) ans = (ans + f[power[n] - 1][i]) % P; printf("%d\n", ans); fclose(stdin); fclose(stdout); return 0;}
-
5231. 序列问题
Description
Input
输入文件名为seq.in。
首先输入n。接下来输入n个数，描述序列 A。Output
输出文件名为seq.out。 输出一行一个整数代表答案。
Sample Input
70 35 40 45 56 65 94
Sample Output
66636
Data Constraint
对于30%的数据，n<=5000
对于60%的数据，n<=50000对于100%的数据，n<=500000,0<=A[i]<=10^9思路
一道分治好题，注意求区间的最大值/最小值/balabala都往双指针或线段树分治之类的方面想一想，必要时分类讨论，求每个数后面第一个XX的数可以用单调栈解决。
或
代码
#include#include #include #include using namespace std;const int N = 500010;const int P = (int)1e9 + 7;long long n, a[N], maxx[N], minn[N], s[N], ans = 0, x = 0, y = 0x3f3f3f;long long z[N], t = 0, z1[N], t1 = 0;long long sum[N][2];void find(long long l, long long r){ if (r < l) return; if (l == r) { ans = (ans + a[l] * a[l] % P) % P; return; } long long mid = (l + r) / 2; find(l, mid); find(mid + 1, r); long long mx = -1, mi = 0x7fffffff, u, v; sum[mid][0] = sum[mid][1] = s[mid] = 0; for (long long i = mid + 1; i <= r; i++) { mx = max(mx, a[i]); mi = min(mi, a[i]); sum[i][0] = sum[i - 1][0] + mx; sum[i][1] = sum[i - 1][1] + mi; s[i] = (s[i - 1] + mx * mi) % P; } mx = -1, mi = 0x7fffffff; long long uu, vv; for (long long i = mid; i >= l; i--) { if (a[i] > mx) mx = a[i], uu = i; if (a[i] < mi) mi = a[i], vv = i; u = min(r + 1, maxx[uu]); v = min(r + 1, minn[vv]); if (u < v) (ans += (s[r] - s[v - 1] + P) % P + (sum[v - 1][0] - sum[u - 1][0]) % P * mi % P + mx % P * mi % P * (u - mid - 1) % P) %= P; else (ans += mx % P * mi % P * (v - mid - 1) % P + (sum[u - 1][1] - sum[v - 1][1]) % P * mx % P + (s[r] - s[u - 1] + P) % P) %= P; } return;}int main(){ freopen("seq.in", "r", stdin); freopen("seq.out", "w", stdout); scanf("%lld", &n); memset(minn, 0x3f, sizeof minn); memset(maxx, 0x3f, sizeof maxx); for (long long i = 1; i <= n; i++) scanf("%lld", &a[i]); for (long long i = 1; i <= n; i++) { while (t && a[i] > a[z[t]]) maxx[z[t--]] = i; z[++t] = i; while (t1 && a[i] < a[z1[t1]]) minn[z1[t1--]] = i; z1[++t1] = i; } find(1, n); printf("%lld\n", ans); fclose(stdin); fclose(stdout); return 0;}
注意在算u和v中间一段的时候(sum[v - 1][0] - sum[u - 1][0]) % P * mi % P这个顺序不能反！！！两个大数相乘的时候要严格遵守u % P * v % P（u > v）的顺序！！！（否则你会和我一样调一个小时）
JZOJ 2019.01.28【NOIP提高组】模拟 B 组
-
4228. C
Description
在远古的YL国大地上，有n个祭坛，每个祭坛上四个方向写有“艄、毜、鼛、瓯”四个大字，其实这在YL国古代分别是“东、南、西、北”的意思。
YL国每年都要举行祈福消灾的祭祀活动，这个时候，每个祭坛都要在艄毜鼛瓯四个方向中选一个方向，祭坛将向这个方向发出一道隐形的光线，如果两个祭坛发出的光线相交，或者祭坛发出的光线经过了别的祭坛，则祭祀不仅不能成功还将遭到上天的惩罚，如果这些条件都满足则祭祀将成功，YL国在接下来的一年内将不会有任何灾难，甚至只会有人出生不会有人死亡。抽象的来说，如果我们以“艄”方向为x轴，“瓯”方向为y轴，建立笛卡尔坐标系，那么每个祭坛将会对应一个整点。每个点向上下左右四个方向之一连出一条射线，这些射线不能相交且射线不能经过除了发出点之外的其他点}。现在他们又到了祭祀活动的时候，他们想知道，有多少种方法选择每个祭坛的方向}，使得自己的祭祀能成功？输出方案数对998244353取模后的值}。Input
第一行一个正整数n。 接下来n行，第i + 1行两个整数x_i, y_i，表示第i个祭坛在题目中所述的坐标系下的坐标为(x_i, y_i)。
Output
输出一行一个整数，表示要求的方案数对998244353取模后的值。
Sample Input
输入1： 1 1 1 输入2： 2 1 1 2 2 输入3： 6 0 0 0 1 0 2 0 3 0 4 0 5 输入4： 5 1 3 -4 6 2 4 1 6 5 9 输入5： 10 175470546 566770243 501153312 923840801 -36922529 -888266785 -587403745 908979876 -483726071 -96937502 991096990 -783436017 766700568 -679180551 -601529754 815529478 961445805 303768338 245415738 325847411
Sample Output
输出1： 4 样例1解释：只有一个祭坛，显然四个方向都可以发射。 输出2： 14 样例2解释： 对于所有的4 × 4 = 16种情况中，只有两种不可行： 1号祭坛向上，2号向左。 1号向右，2号向下 输出3： 144 样例3解释： 最上面的祭坛可以向左中右三个方向连出射线，最下面的祭坛可以向右下左三个方向连出射线，中间4个祭坛可以向左右连出射线，方案数为3 × 2 × 2 × 2 × 2 × 3 = 144。 输出4： 117 样例4解释： 祭坛的位置如图所示：
输出5： 24341
Data Constraint
对于前30%的数据，n ≤ 9。
对于前40%的数据，n ≤ 18。对于前60%的数据，n ≤ 36。对于前100%的数据，n ≤ 54，对于所有i, j，有x_i ≠ x_j或y_i ≠ y_j，且|x_i|, |y_i| ≤ {10} ^ 9。思路
其实一开始看题解挺懵的来着，后来才明白了五维DP的意思。
设f[l][r][u][d][p]为方案数，l表示排序后第l号节点是目前可以向右发出射线的点中y坐标最大的（通俗地说就是最上面的）， r表示可以向右发出射线的点中最下面的，u表示可以向下发出射线的点中最上面的点，d是可以向上发出射线的点中最下面的点。然后结合代码就很容易理解思路啦，应该很容易想到DP，而且需要简化判定条件，把x坐标的限制通过排序取消，DP其实就是优化后的暴力啦。
用滚动数组搞一搞。
代码
#include#include #include using namespace std;const int N = 60, P = 998244353;struct node{ int x, y;}a[N];int n, ans = 0, boo, f[N][N][N][N][2];bool cmp(node u, node v) { return u.x < v.x || (u.x == v.x && u.y < v.y); }int Min(int u, int v) { return (a[u].y < a[v].y || !a[v].y) && a[u].y ? u : v; }int Max(int u, int v) { return (a[u].y > a[v].y || !a[v].y) && a[u].y ? u : v; }bool check(int i,int j,int k){ if (j == 1 && a[k].x == a[i + 1].x && a[k].y > a[i + 1].y) return false; if (j == 2 && a[k].x == a[i + 1].x && a[k].y < a[i + 1].y) return false; if (j == 3 && a[k].y == a[i + 1].y && a[k].x < a[i + 1].x) return false; if (j == 4 && a[k].y == a[i + 1].y && a[k].x > a[i + 1].x) return false; return true;}int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y); sort(a + 1, a + n + 1, cmp); int p = 0, q = 1; f[0][0][0][0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 1; j <= 4; j++) { boo = 0; for (int k = 1; k <= n; k++) if (!check(i, j, k)) { boo = 1; break; } if (boo) continue; for (int l = 0; l <= i; l++) for (int r = 0; r <= i; r++) for (int u = 0; u <= i; u++) for (int d = 0; d <= i; d++) if (f[l][r][u][d][p]) { if (j == 1 && (a[l].y < a[i + 1].y || !l)) f[l][r][Min(i + 1, u)][d][q] = (f[l][r][Min(i+1, u)][d][q] + f[l][r][u][d][p]) % P; if (j == 2 && (a[r].y > a[i + 1].y || !r)) f[l][r][u][Max(i + 1, d)][q] = (f[l][r][u][Max(i+1, d)][q] + f[l][r][u][d][p]) % P; if (j == 3 && ((a[u].y > a[i + 1].y && a[d].y < a[i + 1].y) || (!u && !d) || (a[u].y > a[i + 1].y && !d) || (a[d].y < a[i + 1].y && !u))) f[l][r][u][d][q] = (f[l][r][u][d][p] + f[l][r][u][d][q]) % P; if (j == 4) f[Max(i + 1, l)][Min(i + 1, r)][u][d][q] = (f[Max(i + 1, l)][Min(i + 1, r)][u][d][q] + f[l][r][u][d][p]) % P; } } p = (p + 1) & 1; q = (q + 1) & 1; for(int l = 0; l <= n; l++) for(int r = 0; r <= n; r++) for(int u = 0; u<=n; u++) for(int d = 0; d <= n; d++) f[l][r][u][d][q] = 0; } for(int l = 0; l <= n; l++) for(int r = 0; r <= n; r++) for(int u = 0; u<=n; u++) for(int d = 0; d <= n; d++) ans = (ans + f[l][r][u][d][p]) % P; printf("%d\n", ans); return 0;}
JZOJ 2019.01.29【NOIP提高组】模拟 B 组、2019.01.30【NOIP提高组】模拟 B 组
这两天题目都很水，可以用暴力加优化搞定，注意spfa的队列不能开小！！！最好开n方！！！还有打暴力的时候真的把能加的简直都加上去能赚很多分啊...