普及T1 计数问题
某一道著名数位DP的弱化版。
模拟即可，时间复杂度为$O(n)$。1
2
3
4
5
6
7
8
9
10
11
using namespace std;
int n,ans=0,x;
int main(){
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++)
for(int j=i;j;j/=10)
ans+=(j%10==x);
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
using namespace std;
char k[1200005]={0};
int len,st[2][100005]={0},top[2]={0},pro[255];
void push(int a,int to){
st[to][top[to]++]=a;
}
int pop(int to){
top[to]--;
return st[to][top[to]];
}
void opr(){
int a1,a2,p;
a2=pop(1),a1=pop(1),p=pop(0);
if(p=='+')push((a1+a2)%10000,1);
if(p=='*')push((a1%10000)*(a2%10000)%10000,1);
}
int main(){
fgets(&k[1],1200000,stdin);
k[0]='(',len=strlen(k);
while(isspace(k[len-1]))
k[--len]='\0';
k[len++]=')';
pro['+']=pro['-']=1;
pro['*']=pro['/']=2;
int sum=-1;
for(int i=0;i<len;i++){
if(isdigit(k[i])){
if(sum==-1)sum=k[i]-'0';
else sum=sum*10+k[i]-'0';
}else{
if(sum>-1)
push(sum,1),sum=-1;
if(k[i]=='(')
push('(',0);
else if(k[i]==')'){
while(st[0][top[0]-1]!='(')
opr();
pop(0);
}else{
while(st[0][top[0]-1]!='('&&pro[st[0][top[0]-1]]>=pro[k[i]])
opr();
push(k[i],0);
}
}
}
printf("%d\n",pop(1)%10000);
return 0;
}
普及T3 小朋友的数字
容易看出这是一个最大子段和的问题。我们知道小朋友的分数是不递减的，所以边算便取模即可。
完了吗？
没有。
相信很多人都挂在了第一个点。
这个点很有意思，因为通过它，我们发现上文的一个重要结论是错的。
小朋友的分数在第2-n个是不递减的。但第一个不是。
所以要加上对第一个的特判，方法就是：如果当前记录的（分数+特征值）的最大值还是负数，答案就取第一个分数和当前分数的较大值，否则直接取当前分数。因为如果（分数+特征值）的最大值还是负数，那么他一定还有可能小于第一个的分数。
时间复杂度：$O(n)$。
本题代码可能有疏漏，如果能hack掉请告诉我一声，谢谢！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
using namespace std;
typedef long long ll;
ll d,maxspc=-INF,sum=0,ans,maxi=-INF,mini=INF,p,sc,beg;
int n;
int main(){
scanf("%d%lld%lld",&n,&p,&d);
mini=0,sum=d,maxi=d,maxspc=2*d,sc=maxi%p,ans=maxi%p;
beg=d;
for(int i=2;i<=n;i++){
mini=min(mini,sum),
scanf("%lld",&d),sum+=d,
maxi=max(maxi,sum-mini);//sp[i]
sc=maxspc%p;
if(maxi>0){
maxspc=(maxi+sc)%p;
if(maxspc<0)ans=max(sc,beg);
else ans=sc;
}
}
printf("%lld\n",ans);
return 0;
}
普及T4 车站分级
一眼看出来是差分约束，后来发现这个图是一个$DAG$（题目保证存在这么一个方案，就不会有环的存在），求最长路可以直接跑拓扑排序，所以就做完了。
时间复杂度为$O(n^2m)$，理论上如此，但实际操作中还行。（主要花在建图上）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
using namespace std;
typedef long long ll;
int n,m,cnt[1005]={0},to[1005][1005],lis[1005];
int vis[1005],d[1005]={0},que[1005],f,r,du[1005]={0};
bool mat[1005][1005]={0};
void init(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
memset(vis,0,sizeof(vis));
int u,v,k,fi,en;
scanf("%d",&k);
for(int j=0;j<k;j++)
scanf("%d",&lis[j]),vis[lis[j]]=1;
fi=lis[0],en=lis[k-1];
//有无人向我连边？
for(int j=fi+1;j<en;j++){
if(vis[j])continue;
for(u=0;u<k;u++)
if(!mat[j][lis[u]])
mat[j][lis[u]]=1,
to[j][cnt[j]++]=lis[u],
du[lis[u]]++;
}
}
}
void solve(){
int i,j,lst,at,ans=0;
memset(vis,0,sizeof(vis));
fill(d+1,d+n+1,-1);
f=r=0;
for(i=1;i<=n;i++)
if(!du[i])
d[i]=0,que[r++]=i;
while(r-f){
int h=que[f++],v;
for(int i=0;i<cnt[h];i++){
v=to[h][i];
d[v]=max(d[v],d[h]+1);
du[v]--;
if(!du[v])que[r++]=v;
}
ans=max(ans,d[h]);
}
printf("%d\n",ans+1);
}
int main(){
init();
solve();
return 0;
}
提高D1T1 转圈游戏
相当于每一次对编号加一个$m$，然后对$n$取模，如此做$10^k$次。
所以答案就是$(m+m+m+…+m+x)\mod n=(m\times 10^k+x)\mod n$。
使用快速幂即可，时间复杂度$O(logk)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
typedef long long ll;
ll Pow(ll a,ll b,ll c){
ll res=1;
while(b){
if(b&1)res=(res*a)%c;
a=(a*a)%c,b>>=1;
}
return res;
}
ll n,m,k,x;
int main(){
scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
printf("%lld\n",((Pow(10%n,k,n))*m+x)%n);
return 0;
}
提高D1T2 火柴排队
如果你知道什么叫排序不等式，这题就是道裸题。
如果你不知道，额，你也可以自己证明：当，时，。
这样，我们得到结论：当上下两列火柴的大小关系相互对应时两列火柴间的距离最小。也就是说，第一列的第一长对第二列的第一长，第一列的第二长对第二列的第二长，以此类推。
得到这个结论，问题解决了一半。另一半问题在于：怎么求最小步数。
仔细读题，发现这个排序方式其实就是交换排序。然后我们可以发现另一个结论：只对上一列或者下一列的火柴进行排序，或者两列都动，最短步数不变。
这是因为当我们把某一列的火柴排列看作是一个排名（比方说$2,1,4,3$，长度第二的排名是$1$，长度第一的排名是$2$，以此类推），然后对另一列火柴按照这样的排名去排序时，另一列火柴的逆序对数不变。而我们知道，逆序对数就是总的交换步数。
可能有些难以理解，不妨手算验证这个结论。
因此，离散化后求一次逆序对即可，时间复杂度是$O(nlogn)$。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
using namespace std;
//第一行-->名次-->下标
//第二行-->名次-->下标 沿用以上
int a[100005],b[100005],to[100005],n,t[100005],t1[100005];
long long ans=0;
void Merge(int s,int h,int e){
int lp=s,rp=h,pos=s;
while(lp<h&&rp<=e)
if(t1[lp]<=t1[rp])
t[pos++]=t1[lp++];
else
ans+=h-lp,
t[pos++]=t1[rp++];
while(lp<h)t[pos++]=t1[lp++];
while(rp<=e)t[pos++]=t1[rp++];
memcpy(t1+s,t+s,sizeof(int)*(e-s+1));
}
void MSort(int l,int r){
if(l==r)t[l]=t1[l];
else{
int m=(l+r)/2;
MSort(l,m),
MSort(m+1,r),
Merge(l,m+1,r);
}
}
int main(){
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++)
scanf("%d",&a[i]),
t[i]=a[i];
for(i=0;i<n;i++)
scanf("%d",&b[i]),
t1[i]=b[i];
sort(a,a+n),
sort(b,b+n);
memset(to,-1,sizeof(to));
for(i=0;i<n;i++){
j=lower_bound(a,a+n,t[i])-a;
while(to[j]>=0)j++;
to[j]=i;
}
for(i=0;i<n;i++)
j=lower_bound(b,b+n,t1[i])-b,
t1[i]=to[j];
MSort(0,n-1);
printf("%lld\n",ans%99999997);
return 0;
}
提高D1T3 货车运输
我们希望每一个点到其他点的路上的限重的最小值都尽量大。
有一种叫最大瓶颈生成树的东西可以满足你的需求。
怎么求他？求一个最大生成树，完。
怎么求两点间路上限重的最小值？求一个LCA，记录一下，完。
细节很多，但不难。
使用$kruskal$和倍增求$LCA$的话，时间复杂度为$O(mlogm+qlogn)$。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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
using namespace std;
struct Edge{
int u,v,cost,nex;
};
Edge edge[110005];
int cmp(const void *a,const void *b){
int *c=(int*)a,*d=(int*)b;
return edge[*c].cost-edge[*d].cost;
}
int n,m,q,par[10005],at[10005],cnt=0,_par[10005][15];
int son[10005],bro[10005],depth[10005],que[10005],f,r;
int id[100005],dis[10005][15];
char vis[100005]={0},_vis[10005]={0};
//1.dfs出每个点所在集合并用id表示
//2.求出每一个集合的最小生成树
//3.大力lca，求最短容量
void addedge(int _u,int _v,int _c){
edge[cnt].u=_u,
edge[cnt].v=_v,
edge[cnt].cost=_c,
edge[cnt].nex=at[_u],
at[_u]=cnt++;
}
void _init(int S){
int i,j,h,u,v,c;
f=r=0;
que[r++]=S,_vis[S]=1;
depth[S]=1;
while(r-f){
h=que[f++];
for(i=at[h];i!=-1;i=edge[i].nex){
v=edge[i].v,c=edge[i].cost;
if(vis[i]&&!_vis[v]){//这条边和这个点都访问过
_par[v][0]=h,dis[v][0]=c,
bro[v]=son[h],son[h]=v,
depth[v]=depth[h]+1,
_vis[v]=1,que[r++]=v;
}
}
for(i=1;i<=14;i++)
if(_par[h][i-1]>=0)
_par[h][i]=_par[_par[h][i-1]][i-1],
dis[h][i]=max(dis[h][i-1],dis[_par[h][i-1]][i-1]);
else break;
}
}
int query(int u,int v){
int i,j,d,ans=-999999;
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])
ans=max(ans,dis[u][i]),
u=_par[u][i];
if(u==v)return -ans;
for(i=14;i>=0;i--)
if(_par[u][i]>=0&&_par[u][i]!=_par[v][i])
ans=max(ans,max(dis[u][i],dis[v][i])),
u=_par[u][i],v=_par[v][i];
ans=max(ans,max(dis[u][0],dis[v][0]));
return -ans;
}
void init(){
for(int i=1;i<=n;i++)
par[i]=i;
}
int Find(int x){
if(par[x]==x)return x;
return (par[x]=Find(par[x]));
}
void unite(int x,int y){
par[Find(x)]=Find(y);
}
void kruskal(){
qsort(id,cnt,sizeof(id[0]),cmp);
int Cnt=n,cur=0,_u,_v,i;
while(cur<cnt){
_u=edge[id[cur]].u,_v=edge[id[cur]].v;
if(Find(_u)!=Find(_v)){
unite(_v,_u),Cnt--;
if(id[cur]&1)
vis[id[cur]]=vis[id[cur]-1]=1;
else
vis[id[cur]]=vis[id[cur]+1]=1;
}
cur++;
}
//在这里建树，求出_par
for(i=1;i<=n;i++)
if(!_vis[Find(i)])
_init(par[i]);
}
void read(){
scanf("%d%d",&n,&m);
int i,x,y,z;
memset(at,-1,sizeof(at));
for(i=0;i<m;i++)
scanf("%d%d%d",&x,&y,&z),
addedge(x,y,-z),
addedge(y,x,-z);
for(i=0;i<cnt;i++)
id[i]=i;
}
void solve(){
init();
memset(son,-1,sizeof(son));
memset(bro,-1,sizeof(bro));
memset(_par,-1,sizeof(_par));
kruskal();
}
void answer(){
scanf("%d",&q);
int u,v,ans;
while(q--){
scanf("%d%d",&u,&v);
if(Find(u)==Find(v))
printf("%d\n",query(u,v));
else printf("-1\n");
}
}
int main(){
read();
solve();
answer();
return 0;
}
提高D2T1 积木大赛
$O(n)$做法
发现对于一个不递减的区间，它的搭建次数为最高的那个的高度。所以把整个积木序列拆成尽量多的不递减段即可。
具体做法是从左到右遍历，每次记录当前段最高点，如果这个位置上的积木比前面的高就加上搭建当前高度所需要的次数（即当前高度-最大高度），并且直接更新最高点，否则更新最高点，因为此时已经开始了新的一个段，当前积木就是新段的开头。1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int h,maxi,n,ans=0;
int main(){
scanf("%d%d",&n,&maxi);
ans+=maxi;
for(int i=2;i<=n;i++){
scanf("%d",&h);
if(h>maxi)ans+=h-maxi;
maxi=h;
}
printf("%d\n",ans);
return 0;
}
$O(nlogn)$做法
把搭积木想象成拆积木，一次拆一层，从低往高拆。所以把积木按高度排序，每一次把最低的一层积木全部弹掉，然后动态维护一下段数即可。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
using namespace std;
pair<int,int> high[100005];
int n,ans=0,l=1;
char destroyed[100005]={0};
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&high[i].first),high[i].second=i;
sort(high+1,high+1+n);
int low=high[1].first,last=0,loc;
destroyed[0]=destroyed[n+1]=1;
for(int i=1;i<=n;i++){
ans+=(low-last)*l;
while(i<=n&&high[i].first==low){
loc=high[i].second,
destroyed[loc]=1;
if(destroyed[loc-1]||destroyed[loc+1]){
if(destroyed[loc-1]&&destroyed[loc+1])l--;
}else l++;
i++;
}
last=low,low=high[i--].first;
}
printf("%d\n",ans);
return 0;
}
提高D2T2 花匠
好迷啊这题，可以贪心也可以DP。。。
DP做法
保存2个dp值，记录最后一次是上升时/下降时的长度以及花的高度。
然后两个DP值之间相互转移。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
using namespace std;
int d[100005],n,f1[2],f2[2];
int main(){
scanf("%d",&n);
int i,j,t,ans=1;
for(i=0;i<n;i++)
scanf("%d",&d[i]);
f1[0]=f2[0]=1,f1[1]=f2[1]=d[0];
for(i=1;i<n;i++){
if(d[i]>=f1[1]&&d[i]>=f2[1]){
if(f1[0]>f2[0])f1[1]=max(f1[1],d[i]);
else f1[1]=d[i],f1[0]=f2[0]+1;
}else if(d[i]<f1[1]&&d[i]>f2[1]){
if(f1[0]>=f2[0])f2[1]=d[i],f2[0]=f1[0]+1;
else f1[1]=d[i],f1[0]=f2[0]+1;
}else{
if(f2[0]>f1[0])f2[1]=min(f2[1],d[i]);
else f2[1]=d[i],f2[0]=f1[0]+1;
}
}
printf("%d\n",max(f1[0],f2[0]));
return 0;
}
贪心做法
类似于模拟？直接记录当前要找的是波峰还是波谷，然后可以从波峰到波谷或者可以从波谷到波峰的话就计数器+1，然后更新下一个要找的波形。波峰波谷判断不需要记录什么特别的变量，只要看当前高度比之前高还是比之前低即可。具体代码参考洛谷题解，我只在此解释一下。
提高D2T3 华容道（待修正）
容易发现一个棋子移动的必要条件是它的四个方向上有空白格子。
容易观察到，所谓的棋子的移动，等价于空白格子的移动。
我们会想到求出一个格子到其他所有格子的最短步数，但这时我们会发现：空方格不能经过指定棋子，否则不符合条件。强行这么做的时间复杂度是$O(V^3)$的，显然不行。
但这时可以发现，对于一个可能的位置$(x,y)$而言，
所以，一开始先把空白格子移到指定棋子的周围，并且算出这个步数。然后以指定棋子的坐标和空格的相对位置所构成的三元组跑$SPFA$即可，时间复杂度$O(nmq+n^2m^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
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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;
}
struct Pos{
int x,y,d;//空格在指定棋子周围的位置 0上 1下 2左 3右
};
Pos que[1000005];
struct Dis{
int ddis[32][32];
Dis(){
memset(ddis,0x3f,sizeof(ddis));
}
};
Dis D[32][32][4];
int dis[32][32][5],n,m,q,f,r;
int bdis[32][32];
int ex,ey,sx,sy,tx,ty,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
bool mp[32][32],in[32][32][5];
void bfs(int xx,int yy,Dis *dist){
f=r=0;
que[r].x=xx,que[r++].y=yy,dist->ddis[xx][yy]=0;
int cx,cy,px,py,_dis;
while(r>f){
cx=que[f].x,cy=que[f++].y;
_dis=dist->ddis[cx][cy];
//printf("%d %d\n",cx,cy);
for(int i=0;i<4;i++){
px=cx+dx[i],py=cy+dy[i];
if(!mp[px][py]||dist->ddis[px][py]<=_dis+1)continue;
dist->ddis[px][py]=_dis+1;
que[r].x=px,que[r++].y=py;
}
}
}
void bfs1(){
memset(bdis,-1,sizeof(bdis));
f=r=0;
que[r].x=ex,que[r++].y=ey,bdis[ex][ey]=0;
int cx,cy,px,py;
while(r>f){
cx=que[f].x,cy=que[f++].y;
for(int i=0;i<4;i++){
px=cx+dx[i],py=cy+dy[i];
if(!mp[px][py])continue;
if(px==sx&&py==sy)continue;
if(bdis[px][py]>=0)continue;
bdis[px][py]=bdis[cx][cy]+1;
que[r].x=px,que[r++].y=py;
}
}
f=r=0;
for(int i=0;i<4;i++){
px=sx+dx[i],py=sy+dy[i];
if(!mp[px][py]||bdis[px][py]<0)continue;
dis[sx][sy][i]=bdis[px][py],
que[r].x=sx,que[r].y=sy,que[r++].d=i,
in[sx][sy][i]=1;
}
}
inline void update(int cx,int cy,int dd,int _dis){
if(dis[cx][cy][dd]>_dis){
dis[cx][cy][dd]=_dis;
if(!in[cx][cy][dd])
in[cx][cy][dd]=1,
que[r].x=cx,que[r].y=cy,que[r++].d=dd;
}
}
void bfs2(){
int cx,cy,dd,px,py,_dis;
Dis *dist;
while(r>f){
cx=que[f].x,cy=que[f].y,dd=que[f++].d;
_dis=dis[cx][cy][dd],dist=&D[cx][cy][dd];
in[cx][cy][dd]=0;
for(int i=0;i<4;i++){
if(i==dd)continue;
update(cx,cy,i,_dis+dist->ddis[cx+dx[i]][cy+dy[i]]);
}
if(dd==0){
update(cx-1,cy,1,_dis+1);
}else if(dd==1){
update(cx+1,cy,0,_dis+1);
}else if(dd==2){
update(cx,cy-1,3,_dis+1);
}else {
update(cx,cy+1,2,_dis+1);
}
}
}
void init(){
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mp[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]){
mp[i][j]=0;
for(int k=0;k<4;k++){
int px=i+dx[k],py=j+dy[k];
if(!mp[px][py])continue;
bfs(px,py,&D[i][j][k]);
}
mp[i][j]=1;
}
}
void solve(){
ex=read(),ey=read(),sx=read(),sy=read(),
tx=read(),ty=read();
if(sx==tx&&sy==ty){
printf("0\n");
return ;
}
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
bfs1();
bfs2();
int ans=0x3f3f3f3f;
for(int i=0;i<4;i++)
ans=min(ans,dis[tx][ty][i]);
if(ans==0x3f3f3f3f)printf("-1\n");
else printf("%d\n",ans);
}
int main(){
init();
while(q--)solve();
return 0;
}