原题：Partial Sum 原题大意给定一个长度为n的数列A，初始一个变量cnt = 0，每次在0~n里选一个了l和r，然后求出A（l+1）~A（r）的和，将和的绝对值减去常数C，并且加到cnt上，这样的操作最多有m次，求cnt的最大值。 算法分析 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, C; int a[100005]; ll sum[100005]; bool cmp(ll a, ll b){ return a > b; } int main(){ //freopen("input.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); while(cin >> n >> m >> C){ for(int i = 1; i <= n; i++) ...

原题：Determinant 原题大意给出n × (n-1) 的矩阵，要求从左到右，依次去掉一列后，剩余行列式的值，同时答案mod1e9+7。 算法分析仔细分析后发现是求伴随矩阵的原值（不要求根据行和列的奇偶改变符号），根据方阵的公式：由逆矩阵和行列式值的乘积，可以求出伴随矩阵。 所以先将矩阵补成n × n的（随机补全排除偶然性，否则可能有其他其他情况，比如不存在逆矩阵，行列式值为0），我补的是最下面一行（哪一行这个也任意）。关于求逆矩阵，先将原矩阵变成n ×（2n），并且右边是单位矩阵，将左边的变成单位矩阵，右边的就是逆矩阵。 所以这里用到了高斯消元，但是由于是mod运算，所以不能用double，加减乘要mod，除就是乘以逆元，最后得到的矩阵乘以行列式的值，最后一列就是我们要求的答案，并且根据行列的和的奇偶将值改回来，所以依次输出最后一列的值。 程序代码#include <bits/stdc++.h> using namespace std; const int maxn = 202; typedef long long ll; const ll mod = 1e9+7; ...

原题：逃离迷宫II 原题大意小Hi被坏女巫抓进里一间有N x M个格子组成的矩阵迷宫。 有些格子是小Hi可以经过的，我们用’.’表示；有些格子上有障碍物小Hi不能经过，我们用’#’表示。小Hi的起始位置用’S’表示，他需要到达用’T’表示的格子才能逃离迷宫。 麻烦的是小Hi被坏女巫施了魔法，他只能选择上下左右某一个方向，沿着这个方向一直走，直到遇到障碍物或者迷宫边界才能改变方向。新的方向可以是上下左右四个方向之一。之后他还是只能沿着新的方向一直走直到再次遇到障碍物或者迷宫边界…… 小Hi想知道他最少改变几次方向才能逃离这个迷宫。 算法分析bfs，起初想用dfs，发现如果终点不在边界就不好判断了，所以改用bfs，但是由于考虑不周导致被卡了两天，这种题还是要细心一点。 程序代码#include <bits/stdc++.h> using namespace std; const int maxn = 505; char g[maxn][maxn]; int vis[maxn][maxn]; int n, m; int sx, sy, ex, ey; int d[4][2]= ...

原题：Max Score 原题大意给一个数列A，每次从里面取一个数，然后用已经取出的数之和去mod这个数，得到的值加入score里，并且把这个数加入到已经取出的集合里，直到取完所有数，问score最大是多少？ 算法分析本想贪心来写发现完全错了，看了题解才知道用dp，题中给出的n最大为20，所以很容易用位运算进行状态压缩，然后用记忆型dp来写，题解中给出了转移方程：f(s) = max(f(subset(s,i))) + (∑ e) mod ai;subset(s,i)，指除了ai以外包含s里所有元素的集合这里的需要枚举i，e属于subset(s,i)。 转移方程详见题解： https://www.hackerrank.com/contests/rookierank-3/challenges/max-score/editorial 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; int n; ll a ...

原题： Culture Conference 原题大意首先看一下什么是最小支配集： http://www.cnblogs.com/Ash-ly/p/5775934.html 本题中也类似，给一棵树，n个人编号0~n-1，0为CEO，其余每个人都有一个直接上司，现在问题是有些人比较懒（用0表示），所以这些人需要去参加会议（估计是批斗大会什么的），当这些人回来后，他们就变得勤奋努力，认真踏实……，而且带动与他相连的结点也进入一样的状态（如果本来就是1，就没有什么变化，否则由0变成1），现在问最少喊几个人去开会，能使所有人变得不懒惰。（注意！CEO永远不会懒惰，且没有上司） 算法分析本题是一个很好的模版题，填补了我对于最小支配集的空缺，官方题解也很详细。 最小支配集的算法： http://www.cnblogs.com/Ash-ly/p/5783877.html 官方题解： https://www.hackerrank.com/contests/rookierank-3/challenges/culture-conference/editorial 程序代码#include &l ...