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; }