51nod刷题计划

atcoder的题解好像有点少……
去刷51nod吧,好像很多是翻译成中文的原题
感觉思维难度还是不错的

1 1051 最大子矩阵和

9.25 难度1

请先思考后再展开

二维版,套个一维的+前缀和就好了

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
int a[MAX_N][MAX_N];
ll sum[MAX_N][MAX_N];//向上前缀和
void main()
{
int m,n;scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
sum[j][i]=sum[j][i-1]+a[i][j];
ll ans=0;
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++)
{
ll now=0;
for(int t=1;t<=m;t++)
{
if(now<0) now=0;
now+=sum[t][r]-sum[t][l-1];
ans=max(ans,now);
}
}
printf("%lld",ans);
}

2 1020 逆序排列 HAOI2009 逆序对数列

9.25 难度1

请先思考后再展开

$f(n,k)=\sum_{i=0}^{n-1} f(n-1,k-i)$
不能开ll,会被卡空间
然后为了方便可以相邻做差,具体看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MOD=1e9+7;
int f[1001][20001];
void main()
{
f[1][0]=1;
for(int n=2;n<=1000;n++)
{
f[n][0]=1;
for(int k=1;k<=20000 and k<=n*(n-1)/2;k++)
{
f[n][k]=(f[n][k-1]+f[n-1][k])%MOD;
if(k-n>=0) (f[n][k]-=f[n-1][k-n])%=MOD;
}
}
int T;scanf("%d",&T);
while(T--)
{
int n,k;scanf("%d%d",&n,&k);
printf("%d\n",(f[n][k]+MOD)%MOD);
}
}

3 1674 区间的价值 V2

9.25 难度1

请先思考后再展开

枚举每个l,然后向右看,计算贡献
分开来考虑每个位,对于and只关心第一个1,or只关心or
那么可以统计每个位的贡献,分成两部分的权值,最多共有60个不同的断点
那么排序一下就好了,差分统计贡献

我真的好菜啊上一道题的maxn忘记改了……

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
87
88
89
90
91
92
93
94
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int MAX_N=110000;
const int INF=0x3f3f3f3f;
typedef long long ll;
struct LJB
{
int hou[MAX_N];
int to[MAX_N*2],g[MAX_N*2];
int ln;void ins(int x,int y) {to[++ln]=y;g[ln]=hou[x];hou[x]=ln;}
LJB() {ln=0;memset(hou,0,sizeof hou);}
}E;
const ll MOD=1000000007;
struct Pos
{
int p,op;
ll c;
}p[200];//0-and 1-or
bool cmp(Pos a,Pos b) {return a.p<b.p;}
int a[MAX_N];
int nx[40][MAX_N],lst[40][2];
int f[40][2];//指针
int bin[40];
void main()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(int j=0;j<=30;j++)
{
int t=(a[i]&bin[j])>0;
if(f[j][t]==0) f[j][t]=i;
nx[j][lst[j][t]]=i;lst[j][t]=i;
}
}
for(int j=0;j<=30;j++)
{
nx[j][lst[j][0]]=n+1;
nx[j][lst[j][1]]=n+1;
if(f[j][0]==0) f[j][0]=n+1;
if(f[j][1]==0) f[j][1]=n+1;
}
ll ans=0;
for(int l=1;l<=n;l++)
{
int tot=0;
int nowand=0,nowor=0;
for(int j=0;j<=30;j++)
{
if(f[j][0]>1) nowand+=bin[j],p[++tot]=(Pos){f[j][0],0,-bin[j]};//and
p[++tot]=(Pos){f[j][1],1,bin[j]};//or
f[j][(a[l]&bin[j])>0]=nx[j][l];//update
}
sort(p+1,p+tot+1,cmp);p[tot+1].p=n;
for(int i=1;i<=tot;i++)
{
if(p[i].p>n) break;//debug
if(p[i].op==0) nowand+=p[i].c;
else nowor+=p[i].c;
if(p[i].p==p[i+1].p) continue;
ans=(ans+(ll)nowor*nowand%MOD*(p[i+1].p-p[i].p)%MOD)%MOD;
}
}
printf("%lld",(ans+MOD)%MOD);
}
}
int main()
{
mine::main();
}

4 1675 序列变换

9.26 难度2

请先思考后再展开

莫反显然,但我发现我不会计算条件2……
看题解,原来用个桶就好了,根据调和级数是log的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int basket[MAX_N];
ll F[MAX_N];
int a[MAX_N],b[MAX_N];
void main()
{
pre();
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int d=1;d<=n;d++)
{
for(int y=d;y<=n;y+=d) basket[ b[a[y]] ]++;
for(int x=d;x<=n;x+=d) F[d]+=basket[ a[b[x]] ];
for(int y=d;y<=n;y+=d) basket[ b[a[y]] ]=0;//保证复杂度
}
ll ans=0;
for(int d=1;d<=n;d++) ans+=(ll)mu[d]*F[d];
printf("%lld",ans);
}

5 1682 中位数计数

9.26 难度2

请先思考后再展开

又是巧妙地用桶,套路地转化为-1和1,然后找和为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[MAX_N];
int basket[MAX_N+MAX_N];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int ans=0;memset(basket,0,sizeof basket);
for(int sum=0,j=i;j>=1;j--) sum+=(a[j]<a[i]?-1:(a[j]!=a[i])),basket[MAX_N+sum]++;
for(int sum=0,j=i;j<=n;j++) sum+=(a[j]<a[i]?-1:(a[j]!=a[i])),ans+=basket[MAX_N-sum];
printf("%d ",ans);
}
}

6 1686 第K大区间

9.26 难度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
int n;ll k;
int a[MAX_N];
int num[MAX_N];
bool check(int mid)
{
ll ans=0;memset(num,0,sizeof num);
for(int l=1,r=0;l<=n;num[a[l]]--,l++)
{
if(l>r) num[a[++r]]++;
while(r+1<=n)
{
if(num[a[r+1]]+1>mid) break;
num[a[++r]]++;
}
ans+=r-l+1;
}
return ans<=(ll)n*(n+1)/2-k;
}
struct Nod
{
int d,p;
}s[MAX_N];
bool cmp(Nod a,Nod b) {return a.d<b.d;}
void main()
{
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&s[i].d),s[i].p=i;
sort(s+1,s+n+1,cmp);
int rx=1;a[s[1].p]=rx;
for(int i=2;i<=n;i++)
{
if(s[i-1].d!=s[i].d) rx++;
a[s[i].p]=rx;
}
int l=1,r=n,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid-1)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d",ans);
}

7 1052 最大M子段和

9.26 难度1

请先思考后再展开

显然的dp
前缀和mx优化一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll sum[MAX_N];
ll f[MAX_N][2];
ll mx[MAX_N][2];//前缀最大继承位置
void main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&sum[i]),sum[i]+=sum[i-1];
for(int k=0;k<=m;k++)
{
for(int i=k;i<=n;i++)
{
if(k>0) f[i][k&1]=max(mx[i-1][(k-1)&1]+sum[i],f[i-1][k&1]);
mx[i][k&1]=max(mx[i-1][k&1],f[i][k&1]-sum[i]);
}
}
printf("%lld",f[n][m&1]);
}

8 1120 机器人走方格 V3

9.26 难度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
const int MOD=10007;
int qpower(int x,int e)
{
int ans=1;x%=MOD;//debug
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
int inv(int x) {return qpower(x,MOD-2);}//is prime
int fac[MOD+10];
int C(int n,int m)
{
if(n<m) return 0;
if(n>=MOD or m>=MOD) return C(n/MOD,m/MOD)*C(n%MOD,m%MOD)%MOD;
return fac[n]*inv(fac[m])%MOD*inv(fac[n-m])%MOD;
}
int Cat(int n) {return C(2*n,n)*inv(n+1)%MOD;}
void main()
{
fac[0]=1;for(int i=1;i<=MOD;i++) fac[i]=fac[i-1]*i%MOD;
int n;scanf("%d",&n);
printf("%d",Cat(n-1)*2%MOD);
}

9 1555 布丁怪

9.29 难度2

请先思考后再展开

本来以为这是一道找性质题,然后想了个错误的性质,就凉了……

首先不难想到,问题会转化成,求一个序列的某一段,其中每个数都出现且仅出现一次,并且连续覆盖
本来想着可能可以用什么巧妙的技巧去判断bitset中连续的1,但没什么想法……

正解是转化为区间极值,让极值的差和长度差相同
log方的话显然线段树
但也可以分治,每一层,处理l和r不在相同区间的问题

这个极值挺麻烦的,用分情况讨论可以简化
一、min和max都在左边,此时计算一下前缀后缀与mid的极值即可快速计算
二、min在左边,max在右边,此时需要用两个尺取法,同时维护,并用桶维护公共区间

另外的两种情况是镜像问题,可以通过 【翻转序列+调整mid】 简化代码复杂度

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=310000;
int a[MAX_N];
ll ans=0;
int basket[MAX_N*2];
int mx[MAX_N],mi[MAX_N];//与mid的前后缀极值
void solve(int fl,int fr,int op)
{
if(fl>=fr) return;
int mid=(fl+fr-op)/2;//处理l和r不同区间的情况
mx[mid]=mi[mid]=a[mid];for(int i=mid-1;i>=fl;i--) mx[i]=max(mx[i+1],a[i]),mi[i]=min(mi[i+1],a[i]);
mx[mid+1]=mi[mid+1]=a[mid+1];for(int i=mid+2;i<=fr;i++) mx[i]=max(mx[i-1],a[i]),mi[i]=min(mi[i-1],a[i]);
//1. 都在左边
for(int l=fl;l<=mid;l++)
{
int r=mx[l]-mi[l]+l;
ans+=(mx[r]<mx[l] and mi[r]>mi[l] and mid+1<=r and r<=fr);//debug 没有判断越界!
}
//2. 左min右max
for(int l=fl,mir=fr,mxr=fr+1;l<=mid;l++)
{
while(mir>=mid+1 and mi[mir]<mi[l]) basket[MAX_N+mir-mx[mir]]--,mir--;
while(mxr-1>=mid+1 and mx[mxr-1]>mx[l]) mxr--,basket[MAX_N+mxr-mx[mxr]]++;
ans+=(mxr<=mir?basket[MAX_N+l-mi[l]]:0);
}
for(int i=mid+1;i<=fr;i++) basket[MAX_N+i-mx[i]]=0;
solve(fl,mid,op);solve(mid+1,fr,op);
}
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);a[x]=y;}
solve(1,n,0);
for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
solve(1,n,1);
printf("%lld",ans+n);
}
}
int main()
{
mine::main();
}

10 1125 交换机器的最小代价

10.1 难度2

请先思考后再展开

每个位置向它想去的点连边,那么因为每个点出度和入度都是1,一定是若干个环组成的
对于每个环,有两种策略
一、用内部最小的节点逛一圈
二、用外部最小的节点逛一圈再回去

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=51000;
struct Nod{int d,p;}p[MAX_N];
bool cmp(Nod a,Nod b) {return a.d<b.d;}
int to[MAX_N];
bool v[MAX_N];
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t;scanf("%d",&t);
p[i]=(Nod){t,i};
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++) to[p[i].p]=i;
ll ans=0;
for(int st=1;st<=n;st++) if(!v[st] and to[st]!=st)
{
v[st]=1;
int t=st,mi=p[to[t]].d,ln=1;
while(to[t]!=st) t=to[t],v[t]=1,ans+=p[to[t]].d,mi=min(mi,p[to[t]].d),ln++;
//ans+=p[to[st]].d+min((ll)mi*(ln-2),(ll)p[1].d*(ln+1)); debug
ans+=p[to[st]].d+min((ll)mi*(ln-2),(ll)p[1].d*(ln+1)+mi);
}
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

11 1131 覆盖数字的数量

10.1 难度2

请先思考后再展开

根据 $num\%a \leq b-a+1$ 可知能表示的区间一定是用 $ka \to kb$ 组成的
然后当k达到一定大小后,后面都会重叠,所以二分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
51
52
53
54
55
56
57
58
59
60
61
62
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const double eps=1e-3;
ll solve(ll A,ll B)
{
ll l=1,r=1ll<<60,ans=-1;
while(l<=r+eps)
{
ll mid=(l+r)/2;
if( (double)mid*B>=double(mid+1)*A-1-eps ) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
void main()
{
int T;scanf("%d",&T);
while(T--)
{
ll A,B,X,Y;scanf("%lld%lld%lld%lld",&A,&B,&X,&Y);//debug 爆ll
if(A<=X and Y<=B) {printf("%lld\n",Y-X+1);continue;}
ll k=solve(A,B);//k~INF
ll ans=0;
ll st=X/A,ed=min(Y/A,k-1);
if(st<=ed)
{
if((double)st*B>=X-eps) ans+=min(st*B,Y)-X+1;
st+=1;
if((double)ed*B>Y+eps) ans+=Y-max(X,ed*A)+1,ed-=1;
ans+=(double)(st+ed)*(ed-st+1)/2*(B-A)+(ed-st+1);
}
k=max(k,st);k=min(k,ed+1);
if((double)A*k<=Y) ans+=Y-max(A*k,X)+1;//连续
printf("%lld\n",ans);
}
}
};
int main()
{
mine::main();
}

12 1189 阶乘分数

10.3 难度2

请先思考后再展开

bzoj2721

感觉我不可能想到……
$n!(x+y)=xy,x>n!,y>n!$
$y=n!+z$
$x=\frac{(n!)^2}{z} + n!$
$ans=(n!)^2 的约数$
那么筛一下最小质因子,套个公式就好了

13 1201 整数划分

10.16 难度2

请先思考后再展开

好像又被套路了
感觉这种思路非常难想
主要是因为互不相同,你可以维护一个相对大小关系,这个关系一定是从1开始的
然后经过一系列的整体增加1得到当前的方案
那么现在dp,要么群体加1,要么群体加1然后前面插入一个1,总是能保证互不相同的

1
2
3
4
5
6
7
8
9
10
11
12
13
const int MOD=1e9+7;
int f[330][51000];
void main()
{
int n;scanf("%d",&n);
f[0][0]=1;
for(int ln=1;ln<=320;ln++)
for(int num=1;num<=n;num++)
if(num>=ln) f[ln][num]=(f[ln-1][num-ln]+f[ln][num-ln])%MOD;
int ans=0;
for(int ln=1;ln<=320;ln++) (ans+=f[ln][n])%=MOD;
printf("%d",ans);
}

14 1215 数组的宽度

10.16 难度2

请先思考后再展开

被lxj锤爆了,只会分治的nlogn做法
处理出min和max下,每个数能覆盖的范围
然后柿子是可以拆开来的,min和max拆开统计就行了

15 1217 Minimum Modular CF303C

10.16 难度2

请先思考后再展开

感觉这题有点难度
考虑相等的二元组, $a_i=a_j (\% m)$
如果枚举每个m,那么他们的差一定是m的倍数(包括0)
那么如果存储差,通过枚举m的倍数,就能得到所有的数对,而且是mlogm的
注意到k很小,数对显然不会超过 $k(k+1)/2$ 对,是很强力的剪枝
对于每一种实际的余数,第一个不需要删除,可以用链表拿出所有点对,进行计算
该做法的复杂度是有保证的,但常数略大,很容易被暴力枚举n的做法吊锤,而且还被卡空间……

故本代码暂时没ac,但一定是正确的

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=5001;
int n,k;
#define pr pair<short,short>//卡空间
#define FR first
#define SE second
vector<pr> ct[1000010];
int a[MAX_N];
bool in[MAX_N];bool v[1100000];//实际余数的存在性
int all;
int tmp[100];//撤回操作
void put(int x,int m)
{
if(!in[x])
{
in[x]=1;
tmp[++tmp[0]]=x;
if(!v[a[x]%m]) v[a[x]%m]=1;else all++;
}
}
void erase(int x,int m) {v[a[x]%m]=0;in[x]=0;}
int solve()
{
for(int m=1;m<=1000001;m++)
{
int tot=0;
for(int now=0;now<=1000001;now+=m) tot+=ct[now].size();
if(tot>k*(k+1)/2) continue;//最坏情况
//利用k剪枝
all=0;tmp[0]=0;
for(int now=0;now<=1000001;now+=m)
for(int t=0;t<(int)ct[now].size();t++)
put(ct[now][t].FR,m),put(ct[now][t].SE,m);
for(int t=1;t<=tmp[0];t++) erase(tmp[t],m);
if(all<=k) return m;
}
return -1;
}
void main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
ct[abs(a[i]-a[j])].push_back( make_pair(i,j) );
printf("%d",solve());
}
};
int main()
{
mine::main();
}

16 1241 特殊的排序

10.16 难度2

请先思考后再展开

非常秒的思维题
答案是,保留一段值连续数列,其他的一定存在一种方案,移动到左边或者右边
所以线性dp一下就好了

17 1259 整数划分 V2

10.16 难度2

请先思考后再展开

因为可以相同,数的数量会达到n
可以巧妙地分块

  1. 只用1~T的数, $g(num)=\sum g(num-a)$
  2. 用后面的数,那么这个部分,数的数量会在n/T以内,
    那么又可以用前面的做法了,不过不在需要保证互不相同了,在插入一个T+1的时候,其他不需要增加
    $f(i,num)=f(i-1,num-(T+1)),f(i,num-i)$
    答案就是其卷积
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    const int MAX_N=51000;
    const ll MOD=1e9+7;
    ll g[MAX_N],f[320][MAX_N];
    void main()
    {
    int n;scanf("%d",&n);int T=sqrt(n);
    g[0]=1;
    for(int a=1;a<=T;a++)
    for(int num=a;num<=n;num++)
    g[num]=(g[num]+g[num-a])%MOD;
    f[0][0]=1;
    for(int i=1;i<=n/T;i++)
    for(int num=i*(T+1);num<=n;num++)
    f[i][num]=(f[i][num-i]+f[i-1][num-(T+1)])%MOD;
    int ans=0;
    for(int a=0;a<=n;a++) for(int i=0;i<=n/T;i++) (ans+=g[a]*f[i][n-a]%MOD)%=MOD;
    printf("%d",ans);
    }

18 1262 扔球

10.16 难度1

请先思考后再展开


其实画这个图的途中,想了很多东西,最后的结论只和左下角那个反例有关
那就是你必须经过这n+1个点!
那画图的时候,我枚举了一个跨度,这也是灵感的来源
这个跨度必须和n+1互质,用公式求一下欧拉函数即可
ans=phi(n+1)

19 1273 旅行计划

10.17 难度2

请先思考后再展开

我的思路,下限nlogn:
维护一个线段树表示,以dfs序为编号,每个点到根的距离
然后动态选取最大的那个,把这条链并到根节点,合并的途中影响的总是子树整体,dfs序上是连续的
然后每个节点只会被合并一次,所以是nlogn

正解,下限n:
显然选择的点总是叶子节点,每个节点只会被一个叶子节点覆盖,
父亲节点被覆盖的候选总是在儿子节点中产生,dfs回溯的时候处理即可
最后再把叶子排序即可

20 1274 最长递增路径

10.17 难度2

请先思考后再展开

性质1: 一条边最多经过1次
性质2:路径上边权严格递增
将每条边排序,然后加入图中,此时一定是路径的最后一条(严格递增),没有后效性,可以直接转移
(但为了保证严格单调,需要将同权值的边分组,滚动一下即可)

21 1277 字符串中的最大值

10.17 难度2

请先思考后再展开

kmp
$f(nxt[i])+=f(i)$

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=110000;
int ln;
char s[MAX_N];
int nxt[MAX_N];
void getnext()
{
nxt[1]=0;
for(int i=2;i<=ln;i++)
{
int j=nxt[i-1];
while(j!=0 and s[j+1]!=s[i]) j=nxt[j];
if(s[j+1]==s[i]) nxt[i]=j+1;
else nxt[i]=j;
}
}
int num[MAX_N];
void main()
{
scanf("%s",s+1);ln=strlen(s+1);
getnext();
ll ans=0;
for(int i=ln;i>=1;i--)
{
num[i]+=1;
num[nxt[i]]+=num[i];
ans=max(ans,(ll)num[i]*i);
}
printf("%lld",ans);
}
};
int main()
{
mine::main();
}

22 1293 球与切换器

10.17 难度2

请先思考后再展开

这是一道sb题,但我也是个sb……
唯一提示:可以看作所有球同时放进去

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1100;
int mp[MAX_N][MAX_N];
ll f[MAX_N][MAX_N][2];//0上1左
void main()
{
int m,n;scanf("%d%d%lld",&m,&n,&f[1][1][0]);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]==0)
{
f[i+1][j][0]+=f[i][j][0];
f[i][j+1][1]+=f[i][j][1];
}
else
{
ll sum=f[i][j][0]+f[i][j][1];
f[i][j+1][1]+=sum/2+(sum&1 and mp[i][j]>0);
f[i+1][j][0]+=sum/2+(sum&1 and mp[i][j]<0);
}
}
}
printf("%lld",f[n+1][m][0]);
}
};
int main()
{
mine::main();
}

23 1296 有限制的排列

10.17 难度2

请先思考后再展开

显然先拆开,变成每个位置,和前面的大小关系
然后我就卡住了,不知道怎么解决,必须是排列这个条件
然后好像这是一个套路?
dp的时候保证f(i)是大小为i的排列,时刻保证合法性,
然后插入一个数的话可以把前面>=num的部分整体+1

24 1322 关于树的函数

10.18 难度2

请先思考后再展开

一道sb题,但我这sb又没想到
唯一提示:
||A1|B1|
|:-:|:-:|:-:|
|A2|a|b|
|B2|c|d|

a+b=a+c=b+d=c+d=n

25 1328 比赛往事

10.18 难度2

请先思考后再展开

这道题ac人数极少,我想写一发网上第一篇正式题解(思路主要是自己想的,少量参考了出题人的口胡)
题目的性质:确定一些位置后,内部元素是可以任意交换的
抓住这个性质,先定位出所有非法的位置,他们一定是要操作的
对于每次固定位置后,最优策略一定是a和b分别排序
如果合法了,直接退出,否则利用其它元素进行修正

维护好一个非法集合,那么里面每个元素迟早要被再次替换
我们每次选取最大的那个place,外面能参与进来的一定是 $cutoff \geq place$
在可参与的集合中,显然应该选择最小的那个place,加入后产生了推移
循环地执行此操作即可,最多加入n次,内部要排序一下,所以时间复杂度是 $O(n^2logn)$ (当然你非要写个插入排序也行)

下来我们讨论一些细节:

  1. 是否有可能找出来的a,无法使整个串推移呢?答:其实这是个无解情况,break否随你
  2. 不选取最小a行不行?答:可能可以,但这样显然不会更差
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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1100;
struct Nod{int a,b;}ok[MAX_N];
bool use[MAX_N];
int n;
int g1[MAX_N],g2[MAX_N],ans;
bool check()
{
for(int i=1;i<=ans;i++) if(g1[i]>g2[i]) return 0;
return 1;
}
void main()
{
scanf("%d",&n);
ans=0;int num_ok=0;
for(int i=1;i<=n;i++)
{
int a,b;scanf("%d%d",&a,&b);
if(a>b) g1[++ans]=a,g2[ans]=b;
else ok[++num_ok]=(Nod){a,b};
}
if(ans==0) {puts("0");return;}
while(1)
{
sort(g1+1,g1+ans+1);sort(g2+1,g2+ans+1);
if(check() or ans==n) break;
int mxa=-1;for(int i=1;i<=ans;i++) if(g1[i]>g2[i] and (mxa<0 or g1[i]>g1[mxa])) mxa=i;//取非法元素
int pos=-1;for(int i=1;i<=num_ok;i++) if(!use[i] and (pos<0 or ok[i].a<ok[pos].a) and ok[i].b>=g1[mxa]) pos=i;
++ans;g1[ans]=ok[pos].a,g2[ans]=ok[pos].b;use[pos]=1;
}
if(!check()) puts("-1");
else printf("%d",ans);
}
};
int main()
{
mine::main();
}

26 1353 树

10.18 难度2

请先思考后再展开

$f(x,siz=1 \to siz_x)=f(x,siz-a) \times f(y,a)+f(x,siz) \times f(y,k \to siz_y)$

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=2100;
int hou[MAX_N],siz[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int K;
const ll MOD=1e9+7;
ll f[2][MAX_N][MAX_N];
void dp(int x,int fa)
{
siz[x]=1;int now=1;f[0][x][1]=1;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dp(y,x);
memset(f[now&1][x],0,sizeof f[now&1][x]);
for(int a=siz[x];a>=1;a--)//01背包
{
for(int b=1;b<=siz[y];b++)
(f[now&1][x][a+b]+=f[(now-1)&1][x][a]*f[0][y][b]%MOD)%=MOD;//不断
(f[now&1][x][a]+=f[(now-1)&1][x][a]*f[0][y][0]%MOD)%=MOD;//断
}
siz[x]+=siz[y];
now++;
}
if((now&1)==0) memcpy(f[0][x],f[1][x],sizeof f[1][x]);//0为转移点
for(int a=K;a<=siz[x];a++) (f[0][x][0]+=f[(now-1)&1][x][a])%=MOD;
}
void main()
{
int n;scanf("%d%d",&n,&K);
for(int i=1;i<=n-1;i++) {int x,y;scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}
dp(1,0);
int ans=0;for(int i=K;i<=n;i++) ans=(ans+f[0][1][i])%MOD;
printf("%d",ans);
}
};
int main()
{
mine::main();
}

27 1354 选数字

10.18 难度1

请先思考后再展开

离散化约数,做个乘法背包即可

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1100;
ll ys[2000],tot;
int findid(ll num)
{
int t=lower_bound(ys+1,ys+tot+1,num)-ys;
return (ys[t]==num)?t:0;
}
int a[MAX_N];
const int MOD=1e9+7;
ll f[2000];
void main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k;scanf("%d%d",&n,&k);
tot=0;
for(int t=1;t*t<=k;t++)
{
if(k%t>0) continue;
ys[++tot]=t;
if(t*t!=k) ys[++tot]=k/t;
}
sort(ys+1,ys+tot+1);
memset(f,0,sizeof f);f[1]=1;
for(int i=1;i<=n;i++)
{
int now;scanf("%d",&now);
for(int t=tot;t>=1;t--) (f[findid((ll)ys[t]*now)]+=f[t])%=MOD;
}
printf("%lld\n",f[tot]%MOD);
}
}
};
int main()
{
mine::main();
}

28 1378 夹克老爷的愤怒

10.22 难度2

请先思考后再展开

贪心+树形dp
仅当必须要放的时候再放
比【救火站】简单一点(自行搜索blog)

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans;
}
void qwrite(int num)
{
if(num>9) qwrite(num/10);
putchar('0'+num%10);
}
const int MAX_N=110000;
int hou[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int K,ans=0;
int dfs(int x,int fa)//<0贡献;>0需求
{
if(e[hou[x]].g==0 and fa!=0) return 1;
int mi=K+1,mx=-K-1;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
int t=dfs(y,x);
mi=min(mi,t);
mx=max(mx,t);
}
if(mx>=K) {ans++;return -K;}
else return (mx>=(-mi)?mx:mi)+1;
}
void main()
{
int n=qread();K=qread();
for(int i=1;i<n;i++)
{
int x=qread(),y=qread();
x++;y++;
ins(x,y);ins(y,x);
}
if(K==0) {printf("%d",n);return;}
if(dfs(1,0)>0) ans++;
printf("%d",ans);
}
};
int main()
{
mine::main();
}

29 1379 索函数

10.23 难度2

请先思考后再展开

前置知识:

  1. 斐波那契通项公式: $\frac{1}{\sqrt 5} [ (\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n ]$
  2. num在二进制下的位数为 $\lfloor log_2 num \rfloor +1$
    然后经过打表、感性理解可知, $Sor(n)=2^{Fib(n)的位数}-1$
    小证明:斐波那契数列的每个1,因为是不断加法得到的,显然一定是通过后一个位的两个1组成的,
    根据数学归纳法可知,该性质成立

当n=0,输出0
当n比较大时,后面的部分趋近于0
n较小时暴力计算

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans;
}
void qwrite(ll num)
{
if(num>=10) qwrite(num/10);
putchar('0'+num%10);
}
void qwriteln(ll num) {qwrite(num);puts("");}
const ll MOD=1e9+7;
ll qpower(ll x,ll e)
{
ll ans=1;
while(e>0)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
void main()
{
int T;scanf("%d",&T);
while(T--)
{
ll n;scanf("%lld",&n);
if(n<=90)
{
if(n==0) puts("0");//log2 0 会炸
else
{
ll k=floor(log2( (pow((sqrt(5.0)+1)/2,n)-pow((1-sqrt(5.0))/2,n))/sqrt(5.0) ));
printf("%lld\n",qpower(2,k+1)-1);
}
}
else
{
ll k=floor( (double)n*log2((sqrt(5.0)+1)/2)-log2(sqrt(5.0)) );
printf("%lld\n",qpower(2,k+1)-1);
}
}
}
};
int main()
{
mine::main();
}

30 1383 整数分解为2的幂

10.23 难度1

请先思考后再展开

方法一:
$f(num,k)$ 表示num这个数,最大为 $2^k$ 的方案计数
$f(num,k)=\sum_{i=0}^k f(num-2^k,i)$
前缀和优化后,时间 $O(nlogn)$

方法二:
$f(num)=f(num-1)+[num是偶数] \times f(num/2)$

31 1423 最大二“货”

10.23 难度2

请先思考后再展开

思路从一开始就是错误的
枚举每个数作为最大值的贡献,那么找次大值会很麻烦,还曾考虑可持久化字典树什么的……
但其实用次大值找最大值就好了……单调栈一下就没了……

32

10.23 难度2

请先思考后再展开
1
2

33

10.23 难度2

请先思考后再展开
1
2

34

10.23 难度2

请先思考后再展开
1
2

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8a7d.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%