现在的位置: 首页 > 综合 > 正文

tc-552-div2

2013年08月26日 ⁄ 综合 ⁄ 共 3612字 ⁄ 字号 评论关闭
30元程序员衣装优惠券,仅剩3天!点击领取

250 题:

在一个矩阵中取出一个点,求不包含那个点的权值最大的矩阵。

直接枚举四种情况。

/*
收获:
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;

const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<30);

const double eps=1e-10;
const double pi=acos(-1.0);

#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))


template<class T> inline T gcd(T a,T b)//NOTES:gcd(
  {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm(
  {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}


typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下,左下,左,左上,上,右上,右,右下。

//******* WATER ****************************************************************

//flag = 0,横;flag = 1,竖
int calc(vector <string> flowers, bool flag, int start, int end) {
    int ret = 0;
    if(start > end) return 0;
    if(!flag) {
        for(int j = 0; j < flowers[0].length(); j++) {
            for(int i = start; i <= end; i++) {
                if(flowers[i][j] == 'F') ret++;
            }
        }
    }
    else {
        for(int i = 0; i < flowers.size(); i++) {
            for(int j = start; j <= end; j++) {
                if(flowers[i][j] == 'F') ret++;
            }
        }
    }
    return ret;
}

class FoxAndFlowerShopDivTwo {
	public:
	int theMaxFlowers(vector <string> flowers, int r, int c) {
	    int ret = 0, tmp;
	    tmp = calc(flowers, false, 0, r - 1);
	    ret = chmax(tmp, ret);
	    tmp = calc(flowers, false, r + 1, flowers.size() - 1);
	    ret = chmax(tmp, ret);
	    tmp = calc(flowers, true, 0, c - 1);
	    ret = chmax(tmp, ret);
	    tmp = calc(flowers, true, c + 1, flowers[0].length() - 1);
	    ret = chmax(tmp, ret);
	    return ret;
	}
};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


500:

题目要求对一个三角形的一堆球用三种颜色染色,相邻的球的颜色不同,注意会有规律:。

                          1 

                      2    3

                    3   1   2

                 1    2    3   1

               2    3    1    2   3

            3    1     2    3    1   2

球的个数有两种情况:

1.所有的1,2,3中颜色的球的个数相同,这时候N%3 == 2;

2.所有的1,2,3中颜色1的多一个,颜色2和3的相同。颜色1的个数为ceil(sum/3),颜色2和3的个数为floor(sum/3),其中sum = (N + 1) * N ;

RGB三种颜色最多各染r,g,b种,那么有两种情况:

1. r + g + b总数不够染色,限制染色数目,为:floor((r +g+b)/sum);

2.最少的颜色限制染色数目,floor(min_color / ceil(sum/3));其中min_color = min(r, g, b);

code:

/*
收获:
*/
#include<iostream>
#include<cstdlib>
#include<vector>
#include<map>
#include<cstring>
#include<set>
#include<string>
#include<algorithm>
#include<sstream>
#include<ctype.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stack>
#include<queue>
#include<ctime>
//#include<conio.h>
using namespace std;

const int INF_MAX=0x7FFFFFFF;
const int INF_MIN=-(1<<30);

const double eps=1e-10;
const double pi=acos(-1.0);

#define pb push_back   //a.pb( )
#define chmin(a,b) ((a)<(b)?(a):(b))
#define chmax(a,b) ((a)>(b)?(a):(b))


template<class T> inline T gcd(T a,T b)//NOTES:gcd(
  {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<class T> inline T lcm(T a,T b)//NOTES:lcm(
  {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}


typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
int dir_4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int dir_8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//下,左下,左,左上,上,右上,右,右下。

//******* WATER ****************************************************************



class FoxPaintingBalls {
	public:
	long long theMax(long long R, long long G, long long B, int N) {
	    LL minx = chmin(R, chmin(G, B));
	    LL tot = (N + 1) * N / 2;
	    LL one = tot / 3;
	    if(N == 1) return R+G+B;
	    return chmin((R+G+B) / tot, minx / one);
	}
};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

1000分,目前不会,等待题解中。。。

30元程>序员衣装优惠券,仅剩3天!点击领取

抱歉!评论已关闭.