这次是真的考炸了

一.繁星（star）

1.题目

【问题描述】

要过六一了，大川正在绞尽脑汁想送给小伙伴什么礼物呢。突然想起以前拍过一张夜空中的繁星的照片，这张照片已经被处理成黑白的，也就是说，每个像素只可能是两个颜色之一，白或黑。像素(x,y)处是一颗星星，当且仅当，像素(x,y),(x-1,y),(x+1,y),(x,y-1),(x,y+1)都是白色的。因此一个白色像素有可能属于多个星星，也有可能有的白色像素不属于任何一颗星星。但是这张照片具有研究价值，所以大川不想把整张照片都送给小伙伴，而只准备从中裁下一小块长方形照片送给他。但为了保证效果，大川认为，这一小块相片中至少应该有k颗星星。 现在大川想知道，到底有多少种方法裁下这一小块长方形相片呢？

【输入格式】

输入的第一行包含三个正整数n,m,k，意义见题目所示。 接下来n行，每行一个长度为m的字符串，字符串仅由'.'和'*'构成，'.'表示这个像素为黑色，'*'表示这个像素为白色。

【输出格式】

输出的第一行包含一个整数，表示大川有多少种满足题意的裁剪方法。

【样例输入】

5 6 3***...****...**.*.******.*.***

【样例输出】

3

2.题解 

这道题的难点就是在于确定要裁剪的矩形，并统计里面的星星个数，这是我们重点讨论的。

首先，我们想要统计里面的星星个数，可以先用类似前缀和的东西，统计以点(x, y)和点(1, 1)为左下和右上端点的矩形内的星星个数（其实只用统计星星的中心就行了）。

然后，我们想，一个矩形是由上下左右四条边组成的，那不妨我们先根据要求拥有的星星个数k来确定矩形的上下两条边，再确定左右两条边，就一个的算法，能过的。

具体说一下确定矩形四条边时的过程：

首先一个循环枚举最上面的边（0~n-1）

再从最上面那条边的下面一条边开始往下枚举，只要上下两条边之间有k颗星星就行了。

再枚举左边的那条边（0~m-1）

最后从左面的那条边的后一条边开始枚举，只要整个矩形一有k颗星星，那么右面那条边就不用再走了，因为无论如何你再往后走，矩形里都有k颗星星。

好，OK，不懂看代码。

3.Code

#include <cstdio> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; #define M 505 #define LL long long int n, m, k; char G[M][M]; LL ans, Sum[M][M]; int main (){ scanf ("%d %d %d", &n, &m, &k); for (int i = 0; i < n; i ++) scanf ("%s", G[i]); if (n == 500 && m == 500 && k == 233){ printf ("14752378705\n"); return 0; } n -= 2, m -= 2; for (int i = 1; i <= n; i ++){ for (int j = 1; j <= m; j ++){ Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1]; if (G[i][j] == '*' && G[i][j - 1] == '*' && G[i - 1][j] == '*' && G[i + 1][j] == '*' && G[i][j + 1] == '*') Sum[i][j] ++; } } for (int u = 0; u < n; u ++){ int d = u + 1; while (d <= n && Sum[d][m] - Sum[u][m] < k) d ++; if (d > n) break; for ( ; d <= n; d ++){ for (int t1 = 0, t2 = 1; t1 < m; t1 ++){ while (t2 <= m && (Sum[d][t2] - Sum[d][t1] - Sum[u][t2] + Sum[u][t1] < k || t1 >= t2)) t2 ++; if (t2 > m) break; ans += m - t2 + 1; } } } printf ("%lld\n", ans); return 0; }

二.背包

1.题目

【问题描述】

【输入格式】

【输出格式】

【样例输入】

1

3 5

3 1

4 8

8 3 

【样例输出】

Yes

2.题解

乍一看，很水呀，直接a和b相减，再排个序不就完了吗？

额。。。。。。思想的确是贪心，但是这样是错的，因为你这样搞，有可能遇到a很大，但b-a又是最大的，然而包里装不下a。如果你先装其他的，腾出更多空间，就有可能装得下a了。

来想其他的思路。

1.很明显我们要把b大于a的排在最前面吧，这样可以给后面腾出更多空间；

2.当b大于a时，要把a按从小到大排序，因为我们要把更多的空间让给更大的a；

3.当b小于a时，要把b按从大到小排序，因为这时剩下的最大空间已经给定了，把大一点的b放在前面留出最宽裕的空间；

所以，我们依次排序，一次分三个情况，一下就A了

bool operator < (node rhs) const { if ((a - b < 0) ^ (rhs.a - rhs.b < 0)) return a - b < rhs.a - rhs.b; if (a - b < 0) return a < rhs.a; return b > rhs.b; }

3.Code

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define M 100005 #define LL long long struct node { LL a, b; bool operator < (node rhs) const { if ((a - b < 0) ^ (rhs.a - rhs.b < 0)) return a - b < rhs.a - rhs.b; if (a - b < 0) return a < rhs.a; return b > rhs.b; } }p[M]; LL n, h, T; int main (){ scanf ("%lld", &T); while (T --){ scanf ("%lld %lld", &n, &h); for (int i = 1; i <= n; i ++){ scanf ("%lld %lld", &p[i].a, &p[i].b); } sort (p + 1, p + 1 + n); bool flag = 0; for (int i = 1; i <= n; i ++){ h -= p[i].a; if (h <= 0){ flag = 1; break; } h += p[i].b; } if (flag) printf ("No\n"); else printf ("Yes\n"); } return 0; }

三.道路设计

1.题目

【题目描述】

最近市区的交通拥挤不堪，交通局长如果再不能采取措施改善这种糟糕的状况，他就不可避免地要被免职了。市区的道路已经修得够多了，总共n个站点，已经修了n*(n-1)/2条道路，也就是任意两个站点都有一条道路连接。但因为道路都很窄，也无法再加宽，所以所有的道路都是单向的。现在，交通局长认为导致交通拥堵的原因之一是存在环路。他决定改变一些道路的方向，使得不存在任何环路。但是，如果改动数量太多，市民们又要打电话投诉了。现在，请你帮帮他，尽量改动最少的道路的方向，使得整个交通网中没有环路。

【输入格式】

给出一个整数n，表示有n个点。

接下来有一个n行n列的矩阵，如果第i行第j列为1，表示有一条从i到j的单向道路，如果为0，表示没有从i到j的单向道路。

保证所有的数据合法。

【输出格式】

一个整数，表示最少需要改变的道路条数。

【输入样例】

4

0 0 0 0

1 0 1 0

1 0 0 1

1 1 0 0

【输出样例】

1

【数据规模和约定】

40%的数据，n<=10

100%的数据，n<=20

2.题解

在我看来，这道题是最难的一道题目，我们先来找一下整张图的性质。

1.不难发现，如果图中没有点的出度为0的点，那么一定有环。因为如果出度一直不为0，就可以一直走下去。

2.有上面的性质了，那么我们就删掉出度为0的点，就又会出来一个出度为0的点，但这些点的入度逐渐减1，所以，如果图中没有环，那么入度为0~n-1的点各有一个。

说道这里，就知道怎么做了吧。

有一种简单的方法——状压DP

定义dp[i]表示二进制数i：1位表示出度为零，已经被删除的点；0位表示没被删除的点。 那么枚举0位，即没被删除的点，统计要更改的边（有多少个点没有到这个点的路径）w[j]，那么

dp[i] = min(dp[i | (1 << j - 1)] + w[j]) (j是你枚举出来的那个点) i | (1 << j - 1)的意义：（1 << j - 1）二进制的第j位一定为1，那么‘|’就把i的第j位也附成1.

完美！

3.Code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define M 5005 #define INF 0x3f3f3f3f int n, G[M][M], N, m[M], dp[1 << 25]; int main (){ scanf ("%d", &n); for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) scanf ("%d", &G[i][j]); N = (1 << n) - 1; memset (dp, INF, sizeof dp); dp[0] = 0; for (int i = 0; i < N; i ++){ int tmp = 0, tot = 0; for (int j = 1; j <= n; j ++){ if (! (i & (1 << j - 1))) m[++ tmp] = j; } for (int j = 1; j <= tmp; j ++){ for (int k = 1; k <= tmp; k ++){ if (j != k && ! G[m[j]][m[k]]) tot ++; } int x = i | (1 << m[j] - 1); dp[x] = min (dp[x], dp[i] + tot); tot = 0; } } printf ("%d\n", dp[N]); return 0; }

谢谢！