题目描述 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 输入格式 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N） 输出格式 所得的方案数 输入输出样例 输入 #1 3 2 输出 #1 16 分析 分析就不分析了吧，这题简直就是炮兵阵地的弱化版套上个背包啊。我直接贴代码吧。 代码如下 #include <bits/stdc++.h> #define N 10 #define LL long long using na...

题目描述 很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。 某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。 现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接...

题目描述 在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。 某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。 小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只移动到区间[i+l,i+r]中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。 每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大...

题目描述 有一个     a   ∗   b    a*b   a∗b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 输入格式 第一行为3个整数，分别表示a,b,n的值 第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。 输出格式 仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。 输入输出样例 输入 #1 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 输出 #1 1 说明/提示 问题规模 （1）矩阵中的所有...

Problem Description XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure—超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ), 但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。 Input 输入包括多个测试实例，每个实例包括： 第一行有2个正整数n (1<n&lt...

分析 我尼玛，这题目也太长了吧。 emmmm，先考虑70分做法，先       n   2     n^2   n2 处理每个点的最近和次近，每次询问手动模拟。 考虑优化，手动模拟，有点像爬树的过程，可以用倍增优化成      O   (   m   l   o   g   n   )    O(mlogn)   O(mlogn)。 问题在于，怎么处理出最近和次近呢？ 呃呃呃这还是陈老师教我的，用双向链表。 按高度从小到大排序后，从      1    1   1 扫到      n    n   n ，每次找到 编号为      i    i   i 的 左边和右边（左小右大），经过一通比较...

题   面   是   中   文   版    题面是中文版   题面是中文版     分析 个人认为这题非常考验对背包的理解！ 我尝试把这道题讲清楚吧。 首先见到这题第一感觉就是NOIP2006金明的预算方案。把每一个主件的所有组合记录下来，然后进行分组背包，代码如下： #include <bits/stdc++.h> #define N 100005 using namespace std; int f[N], cnt[55], w[55][1050], v[55][1050], p[11], q[11]; int main(){ int i, j, k, n, m, a, ...

Problem Description ZLGG found a magic theory that the bigger banana the bigger banana peel .This important theory can help him make a portal in our universal. Unfortunately, making a pair of portals will cost min{T} energies. T in a path between point V and point U is the length of the longest edge...

做这种题目呢，我们只需要分清楚每种操作的优先级就行了。在这里，我们规定优先级：区间赋值>区间乘>区间加。 也没啥好说而呀，我要咋办= =。 记得      q   u   e   r   y    query   query 和      u   p   d   a   t   e    update   update 时要 标记下饭(放就行了。 放代码吧。 代码如下 #include <bits/stdc++.h> #define LL long long #define lson l, m, rt<<1 #define rson m+1, r, rt&l...

Problem Description Recognizing junk mails is a tough task. The method used here consists of two steps:  Extract the common characteristics from the incoming email. Use a filter matching the set of common characteristics extracted to determine whether the email is a spam.  We want to extract the set...

Description Given a connected undirected graph, tell if its minimum spanning tree is unique. Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V’, E’), with the following properties:  V’ = V. T is connected and acyclic....

A 题目描述 Venn非常喜欢积木，所以这是一道和积木有关的题。 BLUESKY007和Venn在堆积木。Venn有一个     n   ×   m    n×m   n×m的场地，BLUESKY007有     q    q   q次操作。 BLUESKY007每次会选定一个矩形区域。具体的每次给一组     (    x   1    ,    y   1    )   ,   (    x   2    ,    y   2    )    (x_1,y_1),(x_2,y_2)   (x1​,y1​),(x2​,y2​)表示矩阵的左下角和右上角。在这个矩阵所覆盖的每一个格子里，累加一个...

定义      φ   (   n   )    \varphi(n)   φ(n)(读作fai)定义为[1, n]中与n互质的数的个数 显然，当      n    n   n 是素数时，      φ   (   n   )   =   n   −   1    \varphi(n) = n-1   φ(n)=n−1    欧拉函数的求法 关于      φ   (   n   )    \varphi(n)   φ(n) ，有几种不同的求法，视情况使用。  首先呢，我们需要知道一个性质。 两个数     a   ,   b    a, b   a,b 互质时，     φ   (   a...

题目描述 假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。 输入格式 输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。 输出格式 仅一行，包含一个数，即最少的涂色次数。 输入输出样例 输入 #1 AAAAA 输出 #1...