/************************************************
* Author :Running_Time
* Created Time :2015/9/28 星期一 16:58:13
* File Name :A.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int main(void) {
int a, b; scanf ("%d%d", &a, &b);
int ans = min (a, b);
printf ("%d ", ans);
a -= ans, b -= ans;
ans = a / 2 + b / 2;
printf ("%d
", ans);
return 0;
}
从后往前，维护一个后缀最大值
/************************************************
* Author :Running_Time
* Created Time :2015/9/28 星期一 16:58:21
* File Name :B.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int a[N], mx[N], ans[N];
int main(void) {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
}
mx[n] = a[n]; ans[n] = 0;
for (int i=n-1; i>=1; --i) {
if (a[i] <= mx[i+1]) {
ans[i] = mx[i+1] + 1 - a[i];
}
mx[i] = max (mx[i+1], a[i]);
}
for (int i=1; i<=n; ++i) {
printf ("%d%c", ans[i], i == n ? '
' : ' ');
}
return 0;
}
题意：给n个数，最多可以增加k，每个数上限为100，问max sum (a[i] / 10)
分析：若k很小时，优先加给需要最小数字能到下一个十整数的，按照这个规则排序。若还有多余则继续，此时每个数字加10，直到100或者k<=0，及时break。
/************************************************
* Author :Running_Time
* Created Time :2015/9/28 星期一 16:58:28
* File Name :C.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int a[N];
int cal(int x) {
if (x == 100) return 0;
int a = x / 10;
return (a + 1) * 10 - x;
}
bool cmp(int x, int y) {
return cal (x) < cal (y);
}
int main(void) {
int n, k; scanf ("%d%d", &n, &k);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]);
}
sort (a+1, a+1+n, cmp);
while (k > 0) {
bool up = false;
for (int i=1; i<=n; ++i) {
if (a[i] == 100) continue;
int dt = cal (a[i]);
if (dt > k || k <= 0) break;
if (dt <= k) {
k -= dt; a[i] += dt;
up = true;
}
}
if (!up) break;
}
int ans = 0;
for (int i=1; i<=n; ++i) {
ans += a[i] / 10;
}
printf ("%d
", ans);
return 0;
}
题意：很好理解，就是三个矩形组合成一个正方形
分析：想到了很简单，无非就是两种情况，比赛时没想那么多，代码很挫，建议看图片就行了。。。
/************************************************
* Author :Running_Time
* Created Time :2015/9/28 星期一 17:39:02
* File Name :D.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int main(void) {
int x[3], y[3];
for (int i=0; i<3; ++i) {
scanf ("%d%d", &x[i], &y[i]);
if (x[i] > y[i]) swap (x[i], y[i]);
}
int sx = x[0] + x[1] + x[2];
if (sx == y[0] && sx == y[1] && sx == y[2]) { //第一种情况
printf ("%d
", sx);
for (int i=0; i<3; ++i) {
for (int j=1; j<=x[i]; ++j) {
for (int k=1; k<=y[i]; ++k) {
printf ("%c", i == 0 ? 'A' : (i == 1) ? 'B' : 'C');
}
puts ("");
}
}
}
else { //第二种情况
bool flag = false;
int n = 0, id = 0;
for (int i=0; i<3; ++i) {
if (n < y[i]) {
n = y[i]; id = i;
}
}
int tx = n - x[id];
for (int i=0; i<3; ++i) {
for (int j=0; j<3; ++j) {
if (i == id || j == id) continue;
if (x[i] == x[j] && x[i] == tx) {
if (y[i] + y[j] == n) {
flag = true; break;
}
}
else if (x[i] == y[j] && x[i] == tx) {
if (y[i] + x[j] == n) {
flag = true; break;
}
}
else if (y[i] == x[j] && y[i] == tx) {
if (x[i] + y[j] == n) {
flag = true; break;
}
}
else if (y[i] == y[j] && y[i] == tx) {
if (x[i] + x[j] == n) {
flag = true; break;
}
}
}
}
if (flag) { //输出答案
printf ("%d
", n);
for (int i=1; i<=x[id]; ++i) {
for (int j=1; j<=y[id]; ++j) {
printf ("%c", id == 0 ? 'A' : (id == 1) ? 'B' : 'C');
}
puts ("");
}
char p, q;
if (id == 0) p = 'B', q = 'C';
else if (id == 1) p = 'A', q = 'C';
else p = 'A', q = 'B';
for (int i=0; i<3; ++i) {
for (int j=0; j<3; ++j) {
if (i == id || j == id) continue;
if (x[i] == x[j] && x[i] == tx) {
if (y[i] + y[j] == n) {
for (int k=1; k<=tx; ++k) {
for (int l=1; l<=n; ++l) {
printf ("%c", l <= y[i] ? p : q);
}
puts ("");
}
return 0;
}
}
else if (x[i] == y[j] && x[i] == tx) {
if (y[i] + x[j] == n) {
for (int k=1; k<=tx; ++k) {
for (int l=1; l<=n; ++l) {
printf ("%c", l <= y[i] ? p : q);
}
puts ("");
}
return 0;
}
}
else if (y[i] == x[j] && y[i] == tx) {
if (x[i] + y[j] == n) {
for (int k=1; k<=tx; ++k) {
for (int l=1; l<=n; ++l) {
printf ("%c", l <= x[i] ? p : q);
}
puts ("");
}
return 0;
}
}
else if (y[i] == y[j] && y[i] == tx) {
if (x[i] + x[j] == n) {
for (int k=1; k<=tx; ++k) {
for (int l=1; l<=n; ++l) {
printf ("%c", l <= x[i] ? p : q);
}
puts ("");
}
return 0;
}
}
}
}
}
else puts ("-1");
}
return 0;
}
最后老夫夜观星相，预测此次rating会超1700，为了能够在div2继续虐菜，“故意”hack失败。。
