\(Preface\)
\(Rank35/41\)
\(80pts + 0pts = 80pts\)
蒻爆了
\(\mathfrak{T1}\ 世界冰球锦标赛\)
这就是我在这里说的那个更板的题，全场就我一个人打记搜，别人没\(A\)都是写假了好像
所以我就去学了一下折半搜索
确实简单
就是分两次搜，然后结果合并的时候用lower_bound等等的吧想办法合并，就完了
这题，还，还用说？。。。———lin4xu学长
呃呃我写正解代码莫名常数有点大，评测机波动卡过去的。。
T1·记搜80pts
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 45
#define ll __int128
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
这题是爆搜？
别把
应该是个动归
但是我只会爆搜(
可以记忆化一下，但是即使map记录也可能会爆空间
但是对于5~7数据点，我决定冲一把记搜
记搜的小样例过了，大样例没有给
就这样吧
*/
inline ll read(){
ll x = 0; char c;
while (!isdigit(c = getchar()));
do {x = (x << 3) + (x << 1) + (c & 15);} while(isdigit(c = getchar()));
return x;
}
void ot(ll x){
if (x > 9) ot(x/10);
putchar((x%10)+48);
}
ll n, m, final_ans;
ll a[N];
ll mry[N][1000005];
inline bool comp(ll x, ll y){
return x > y;
}
void XIN_team(ll x, ll sum){
if (x == n+1)
{final_ans ++; return ;}
// 选
if (sum + a[x] <= m)
XIN_team(x+1, sum+a[x]);
// 不选
XIN_team(x+1, sum);
}
ll XIN_team2(ll x, ll sum){
if (x == n+1)
{return 1;}
if (mry[x][sum] != 0)
{return mry[x][sum];}
ll res(0);
// 选
if (sum + a[x] <= m)
res += XIN_team2(x+1, sum+a[x]);
// 不选
res += XIN_team2(x+1, sum);
mry[x][sum] = res;
return res;
}
void work(){
n = read(), m = read();
for (ll i = 1 ; i <= n ; ++ i)
a[i] = read();
sort(a+1, a+n+1, comp);
while (a[n] > m)
n --;
if (n > 23 and m <= 1000003)
goto Specialer;
// cerr << "ASD" << '\n';
XIN_team(1, 0);
ot(final_ans), putchar('\n');
return ;
Specialer:{
final_ans = XIN_team2(1, 0);
ot(final_ans), putchar('\n');
}
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
// Fastio_setup();
work();
return GMY;
}
T1·折半搜索100pts
#include <iostream>
#include <algorithm>
#include <cmath>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define int long long
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define Dendl cerr << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 45
#define S_ER 1048902
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
没学折半搜索
没想到大佬们都A了
我这记搜情何以堪
然后就现学
ripo
*/
int n, S, SS, final_ans, ner;
long long m;
long long a[S_ER], b[S_ER], val[N];
#define lowbit(x) ((x) & (-(x)))
void work(){
cin >> n >> m;
for (re i = 1 ; i <= n ; ++ i)
cin >> val[i];
ner = ceil((double)n/2);
S = pow(2, ner) - 1; SS = pow(2, n-ner) - 1;
// cerr << S << _ << SS << _ << ner << '\n';
for (re i = 0, s, plc, res ; i <= S ; ++ i){
s = i; res = 0;
while (s != 0){
plc = log2(lowbit(s)) + 1;
res += val[plc];
if (res > m)
break;
s ^= lowbit(s);
}
if (res <= m)
a[++ a[0]] = res;
}
sort(a+1, a+a[0]+1);
for (re i = 0, s, plc, res ; i <= SS ; ++ i){
s = i; res = 0;
while (s != 0){
plc = log2(lowbit(s)) + ner + 1;
res += val[plc];
if (res > m)
break;
s ^= lowbit(s);
}
if (res <= m)
b[++ b[0]] = res;
}
sort(b+1, b+b[0]+1);
/*cerr << a[0] << _ << b[0] << '\n';
for (re i = 0 ; i <= a[0] ; ++ i)
cerr << a[i] << _;
Dendl;
for (re i = 0 ; i <= b[0] ; ++ i)
cerr << b[i] << _;
Dendl; Dendl;*/
for (re i = 1, plc ; i <= a[0] ; ++ i){
plc = lower_bound(b+1, b+b[0]+1, m-a[i]) - b;
// cerr << "before: " << a[i] << _<< m-a[i] << _ << plc << _ << b[plc] << '\n';
if (b[plc] + a[i] > m or (b[plc] == 0 and plc != 1))
plc --;
if (b[plc] == 0 and plc == 1)
{final_ans ++ ; continue;}
while (b[plc] == b[plc+5])
plc += 5;
if (b[plc] == b[plc+4])
plc += 4;
else if (b[plc] == b[plc+3])
plc += 3;
else if (b[plc] == b[plc+2])
plc += 2;
else if (b[plc] == b[plc+1])
plc ++;
// cerr << "after: " << a[i] << _<< m-a[i] << _ << plc << _ << b[plc] << '\n';
// Dendl;
final_ans += plc;
}
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T2}\ 滚\)
莫队。然后\(O(n)\)暴力查询
具体实现看代码
hmy[]就是\(how\ many\)
T2
#include <iostream>
#include <algorithm>
#include <cmath>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 200005
#define QUERY 200005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
我用分块
结果是莫队
鼓掌
*/
int n, Q, blocklen;
int a[N], w[N], belong[QUERY], f[N], hmy[N], ans[QUERY];
struct Question{
int l, r, k, id;
friend bool operator < (Question A, Question B){
if (belong[A.l] != belong[B.l])
return A.l < B.l;
return (((belong[A.l] & 1) == 1) ? (A.r < B.r) : (A.r > B.r));
}
}q[QUERY];
/*
7 3
1 3 3 2 1 3 3
1 2 3 4 5 6 7
1 7 1
3 5 1
5 7 1
10 3
1 2 3 3 2 3 3 2 4 4
1 1 4 5 1 4 1 9 1 9
2 6 1
3 9 3
1 10 1
*/
inline void _insert(int col){
if (f[col] > 0)
hmy[f[col]] --;
f[col] ++; hmy[f[col]] ++;
}
inline void _delete(int col){
hmy[f[col]] --; f[col] --;
if (f[col] > 0)
hmy[f[col]] ++;
}
inline int Query(int k, int num){
int lst(-1145141919), mx(-1);
for (re i = 1 ; num != 0 ; ++ i){// f[x]
if (hmy[i] == 0)
continue;
num -= hmy[i]*i;
if (lst+k >= i)
mx = MAX(mx, w[i]);
lst = i;
}
return mx;
}
void work(){
cin >> n >> Q;
for (re i = 1 ; i <= n ; ++ i)
cin >> a[i];
for (re i = 1 ; i <= n ; ++ i)
cin >> w[i];
for (re i = 1 ; i <= Q ; ++ i)
{cin >> q[i].l >> q[i].r >> q[i].k; q[i].id = i;}
blocklen = sqrt(Q);
for (re i = 1 ; i <= Q ; ++ i)
belong[i] = ((i-1) / blocklen) + 1;
// for (re i = 1 ; i <= Q ; ++ i)
// cerr << belong[1] << _ << belong[Q];
// cerr << '\n';
sort(q+1, q+Q+1);
for (re i = 1, l(0), r(0) ; i <= Q ; ++ i){
while (q[i].l < l) _insert(a[l-1]), l --;
while (q[i].r > r) _insert(a[r+1]), r ++;
while (q[i].l > l) _delete(a[l]), l ++;
while (q[i].r < r) _delete(a[r]), r --;
// cerr << "Ive been there" << '\n';
// cerr << l << _ << r << '\n';
ans[q[i].id] = Query(q[i].k, q[i].r-q[i].l+1);
}
for (re i = 1 ; i <= Q ; ++ i)
cout << ans[i] << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}