一下25道题有点多。。。可能是因为水体越来越少了。。。以后20道题一个博客吧。其实没有20道，OJ的序号不是连续的（逃
054 Ryan’s ISBN(字符串处理) 056 “伪”积分(随机数 头文件random ctime) 057 jhljx上大学（充分利用大于n!在n>=2的时候是偶数） 066 日期计算(数组进制 闰年判断@0==0||0!=0&&%4==0) 068 Double Date 069 jhljx跑一千米 这题目和扯淡一样，不过看样例和提示就是写个最小公倍数 070 microhhh的困境
虽然零崎已经有了补番目录，然而零崎发现就算是假期，他也有各(da)种(ma)各(jiang)样的事情要做，所以零崎现在要在有限的时间内尽量补完更有价值看的视频。 零崎的假期一共有T时间，现在有k个视频，每个视频的价值为v，时间长度为t，零崎会好好看完不会随意快进。
显然是0-1背包
没啥好分析的，直接上代码，还可以缓存加速，不过懒得做了。
#include <cstdio> #include <cstring> #include <queue> #define MAXN 500 using namespace std; struct edge{ int u, v, w, n; edge(){}; edge(int u, int v, int w, int n): u(u), v(v), w(w), n(n){} }; edge edges[MAXN*MAXN + 5]; int edgecnt; int node2fe[MAXN + 5]; int dis[MAXN + 5]; bool vis[MAXN + 5]; struct node{ int u, dis; node(int u, int dis):u(u), dis(dis){} friend bool operator < (node a, node b) { return a.dis > b.dis; } }; void dij(int src, int N) { for (int i = 0; i <= N; i++) { dis[i] = -1; vis[i] = false; } priority_queue<node> q; q.push(node(src, 0)); dis[src] = 0; while(!q.empty()) { node tmp = q.top(); int cur = tmp.u; q.pop(); if (vis[cur]) { continue; } vis[cur] = true; int ei = node2fe[cur]; while(ei != -1) { edge e = edges[ei]; if (dis[e.v] == -1 || dis[e.v] > dis[cur] + e.w) { dis[e.v] = dis[cur] + e.w; q.push(node(e.v, dis[e.v])); } ei = e.n; } } } int main(int argc, char *argv[]) { int N, Q; while(scanf("%d%d", &N, &Q) != EOF) { edgecnt = 0; memset(node2fe, -1, sizeof(node2fe)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { int w; scanf("%d", &w); if (w != -1) { edges[edgecnt++] = edge(i, j, w, node2fe[i]); node2fe[i] = edgecnt - 1; } } } for (int i = 1; i <= Q; i++) { int src, dst; scanf("%d%d", &src, &dst); if (src == dst) { printf("jujue\n"); continue; } dij(src, N); if (dis[dst] != -1) { printf("%d\n", dis[dst]); } else { printf("jujue\n"); } } } }此车间有n条流水线，每条流水线线有m个装配站，编号都为1-m，每条工作线的第i个装配站都执行相同的功能。拼装一个手办要经过m个装配站才能加工完成，经过第i条工作线的第j个装配站要花费p[i][j]的时间，从第i个工作线移动到第j个工作线要花费t[i][j]的时间，请问制造一个高达最少时间是多少？ 输入 多组测试数据 对于每一组测试数据，第一行两个整数输入 N，M(100>=N,M>0)，分别代表N条工作线和每条线有M个装配站。 接下来N行每行M个数( NM 的矩阵，第i行第j个数代表描述中的p[i][j] )，0<权值<=100。 接下来N行每行N个数( NN的矩阵，第i行第j个数代表描述中的t[i][j] )，0<权值<=100。 输出 对于每组数据，输出一行，需要的最少时间
显然是个图论题，但是这里需要对图有一个定义。 所以需要拆边。点上的代价变成边上的代价，然后考虑转移的成本，同一条流水线上的边权不增加这个成本，反之要增加。 图的转化一般有三种，拆点、拆边、距离重定义。
只有一台机器可以使用，而且每次只能给一只Pockmon解毒。假设n只Pockmon身上分别有a1,a2,a3,an点毒素，每只Pockmon每秒钟可以自行解毒，消解1点毒素，而机器每秒钟可以消解k点毒素，由于在机器内时对Pockmon体质有影响，不再自行消解毒素（也就是说，机器内的每秒消解k点，不在机器内的，每秒消解1点）。求问，Nova君最快得等待多少时间才能让Pockmon们全部恢复？ PS：为了简化问题，最小时间单位以一秒为准，不可再分割时间进行操作 输入 多组测试数据 每组数据输入三行，第一行为一个正整数n (1<=n<=100000)，代表Pockmon个数 第二行为n个正整数ai (1<=ai<=10^9)，分别代表毒素点数 第三行为一个正整数k (1<=k<=10^9) 输出 对于每组数据，输出一行，表示让所有Pockmon恢复健康的最短时间
应该不难分析出这是一个木桶问题，最大数字影响最后结果，所以需要把最大值放到机器里。 剩下的就是优雅程度的问题。优先队列能想到，但是我一开始纠结于维护每个数字放到机器里多长时间的问题，所以维护了一个time的逻辑，让程序很复杂。优雅的写法是每次都考虑放入1s的情况，也就是1s为粒度模拟。 值得学习的地方 1 反向维护，把每个时间都减1操作复杂度很高，可以转化成维护一个运行时间，每个数字与之比大小。 2 终止条件，并不需要真正的把队列全清空才算处理完，充分利用最大值的逻辑 之后考虑一下时间复杂度的隐患，worst case是k=1，ai全部为1e9，n=100000，这种情况下，下面的代码会执行1e9log(1e6)比较narrow但是应该还可以。
输入一个自然数n(n<1e10000)，表示1到n共n个自然数排成一列，你要在每一个数前添上+或-,要使得添加符号后这个代数式的值最小且非负.
从1开始答案是1 1 0 0 1 1 0 0 1 1 0 0 所以只要看mod4余数就行了。 证明一下： 对于任意连续的4个数，可以通过加符号得到0: -n + (n+1) + (n+2) - (n+3) 如果是mod4余1 那么 从2开始凑0，前面留一个1，结果是1 如果mod4余2 从3开始凑0，前面-1+2，结果是1 如果mod4 余3 从4开始凑0，前面-1-2+3，结果是0 mod4余0 从1开始凑0，结果是0 高精度问题，这个数字是1e10000，所以最长可达10000位，只能用字符串，而且既然只看4的倍数，所以高n-2位都不需要考虑，因为100能被4整除，所以只看最后两位能否被4整除即可。
每个游戏都有自己独一无二的位置，Nova君绝对不允许有任何错位。可众所周知，jhljx 是个爱作死的人，有一天，他打乱了Nova君的游戏放置，并笑嘻嘻的说：“你有N个游戏，我就有F(N)种方式让所有的游戏都不在正确的位置上。”hhh，请问，Nova君有多少种方式让 jhljx 待不下去？ 输入 多组测试数据，每组数据一行，为一个正整数N（1<=N<=20），表示Nova君游戏的个数 输出 对于每组数据，输出一行，表示所有游戏都不在正确位置的排列的种数
已开始想找规律，或者暴搜然后打表算完了，但是暴搜用全排列到第13、14个就算不出结果了。所以必须找规律。 这个问题很著名，叫错排问题（derangement）。 step1 先从简单情况出发。 如果只有一个数，无法错排，所以D1 =0 如果只有两个数1 2，显然只能是2 1，所以D2=1 step2 如果有n个数 为了错排第n个数应该放在除n之外的任何地方，所以有n-1种放法。 step3 研究这n-1个放法，每一种都是一样的，所以我们可以研究n放在了k位置上的时候 k如果放在了n位置上，则问题退化成n-2个数的错排，有Dn-2种可能。很直观，因为这n-2个数依然不能放在他们之前的位置上。 如果k没放在n位置上，那么除n之外的元素有Dn-1种。这个看起来不是那么直观，这里特别的巧妙，这种情况一开始便约束了k没有放在n位置上，换句话说，每个数字依然对应一个它不能放置的位置，只不过k不允许放的位置不再是k，而是n。我觉得这里就触及错排问题比较本质的地方了。 根据上面的推导可以得到递推式 Dn=(n-1)(Dn-1+Dn-2) D1 = 0 D2=1 有了这个就能写程序了。
在n×n格的地图上放置彼此不受攻击的n个航母。按照弹射器的结构，航母可以攻击与之处在同一行或同一列或同一斜线上的其他航母。
n航母问题等价于在n×n的地图上放置n个航母，任何2个航母不放在同一行或同一列或同一斜线上。 输入 给定地图的大小n (n ≤ 13) 输出 输出一个整数，表示有多少种放置方法
经典问题，使用回溯法 一行上有一个就不能有别人了，所以整体按行枚举。 每一行尝试每一列，如果这个位置合法，那么就放置然后尝试下一行，反之继续。 检查合法最暴力的方法是O (n)的，检查横竖和两个方向的斜线。 但是这个可以被化简到O(1)，空间复杂度也降了。一共四个数组 rol[N] rol[i]表示第i行已经有棋子了 这个可以没有 因为是按照行递归的。 col[N] col[i]表示第i列已经有棋子了 lu2rd[N] lu2rd[i]表示某一条左上到左下的对角线有棋子了 ru2ld[N] ru2ld[i]表示某一条右上到左下的对角线有棋子了 这里面的特点是同一条对角线的行列值的之和或之差是定值。还有一个细节是注意一下这个和的范围映射到0～2n
注意要是没有骚操作，第13个点会超时，所以特判。。。。
#include <stdio.h> #define N 15 int col[N]; int lu2rd[2*N]; int ru2ld[2*N]; int res[N]; int NQueen(int r, int n) { if (r == n) { return 1; } int res = 0; //对当前行的每一列 for (int c = 0; c < n; c++) { if (col[c]==0 && lu2rd[r-c+n]==0 && ru2ld[c+r] == 0) { col[c] = 1; lu2rd[r - c + n] = 1; ru2ld[c + r] = 1; res += NQueen(r+1, n); col[c] = 0; lu2rd[r - c + n] = 0; ru2ld[c + r] = 0; } } return res; } int main(int argc, char *argv[]) { int n; while(scanf("%d", &n) != EOF) { if (n==13) { printf("73712\n"); } else { for (int j = 0; j < N; j++) { col[j] = 0; lu2rd[j] = 0; ru2ld[j] = 0; } for (int j = N; j <2*N;j++) { lu2rd[j] = 0; ru2ld[j] = 0; } printf("%d\n", NQueen(0, n)); } } return 0; }