SRM 149
DIV2 1000pt
题意：
对于n个人，第i人有pi的钱。将他们分成不超过四个组，每组统一交费x，对每个人，若他拥有的钱超过x则交费，否则不交费。问最多能使这些人交多少钱。
1<= n <= 50，0 <= pi <= 1000。
tag:greedy，think
解法：枚举所有分组情况，每组交费x为该组中最小的pi。如果分组不足四组，补足四组，每组均含一个人钱数为0的人。
Ps：感觉自己的代码写得比题解舒服.....
#line 7 "Pricing.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; inline int MyMod( int a , int b ) { return (a%b+b)%b;} int n, ans; bool cmp(int x, int y)
{
return x > y;
} class Pricing
{
public:
int maxSales(vector <int> p){
p.PB(), p.PB(), p.PB();
n = SZ (p);
if (!n) return ;
ans = ;
sort (p.begin(), p.end(), cmp); for (int i = ; i < n; ++ i)
for (int j = i+; j < n; ++ j)
for (int k = j+; k < n; ++ k)
for (int a = k+; a < n; ++ a){
int tmp = ;
tmp = p[i] * (i+) + p[j] * (j-i);
tmp += p[k] * (k-j) + p[a] * (a-k);
ans = max (ans, tmp);
} return (ans);
}
//by plum rain
};
DIV1 500pt
题意：
字符串匹配。给出字典和一个字符串，询问该字符串是否能用字典里的单词表示，有一种表示方法还是多种表示方法，如果只有一种，输出表示方法。
tag:dp
Ps:以后写dp一定要提前写好状态转移方程- -，错了好多次- -。还有，此题要用long long。
#line 7 "MessageMess.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ;
const int N = ; inline int MyMod( int a , int b ) { return (a%b+b)%b;} int64 dp[N], pat[N]; class MessageMess
{
public:
string restore(vector <string> d, string s){
CLR (dp), CLR (pat);
int m = SZ (d), n = SZ (s);
for (int i = ; i < n; ++ i){
for (int j = ; j < m; ++ j){
int size = SZ (d[j]);
int pos = i - size;
if (pos < -) continue;
string tmp(s, pos+, size);
if (tmp == d[j]){
if (pos == -)
dp[i] += , pat[i] = j;
else if (dp[pos] > )
dp[i] += dp[pos], pat[i] = j;
}
}
} if (!dp[n-]) return "IMPOSSIBLE!";
if (dp[n-] != ) return "AMBIGUOUS!";
VS ans; ans.clear();
int pos = n - ;
while (pos >= ){
int num = pat[pos];
ans.PB(d[num]);
pos -= SZ (d[num]);
}
int len = SZ (ans);
string ret; ret.clear();
ret += ans[len-];
for (int i = len-; i >= ; -- i)
ret += " " + ans[i];
return (ret);
} //by plum rain
};
DIV1 1000pt
题意：
在平面坐标系XOY中，以xi严格递增的顺序给出一些点的坐标(xi, yi)，然后将点(xi, yi)与(x[i+1], y[i+1])连接，得到一条折线。给定整数p，求在这条折线上的某一线段，起点终点分别为(a, b), (a+p, b')，使这一线段平均y值最大，输出最大的平均y值。
x, y范围[0, 10000]。
tag:think, (三分法), good
解法：
没做出来。官方题解提供了两种方法，第一种方法似乎要用三分法，还不太懂- -。
第二种方法是，考虑线段(a, b)——(a+p, b')在折线上移动，记该线段的平均y值为tmp。该线段从原位置移动到(a+1, c)和(a+p+1, c')，则tmp' = tmp - (f(a+1) + f(a)) / 2 + (f(a+p+1) + f(a+p)) / 2), ans = max (tmp, ans)(其中，f(a)表示折线段的在x = a时的y值，ans表示答案)。
然后考虑到线段(a, b)——(a+1, c)和线段(a+p, b')——(a+p+1, c')的斜率可能不同，所以答案线段也有可能出现在移动途中。记两线段y值相等的点为(x1, y0) 和 (x2, y0), 则ans = max (ans, tmp' + ((y0 + c) / 2)* (a+1 - x1) - ((y0 + c') / 2) * (a+p+1 - x2))。
PS：
返回double类型的要注意精度，并且，如果你使用topcoder的插件，在你自己的电脑上判断答案对错时，有可能因为精度问题而将你的正确答案判为错，输出一下返回值看一下是否正确就行。
/*
* Author: plum rain
*/
#line 11 "topcoder.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; inline int MyMod( int a , int b ) {a = a % b;if (a < ) a += b; return a;} class GForce
{
public:
double avgAccel(int p, vector <int> a, vector <int> t){
int n = SZ (a);
VD spd;
spd.clear();
for (int i = ; i < n-; ++ i){
spd.PB(a[i] + 0.0);
double now = a[i] + 0.0;
double cnt = (a[i+] - a[i] + eps) / (t[i+] - t[i] + eps);
for (int j = t[i] + ; j < t[i+]; ++ j)
now += cnt, spd.PB (now);
}
spd.PB (a[n-]); double tmp = 0.0;
for (int i = ; i < p; ++ i)
tmp += (spd[i] + spd[i+]) / 2.0;
double ans = tmp;
for (int i = ; i < spd.size() - p; ++ i){
tmp -= (spd[i] + spd[i-]) / 2.0;
tmp += (spd[i+p] + spd[i+p-]) / 2.0;
ans = max (ans, tmp); double del = (spd[i] + spd[i-]) / 2.0;
double add = (spd[i+p] + spd[i+p-]) / 2.0;
double haf = tmp + (*spd[i]/8.0 + spd[i-] / 8.0) - (*spd[i+p]/8.0 + spd[i+p-]/8.0);
ans = max (ans, haf);
if(fabs(del - add) > eps){
del = (spd[i] - spd[i-]) / 2.0;
add = (spd[i+p] - spd[i+p-]) / 2.0;
double x = ((spd[i] - spd[i+p]) / 2.0) / (del - add);
if (x > eps && x < - eps){
double y = ((spd[i]*spd[i+p-] - spd[i+p]*spd[i-]) / 2.0) / (del - add);
double xy = tmp + (spd[i] + y) * x / 2.0 - (y + spd[i+p]) * x / 2.0;
ans = max (ans, xy);
}
}
} double ret = ans / (p + 0.0);
return (ret);
}
};
SRM 150
DIV2 1100pt
题意：有一个有限大小的平面和一个球，平面上有两种障碍物，第一种障碍物被球撞后会消失，第二种不会。球撞两种障碍物均会反弹，速度不变。给出平面大小和障碍物分布，问球从左上角一某一初速度开始，需要多少时间能让平面上的第一类障碍物全部消失。
解法：模拟。
tag: simulate
#line 10 "BrickByBrick.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; inline int MyMod( int a , int b ) {a = a % b;if (a < ) a += b; return a;} //drt
//1 0 2
//0 0 0
//3 0 4
struct STA{
int x, y;
int drt;
int time;
void clr(){
x = ; y = ; time = ;
}
}; int an[][];
int xmax, ymax, tot;
int ans; inline int change(char x)
{
if (x == '.') return ;
if (x == 'B'){
++ tot;
return ;
}
if (x == '#') return ;
} void init(VS m)
{
CLR (an);
tot = ;
ymax = SZ (m);
for (int i = ; i < ymax; ++ i){
string s = m[i];
xmax = SZ (s);
for (int j = ; j < xmax; ++ j)
an[*i+][*j+] = change(s[j]);
}
} void move(int& x, int& y, int d, int& t)
{
++ t;
if (d == ) -- x, -- y;
if (d == ) ++ x, -- y;
if (d == ) -- x, ++ y;
if (d == ) ++ x, ++ y;
} void D(int& x, int& y, int& d)
{
if (!(x & )){
if (d & )
-- x, d = (d == ? : );
else
++ x, d = (d == ? : );
return ;
}
if (d < ) -- y, d = (d == ? : );
else ++ y, d = (d == ? : );
} int solve()
{
STA sta; sta.clr();
sta.drt = ;
int num = ;
while (sta.time < && sta.time < ans){
move(sta.x, sta.y, sta.drt, sta.time); int x = sta.x, y = sta.y;
int dtmp = sta.drt;
D(x, y, sta.drt);
if (x >= && x <= *xmax && y >= && y <= *ymax){
if (an[y][x] == ) sta.drt = dtmp;
if (an[y][x] == ) an[y][x] = , ++ num;
}
if (num == tot){
return sta.time;
}
}
return -;
} class BrickByBrick
{
public:
int timeToClear(vector <string> m){
init (m); ans = maxint; return (solve());
}
};
DIV1 500pt
题意：给一个用‘A’-‘Z’表示颜色的字符串s，要求将一空白字符串变成给定字符串，（每次变化能将任意个连续位置的字符均变为某个任意的字符）问最少变化多少次。比如给定ABGBA，第一次将空白字符串变为AAAAA，第二次变为ABBBA，第三次变为ABGBA，答案为3。(s.size() <= 50)
解法：设置数组，m[][][]。left位置到left+size-1位置此时颜色均为c，将他们变化为给定字符串对应部分所需要最少的变化次数为m[left][size][c]。
状态转移方程：m[][0][] = 0,
if (color == s[l]) m[left][size][c] = m[left+1][size-1][color];
else m[left][size][color] = min {1 + m[left][i][color] + m[left+i][size-i][k] | 0 < i <= size, 'A' <= k <= 'Z'}
由于要用到记忆化搜索的思想，我又想写成DP，所以感觉写成了四不像- -
tag:dp, memoization, good
#line 10 "StripePainter.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; inline int MyMod( int a , int b ) {a = a % b;if (a < ) a += b; return a;} string s;
int m[][][]; int ask(int l, int n, char c)
{
int& a = m[l][n][(int)c]; if (!n) return ; if (a != -) return a;
a = maxint; if (c == s[l]){
a = ask (l+, n-, c);
return a;
} for (int i = ; i < n; ++ i)
for (int j = 'A'; j <= 'Z'; ++ j)
a = min (a, + ask(l, i, s[l]) + ask(l+i, n-i, c));
a = min (a, + ask(l, n, s[l]));
return a;
} class StripePainter
{
public:
int minStrokes(string stripes){
s.clear();
s = stripes;
memset (m, -, sizeof (m)); int size = SZ (s);
for (int i = ; i < size; ++ i)
for (int j = ; j + i <= size; ++ j)
for (int k = 'A'-; k <= 'Z'; ++ k)
m[i][j][k] = + ask(i, j, (char)k); return (m[][size][(int)s[]]);
}
};