本文主要是介绍143 - ZOJ Monthly, October 2015 - Solution[part]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A-Ant
题意
已知一个长方体一条最长边为n，求所有可能的长方体(旋转视为一种)的最小(对角点在面上的距离L的平方
解法
显然是个n的四次方程。打表找规律。。
an=112(13n4+26n3+17n2+4n)
C-Cake
解法
记dp[i][j]表示当前i个cake，j个属于Alice，在保证前面构成合法的情况下转移。
#include <bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
const ll mod = 1000000007;const int maxn = 805;struct node{int a, b;void in(){scanf("%d%d",&a, &b);}bool operator < (const node & y) const{return b > y.b;}
}p[maxn];
bool vis[maxn];
int dp[maxn][maxn];
int main(){int T,n;scanf("%d", &T);while(T --){scanf("%d", &n);for(int i=0;i<n;i++){p[i].in();}sort(p, p+n);memset(dp, 0, sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;2*j<=i+1;j++){dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+p[i].a);}}cout << dp[n][n/2] << endl;}
}
F-Number Game
题意
从n个数里面每次选择和不超过k的两个数求积，一共选m次，求最后积之和最大
解法
首先忽略m的限制。。
贪心策略：对于当前最大的数a，最好的选择是比k-a小一点的数，这时候积最大
对于每个最大的数a，其实就找到了一个与之匹配的b，（可以证明对于b这个选择也是最优的，即没有更好的数能满足^^自己）
配对之后选前m个最大的即可
用multiset维护即可
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 100005;
int a[maxn],n, m ,k;
multiset<int> ms;
multiset<int>::iterator it;
int ans[maxn];
int main(){int T;scanf("%d", &T);while(T --){scanf("%d%d%d", &n, &m, &k);ms.clear();for(int i=0;i<n;i++){scanf("%d", &a[i]);ms.insert(a[i]);}int tot = 0;while(!ms.empty()){it = ms.end();it --;int t = *it;ms.erase(it);it = ms.upper_bound(k-t);if(it != ms.begin()){it --;ans[tot++] = t*(*it);ms.erase(it);}}sort(ans, ans+tot,greater<int>());ll res = 0;for(int i=0;i<min(tot,m);i++){res += ans[i];}cout << res << endl;}
}I-Prime Query
解法
裸的线段树，初始化质数表，维护区间质数的个数即可
#include <bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
const ll mod = 1000000007;const int maxn = 100005;
const int maxp = 1e7+5;
bool isp[maxp];
int p[maxp/10],pn;void init(){isp[1] = true;for(int i=2;i<maxp;i++){if(isp[i] == false){p[pn++] = i;for(int j=2;i*j<maxp;j++){isp[i*j] = true;}}}
}struct node{int l,r;int cnt;int val;int e;
}t[maxn<<2];#define lson(p) p << 1
#define rson(p) p << 1 | 1void push_up(int p){t[p].cnt = t[lson(p)].cnt + t[rson(p)].cnt;
}void build(int p, int l, int r){t[p].l = l;t[p].r = r;t[p].val = 0;t[p].cnt = 0;t[p].e = 0;if(l == r){int a;scanf("%d", &a);t[p].val = a;if(isp[a] == false)t[p].cnt = 1;return ;}int m = (l + r)/2;build(lson(p), l, m);build(rson(p), m+1, r);push_up(p);
}void push_down(int p){if(t[p].e){t[lson(p)].e = t[rson(p)].e = t[p].e;t[lson(p)].val = t[rson(p)].val = t[p].e;t[lson(p)].cnt = isp[t[p].e] ? 0 : t[lson(p)].r - t[lson(p)].l + 1;t[rson(p)].cnt = isp[t[p].e] ? 0 : t[rson(p)].r - t[rson(p)].l + 1;t[p].e = 0;}
}void update1(int p, int pos, int val){int l = t[p].l;int r = t[p].r;if(l == r){t[p].val += val;if(isp[t[p].val] == false){t[p].cnt = 1;}else {t[p].cnt = 0;}return ;}push_down(p);int m = (l+r)/2;if(pos <= m)update1(lson(p), pos, val);else update1(rson(p), pos, val);push_up(p);
}void update2(int p, int L, int R, int val){int l = t[p].l;int r = t[p].r;if(L <= l && r <= R){t[p].val = val;t[p].e = val;if(isp[val] == false){t[p].cnt = r - l + 1;}else {t[p].cnt = 0;}return ;}push_down(p);int m = (l+r)/2;if(L <= m)update2(lson(p), L, R, val);if(m+1 <= R)update2(rson(p), L, R, val);push_up(p);
}int query(int p, int L, int R){int res = 0;int l = t[p].l;int r = t[p].r;if(L <= l && r <= R ){return t[p].cnt;}push_down(p);int m = (l+r)/2;if(L <= m)res += query(lson(p), L, R);if(m+1 <= R)res += query(rson(p), L, R);push_up(p);return res;
}int main(){int T;init();scanf("%d", &T);while(T --){int N,Q;scanf("%d%d", &N, &Q);build(1, 1, N);for(int i=0;i<Q;i++){char op[4];scanf("%s", op);if(op[0] == 'A'){int a,b;scanf("%d%d", &a, &b);update1(1, b, a);}else if(op[0] == 'Q'){int a,b;scanf("%d%d", &a, &b);printf("%d\n", query(1, a, b));}else if(op[0] == 'R'){int a,b,c;scanf("%d%d%d",&a,&b,&c);update2(1, b, c, a);}}}
}k-Bob wants to pour water
解法
二分。。。
这篇关于143 - ZOJ Monthly, October 2015 - Solution[part]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
