发现博客慢的一个重要原因是那个代码高亮插件
把他禁用掉以后就明显快了不只1个level
以后贴代码还是贴到 http://paste.ubuntu.com/ 上去好了
之前发的就扔那里算了……
分类存档：默认分类
ZOJ Monthly, January 2013
有除了最大的蘑菇题以外的代码。题解因为最近比较忙就……
额，就这样吧……
经检验，下面的代码都可以在ZOJ上AC
ZOJ3676 Edward’s Cola Plan
比较水，看看代码肯定就懂了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
int n, T;
struct Node {
int x, y;
Node(){}
Node (int x, int y): x(x), y(y) {}
bool operator < (const Node &oth) const {
return y - x < oth.y - oth.x;
}
}a[N];
long long sum_x[N];
long long sum_y[N];
int main(){
while (scanf("%d%d", &n, &T) != EOF) {
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i].x, &a[i].y);
}
sort(a + 1, a + n + 1);
sum_x[0] = 0;
sum_y[0] = 0;
for (int i = 1; i <= n; i++) {
sum_x[i] = sum_x[i - 1] + a[i].x;
sum_y[i] = sum_y[i - 1] + a[i].y;
}
for (int i = 0; i < T; i++) {
int m;
scanf("%d", &m);
int index = lower_bound(a + 1, a + n + 1, Node(0, m + 1)) - a;
if (index > n) {
cout << sum_x[n] << "\n";
} else {
cout << sum_x[index - 1] + sum_y[n] - sum_y[index - 1] - m * (n - index + 1) << "\n";
}
}
}
}
ZOJ3677 Paint Erased
这题本质是涂色点集S和那根线上点集L的交。
而S集合是由若干个可能相交的点集聚成：S = A1 ∪ A2 ∪ A3 ∪ …
很容易想到的是把S割成互不相交的子集，然后分别和L求交，最后答案累加即可。
所以很自然地可以想到矩形切割，但是这里有一个很严重的问题，矩形切割切出来的矩形其实并不是没有交集的，他们在矩形的边缘那条线上会出现重叠。这样子就坑爹了，这里大概还是把边缘拿出来单独离散化处理比较好…总之是有点复杂了
这样子的思路本质是求了S，再求S ∩ L
而相对而言求(A1∩L)∪(A2∩L)∪(A3∩L)∪…则方便得多
这样就只用求出一个矩形在线段上的覆盖部分，然后对若干个线段求并什么的就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int MAXN = 1000;
const double eps = 1e-8, PI = atan2(0, -1);
inline double sqr(double x){ return x * x; }
inline bool zero(double x){ return (x > 0 ? x : -x) < eps; }
inline int sgn(double x) { return (x > eps ? 1 : (x + eps < 0 ? -1 : 0)); }
struct point{
double x, y;
point(double x, double y):x(x), y(y) {}
point() {}
bool operator == (const point & a) const{ return sgn(x - a.x) == 0 && sgn(y - a.y) == 0; }
bool operator != (const point & a) const{ return sgn(x - a.x) != 0 || sgn(y - a.y) != 0; }
bool operator < (const point & a) const{ return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && sgn(y - a.y) < 0; }
point operator + (const point & a) const{ return point(x + a.x, y + a.y); }
point operator - (const point & a) const{ return point(x - a.x, y - a.y); }
point operator * (const double & a) const{ return point(x * a, y * a); }
point operator / (const double & a) const{ return point(x / a, y / a); }
double operator * (const point & a) const{ return x * a.y - y * a.x; }//xmult
double operator ^ (const point & a) const{ return x * a.x + y * a.y; }//dmult
double length() const{ return sqrt(sqr(x) + sqr(y)); }
point trunc(double a) const{ return (*this) * (a / length()); }
point rotate(double ang) const{ point p(sin(ang), cos(ang)); return point((*this) * p, (*this) ^ p); }
point rotate(const point & a) const{ point p(-a.y, a.x); p = p.trunc(1.0); return point((*this) * p, (*this) ^ p); }
};
struct DB {
double x;
DB() {}
DB(double x):x(x) {}
bool operator < (const DB &oth) const {
return oth.x - x > eps;
}
};
const int N = 2005;
int n, m;
struct Re {
int t;
point a, b;
}r[N];
PDD mat[N][N];
vector <point> p;
set <DB> radio[N];
bool mark[N];
vector <double> vec;
int main(){
#ifdef cwj
freopen("in", "r", stdin);
#endif
while (scanf("%d%d", &n, &m) == 2) {
p.clear();
for (int i = 0; i < n; i++) {
scanf("%d%lf%lf%lf%lf", &r[i].t, &r[i].a.x, &r[i].a.y, &r[i].b.x, &r[i].b.y);
}
for (int i = 0; i < m; i++) {
double x, y;
cin >> x >> y;
p.push_back(point(x, y));
}
double ans = 0;
for (int i = 0; i + 1 < m; i++) {
radio[i].clear();
for (int j = 0; j < n; j++) {
point vec = p[i + 1] - p[i];
double sr = 0.0, er = 1.0;
if (r[j].a.x <= p[i].x + eps && p[i].x <= r[j].b.x + eps) {
checkmax(sr, 0.0);
} else {
if (zero(vec.x)) {
checkmax(sr, 1e20);
} else {
checkmax(sr, min((r[j].a.x - p[i].x) / vec.x, (r[j].b.x - p[i].x) / vec.x));
}
}
if (r[j].a.y <= p[i].y + eps && p[i].y <= r[j].b.y + eps) {
checkmax(sr, 0.0);
} else {
if (zero(vec.y)) {
checkmax(sr, 1e30);
} else {
checkmax(sr, min((r[j].a.y - p[i].y) / vec.y, (r[j].b.y - p[i].y) / vec.y));
}
}
if (r[j].a.x <= p[i + 1].x + eps && p[i + 1].x <= r[j].b.x + eps) {
checkmin(er, 1.0);
} else {
if (!zero(vec.x)) {
checkmin(er, max((r[j].a.x - p[i].x) / vec.x, (r[j].b.x - p[i].x) / vec.x));
}
}
if (r[j].a.y <= p[i + 1].y + eps && p[i + 1].y <= r[j].b.y + eps) {
checkmin(er, 1.0);
} else {
if (!zero(vec.y)) {
checkmin(er, max((r[j].a.y - p[i].y) / vec.y, (r[j].b.y - p[i].y) / vec.y));
}
}
mat[i][j] = make_pair(sr, er);
// cout << mat[i][j].first << " " << mat[i][j].second << endl;
// cout << sr << " " << er << endl;
if (sr < er) {
radio[i].insert(sr);
radio[i].insert(er);
}
}
vec.clear();
foreach (it, radio[i]) {
vec.push_back(it->x);
}
for (int j = 0; j < vec.size(); j++) mark[j] = 0;
for (int j = 0; j < n; j++) {
if (mat[i][j].first >= mat[i][j].second) continue;
for (int k = (lower_bound(vec.begin(), vec.end(), mat[i][j].first - eps) - vec.begin()); k + 1 < vec.size(); k++) {
if (vec[k + 1] <= mat[i][j].second + eps) {
mark[k] = r[j].t;
}
}
}
for (int j = 0; j + 1 < vec.size(); j++) {
if (mark[j]) ans += (vec[j + 1] - vec[j]) * (p[i + 1] - p[i]).length();
}
}
cout << fixed << setprecision(2) << ans << "\n";
}
return 0;
}
ZOJ3678 The Toy of Flandre Scarlet
考虑三个相邻的数x, y, z。那么作以下操作
x + 1, y + 1, z
x + 1, y, z – 1
于是可以发现，考虑两个点(a, b, c), (d, e, f)。
如果a + b + c和d + e + f的奇偶性相同，那么这两个点之间值是可以互相传递的。
那么可以考虑把所有的值都转到相邻的两个格子中，如果他们相等，那么就可以消完，否则消不完。
#include <cstdio>
const int N = 5;
int L, W, H;
int a[N][N][N];
int pos[N][N][N];
int main() {
while (scanf("%d%d%d", &L, &W, &H) != EOF) {
int cnt = 0;
int sum = 0;
for (int i = 0; i < L; i++) {
for (int j = 0; j < W; j++) {
for (int k = 0; k < H; k++) {
scanf("%d", &a[i][j][k]);
pos[i][j][k] = ++cnt;
if ((i + j + k) & 1) {
sum += a[i][j][k];
} else {
sum -= a[i][j][k];
}
}
}
}
if (sum == 0) {
puts("Yes");
} else {
puts("No");
}
}
}
ZOJ3679 One Touch Drawing
预处理以后蘑菇爆搜就可以了。注意可能出现一直疯狂传送的情况……这时候要判断一下。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <cassert>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105;
int n, m, w;
struct edge {
int x, y, t, d, z;
edge(){}
edge(int x, int y, int t, int d, int z):x(x), y(y), t(t), d(d), z(z) {}
};
vector <edge> E;
int cnt[N], sum;
int transTo[N];
int f[N][N];
void dfs(int x) {
if (sum == 0) {
throw 1;
}
if (f[x][x]) {
return;
}
cnt[x]++;
for (int i = 0; i < m; i++) {
if (E[i].z == x) {
swap(E[i].x, E[i].y);
}
}
if (transTo[x] != -1) {
dfs(transTo[x]);
} else {
for (int i = 0; i < m; i++) {
if (E[i].t && E[i].x == x) {
sum--;
E[i].t--;
dfs(E[i].y);
E[i].t++;
sum++;
} else if (E[i].t && E[i].y == x && !E[i].d) {
sum--;
E[i].t--;
dfs(E[i].x);
E[i].t++;
sum++;
}
}
}
cnt[x]--;
for (int i = 0; i < m; i++) {
if (E[i].z == x) {
swap(E[i].x, E[i].y);
}
}
}
int main(){
while (scanf("%d%d%d", &n, &m, &w) != EOF) {
E.clear();
memset(cnt, 0, sizeof(cnt));
memset(transTo, 0xFF, sizeof(transTo));
memset(f, 0, sizeof(f));
sum = 0;
for (int i = 0; i < m; i++) {
int x, y, t, d, z;
scanf("%d%d%d%d%d", &x, &y, &t, &d, &z);
E.push_back(edge(x, y, t, d, z));
sum += t;
}
for (int i = 0; i < w; i++) {
int s1, s2;
scanf("%d%d", &s1, &s2);
assert(transTo[s1] == -1);
transTo[s1] = s2;
f[s1][s2] = 1;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
f[i][j] |= f[i][k] & f[k][j];
}
}
}
try {
for (int i = 0; i < n; i++) {
dfs(i);
}
} catch (...) {
puts("Yes");
continue;
}
puts("No");
}
}
ZOJ3680 E – Cup 1
蘑菇+爆搜……
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 505;
int n;
vector <pair < int, pair <int,int> > > E[N];
map <string, int> ref;
string name[N];
int _rank[N];
map <string, int> rank;
struct Node {
int point;
int js;
int jq;
int id;
bool operator < (const Node &oth) const {
if (point != oth.point) return point > oth.point;
if (js != oth.js) return js > oth.js;
return jq > oth.jq;
}
bool operator == (const Node &oth) const {
return point == oth.point && js == oth.js && jq == oth.jq;
}
}a[N];
int m;
int v[N];
bool cmp(Node A, Node B) {
if (A.js != B.js) return A.js > B.js;
if (A.jq != B.jq) return A.jq > B.jq;
return _rank[A.id] < _rank[B.id];
}
void calc() {
for (int i = 1; i <= n; i++) {
a[i].point = a[i].js = a[i].jq = 0;
foreach (it, E[a[i].id]) {
a[i].jq += it->second.first;
a[i].js += it->second.first - it->second.second;
if (it->second.first > it->second.second) {
a[i].point += 3;
} else if (it->second.first == it->second.second) {
a[i].point++;
}
}
}
}
void gao(int l, int r) {
if (l == r) return;
m++;
for (int i = l; i <= r; i++) {
v[a[i].id] = m;
}
for (int i = l; i <= r; i++) {
a[i].point = a[i].js = a[i].jq = 0;
foreach (it, E[a[i].id]) {
if (v[it->first] == m) {
a[i].jq += it->second.first;
a[i].js += it->second.first - it->second.second;
if (it->second.first > it->second.second) {
a[i].point += 3;
} else if (it->second.first == it->second.second) {
a[i].point++;
}
}
}
}
sort(a + l, a + r + 1);
vector <Node> buf;
vector <PII> need;
for (int i = l; i <= r; i++) {
if (buf.empty() || a[i] == buf[0]) {
buf.push_back(a[i]);
} else {
need.push_back(PII(i - buf.size(), i - 1));
buf.clear();
buf.push_back(a[i]);
}
}
need.push_back(PII(r + 1 - buf.size(), r));
if (need.size() == 1) {
for (int i = l; i <= r; i++) {
a[i].point = a[i].js = a[i].jq = 0;
foreach (it, E[a[i].id]) {
a[i].jq += it->second.first;
a[i].js += it->second.first - it->second.second;
if (it->second.first > it->second.second) {
a[i].point += 3;
} else if (it->second.first == it->second.second) {
a[i].point++;
}
}
}
sort(a + l, a + r + 1, cmp);
} else {
foreach(it, need) {
gao(it->first, it->second);
}
}
}
int main(){
int Tc = 0;
while (scanf("%d", &n) != EOF) {
if (Tc) puts("");
Tc++;
ref.clear();
rank.clear();
char buf[1000];
for (int i=1;i<=n;i++) E[i].clear();
for (int i = 0; i < n*(n-1)/2;i++) {
scanf("%s",buf);
string team_a(buf);
int x,y;
scanf("%d:%d", &x, &y);
// cout << x << " " << y << endl;
scanf("%s",buf);
string team_b(buf);
if (!ref.count(team_a)) {
ref[team_a] = ref.size();
// cout << team_a << " " << ref[team_a] << endl;
name[ref.size()] = team_a;
}
if (!ref.count(team_b)) {
ref[team_b] = ref.size();
// cout << team_b << " " << ref[team_b] << endl;
name[ref.size()] = team_b;
}
E[ref[team_a]].push_back( make_pair(ref[team_b], make_pair(x, y) ) );
E[ref[team_b]].push_back( make_pair(ref[team_a], make_pair(y, x) ) );
}
int m;
scanf("%d",&m);
for (int i = 0; i < m; i++) {
scanf("%s",buf);
rank[string(buf)] = i;
}
for (int i = 1; i <= n; i++) {
a[i].id = i;
_rank[i] = rank[name[i]];
}
m = 0;
memset(v,0,sizeof(v));
calc();
sort(a + 1, a + n + 1);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (!cnt || a[i].point == a[i - 1].point) {
cnt++;
} else {
gao(i - cnt, i - 1);
cnt = 1;
}
}
gao(n + 1 - cnt, n);
for (int i=1;i<=n;i++) {
cout << name[a[i].id] << endl;
}
}
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const long long INF = 1LL * 1000000000 * 1000000000;
int n, m;
long long F[40];
long long tr(long long x) {
return x / 2 + 1;
}
void init() {
for (int i = 0; i <= 4; i++) {
F[i] = tr(1 << i);
}
for (int i = 5;i<=35;i++) {
F[i] = INF;
for (int j=0;j<i;j++) {
checkmin(F[i], F[i - j] * tr(1LL << j));
}
}
}
int gao(int n) {
int j;
for (int i=0;;i++) {
if (n == (1 << i)) {
j=i;
break;
}
}
return F[j];
}
int main(){
#ifdef cwj
freopen("in", "r", stdin);
#endif
// freopen("out", "w", stdout);
init();
while (scanf("%d%d", &n, &m) != EOF) {
// n = _n;
long long ans = 1;
while (n % 2 == 0) {
n/=2;
ans*=2;
}
ans = gao(ans);
for (int i=3;i*i<=n;i++) {
while (n % i == 0) {
n /= i;
ans = ans * (i / 2 + 1);
}
}
if (n != 1) {
ans = ans * (n / 2 + 1);
}
puts(ans > m ? "No" : "Yes");
printf("%lld\n", ans);
}
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
const int Mod = 1000000007;
int s1, s2;
int n;
int a[N];
int sum[N];
int F[2][N];
int *pf, *f;
int main(){
#ifdef cwj
freopen("in", "r", stdin);
#endif
while (scanf("%d%d", &s1, &s2) != EOF) {
scanf("%d", &n);
sum[0] = 0;
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
sum[i] = sum[i - 1] + a[i];
}
if (s1 > s2) swap(s1, s2);
memset(F, 0, sizeof(F));
F[0][0] = 1;
pf = F[0];
f = F[1];
int Max = 0;
for (int i=1;i<=n;i++) {
int newMax = min(Max + a[i], s1);
for (int j=0;j<=newMax;j++) f[j] = 0;
for (int j=0;j<=Max;j++) {
if (pf[j]) {
if (j + a[i] <= s1) {
f[j + a[i]] += pf[j];
if (f[j + a[i]] >= Mod) f[j + a[i]] -= Mod;
}
if (!(a[i] & 1) && j + a[i] / 2 <= s1 && sum[i - 1] - j + a[i] / 2 <= s2) {
f[j + a[i] / 2] += pf[j];
if (f[j + a[i] / 2] >= Mod) f[j + a[i] / 2] -= Mod;
}
if (sum[i - 1] - j + a[i] <= s2) {
f[j] += pf[j];
if (f[j] >= Mod) f[j] -= Mod;
}
}
}
Max = newMax;
swap(pf, f);
}
printf("%d\n", pf[s1]);
}
}
ZOJ3683 Simple Language
蘑菇题……慢慢磨就可以，不想磨了……= =b
ZOJ3684 Destroy
二分答案+树形dp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=10005;
int n,e,Center;
struct edge{int x,y,c,w;edge *next;}g[N*2],*ls[N];
void addedge(int x,int y,int c,int w){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];
}
void checkmax(int &t,int x){
if (x>t) t=x;
}
namespace Gao1{
int v[N],Min;
int F[N][2];
int From[N];
int who[N][2];
void update(int p,int key,int pos){
if (F[p][0]==-1) { F[p][0]=key; who[p][0]=pos; }
else if (key>F[p][0]){
F[p][1]=F[p][0];
who[p][1]=who[p][0];
F[p][0]=key;
who[p][0]=pos;
}
else if (key>F[p][1]){
F[p][1]=key;
who[p][1]=pos;
}
}
void dfs(int p){
v[p]=1;
bool son=false;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y]){
son=true;
dfs(t->y);
update(p,F[t->y][0]+t->c,t->y);
}
if (!son){
F[p][0]=0;
who[p][0]=p;
}
}
void select(int p,int fa,int faw){
From[p]=0;
if (fa){
From[p]=From[fa]+faw;
if (who[fa][0]==p){
if (F[fa][1]!=-1)
checkmax(From[p],F[fa][1]+faw);
}
else{
if (F[fa][0]!=-1)
checkmax(From[p],F[fa][0]+faw);
}
}
int now=max(F[p][0],F[p][1]);
checkmax(now,From[p]);
if (now<Min){
Min=now;
Center=p;
}
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa)
select(t->y,p,t->c);
}
void Find_Center(){
memset(v,0,sizeof(v));
memset(who,0,sizeof(who));
memset(From,0,sizeof(From));
for (int i=1;i<=n;i++) F[i][0]=F[i][1]=-1;
dfs(1);
Min=0x7FFFFFFF;
select(1,0,0);
}
}
namespace Gao2{
int du[N];
int v[N];
int Limit;
void dfs(int p){
v[p]=1;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y] && t->w>Limit)
dfs(t->y);
}
bool check(int mid){
Limit=mid;
memset(v,0,sizeof(v));
dfs(Center);
for (int i=1;i<=n;i++)
if (du[i]==2 && v[i]) return false;
return true;
}
void gao(){
int l=0,r=100000000;
memset(du,0,sizeof(du));
for (int i=1;i<=e;i++){
du[g[i].x]++;
du[g[i].y]++;
}
while (l<r){
int mid=(l+r)/2;
if (check(mid)) r=mid;
else l=mid+1;
}
cout << l << endl;
}
}
int main(){
while (cin >> n){
e=0;
memset(ls,0,sizeof(ls));
for (int i=1;i<n;i++){
int x,y,c,w;
scanf("%d%d%d%d",&x,&y,&c,&w);
addedge(x,y,c,w);
addedge(y,x,c,w);
}
Gao1::Find_Center();
Gao2::gao();
}
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 10005;
const int M = 1 << 20;
int n;
char s[N];
int sum[M];
bool used[N];
#define abs(x) ((x) < 0 ? -(x) : (x))
int main() {
for (int i = 0; i < M; i++) {
sum[i] = 0;
for (int j = 0; j < 20; j++) {
if (i & 1 << j) {
sum[i] += (j + 1) * (j + 1) * (j + 1);
}
}
}
while (scanf("%d", &n) == 1) {
long long now = 0;
int rest = n > 20 ? 20 : n;
for (int i = n; i > rest; i--) {
if (now > 0) {
now -= (long long)(i) * i * i;
used[i] = 0;
} else {
now += (long long)(i) * i * i;
used[i] = 1;
}
}
long long ans = 1LL << 50;
int all = 0;
int best_mask = -1;
for (int i = 1; i <= rest; i++) all += i * i * i;
for (int mask = 0; mask < 1 << rest; mask++) {
long long tmp = abs(now + sum[mask] * 2 - all);
if (tmp < ans) {
ans = tmp;
best_mask = mask;
}
}
for (int i = 1; i <= rest; i++) used[i] = !!(best_mask & 1 << (i - 1));
for (int i = n; i; i--) putchar(used[i] ? '+' : '-');
puts("");
}
}
SRM 567
Rating += 52
250
这个题写得圡爆了
因为bitset没有重载<弄了好久，最后直接重写了……搞得只剩100分多一点
太圡了。
本质是找<=n的数里面，分解素因子以后，指数奇偶性mask和自己相同的数的个数。
做法是把指数为奇的那些素数乘起来，然后得到一个最小的指数奇偶性mask和自己相同的数值。然后它可以乘的数就是一些完全平方数了。这个先把完全平方数存在一个vector里面然后lower_bound一下算数目就可以了。
500
先统计出每个字母的数目，如果想字典序最小，一定是aaabbbccc这样把相同的字母排在一起的形式。然后和另外的字符串比较的过程中，肯定都是先比a的数目，相等的话再比b的数目，如此下去……
于是每次选一个X的拥有数目是最大之一的字母。如果此时，X是唯一一个最大的，那么就符合了，否则继续。
比赛的时候cha得不够果断啊，要不然起手就能cha两个500
int num[55][26];
int used[26];
vector getWinningStrings(vector S) {
vector ans;
memset(num, 0, sizeof(num));
int n = S.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < S[i].size(); j++)
num[i][S[i][j] - 'a']++;
}
for (int i = 0; i < n; i++) {
bool flag = 0;
memset(used, 0, sizeof(used));
vector vec;
for (int j = 0; j < n; j++) if (j != i) vec.push_back(j);
while (!flag) {
bool found = 0;
for (int j = 0; j < 26; j++) {
if (!used[j]) {
int Max = -1;
foreach (it, vec)
if (num[*it][j] > Max) Max = num[*it][j];
if (Max < num[i][j]) {
flag = 1;
found = 1;
break;
}
if (Max == num[i][j]) {
found = 1;
used[j] = 1;
vector tmp_vec;
foreach (it, vec) {
if (num[*it][j] == Max) tmp_vec.push_back(*it);
}
vec = tmp_vec;
break;
}
}
}
if (!found) break;
}
if (flag) ans.push_back(i);
}
return ans;
}
1000
从后往前搜索，每次对后面的决策有影响的就是那些山的轮廓线……要注意这个轮廓线高度只可能+1 -1或者不变……所以可以用一个初始高度h0加上一个50位的三进制数表示。
然后用map记忆化搜索就好了。
……至于轮廓线数目为什么很少，我也不是很清楚-.-，但是感觉已经把本质相同的状态都合并了，也没有什么再可以利用的信息的，所以不这么做大概也没法做了。
值得一提的是，似乎用map < vector
推荐[[iwi]]的代码
还有练习房里WJMZBMR的无节操hash压状态版本……
钢之炼金术师插曲《兄弟》 – 麦田音乐网
World Final Training 6——2012 Petr Mitrichev Contest 10
上次做完忘了贴了……存着以后好找
传送门
Board
没什么好说的，就是智商被碾压了。rank 3好像还不错，但人家这是单挑比赛好不好T_T
D这种构造题就是死活想不出555
F题和上年GCJ的某题有相似之处，但是birthday hack也死活hack不出来，也不会搞了。
膜拜一下总是随便虐场的WJMZBMR……
复习去了。