1. 赛后感言（？）
T1-T3 属于比较简单的一眼题，J组第一题难度
T4 T6 有思路，没写完
T4 二分 + $BFS$
T6 $Tarjan$求环+$Dijstra$最短路
T5 完全没思路,并查集的做法还是比较新奇
4个小时的题只写了不到三个小时，有点可惜
2.分析
1. 猴子识数
题意简化：
给出一个数$X$，如果是回文数，输出是第几个回文数，否则输出“NO！”。
1<=$X$<1e5
思路：
简单枚举
代码：
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
| #include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main() {
int d[2000];
int i,j,n,sum,b;
for(i=1;i<=9;i++)
d[i]=i;
i=10;
for(j=1;j<=9;j++){
d[i]=j*10+j;
i++;
}
for (j=10;j<=99;j++){
d[i]=j*10+j/10;
i++;
}
for (j=10;j<=99;j++){
d[i]=j*100+j%10*10+j/10;
i++;
}
for (j=100;j<=999;j++){
i++;
}
sum=i-1;
cin>>n;
b=0;
for(i=1;i<=sum;i++)
if(n==d[i])
{ b=1; break; }
if(b==1) cout<<i<<endl;
else cout<<"NO!"<<endl;
return 0;
}
|
2.神奇宝贝
题意简化（我也不会）：
L一共有$N$种神奇宝贝，对于第$Pi$种神奇宝贝,第i个神奇宝贝L必须提供$Ki$
个他喜欢的糖果才能让它进化一次，每个神奇宝贝进化成功后，会返回22个
糖果，神奇宝贝只能接受自己喜欢的糖果。现在L已经知道了每个糖果进化
一次需要的糖果数量，并且为每个宝贝准备了一定数量他们喜欢的糖果，现
在L想知道，所有的宝贝的进化次数之和，同时也想知道哪个神奇宝贝的进
化次数最多，如果有一样的进化次数，输出编号小的。
1<=$N$<=70 ，12<=$Ki$<=400 ， 1<=$Mi$<=10000
Pi的长度不超过20
思路：
小学数学青蛙爬井问题（？）
代码：
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
| #include<bits/stdc++.h>
using namespace std;
string s,name;
int n,k,m,t,sum=0,maxn=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s;
scanf("%d%d",&k,&m);
t=0;
while(m>=k){
m-=k;
t++;
m+=2;
}
sum+=t;
if(t>maxn){
maxn=t;
name=s;
}
}
cout<<sum<<endl;
cout<<name<<endl;
return 0;
}
|
3.冲泡咖啡
题意简化：
有$B$个物品，每个物品都有一个体积$Bi$，输出能组合出最大的不超过$C$的数
10 <=$C$<=35,000 ， 1 <=$B$<= 21 ， 1<=$Bi$<=35000
分析：
01背包模板题，其实就是luogu P1049 [NOIP2001 普及组] 装箱问题
因为 $B$<=21, 所以还有一个质朴思路：$DFS$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
int v,n,w[25],c[25],f[35010];
int main(){
scanf("%d%d",&v,&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
c[i]=w[i];
}
for(int i=1;i<=n;i++){
for(int j=v;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+c[i]);
}
}
printf("%d\n",f[v]);
return 0;
}
|
4.紧急撤离
题意简化：
一个$n * m$的矩阵， 其中有p个火源，从 （$x1$，$y1$）走到（$x2$，$y2$），只能
向上下左右走，的过程中，要求离火源的曼哈顿距离的最小值最大，求出这
个最大值以及在这个最大值的限制下的最短距离。
1 ≤$q$≤ 10000 , 1 ≤ $n,m$≤ 1000 , 0 ≤ $x1,y1,x2,y2$< $n,m$
分析：
很容易可以想到这是道bfs的题。
每个点的距火源的最小距离可以通过$BFS$求出
然后考虑求路程。如果直接一次$BFS$或$BFS$搜索坑定会$TLE$。因为是最小化一个最大值很容易想到用二分，$check$函数用$BFS$,用来求此最大值下的最短路径，问题不大。
思路还是很好想的，只是有些搜索的小细节要注意一下。
代码：
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
| #include<bits/stdc++.h>
using namespace std;
struct point{
int x,y,dist;
};
queue<point> q;
int qu,n,m,sx,sy,fx,fy,firex,firey,mp[1005][1005],ans1,ans2;
const int u[4]={0,0,1,-1};
const int v[4]={1,-1,0,0};
int bfs(int dist){
bool vis[1005][1005];
memset(vis,false,sizeof(vis));
queue<point> a;
a.push((point){sx,sy,0});
vis[sx][sy]=true;
while(!a.empty()){
point t=a.front();
a.pop();
if(t.x==fx&&t.y==fy){
return t.dist;
}
for(int i=0;i<4;i++){
int xx=t.x+u[i],yy=t.y+v[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]>=dist&&!vis[xx][yy]){
a.push((point){xx,yy,t.dist+1});
vis[xx][yy]=true;
}
}
}
return -1;
}
int main(){
scanf("%d%d%d",&qu,&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) mp[i][j]=-1;
}
scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
sx++;sy++;fx++;fy++;
for(int i=1;i<=qu;i++){
scanf("%d%d",&firex,&firey);
firex++;firey++;
q.push((point){firex,firey,0});
mp[firex][firey]=0;
}
while(!q.empty()){
point t=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=t.x+u[i],yy=t.y+v[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]==-1){
q.push((point){xx,yy,t.dist+1});
mp[xx][yy]=t.dist+1;
}
}
}
int l=0,r=mp[sx][sy];
while(l<=r){
int mid=(l+r)>>1;
int t=bfs(mid);
if(t!=-1){
ans1=mid;
ans2=t;
l=mid+1;
}
else r=mid-1;
}
printf("%d %d\n",ans1,ans2);
return 0;
}
|
5.边权最小值
题目简化（已经很简化了）：
给定一颗$N$个节点的树，定义两点距离为他们之间路径中边权最小值。
$Q$次询问$K,V$，询问到$V$距离>=$K$的点有多少（不含V）
对于30%的数据，1≤$N,Q$≤1000 , 1≤$N,Q$≤1000。
对于70%的数据，1≤$N$≤2000 , $Q$≤10^5 , 1≤$N$≤2000 , $Q$≤10^5。
对于100%的数据，1≤$N,Q$≤10^5 , 1≤$w,K$≤10^9 , 1≤$N,Q$≤10^5 , 1≤$w,K$≤10^9。
思路：
有部分分了好耶！
30$pts$：
可以考虑floyd求任意两点间的距离。
70$pts$：
对于每一次询问，可以通过dfs搜索，加点优化，问题不大。
100$pts$：
离线+并查集
将每次询问保存进行离线查询。将边和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
| #include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct edge{
int u,v,w,nxt;
}e[maxn<<2];
int u,v,w,k,n,q,cnt=0,h[maxn],fa[maxn],sz[maxn],ans[maxn];
void add(int u,int v,int w){
e[++cnt]=(edge){u,v,w,h[u]};
h[u]=cnt;
}
bool cmpe(edge a,edge b){
return a.w>b.w;
}
struct que{
int id,k,v;
}qst[maxn];
bool cmpq(que a,que b){
return a.k>b.k;
}
int find(int x){
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
x=find(x);y=find(y);
if(x!=y) fa[x]=y;sz[y]+=sz[x];
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
for(int i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for(int i=1;i<=q;i++){
scanf("%d%d",&qst[i].k,&qst[i].v);
qst[i].id=i;
}
sort(e+1,e+n,cmpe);
sort(qst+1,qst+1+q,cmpq);
int num=1;
for(int i=1;i<=q;i++){
while(num<n&&qst[i].k<=e[num].w){
merge(e[num].u,e[num].v);
num++;
}
ans[qst[i].id]=sz[find(qst[i].v)]-1;
}
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
|
6.军队调遣
题目简化：
一有向图，$ai,bi$ 间有条权值为$ti$的有向边。对于一条边$(u,v)$，如果$v$可以到达$u$, 那么经过这条边是就会产生一个单位的疲劳值。求每个点（除1）到点1的最小疲劳值和对应的最短路，如果不能到达，则输出$-1$。
思路
这是个有向图。所以只有存在环的时候才会产生疲劳值。所以先用$Tarjan$求出图中所有的环，然后再跑一边$Dijtstra$。
$Tarjan$就是普通的有向图模板。因为每条边有两个权值，所以要对$Dijstra$进行改进。
1
2
3
4
5
6
| int v=e[i].v,cost=(scc[u]==scc[v])?1:0;
if(len[v]>len[u]+cost){
len[v]=len[u]+cost;
dis[v]=dis[u]+e[i].w;
q.push((node){v,dis[v],len[v]});
}
|
$len$表示疲劳值，$dis$指所对应的权值和。以疲劳值为第一关键字进行松弛操作。
特别的，当疲劳值相同的时候我们还要可能更新$dis$数组。
所以要特别加一句：
1
2
3
| if(len[v]==len[u]+cost){
dis[v]=min(dis[v],dis[u]+e[i].w);
}
|
这道题的思维难度不大，只是码量稍微有点大。
还有一点需要注意：因为是$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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
#define ll long long
struct edge{
ll u,v,w,nxt;
}e[maxn<<2];
ll n,m,u,v,w,cnt=0,h[maxn],dis[maxn],len[maxn];
ll tcnt=0,low[maxn],dfn[maxn],col=0,scc[maxn],vis[maxn];
stack<int> stk;
void add(int u,int v,int w){
e[++cnt]=(edge){u,v,w,h[u]};
h[u]=cnt;
}
void tarjan(int u){
low[u]=dfn[u]=++tcnt;
vis[u]=1;stk.push(u);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int t;++col;
do{
t=stk.top();
stk.pop();
scc[t]=col;
vis[t]=0;
}while(t!=u);
}
}
struct node{
ll v,d,t;
friend bool operator<(node a,node b){
if(a.t==b.t) return a.d>b.d;
return a.t>b.t;
}
};
priority_queue<node> q;
void dijstra(int be){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) dis[i]=len[i]=inf;
q.push((node){be,0,0});
dis[be]=len[be]=0;
while(!q.empty()){
int u=q.top().v;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v,cost=(scc[u]==scc[v])?1:0;
if(len[v]>len[u]+cost){
len[v]=len[u]+cost;
dis[v]=dis[u]+e[i].w;
q.push((node){v,dis[v],len[v]});
}
if(len[v]==len[u]+cost){
dis[v]=min(dis[v],dis[u]+e[i].w);
}
}
}
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w);
add(v,u,w);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
dijstra(1);
for(int i=2;i<=n;i++){
if(len[i]==inf){
printf("-1\n");
continue;
}
printf("%lld %lld\n",len[i],dis[i]);
}
return 0;
}
|
