按照顺序来。
大意：
给你一个集合，求其所有非空子集的权值的中位数。
某集合的权值即为其元素之和。
1 <= n <= 2000
解：
集合配对，每个集合都配对它的补集。
最大的那个没有配对，所以求(原集合的权值 + 1) >> 1，不小于这个的第一个即为所求。
用bitset实现可行性背包。
#include <cstdio>
#include <bitset> const int N = ; std::bitset<N * N> bt; int a[N]; int main() {
int n, tot = ;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = ; i <= n; i++) {
bt |= (bt << a[i]);
bt[a[i]] = ;
tot += a[i];
}
tot = (tot + ) >> ;
while(bt[tot] == ) {
tot++;
}
printf("%d", tot);
return ;
}
AC代码
大意：
输入 N 个数字和 K 。
如果对于所有包含 Ai ，且和不小于 K 的集合，去掉 Ai 后和还不小于 K ，那么 Ai 就是 no need 的。
问有多少个元素是 no need 的。
1 <= n, k <= 5000
解：
no need 的一定是连续最小的一段，证明如下：
若 x need，且 y > x
对于每个包含 x 且 >= K 的集合，去掉 x 一定小于 K 。
若此集合包含 y ，则去掉 y 也小于 K 。
若此集合不包含 y ，则把 x 换成 y 即可。
这样证明了所有含x的集合。
对于某些把 y 换成 x 就会小于 K 的集合，
把 y 换成 0 也小于 K 。
证毕。
然后二分check。
check函数用上一题的思想，对于 x ，只要去掉 x 的集合和没有在[k - x, k)之间的，x 即为 no need
若 x >= k，单 x 元素即为所求，x 为 need。
#include <cstdio>
#include <bitset>
#include <algorithm> const int N = ; std::bitset<N> bt; int n, a[N], k; inline bool check(int x) {
if(a[x] >= k) {
return ;
}
bt.reset();
for(int i = ; i <= n; i++) {
if(i == x) {
continue;
}
if(a[i] > N - ) {
break;
}
bt |= (bt << a[i]);
bt.set(a[i]);
}
for(int i = k - a[x]; i < k; i++) {
if(bt[i]) {
return ;
}
}
return ;
} int main() {
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
std::sort(a + , a + n + );
int l = , r = n, mid;
while(l < r) {
mid = (l + r + ) >> ;
if(check(mid)) {
r = mid - ;
}
else {
l = mid;
}
}
if(r == && check()) {
r = ;
}
printf("%d", r);
return ;
}
AC代码
大意：
在 n * m 的区域中，输入 k 个黑格子的位置(x,y)。
对于每个 3 * 3 的区域，会包含 0 到 9 个黑格子。
求包含 0 ~ 9 个黑格子的 3 * 3 的区域各有多少个？
1 <= m, n <= 10 ^ 9
0 <= k <= 10 ^ 5
解：
每个黑格子只会对 9 个 3 * 3 的区域产生影响。
注意map的用法： it -> second
#include <cstdio>
#include <map>
#include <algorithm> typedef long long LL; const int N = ; struct A {
int x, y;
A(int x = , int y = ) {
this->x = x;
this->y = y;
}
bool operator < (const A &d) const {
if(x == d.x) {
return y < d.y;
}
return x < d.x;
}
bool operator == (const A &d) const {
return x == d.x && y == d.y;
}
}a[N * ]; std::map<A, int> mp; int ans[]; int main() {
int m, n, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = , x, y; i <= k; i++) {
scanf("%d%d", &x, &y);
for(int j = ; j < ; j++) {
for(int k = ; k < ; k++) {
if(x + j > n || y + k > m || x + j < || y + k < ) {
continue;
}
mp[A(x + j, y + k)]++;
}
}
}
std::map<A, int>::iterator it = mp.begin();
int tot = ;
for(; it != mp.end(); it++) {
tot++;
ans[it->second]++;
}
printf("%lld\n", 1ll * (m - ) * (n - ) - 1ll * tot);
for(int i = ; i <= ; i++) {
printf("%d\n", ans[i]);
}
return ;
}
AC代码
大意：
给定 n 个 a , m 个 b, k 个 c
求所组成的字符串的最小循环表示法的最大字典序。
解(结论):把这些一个一个的字符放入multiset，每次取字典序最大最小的合并放回去。
最后的即为所求。
#include <cstdio>
#include <set>
#include <iostream> using std::string; std::multiset<string> s; int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
s.insert("a");
}
scanf("%d", &n);
for(int i = ; i <= n; i++) {
s.insert("b");
}
scanf("%d", &n);
for(int i = ; i <= n; i++) {
s.insert("c");
}
while(s.size() > ) {
string a = *s.begin();
string b = *(--s.end());
s.erase(s.begin());
s.erase(--s.end());
s.insert((string)(a + b));
}
std::cout << *s.begin();
return ;
}
AC代码
不会...