December 2015 – Page 3

LA 3708 Graveyard

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题4.

思路

大概是构造题。

跟白书不太一样的解法，贪心地把两种方案的一个顶点对在一起，然后逐个检查，取两种方案的最小角度差，加在一起，就是答案。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int main(){
    double a,b;
    while(scanf(" %lf %lf",&a,&b) != EOF){
        double sumdeg = 0;
        for(int i = 0; i <= a; i++){
            double deg = 360.0*(double)i/a;
            while(deg > 360.0/(a+b)){
                deg -= 360.0/(a+b);
            }
            sumdeg += min(deg,abs(360.0/(a+b)-deg));
        }
        double ans = sumdeg*10000.0/360.0;
        printf("%.4lf\n",ans);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int main(){

double a,b;

while(scanf(" %lf %lf",&a,&b) != EOF){

double sumdeg = 0;

for(int i = 0; i <= a; i++){

double deg = 360.0*(double)i/a;

while(deg > 360.0/(a+b)){

deg -= 360.0/(a+b);

}

sumdeg += min(deg,abs(360.0/(a+b)-deg));

}

double ans = sumdeg*10000.0/360.0;

printf("%.4lf\n",ans);

}

return 0;

}

UVa 11300 Spreading the Wealth

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白第一章例题3

思路

大概是个构造题。

解决的方法是把整个题转化成一个方程组，令每个人手里的初始金币数量为Ai(已知)，送出数量Xi,受付数量Yi,最终每个人金币数量M(已知)，这样得到由若干形如Ai-Xi+Yi=M方程组成的方程组，当所有方程形式一样时，考虑逐个联立消去未知量，最终得到了关于X1和Xi的若干等式（注意到Xi和Yi+1的相等关系），我们的目标是令Xi之和最小，我们把所有Xi加在一起，就得到了一个仅关于X1的和式。

这个和式的形式可以几何表示是求数轴上一个点，使得其与若干已知点距离之和最短，这个问题的解取在中位数，这样本问题就可以解决了。（中位数是解的想法在白书上有详细的证明，使用反证法）

综合来看，本体需要适当转化，数学变形，数形结合。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

long long n;
long long c[1000005];

int main() {
    while(scanf(" %lld",&n) != EOF) {
        unsigned long long m = 0;
        for(int i = 1; i <= n; i++) {
            scanf(" %llu",&c[i]);
            m += c[i];
        }
        m /= n;
        for(int i = 1; i <= n; i++) {
            c[i] -= m;
            c[i] += c[i-1];
        }
        sort(c,c+n);
        long long rf;
        if(n % 2) {
            rf = c[n/2];
        } else {
            rf = (c[n/2] + c[n/2-1])/2;
        }
        long long res = 0;
        for(int i = 0; i <= n-1; i++) {
            res += abs(c[i] - rf);
        }
        printf("%lld\n",res);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

long long n;

long long c[1000005];

int main() {

while(scanf(" %lld",&n) != EOF) {

unsigned long long m = 0;

for(int i = 1; i <= n; i++) {

scanf(" %llu",&c[i]);

m += c[i];

}

m /= n;

for(int i = 1; i <= n; i++) {

c[i] -= m;

c[i] += c[i-1];

}

sort(c,c+n);

long long rf;

if(n % 2) {

rf = c[n/2];

} else {

rf = (c[n/2] + c[n/2-1])/2;

}

long long res = 0;

for(int i = 0; i <= n-1; i++) {

res += abs(c[i] - rf);

}

printf("%lld\n",res);

}

return 0;

}

UVa 11729 Commando War

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考《LRJ大礼包::白》第一章例题2

思路

大概是贪心。

只要交代了任务，部下自己就会给做完了，基于这样的题意我们就可以设计这样的一种贪心策略：优先考虑完成任务时间长的，这样交代完了之后就会有更多的时间可以一边交代任务一边有人完成任务，更有效率。

具体操作就是把完成任务时间从大到小排个序，然后顺着检查一遍。

这个策略的证明在白书上面有提供，大概的证明套路就是说明不用这个策略时得到的答案不会更优，在证明时分类讨论了两种情况。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n;
pair<int,int> task[1005];

bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.second == b.second){
        return a.first < b.first;
    }else{
        return a.second > b.second;
    }
}

int work(){
    int bound = 0;
    int now = 0;
    for(int i = 1; i <= n; i++){
        now += task[i].first;
        bound = max(now + task[i].second, bound);
    }
    return bound;
}

int main(){
    int d = 0;
    while(scanf(" %d",&n) != EOF){
        d++;
        if(!n){
            break;
        }
        for(int i = 1; i <= n; i++){
            scanf(" %d %d",&task[i].first,&task[i].second);
        }
        sort(task+1,task+1+n,cmp);
        printf("Case %d: %d\n",d,work());
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n;

pair<int,int> task[1005];

bool cmp(pair<int,int> a,pair<int,int> b){

if(a.second == b.second){

return a.first < b.first;

}else{

return a.second > b.second;

}

int work(){

int bound = 0;

int now = 0;

for(int i = 1; i <= n; i++){

now += task[i].first;

bound = max(now + task[i].second, bound);

}

return bound;

}

int main(){

int d = 0;

while(scanf(" %d",&n) != EOF){

d++;

if(!n){

break;

}

for(int i = 1; i <= n; i++){

scanf(" %d %d",&task[i].first,&task[i].second);

}

sort(task+1,task+1+n,cmp);

printf("Case %d: %d\n",d,work());

}

return 0;

}

POJ 3646 The Dragon of Loowater

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考<LRJ大礼包::白>的第一章例题1.

思路

大概是贪心。因为骑士的能力=能砍多大=花多少钱，这样的话只要排个序，从最便宜的英雄开始检查，从小头开始砍，直到检查完最后一个英雄。

如果没砍死就是没解，否则一定是最优解，这个思维和Kruskal算法是一致的。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n,m;
vector<int> dia;
vector<int> bat;

int work(){
    int ret = 0;
    int cur = 0;
    for(int i = 0; i < bat.size(); i++){
        if(cur < n && dia[cur] <= bat[i]){
            ret += bat[i];
            cur++;
        }
    }
    if(cur < n){
        return -1;
    }
    return ret;
}

int main(){
    while(scanf(" %d %d",&n,&m) != EOF){
        if(n == 0 && m == 0){
            break;
        }
        dia.clear();
        bat.clear();
        dia.resize(n);
        bat.resize(m);
        for(int i = 0; i < n; i++){
            scanf(" %d",&dia[i]);
        }
        for(int i = 0; i < m; i++){
            scanf(" %d",&bat[i]);
        }
        sort(dia.begin(),dia.end());
        sort(bat.begin(),bat.end());
        int res = work();
        if(res == -1){
            puts("Loowater is doomed!");
        }else{
            printf("%d\n",res);
        }
    }


    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n,m;

vector<int> dia;

vector<int> bat;

int work(){

int ret = 0;

int cur = 0;

for(int i = 0; i < bat.size(); i++){

if(cur < n && dia[cur] <= bat[i]){

ret += bat[i];

cur++;

}

if(cur < n){

return -1;

}

return ret;

}

int main(){

while(scanf(" %d %d",&n,&m) != EOF){

if(n == 0 && m == 0){

break;

}

dia.clear();

bat.clear();

dia.resize(n);

bat.resize(m);

for(int i = 0; i < n; i++){

scanf(" %d",&dia[i]);

}

for(int i = 0; i < m; i++){

scanf(" %d",&bat[i]);

}

sort(dia.begin(),dia.end());

sort(bat.begin(),bat.end());

int res = work();

if(res == -1){

puts("Loowater is doomed!");

}else{

printf("%d\n",res);

}

return 0;

}

Editoral for SCUT ICPC Team Qualification Round A

December 05, 20152015-12-05hahaschoolLeave a comment

点按此处下载题面

PROBLEM A

很明显，双方最优策略是一直往前走，对手一直往前就能赢了，所以bx hao sui啊！

PROBLEM B

做这个题需要知道二项式定理，乘法逆元和等比数列求和，组合数取模。

$\sum_{i=1}^{n}(a^{i}+b^{i})^{k} = \sum_{i=1}^{n}\sum_{j=0}^{k} \binom{k}{j} a^{ij}b^{i(k-j)}=\sum_{j=0}^{k}\binom{k}{j} \sum_{i=1}^{n}q^{i}$

$q = a ^ {j} b ^ {k-j}$

后面就是等比数列的求和。

需要注意的是q＝1的时候。

二项式系数可以用阶乘和逆元预处理，等比数列求和也可以用逆元求出来。复杂度O(Klog(N))。

PROBLEM C

这题求的是一个有向无环图的最小树形图。可以对每个点，选一个权值最小的入边加起来就是答案。

PROBLEM D

直接模拟统计出到最后时刻情怀值会受损多少。对于每个时间点，如果不能ak，则损害值增加tn-ti。最后总的损害值如果比原始情怀值小则just enjoy coding，否则fail to graduate。

PROBLEM E

PROBLEM F

PROBLEM G

//模拟易知，画出来的图形是Sierpinski三角形，一种分形图像
//所以可以直接模拟，也可以用递归绘制（just for fun）
//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100;

int n;
char canvas[MAXN][MAXN * 2 - 1];							//画布

#define _USE_FRACTAL_METHOD_								//注释本行，将使用普通画法；否则，使用递归绘制分形

#ifndef _USE_FRACTAL_METHOD_
void draw() {												//普通画法
	canvas[0][n - 1] = '*';									//将第一行中间那个人设为*
	for (int i = 1; i < n; ++i) {							//对于接下来每一行
		for (int j = 0; j < 2 * n - 1; ++j) {				//从左到右查看
			bool flag[3];									//用来记录前方的人的状态
			if (j == 0)										//如果是最左边的人，就不用查看左前方
				flag[0] = false;
			else
				flag[0] = canvas[i - 1][j - 1] == '*';
			flag[1] = canvas[i - 1][j] == '*';				//记录正前方
			if (j == 2 * n - 2)								//如果是最右边的人，就不用查看右前方
				flag[2] = false;
			else
				flag[2] = canvas[i - 1][j + 1] == '*';
			if (!flag[0] && !flag[1] && flag[2])			//四种需要设为*的情况
				canvas[i][j] = '*';
			else if (!flag[0] && flag[1] && flag[2])
				canvas[i][j] = '*';
			else if (flag[0] && !flag[1] && !flag[2])
				canvas[i][j] = '*';
			else if (flag[0] && flag[1] && !flag[2])
				canvas[i][j] = '*';
		}
	}
}
#else
void draw(int row, int col, int size) {						//分形画法，以(row, col)为顶角，绘制大小为size的分形三角形
	if (row >= n || col < 0 || col >= 2 * n - 1)			//如果超出画布范围，就不画了
		return;
	if (size == 1)											//若已经是最小的三角形，直接绘制
		canvas[row][col] = '*';
	else {													//否则递归
		draw(row, col, size / 2);							//三个小三角形的顶角坐标如参数所示
		draw(row + size / 2, col - size / 2, size / 2);
		draw(row + size / 2, col + size / 2, size / 2);
	}
}
#endif // _USE_FRACTAL_METHOD_

int main() {
	while (cin >> n) {
		memset(canvas, '.', sizeof(canvas));				//初始化，将画布充填为.
#ifndef _USE_FRACTAL_METHOD_
		draw();												//普通画法
#else
		int size;											//分形画法需要计算最大三角形的size，size为2^k
		for (size = 1; size < n; size *= 2);				//寻找大于等于n的最小的size
		draw(0, n - 1, size);								//分形画法
#endif // _USE_FRACTAL_METHOD_
		for (int i = 0; i < n; ++i) {						//输出
			for (int j = 0; j < 2 * n - 1; ++j)
				cout << canvas[i][j];
			cout << endl;
		}
		cout << endl;										//输出额外的空行
	}
	return 0;
}

//模拟易知，画出来的图形是Sierpinski三角形，一种分形图像

//所以可以直接模拟，也可以用递归绘制（just for fun）

//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>

#include <cstring>

using namespace std;

const int MAXN = 100;

int n;

char canvas[MAXN][MAXN * 2 - 1]; //画布

#define _USE_FRACTAL_METHOD_ //注释本行，将使用普通画法；否则，使用递归绘制分形

#ifndef _USE_FRACTAL_METHOD_

void draw() { //普通画法

canvas[0][n - 1] = '*'; //将第一行中间那个人设为*

for (int i = 1; i < n; ++i) { //对于接下来每一行

for (int j = 0; j < 2 * n - 1; ++j) { //从左到右查看

bool flag[3]; //用来记录前方的人的状态

if (j == 0) //如果是最左边的人，就不用查看左前方

flag[0] = false;

else

flag[0] = canvas[i - 1][j - 1] == '*';

flag[1] = canvas[i - 1][j] == '*'; //记录正前方

if (j == 2 * n - 2) //如果是最右边的人，就不用查看右前方

flag[2] = false;

else

flag[2] = canvas[i - 1][j + 1] == '*';

if (!flag[0] && !flag[1] && flag[2]) //四种需要设为*的情况

canvas[i][j] = '*';

else if (!flag[0] && flag[1] && flag[2])

canvas[i][j] = '*';

else if (flag[0] && !flag[1] && !flag[2])

canvas[i][j] = '*';

else if (flag[0] && flag[1] && !flag[2])

canvas[i][j] = '*';

}

#else

void draw(int row, int col, int size) { //分形画法，以(row, col)为顶角，绘制大小为size的分形三角形

if (row >= n || col < 0 || col >= 2 * n - 1) //如果超出画布范围，就不画了

return;

if (size == 1) //若已经是最小的三角形，直接绘制

canvas[row][col] = '*';

else { //否则递归

draw(row, col, size / 2); //三个小三角形的顶角坐标如参数所示

draw(row + size / 2, col - size / 2, size / 2);

draw(row + size / 2, col + size / 2, size / 2);

}

#endif // _USE_FRACTAL_METHOD_

int main() {

while (cin >> n) {

memset(canvas, '.', sizeof(canvas)); //初始化，将画布充填为.

#ifndef _USE_FRACTAL_METHOD_

draw(); //普通画法

#else

int size; //分形画法需要计算最大三角形的size，size为2^k

for (size = 1; size < n; size *= 2); //寻找大于等于n的最小的size

draw(0, n - 1, size); //分形画法

#endif // _USE_FRACTAL_METHOD_

for (int i = 0; i < n; ++i) { //输出

for (int j = 0; j < 2 * n - 1; ++j)

cout << canvas[i][j];

cout << endl;

}

cout << endl; //输出额外的空行

}

return 0;

}

PROBLEM H

对于每个数，我们需要满足的条件有两个：一个是各数位数字单调递减，第二个是这个数字满足被6整除。首先，如果直接枚举满足第二个条件的数，那么要枚举的数太多，复杂度太高。那么我们首先考虑满足第一个条件。各个数位的数字单调递减说明了各个数字不同（即每个数只能选一次），而数字只能在0-9这10个数选取（说明最多取10个数），且满足单调递减（说明对每组取的数，只有一个方案是符合的）。于是所有满足条件“各数位数字单调递减”的数字只有C(10, 1) + C(10, 2) + C(10, 3) + … + C(10, 9) + C(10, 10) = 2^10-1 = 1023。于是我们可以通过搜索的方法找到所有满足第一个条件的数，然后判断是否满足第二个条件。搜索的方法是先枚举高位，再枚举低位，每次枚举的数都得比高位的数小，直到没有数可以枚举（最小是0）结束。用递归可以解决。最后我们求出所有满足第一和第二个条件的数只有两百多个。注意最大的数会超出int的范围，所以我们可以用一个long long数组存下满足条件的数。接下来我们由于我们最多只有20组数据，所以我们可以判断每个合法的数是否小于或等于输入数据。

主要部分代码如下：

ong long sum = 0, a[300];
int cnt = 0;

void dfs(int n) {
	for(int i = n-1; i >= 0; --i) {
		sum = sum * 10 + i;
		if(sum % 6 == 0) a[cnt++] = sum;
		dfs(i);
		sum /= 10;
	}
}

ong long sum = 0, a[300];

int cnt = 0;

void dfs(int n) {

for(int i = n-1; i >= 0; --i) {

sum = sum * 10 + i;

if(sum % 6 == 0) a[cnt++] = sum;

dfs(i);

sum /= 10;

}

PROBLEM I

//题意为，在输入矩阵中，数出
//横着或竖着
//连续三个或以上同颜色珠
//的次数
//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>
using namespace std;

int n, m;
char board[128][128];

int main() {
	int t;
	cin >> t;										//输入数据的组数
	while (t--) {
		cin >> n >> m;								//输入矩阵尺寸
		for (int i = 0; i < n; ++i)					//读取矩阵
			for (int j = 0; j < m; ++j)
				cin >> board[i][j];
		int ans = 0;								//答案
		char pre_type;								//储存遇到的上一个珠子的种类
		int cnt;									//计数器，记录当前这种珠子遇到连续几个了
		for (int i = 0; i < n; ++i) {				//对于每一行进行检查
			for (int j = 0; j < m; ++j)
				if (j == 0) {						//如果是第一颗珠子
					pre_type = board[i][j];			//设定
					cnt = 1;
				}
				else {
					if (pre_type == board[i][j])	//如果与上一颗珠子的种类一样
						++cnt;						//累加计数器
					else {							//如果与上一颗珠子的种类不一样
						if (cnt >= 3)				//如果上一种珠子出现的颗数大于等于3
							++ans;					//累加答案
						pre_type = board[i][j];		//更新
						cnt = 1;					//重置计数器
					}
				}
			if (cnt >= 3)							//不要忘了对最后出现的那种珠子判断
				++ans;
		}
		for (int i = 0; i < m; ++i) {				//对于每一列进行检查，下同对行的检查
			for (int j = 0; j < n; ++j)
				if (j == 0) {
					pre_type = board[j][i];
					cnt = 1;
				}
				else {
					if (pre_type == board[j][i])
						++cnt;
					else {
						if (cnt >= 3)
							++ans;
						pre_type = board[j][i];
						cnt = 1;
					}
				}
			if (cnt >= 3)
				++ans;
		}
		cout << ans << endl;						//输出答案
	}
	return 0;
}

//题意为，在输入矩阵中，数出

//横着或竖着

//连续三个或以上同颜色珠

//的次数

//如果你看到的注释没对齐，请在CodeBlocks中打开本代码

#include <iostream>

using namespace std;

int n, m;

char board[128][128];

int main() {

int t;

cin >> t; //输入数据的组数

while (t--) {

cin >> n >> m; //输入矩阵尺寸

for (int i = 0; i < n; ++i) //读取矩阵

for (int j = 0; j < m; ++j)

cin >> board[i][j];

int ans = 0; //答案

char pre_type; //储存遇到的上一个珠子的种类

int cnt; //计数器，记录当前这种珠子遇到连续几个了

for (int i = 0; i < n; ++i) { //对于每一行进行检查

for (int j = 0; j < m; ++j)

if (j == 0) { //如果是第一颗珠子

pre_type = board[i][j]; //设定

cnt = 1;

}

else {

if (pre_type == board[i][j]) //如果与上一颗珠子的种类一样

++cnt; //累加计数器

else { //如果与上一颗珠子的种类不一样

if (cnt >= 3) //如果上一种珠子出现的颗数大于等于3

++ans; //累加答案

pre_type = board[i][j]; //更新

cnt = 1; //重置计数器

}

if (cnt >= 3) //不要忘了对最后出现的那种珠子判断

++ans;

}

for (int i = 0; i < m; ++i) { //对于每一列进行检查，下同对行的检查

for (int j = 0; j < n; ++j)

if (j == 0) {

pre_type = board[j][i];

cnt = 1;

}

else {

if (pre_type == board[j][i])

++cnt;

else {

if (cnt >= 3)

++ans;

pre_type = board[j][i];

cnt = 1;

}

if (cnt >= 3)

++ans;

}

cout << ans << endl; //输出答案

}

return 0;

}

PROBLEM J

把下标乘上1000得到一个递推式子，

BX(n) = BX(n – 1000) + BX(n – 1234)。

答案就是BX(n*1000)

Author Information

ABCJ : doubility(czk)

DH : ConquererV587(kbx)

GI: Xdynix(rxy)