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

codeforces-div2-134

2013年08月07日 ⁄ 综合 ⁄ 共 6412字 ⁄ 字号 评论关闭

A题:

贪心,寻找满足比旁边多至少2个高度的点,然后下降一个高度点,直到一共下降了k点。

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 ****************************************************************


int arr[300];

int main() {
    int n, k, nn;
    while(~scanf("%d%d", &n, &k)) {
        nn = (n << 1) + 1;
        for(int i = 1; i <= nn; i++) scanf("%d", &arr[i]);
        for(int i = 2; i <= nn; i += 2) {
            if(arr[i] > arr[i - 1] + 1 && arr[i] > arr[i + 1] + 1) {
                arr[i]--;
                k--;
            }
            if(k == 0) break;
        }
        printf("%d", arr[1]);
        for(int i = 2; i <= nn; i++) printf(" %d", arr[i]);
        cout << endl;
    }
    return 0;
}

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 ****************************************************************

int arr[1100];
int n, m;
priority_queue<int> pq;

void debug() {
    for(int i = 0; i < m; i++) cout << arr[i];
    cout << endl;
}

int get_min() {
    int nn = n;
    int ret = 0;
    //debug();
    sort(arr, arr + m);
    //debug();
    for(int i = 0; i < m; i++) {
        //cout << "%% " << arr[i] << endl;
        //cout << ret << endl;
        int cal = (arr[i] + 1) * arr[i] / 2;
        if(nn > arr[i]) {
            nn -= arr[i];
            ret += cal;
        }
        else {
            ret += (arr[i] + arr[i] - nn + 1) * nn / 2;
            return ret;
        }
    }
}

int get_max() {
    int ret = 0;
    int cnt = n;
    while(!pq.empty()) pq.pop();
    for(int i = 0; i < m; i++) pq.push(arr[i]);
    while(cnt) {
        int tmp = pq.top();
        pq.pop();
        //cout << tmp << endl;
        ret += tmp;
        pq.push(tmp - 1);
        cnt--;
    }
    return ret;
}


int main() {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; i++) scanf("%d", &arr[i]);
        int minx = get_min();
        //cout << minx << endl;
        int maxx = get_max();
        printf("%d %d\n", maxx, minx);
        return 0;
}

C题:

建图,求连通子图的数目.

/*
收获:
*/
#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 ****************************************************************

int a[110];
int b[110];
bool mat[110][110];
int n;

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);
    memset(mat, 0, sizeof(mat));
    for(int i = 0; i < n; i++) mat[i][i] = true;
    for(int i = 0; i < n; i++) {
        for(int j = 0;j < n; j++) {
            if(a[i] == a[j] || b[i] == b[j]) mat[i][j] = mat[j][i] = true;
        }
    }
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][k] && mat[k][j]) mat[i][j] = mat[j][i] = true;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        bool flag = false;
        for(int j = 0; j < i; j++) {
            if(mat[i][j]) flag = true;
        }
        if(!flag) ans++;
    }
    printf("%d\n", ans - 1);
    return 0;
}

或者用DSU也可以(disjoint Set Union 集合合并)即并查集。

/*
收获:
*/
#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 ****************************************************************


int father[110];
int x[110], y[110];

int get_father(int p) {
    return father[p] == p ? p : father[p] = get_father(father[p]);
}

void mergep(int a, int b) {
    int c = get_father(a);
    int d = get_father(b);
    father[c] = d;
    //cout << "here" << endl;
}

int main() {
    int n, ans = 0;
    scanf("%d", &n);
    //memset(father, -1, sizeof(father));
    for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]);
    for(int i = 0; i < n; i++) father[i] = i;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(x[i] == x[j] || y[i] == y[j])
                mergep(i, j);
        }
    }
    for(int i = 0; i < n; i++) {
        if(father[i] == i || father[i] == -1) {
            ans++;
        }
    }
    printf("%d\n", ans - 1);
    return 0;
}

抱歉!评论已关闭.