Fork me on GitHub

209191110模拟赛题解

$FPX$牛逼!

kyouko

$70$分做法:我们发现我们可以枚举每个数字,然后统计这个数字的$i$次方.然后随便开个$set$去个重之类的就$70$了.
而对于$100$分的做法,我们考虑枚举$k$次方中有多少数字在$[1….n]$之内.首先发现这个东西是可以二分的.然后我们就能二分出来对答案有多少贡献.
但是发现很显然这个东西会算重复,我们考虑怎么去重,我们发现,如果一个次方数$k$,它有平方因子的话,那么它显然可以不被统计进去,而如果一个数有可以被分解成奇数个数的乘积,那么显然这奇数个数都会把他算进去.
而我们发现这个容斥系数就是莫比乌斯函数,所以直接容斥即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>

using namespace std;

#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif

long long n;

int mu(int x){
int res=-1;
for (int a=2;a*a<=x;a++)
if (x%a==0){
int cnt=0;
while (x%a==0){
x/=a;
cnt++;
}
if (cnt>1) return 0;
res=-res;
}
if (x!=1) res=-res;
return res;
}

int main(){
freopen("kyouko.in","r",stdin);
freopen("kyouko.out","w",stdout);
scanf(LL,&n);
long long ans=1;
for (int a=2;;a++){
int l=1,r=1000000001;
while (l+1!=r){
int m=(l+r)>>1;
if (pow((double)m,a)<=(double)n) l=m;
else r=m;
}
ans+=mu(a)*(l-1);
if (l==1) break;
}
printf(LL "\n",ans);

return 0;
}

nanami

发现可以二分这个最小值,然后考虑怎么$check$.我们发现对于我们当前二分的这个$x$,如果有$high_i$小于$x$的话,那么我们为了让这个达到我们二分的值,我们就必须使这个点被浇水浇到$x$那么高.但是因为如果这个点之前没有比$x$小的点的话,为了向后延申更多被浇水浇到的位置,显然从$x$这个位置开始浇水更优.
然后我们模拟这个浇水的过程,不难发现如果暴力修改的话那么时间复杂度最坏是$O(n^2)$的,显然不行.但是我们想一下我们要做什么处理,我们要把单点求出一个数,然后进行区间加.显然这是树状数组可以解决的问题.
所以我们可以用树状数组来优化这个暴力的过程,时间复杂度为$O(n \times log_2n \times log_2V)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define int long long

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

using namespace std;

const int N = 1e5 + 10;

int n , m , l;
int high[N] , nep[N] , tmp[N];
int tree[N];

inline int lowbit ( int x ) {
return x & -x;
}
inline void add ( int x , int pos ) {
while ( pos <= n ) {
tree[pos] += x;
pos += lowbit ( pos );
}
return;
}
inline int query ( int pos ) {
int res = 0;
while ( pos ) {
res += tree[pos];
pos -= lowbit ( pos );
}
return res;
}

inline bool check ( int x ) {
memset ( nep , 0 , sizeof ( nep ) );
memset ( tree , 0 , sizeof ( tree ) );
int las = 0;
for ( int i = 1 ; i <= n ; i++ ) {
high[i] = tmp[i];
add ( high[i] - las , i );
las = high[i];
}
int use = 0;
for ( int i = 1 ; i <= n ; i++ ) {
int hhh = query ( i );
if ( hhh < x ) {
nep[i] = x - hhh;
use += nep[i];
if ( use > m )
return false;
add ( nep[i] , i );
add ( -nep[i] , i + l );
}
}
if ( use <= m )
return true;
else
return false;
}

signed main ( void ) {
freopen ( "nanami.in" , "r" , stdin );
freopen ( "nanami.out" , "w" , stdout );
n = read () , m = read () , l = read ();
for ( int i = 1 ; i <= n ; i++ ) {
high[i] = read ();
tmp[i] = high[i];
}
int l = 0 , r = 1e9 + 7 , ans;
while ( l <= r ) {
int mid = ( l + r ) >> 1;
if ( check ( mid ) ) {
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
printf ( "%lld\n" , ans );
return 0;
}

chisa

能直接暴力爆过去的题为什么要想正解.

首先这道题的正解是从前缀做一遍背包,再从后缀做一遍背包,然后对于不能选物品$i$的情况,我们从$f_{1…..i-1,j}$中取一个$max$再从$g_{i+1….n,j}$中取一个$max$即为答案.
但是你看数据范围只有$1000$说明暴力也是可以做的嘛.
我们设$ans_{i,j}$表示我们在不用$i$这个物品时,最多用$j$的空间最多能拿多少价值的物品.显然$ans_{i,j}=max(ans_{i,j-1},ff_{i,j}$.其中$ff$是我们在不选择第$i$件物品时,填满$j$的空间最多的价值.
那么我们直接预处理是跑满$O(n^3)$的.有个小的技巧就是我们发现我们每次不选的物品移动时(假设是$ignore$),那么我们在枚举$i$时不用从$1$开始,直接从$ignore-1$开始即可.这样可以有一个$\frac{1}{2}$的常数.
输出优化有奇效.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>

struct ios {
inline char gc(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}

template <typename _Tp> inline ios & operator >> (_Tp&x){
static char ch,sgn; ch = gc(), sgn = 0;
for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
sgn&&(x=-x); return *this;
}
} io;

using namespace std;

const int N = 1005;

int ff[N][N];
int f[N][N] , ans[N][N];

int n , m;
struct Node {
int v , w;
} nd[N];

inline void writeln ( int x ) {
if ( x / 10 > 0 )
writeln ( x / 10 );
char s = x % 10 + '0';
putchar ( s );
}

int main ( void ) {
freopen ( "chisa.in" , "r" , stdin );
freopen ( "chisa.out" , "w" , stdout );
io >> n;
for ( int i = 1 ; i <= n ; i++ ) {
io >> nd[i].v >> nd[i].w;
int five;
io >> five;
}
for ( int ignore = 1 ; ignore <= n ; ignore++ ) {
for ( int i = max ( 1 , ignore - 1 ) ; i <= n ; i++ ) {
for ( int j = 0 ; j <= 1000 ; j++ ) {
f[i][j] = f[i - 1][j];
if ( j - nd[i].v >= 0 && i != ignore )
f[i][j] = max ( f[i][j] , f[i - 1][j - nd[i].v] + nd[i].w );
ff[ignore][j] = max ( ff[ignore][j] , f[i][j] );
}
}
}
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= 1000 ; j++ )
ans[i][j] = max ( ans[i][j - 1] , ff[i][j] );
io >> m;
for ( int i = 1 ; i <= m ; i++ ) {
int vp , MaxV;
io >> vp >> MaxV;
vp++;
writeln ( ans[vp][MaxV] );
puts ( "" );
}
return 0;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:209191110模拟赛题解

文章作者:KRrrrrrrrr

发布时间:2019年11月11日 - 07:11

最后更新:2019年11月11日 - 11:11

原始链接:http://krrrr.xyz/2019/11/11/209191110模拟赛题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。