普及T1 买铅笔
对于每一种都判断一下，我要达到这个量最少要买几包铅笔。
这是一个简单的除法和模运算。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
int n,c,v,ans=2000000000;
int main(){
int i,j;
scanf("%d",&n);
for(i=0;i<3;i++){
scanf("%d%d",&v,&c);
j=(n%v==0)?n/v:(n/v+1);
j*=c,ans=min(ans,j);
}
printf("%d\n",ans);
return 0;
}
普及T2 回文日期
你可以估计一下年份的范围，然后直接暴力统计。
使用字符串函数是基本功呢。（笑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
using namespace std;
char a[10],b[10];
int rs[]={1,3,5,7,8,10,12},ans=0,x1,x2,y1,y2,m1,m2,d1,d2;
bool cmp(int ye,int mo,int da){
if(ye<y1||ye>y2)return false;
if(ye==y1){
if(mo<m1)return false;
else if(mo==m1){
if(da<d1)return false;
}
}else if(ye==y2){
if(mo>m2)return false;
else if(mo==m2){
if(da>d2)return false;
}
}
return true;
}
int main(){
scanf("%s%s",a,b);
x1=atoi(a),x2=atoi(b);
y1=x1/10000,y2=x2/10000;
m1=(x1%10000)/100,m2=(x2%10000)/100;
d1=x1%100,d2=x2%100;
int i,j,k,l,t,ye,mo,da,ok;
for(i=0;i<=1;i++)
for(j=0;j<=9;j++){
mo=i*10+j;
if(mo>12)break;
if(!mo)continue;
for(k=0;k<=3;k++){
if(k==3&&mo==2)break;
for(l=0;l<=9;l++){
ye=l*1000+k*100+j*10+i,
da=k*10+l;
if(da>31)break;
if(!da)continue;
if(da==31){
for(ok=t=0;t<7;t++)
if(mo==rs[t])ok=1;
if(!ok)break;
}
if(ye%400==0||(ye%4==0&&ye%100!=0)){
if(mo==2&&da>29)break;
}else if(mo==2&&da>28)break;
if(!cmp(ye,mo,da))continue;
ans++;
}
}
}
printf("%d\n",ans);
return 0;
}
普及T3 海港
统计？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
using namespace std;
typedef struct{
int t,k,st;
}D;
D _q[100005];
int n,cnt[100005]={0},_cnt=0,q[300005],f,r,cur=0;
int main(){
scanf("%d",&n);
int t,m,i,j,l;
f=r=0;
for(i=0;i<n;i++){
scanf("%d%d",&t,&m);
_q[r].t=t,_q[r++].k=m;
while(r>f&&_q[f].t<=t-86400){
for(j=_q[f].st,l=0;l<_q[f].k;l++,j++){
cnt[q[j]]--;
if(!cnt[q[j]])_cnt--;
}
f++;
}
_q[r-1].st=cur;
for(l=0;l<m;l++,cur++){
scanf("%d",&q[cur]);
cnt[q[cur]]++;
if(cnt[q[cur]]==1)_cnt++;
}
printf("%d\n",_cnt);
}
return 0;
}
普及T4 魔法阵
好方法
不妨设，那么对于每一个$i$，设，枚举一次$len$。
接下来的事情就很玄学了：$len$的限制是$len\le i-1$且$len\le 2\times\lfloor \frac{n-i-1}7 \rfloor$，算一下发现$len_{max}=\lfloor \frac{2n-4}9 \rfloor$，又由于$len$是偶数，所以每一次枚举的次数至多为$\lfloor \frac n 9 \rfloor$。
这个常数很小，考虑暴力。
总体上是枚举长度$len$，每一次枚举，，算出可行的，贡献，再对，做一遍。（当然也可以只做一遍，那样会很麻烦，见下面的下面的失败代码）
这里可以发现随着，的递增，是递增的，所以可以用前缀和优化；对于，同理。
时间复杂度$O(n^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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,m,a[40005],cnt[15005]={0};
int ca[15005],cb[15005],cc[15005],cd[15005];
void init(){
n=read(),m=read();
for(int i=1;i<=m;i++)
a[i]=read(),cnt[a[i]]++;
}
void solve(){
int hf_max=n/9,len,rp,xa,xb,xc,xd,sum;
for(int hf=1;hf<=hf_max;hf++){//长度的一半
len=hf<<1,sum=0;
for(xc=4*len+2;xc<=n-hf;xc++){//枚举xc
xd=xc+hf,xa=xc-4*len-1,xb=xa+len;
sum+=cnt[xa]*cnt[xb];
cc[xc]+=cnt[xd]*sum,cd[xd]+=cnt[xc]*sum;
}
sum=0;
for(xb=n-7*hf-1;xb>=len+1;xb--){//枚举xb
xa=xb-len,xd=7*hf+xb+1,xc=xd-hf;
sum+=cnt[xc]*cnt[xd];
ca[xa]+=cnt[xb]*sum,cb[xb]+=cnt[xa]*sum;
}
}
for(int i=1;i<=m;i++)
printf("%d %d %d %d\n",ca[a[i]],cb[a[i]],cc[a[i]],cd[a[i]]);
}
int main(){
init();
solve();
return 0;
}
劣方法
之前写了一个不够好，但是空间够大的情况下可以拿95分（大概）的程序。。。有兴趣的同学可以看看。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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,m,a[40005],ws[15005];
int pre[2005][15005],dc[2005][15005],dd[2005][15005];
int ca[15005],cb[15005],cc[15005],cd[15005];
bool calced[15005];
void calc(int at,int len){
int *cur=pre[len];
for(int i=at;i+len<=n;i++)
cur[i]=cur[i-1]+ws[i]*ws[i+len];
calced[len]=1;
}
void init(){
n=read(),m=read();
for(int i=1;i<=m;i++)a[i]=read(),ws[a[i]]++;
}
void solve(){
int xb,len,cnt,cnt_c,xs,hf;
int lenmax=n/9,*tc,*td;
for(int i=2;i<=n;i++){
if(!ws[i])continue;
cnt=0;
for(int len=2;len<xb;len+=2){
int rp=7*(len>>1)+i+1;
if(rp>n)break;
if(!ws[i-len])continue;
xs=ws[i-len]*ws[i],hf=(len>>1);
dc[hf][rp-hf]+=xs,dc[hf][n-hf+1]-=xs;
dd[hf][rp]+=xs,dd[hf][n+1]-=xs;
if(!calced[hf])calc(rp-hf,hf);
cnt_c=pre[hf][n-hf]-pre[hf][rp-hf-1];
cnt_c*=xs,cnt+=cnt_c,ca[i-len]+=cnt_c;
}
cb[i]+=cnt;
}
for(int i=1;i<=lenmax;i++){
tc=dc[i],td=dd[i];
for(int j=8*i+2;j<=n-i;j++)
tc[j]+=tc[j-1],td[j+i]+=td[j+i-1],
cc[j]+=tc[j]*ws[j+i],cd[j+i]+=td[j+i]*ws[j];
}
for(int i=1;i<=m;i++)
printf("%d %d %d %d\n",ca[a[i]]/ws[a[i]],cb[a[i]]/ws[a[i]],cc[a[i]],cd[a[i]]);
}
int main(){
init();
solve();
return 0;
}
提高D1T1 玩具谜题
按照题意模拟即可。
确定左右方向就用异或的方法。当然，多写几行判断也是可行的。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
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int in_or_out[100005],n,m;//in 0,out 1
char job[100005][20];
void init(){
n=read(),m=read();
for(int i=0;i<n;i++)
scanf("%d%s",&in_or_out[i],job[i]);
}
void solve(){
int opr,s,lst=0;
while(m--){
opr=read(),s=read();
int res=opr^in_or_out[lst];
if(!res)lst=(lst-s+n)%n;
else lst=(lst+s)%n;
}
printf("%s\n",job[lst]);
}
int main(){
init();
solve();
return 0;
}
提高D1T2 天天爱跑步
当初比赛的时候连暴力都没写对orz
暴力的话，直接上$LCA$，大力模拟即可，大概可以拿25分。。。
满分做法是从链状做法中过渡而来的。
我们发现，从$S$到$T$总是经过他们的$LCA$的（废话），也就是说，可以从$LCA$的角度入手。
然后考虑把树问题变成链问题，只要把$LCA$两边的链扯出来即可。
对于一条链，一个点$S$可以给另一个点$i$贡献的情况只有
从$S$到$i$走的步数=$W_i$。
反映在链上，就是$|S-i|=W_i$。
反映在树上，就是$depth[S]-depth[i]=W_i$，即$depth[S]=W_i+depth[i]$。这里假定$S$不是LCA，那么从$S$出发时不会往下面走的。
我们显然希望对于$i$统计合法的对应$S$。那么就造一个数组，统计当前合法的$S$的个数，走到一个$i$上查一下即可。
同理，另一边，有从LCA向下走到$T$，也是一样的道理，多开一个数组就行。
（条件是$depth[i]-W_i=depth[T]-len(x,y)$）
计算答案的顺序需要注意：
- 进入的时候先减掉答案，出去的时候再加上，才可以得到自身的贡献。（对于自己统计到的$S$和$T$）
- 由于$S$到$LCA$是向上，并且我们只希望在$S$到$LCA$的路径上查到我们想要的贡献，所以在向下DFS时添加自己作为$S$的信息，并在回到$LCA$时再减掉$S$的贡献；对$LCA$到$T$，我们只要它向上走的贡献，所以在回溯的时候在$T$处加上，再在$LCA$处减去。
- 负数下标。
总结一下，这道题有一个类似于差分的思想。。。在2015年应该有所领略。
时间复杂度取决于你求$LCA$时算法的时间复杂度。为$O((n+m)logn)$或者$O(n+m)$。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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,to[MAXN*2],_next[MAXN*2],at[MAXN]={0},Cnt=0;
//树部分
int que[MAXN],depth[MAXN],par[MAXN][MAXL]={0},LOG;
//LCA部分
int at2[MAXN]={0},to2[MAXN],_next2[MAXN],Cnt2=0;
//存T的信息
int ats[MAXN]={0},tos[MAXN],_nexts[MAXN],Cnts=0;
//自己是LCA时存S的深度
int att[MAXN]={0},tot[MAXN],_nextt[MAXN],Cntt=0;
//自己是LCA时存T的深度
int m,ans[MAXN],w[MAXN],c[MAXN]={0};
//ans答案 w出现时间 cS人数
int down[MAXN],up[MAXN*2]={0};
//up S->LCA down LCA->T（可能有负数）
void addedge(int _u,int _v){
to[++Cnt]=_v,_next[Cnt]=at[_u],at[_u]=Cnt;
}
void bfs(){
int f=0,r=0;
que[r++]=1,depth[1]=1;
while(r-f){
int h=que[f++];
for(int i=at[h];i;i=_next[i]){
int _v=to[i];
if(_v==par[h][0])continue;
que[r++]=_v,depth[_v]=depth[h]+1,par[_v][0]=h;
}
for(int i=1;i<=LOG;i++)
if(par[h][i-1])par[h][i]=par[par[h][i-1]][i-1];
else break;
}
}
int query(int u,int v){
int i,j,d;
if(depth[u]<depth[v])
swap(u,v);
for(d=depth[u]-depth[v],i=0;(1<<i)<=d;i++);
for(i--;i>=0&&depth[u]!=depth[v];i--)
if(depth[u]-(1<<i)>=depth[v])
u=par[u][i];
if(u==v)return u;
for(i=LOG;i>=0;i--)
if(par[u][i]>0&&par[u][i]!=par[v][i])
u=par[u][i],v=par[v][i];
return par[u][0];
}
//倍增求解LCA
void dfs(int cur){
//主要求解过程
int up_ans=up[depth[cur]+w[cur]],
down_ans=down[depth[cur]-w[cur]+MAXN];
//旧的答案
up[depth[cur]]+=c[cur];
//作为S，添加自己
for(int i=at[cur];i;i=_next[i])
if(to[i]!=par[cur][0])dfs(to[i]);
//搜索子树
for(int i=at2[cur];i;i=_next2[i])
down[to2[i]+MAXN]++;
//作为T，添加自己的信息
ans[cur]=up[depth[cur]+w[cur]]+down[depth[cur]-w[cur]+MAXN]-up_ans-down_ans;
//利用DFS性质计算自己的答案
for(int i=ats[cur];i;i=_nexts[i]){
up[tos[i]]--;//回溯时删去S
if(tos[i]==depth[cur]+w[cur])ans[cur]--;//如果S就是LCA，那么答案重复，减掉1个
}
for(int i=att[cur];i;i=_nextt[i])
down[tot[i]+MAXN]--;//作为LCA，回溯时删去T
}
void init(){
n=read(),m=read();
for(LOG=1;(1<<LOG)<n;LOG++);
int u,v;
for(int i=1;i<n;i++){
u=read(),v=read();
addedge(u,v),addedge(v,u);
}
bfs();
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1;i<=m;i++){
u=read(),v=read();
int lca=query(u,v),len=depth[u]+depth[v]-2*depth[lca];
c[u]++;
tos[++Cnts]=depth[u],_nexts[Cnts]=ats[lca],ats[lca]=Cnts;
tot[++Cntt]=depth[v]-len,_nextt[Cntt]=att[lca],att[lca]=Cntt;
to2[++Cnt2]=depth[v]-len,_next2[Cnt2]=at2[v],at2[v]=Cnt2;
}
}
void solve(){
dfs(1);
for(int i=1;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
int main(){
init();
solve();
return 0;
}
提高D1T3 换教室
很水的期望DP，但是对于第一次写的人有点难度。
（比方说我）
题目说要求最小的体力消耗期望值，并给出了地图，说明肯定先要求一次多源最短路。
然后在现实意义上理解一下这里期望的意义。
在这里，期望是概率和权值的乘积之和。并且每一次是否选课和其他几次都是没有关系的。
会对权值造成影响的是这一次和前一次的申请情况。比如第$i$次申请了，第$i-1$次没申请，那么有两种情况：一是申请通过，本次体力消耗是到的最短路长；二是没有通过，本次体力消耗是到的最短路长。那么期望体力就是
以此类推，都申请有4种情况，一个申请一个不申请有2种情况，都不申请有1种情况，每种情况对应的期望体力是不变的。这样就转化为了一个类似背包的问题。
设$f(i,j,k)$表示对于前$i$节课，使用了$j$次机会时需要的最小期望体力，$k=0$表示此次不申请，$k=1$表示此次不申请，分类讨论即可写出状态转移方程。具体见代码。
时间复杂度：$O(nm+V^3)$
注意，由于涉及了浮点数运算，该题的代码如果写的常数太大的话就会在最后一个点TLE。所以要适度卡常。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
using namespace std;
typedef long long ll;
int n,m,V,E,INF=1000000000;
int d[305][305];
int p1[2005],p2[2005];
double f[2005][2005][2],p[2005],inf=1e9;
void floyd(){
for(int k=0;k<V;k++)
for(int i=0;i<V;i++)
for(int j=0;j<V;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
void init(){
scanf("%d%d%d%d",&n,&m,&V,&E);
int i,j,u,v,c;
for(i=0;i<n;i++)
scanf("%d",&p1[i]),p1[i]--;
for(i=0;i<n;i++)
scanf("%d",&p2[i]),p2[i]--;
for(i=0;i<n;i++)
scanf("%lf",&p[i]);
for(i=0;i<V;i++)
for(j=0;j<V;j++)
d[i][j]=(i==j)?0:INF;
for(i=0;i<E;i++){
scanf("%d%d%d",&u,&v,&c);
if(d[u-1][v-1]>c)
d[u-1][v-1]=d[v-1][u-1]=c;
}
floyd();
}
void solve(){
int i,j,A,B,C,D;
double choice,ans=inf;
for(i=0;i<n;i++)
for(j=0;j<=m;j++)
f[i][j][0]=f[i][j][1]=inf;
f[0][0][0]=f[0][1][1]=0;
for(i=1;i<n;i++){
A=d[p1[i-1]][p1[i]],
B=d[p1[i-1]][p2[i]],
C=d[p2[i-1]][p1[i]],
D=d[p2[i-1]][p2[i]];
f[i][0][0]=f[i-1][0][0]+A;
for(j=1;j<=m;j++){
choice=min(f[i-1][j][0]+A,
f[i-1][j][1]+p[i-1]*C+(1-p[i-1])*A);
f[i][j][0]=min(f[i][j][0],choice);
choice=min(f[i-1][j-1][0]+p[i]*B+
(1-p[i])*A,
f[i-1][j-1][1]+p[i-1]*p[i]*D+
(1-p[i-1])*p[i]*B+
p[i-1]*(1-p[i])*C+
(1-p[i-1])*(1-p[i])*A);
f[i][j][1]=min(f[i][j][1],choice);
}
}
for(i=0;i<=m;i++)
ans=min(ans,min(f[n-1][i][0],f[n-1][i][1]));
printf("%.2lf\n",ans);
}
int main(){
init();
solve();
return 0;
}
提高D2T1 组合数问题
这题给你公式就是给你坑。（如果你不会求逆元的话）
实际上没有必要求逆元，直接拿组合数经典公式就可以做了。
我们知道：。
同时，如果一个组合数是$k$的倍数，那么。
所以就$O(nm)$递推一下，在递推的过程中让对$k$取模，如果结果为$0$就在当前位置记录一下。
这样可以解决一次回答，但时间复杂度不够优，每次都这么做是的，可能只能过70%左右的数据。
发现$k$不变，所以考虑预处理再回答。这里使用前缀和思想。
设$ans(n,m)$表示所有$0\le i\le n,0\le j \le m$中，有多少是$k$的倍数，即。先求出每一行的前缀和，再求一次每一列的前缀和就可得到所有的$ans(n,m)$。（详见代码）
这样回答一个询问的时间是$O(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
using namespace std;
int T,k,C[2005][2005],sum[2005][2005]={0},maxn=0,maxm=0,n[10005],m[10005];
void init(){
int i,j,v;
for(i=0;i<=maxn;i++)
C[i][0]=1;
for(i=1;i<=maxn;i++)
for(j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%k;
for(i=1;i<=maxn;i++)
for(j=1;j<=maxm;j++){
if(j<=i&&C[i][j]==0)v=1;else v=0;
sum[i][j]=sum[i-1][j]+v;
}
for(i=1;i<=maxn;i++)
for(j=1;j<=maxm;j++)
sum[i][j]+=sum[i][j-1];
}
int main(){
scanf("%d%d",&T,&k);
for(int i=1;i<=T;i++)
scanf("%d%d",&n[i],&m[i]),maxn=max(maxn,n[i]),maxm=max(maxm,m[i]);
init();
for(int i=1;i<=T;i++)
printf("%d\n",sum[n[i]][m[i]]);
return 0;
}
提高D2T2 蚯蚓
考场上我想到了这个方法，但因为没证明所以不敢用。。。
结果一看题解就吓傻了。
可以证明同一种切法下，先切割的比后切割的长度会更长，所以维护$3$个递减队列，然后先把所有初始蚯蚓放在队列$1$，然后不断取出，把$\lfloor px\rfloor$的放在队列$2$中，$x-\lfloor px\rfloor $放在队列$3$中，每一次取$1,2,3$中最大值出来切。
注意：1.维护下标（切的时间）很麻烦，不妨直接先减去当前时间和$q$的乘积，然后到了它在加上。
为什么可以这么做？因为一条蚯蚓的实际长度是，展开得，所以队列里只需要维护前面括号里的元素即可。相应的，在求最大值时，初始最大值要取很小，因为要维护的值可能是个很小的负数。
2.要卡常，STL慢的飞起。
时间复杂度$O(n+m)$。
补充证明上面那个性质。
假设有$2$条蚯蚓长度分别是$a,b(a>b)$，那么$a$会比$b$先被切。
设两个蚯蚓被切得时间点分别是，比例是$p$，那么时刻切完后四个蚯蚓的长度分别是
$\lfloor p\times a\rfloor +(t_b-t_a)\times q,a-\lfloor p\times a\rfloor+(t_b-t_a)\times q,\lfloor p\times b\rfloor,b-\lfloor p\times b\rfloor$。
显然有
和。
所以上面的命题成立，证毕。大家都看的出来好嘛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
using namespace std;
int q1[100005]={0},q2[7000005],q3[7000005],n,m,q,u,v,t;
int f1=0,f2=0,f3=0,r1=0,r2=0,r3=0;
double xs,tmp;
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
xs=u,xs/=(double)v;
int i,j,k,maxi,_max,fi,se,ok=0;
for(i=0;i<n;i++)
scanf("%d",&q1[i]);
sort(q1,q1+n);
r1=n,reverse(q1,q1+n);
for(i=0;i<m;i++){
maxi=_max=0x80000001;
if(r1>f1)maxi=1,_max=q1[f1];
if(r2>f2&&_max<q2[f2])maxi=2,_max=q2[f2];
if(r3>f3&&_max<q3[f3])maxi=3,_max=q3[f3];
if(maxi==1)f1++;
if(maxi==2)f2++;
if(maxi==3)f3++;
_max+=i*q;
if((i+1)%t==0){
if(ok)printf(" ");
ok=1,printf("%d",_max);
}
tmp=_max,tmp*=xs;
fi=(int)floor(tmp),se=_max-fi;
q2[r2++]=fi-(i+1)*q,
q3[r3++]=se-(i+1)*q;
}
printf("\n");
for(ok=i=0;i<m+n;i++){
maxi=_max=0x80000001;
if(r1>f1)maxi=1,_max=q1[f1];
if(r2>f2&&_max<q2[f2])maxi=2,_max=q2[f2];
if(r3>f3&&_max<q3[f3])maxi=3,_max=q3[f3];
if(maxi==1)f1++;
if(maxi==2)f2++;
if(maxi==3)f3++;
_max+=m*q;
if((i+1)%t==0){
if(ok)printf(" ");
ok=1,printf("%d",_max);
}
}
printf("\n");
return 0;
}
提高D2T3 愤怒的小鸟
状压搜索/DP
枚举抛物线，看一次抛物线能砸死哪些猪，然后跑DP
搜索过不去？那就卡时呗。
DP？设$f(i,S)$表示解决了前i头猪，正在解决第$i+1$头，猪被打死的情况为$S$的最小方案数。那么先算出以包含第$i$头猪在内的所有抛物线能砸死的猪的情况（压位表示），然后跑记忆化搜索即可。
时间复杂度：
搜索：$O($你卡时就能过$)$
DP：$O($你不卡时也能过$)$
实际检验发现，搜索效率很高，对于小数据非常轻松。但DP的发挥更加稳定，不会被奇奇怪怪的东西卡死。
在洛谷上，搜索不卡时95分，花费254ms；DP花费2154ms。
DP做法
1 |
|
搜索做法
1 |
|