BearChild's Blog

方格取数 Time Limit: 5 Sec Memory Limit: 64 MB Description 在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。 Input 第一行一个数n；接下来n行每行n个数描述一个方阵 Output 仅一个数，即最大和 Sample Input 2 　1 2 　3 5 Sample Output 6 HINT n<=30 Main idea 给定一个矩阵，取了一个点就不能取上下左右的点了，求能取出的最大价值。 Solution 求的显然是最大权独立集，最大权独立集=总权-最小权覆盖集，对于最小权覆盖集我们用最小割来解。 由于取了一个点，不能取上下左右的点，即i±1 or j±1，那么显然是一个二分图，根据奇偶分类。 然后就是一个最小割的模型，我们左边的点向上下左右的点连边，容量为INF(必然不是割)，然后跑最大流即可。 Code 123456789101112131415161718192021222324252627282930313233343536373839 ...

人员雇佣 Time Limit: 20 Sec Memory Limit: 259 MB Description 作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。 然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j 是同一个）。 作为一个效率优先的人，小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗？ Input 第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数，表示Ei,j，即经理i对经理j的了解程度。（输入满足Ei,j=Ej,i） Output 第一 ...

能量魔方 Time Limit: 10 Sec Memory Limit: 64 MB Description 小C 有一个能量魔方，这个魔方可神奇了，只要按照特定方式，放入不同的 能量水晶，就可以产生巨大的能量。 能量魔方是一个 NNN 的立方体，一共用 N3 个空格可以填充能量水晶。 能量水晶有两种： ·一种是正能量水晶(Positive) ·一种是负能量水晶(Negative) 当这个魔方被填满后，就会依据填充的能量水晶间的关系产生巨大能量。对 于相邻两(相邻就是拥有同一个面)的两个格子，如果这两个格子填充的是一正一 负两种水晶，就会产生一单位的能量。而整个魔方的总能量，就是这些产生的能 量的总和。 现在，小 C 已经在魔方中填充了一些水晶，还有一些位置空着。他想知道， 如果剩下的空格可以随意填充，那么在最优情况下，这个魔方可以产生多少能量。 Input 第一行包含一个数N，表示魔方的大小。 接下来 N2 行，每行N个字符，每个字符有三种可能： P：表示此方格已经填充了正能量水晶； N：表示此方格已经填充了负能量水晶； ?：表示此方格待填充。 上述 N*N 行，第(i-1 ...

置换 Time Limit: 10 Sec Memory Limit: 256 MB Description 定义一个置换Р的平方Q为对[1,2,3,… ,n-1,n]做两次该置换得到的排列，即 $Q_i = P_{P_i} $ 现在已知一个置换的平方，求该置换。 Input 第一行一个整数n表示排列长度。 第二行n个整数表示所求置换的平方。 Output 若有解则输出一行n个数表示原置换(输出任意一个)，否则输出-1 Sample Input 4 　　2 1 4 3 Sample Output 3 4 2 1 HINT 1<=n<=10^6 Main idea 已知一个置换置换自己得到的序列，求这个置换。 Solution 显然是置换题。首先我们正向考虑，考虑一下一个置换置换自己会发生怎样的结果。 然后我们一波画图发现：如果一个轮换的长度是奇数，那么这个环所有点连边向后移一位；如果一个轮换的长度数偶数，那么就会拆解成两个长度一样的新轮换。 然后我们倒着来想，考虑如何合并。显然现在的轮换是奇数的话，我们将所有点连边向前移动一位。如果是偶数的话，再找一个长度和这个一样的轮换， ...

Crash的数字表格 Time Limit: 20 Sec Memory Limit: 259 MB Description 今天的数学课上，Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b，LCM(a, b)表示能同时被a和b整除的最小正整数。例如，LCM(6, 8) = 24。回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张NM的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i, j)。一个45的表格如下： 1 2 3 4 5 2 2 6 4 10 3 6 3 12 15 4 4 12 4 20 看着这个表格，Crash想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当N和M很大时，Crash就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题。由于最终结果可能会很大，Crash只想知道表格里所有数的和mod 20101009的值。 Input 输入的第一行包含两个正整数，分别表示N和M。 Output 输出一个正整数，表 ...

Gcd Time Limit: 10 Sec Memory Limit: 256 MB Description 给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的 　数对(x,y)有多少对. Input 一个整数N Output 如题 Sample Input 4 Sample Output 4 HINT 1<=N<=10^7 Solution 直接莫比乌斯反演即可。 然后对于这个式子，我们下界分块一下即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;typedef long long s64;const int ONE = 1e7+5;int T;int n,m;bool isp[ONE];int prime[664580],p_num;int miu[ONE ...

Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。 Input 第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k Output 共n行，每行一个整数表示满足要求的数对(x,y)的个数。 Sample Input 2 　2 5 1 5 1 　1 5 1 5 2 Sample Output 14 　3 HINT 100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000 Solution 显然可以考虑容斥，分为四块来做，剩下的就是： Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707 ...

YY的GCD Time Limit: 10 Sec Memory Limit: 512 MB Description 求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对k。 Input 第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M。 Output T行，每行一个整数表示第 i 组数据的结果 Sample Input 2 　10 10 　100 100 Sample Output 30 　2791 HINT T = 10000 　N, M <= 10000000 Solution Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<bits/stdc++.h>using namespace std;typedef long long s64;const in ...

Zap Time Limit: 10 Sec Memory Limit: 162 MB Description 对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。 Input 第一行包含一个正整数n，表示一共有n组询问。接下来n行，每行表示一个询问，每行三个正整数，分别为a,b,d。 Output 输出一个正整数，表示满足条件的整数对数。 Sample Input 2 　4 5 2 　6 4 3 Sample Output 3 　2 HINT 1<=n<= 50000, 1<=d<=a,b<=50000 Solution 我们运用莫比乌斯反演，然后推一下式子得到： 我们依旧对于下界分块求解即可。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include<bits/stdc+ ...

jzptab Time Limit: 10 Sec Memory Limit: 512 MB Description 求 $ \sum_{i=1}^{n} \sum_{j=1}^{m} lcm(i,j) $ Input 第一行一个 T 表示数据组数 接下来T行 每行两个正整数 表示N、M Output T行 每行一个整数 表示第i组数据的结果 Sample Input 1 　4 5 Sample Output 122 HINT T <= 10000 　N, M<=10000000 Solution 我们先根据 [Crash的数字表格] 运用莫比乌斯反演推到一个式子，然后优化求解： Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include<bits/stdc++.h>using namespace std;typedef ...