洛谷1525 关押罪犯

  • 发现题解里面二分图的解法都是(基本上)$bfs$的,所以我就来一发$dfs$的,应该也挺快$(269ms)$,我没有打快读。
  • 至于为什么要二分图我就不解释了,楼上都说的很清楚。二分枚举最大的冲突大小$(Max)$,然后进行二分图染色,如果一条边的权值,小于$Max$,就不鸟它,即把这条边所连接的点暂时保持原来的颜色。因为可能这个点会在后面的$dfs$中被染色。
  • 打个广告:$Blog$
  • 翻了所有的题解,发现竟然没有用$Trie$字典树做的,那我就来一发。
  • $Trie$字典树的复杂度对于这道题来说还行,刚好卡的过去,我只是提供一种思路,泥萌最好还是用哈希表。
  • 计算复杂度:
    • 数字长度$\leq 32$,数字总数$\leq 50000$,数据组数$\leq 50$
    • 最坏所有数字都不一样,一组数据共建树结点次数:$32 \times 50000 = 1600000 = 1.6 \times 10^6$。
    • $50$组数据:$1.6 \times 10^6 \times 50 = 8 \times 10^7$
  • 所以说可以刚刚好卡过了。
  • 算法:
    • 每读入一个数,就添加到字典树中,到最后一个结点发现不存在时,输出这个数;存在时,不输出这个数。以达到去重效果。

洛谷1194 买礼物

  • 图论的最后这道题竟然这么简单,只有建图的问题,其他就是非常基础最小生成树了。
  • 优惠就是图中的一条边,不要建边两次,最小生成树我用的是$Kruskal$。
  • Code:
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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int u,v,w;
}e[250005];
int A,B,cnt,tot=1,ans,f[505];
bool cmp(node x,node y){
return x.w<y.w;
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void Update(int a,int b){
int x=find(a);
int y=find(b);
if(x!=y) f[x]=y;
return;
}
void addEdge(int a,int b,int c){
cnt++;
e[cnt].u=a;
e[cnt].v=b;
e[cnt].w=c;
return;
}
void kruskal(){
int i=1;
while (i<=cnt&&tot<=B){
if (find(e[i].u)!=find(e[i].v)){
tot++;
ans+=e[i].w;
Update(e[i].u,e[i].v);
}
i++;
}
return;
}
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++){
int w;
scanf("%d",&w);
if(i<j&&w!=0) addEdge(i,j,w);//0的情况要特判!
}
for(int i=1;i<=B;i++) addEdge(0,i,A);
for(int i=0;i<=B;i++) f[i]=i;
sort(e+1,e+cnt+1,cmp);
kruskal();
printf("%d\n",ans);
return 0;
}

洛谷1144 最短路计数

  • 本来写了个和一些题解比较相像的什么$SPFA$、$Dijkstra$之类的,后面出$bug$懒得弄了,就看了眼题解,第一篇$dalao$用$bfs$做,做法十分清爽,不得不orz。但是为什么很多$dalao$写的题解都比较简略呢。。。。看来我太菜了吧QAQ

  • 所以我就写了一篇$dalao​$代码较详细的解释。因为边的权值都为1,所以这道题才能用$bfs​$,$dalao​$说的:

    一个点最短路一定经过了一个层数比它少一的结点(否则不是最短路)。

    所以用每个相邻且层数比当前结点层数少一的点更新当前点的路径跳数即可。

    有一些人看不懂,这中间的层数就是离源点(顶点1)的距离,或者说是$bfs$搜索树的深度。所以这个最短路一定是沿着从深度比它少1的结点来的,不然它就不算最短路,这个跳数应该就是把最短路数量从旁边的点转移过来。

  • Code:更多解释请看代码

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 1<<30
#define Mod 100003
using namespace std;
vector<int> G[1000005];//注意这是2维数组,用来存每一个点所连的边,而题目中有10^6个点,所以是10^6+5
queue<int>Q;//bfs所需要的队列
int dep[1000005],cnt[1000005];//dep是每个点对于源点的深度,cnt储存答案,即到点i的最短路个数
bool vis[1000005];//判断点是否使用
int main(){
int N,M;
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++){
int x,y;scanf("%d%d",&x,&y);
G[x].push_back(y);//存边,无向图存有向边两次
G[y].push_back(x);
}
dep[1]=0;
vis[1]=1;
Q.push(1);
cnt[1]=1;
while(!Q.empty()){//bfs核心代码
int x=Q.front();
Q.pop();
for(int i=0;i<G[x].size();i++){//遍历点所连的每一条边
int t=G[x][i];
if(!vis[t]){
vis[t]=1;
dep[t]=dep[x]+1;//深度+1
Q.push(t);
}
if(dep[t]==dep[x]+1)//dalao说的最后一句话,这个点直接从旁边深度-1的结点添加最短路数量
cnt[t]=(cnt[t]+cnt[x])%Mod;//不要忘记要%Mod
}
}
for(int i=1;i<=N;i++)
printf("%d\n",cnt[i]);
return 0;
}
  • %%%GGN_2015
  • 本人个人Blog,欢迎$dalao​$进来拍砖,交换友链什么的^ _ ^

洛谷1074 靶形数组

  • emm,需要一些剪枝的一道题(废话),要从0的个数最少的行开始搜,很显然这样搜出去的分支就会少很多。
  • 因为我太菜了,所以我这题抄了下题解……
  • Code:
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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10;
int a[N][N],ans[N][N],vis[3][N][N],b[82],maxn,flag;
struct Row{
int h,zero_cnt;
}row[N];
int cmp(Row row1,Row row2){
return row1.zero_cnt<row2.zero_cnt;
}
int getGrid(int x,int y){//获取在哪个小格子
if(x>=1&&x<=3){
if(y>=1&&y<=3) return 1;
else if(y>=4&&y<=6) return 2;
else return 3;
}
if(x>=4&&x<=6){
if(y>=1&&y<=3) return 4;
else if(y>=4&&y<=6) return 5;
else return 6;
}
if(x>=7&&x<=9){
if(y>=1&&y<=3) return 7;
else if(y>=4&&y<=6) return 8;
else return 9;
}
}
int getScore(int x,int y){//获取搜索完后的得分
if(x==1||y==1||x==9||y==9) return 6;
else if(x==2||y==2||x==8||y==8) return 7;
else if(x==3||y==3||x==7||y==7) return 8;
else if(x==4||y==4||x==6||y==6) return 9;
else return 10;
}
int cal(){
int sum=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
sum+=ans[i][j]*getScore(i,j);
return sum;
}
void dfs(int xh){
if(xh>81){
flag=1;
maxn=max(maxn,cal());
return;
}
int x=b[xh]/9+1;
int y=b[xh]%9;
if(y==0)
x=b[xh]/9,y=9;
if(!a[x][y]){
for(int j=1;j<=9;j++){
int g=getGrid(x,y);
if(!vis[0][x][j]&&!vis[1][y][j]&&!vis[2][g][j]){
ans[x][y]=j;
vis[0][x][j]=1,vis[1][y][j]=1,vis[2][g][j]=1;
dfs(xh+1);
vis[0][x][j]=0,vis[1][y][j]=0,vis[2][g][j]=0;
}
}
}
else dfs(xh+1);
return;
}
void Init(){
for(int i=1;i<=9;i++){
int cnt=0;
for(int j=1;j<=9;j++){
cin>>a[i][j];
if(a[i][j]==0)
cnt++;
else{
int v=a[i][j];
int g=getGrid(i,j);
ans[i][j]=v;
vis[0][i][v]=1,vis[1][j][v]=1,vis[2][g][v]=1;
}
}
row[i].h=i;
row[i].zero_cnt=cnt;
}
sort(row+1,row+9+1,cmp);
int num=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
int x=row[i].h,y=j;
num++;
b[num]=(x-1)*9+y;
}
return;
}
int main(){
Init();
dfs(1);
if(flag)
cout<<maxn<<endl;
else
cout<<-1<<endl;
return 0;
}
  • 最短路径基本上就用$bfs$,这道题很恶心的地方是要把障碍物转化为格点上的障碍,还有不能贴着墙壁走,还要判断机器人有没有跳过障碍物。
  • 性能也要优化,在$book​$数组中还要加一个方向,这玩意如果不标记会很耗空间和时间。
  • Code:
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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
int dic,x,y,ans;
}t,now;
queue<node> q;
int n,m,fx,fy;
int cmp[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool p[105][105],book[105][105][4];
bool check(node next){//判断障碍物和边界
if (next.x<=1||next.x>=n+1||next.y<=1||next.y>n+1) return false;
if (book[next.x][next.y][next.dic]||p[next.x][next.y]) return false;
return true;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
int num;
scanf("%d",&num);
if (!num) continue;
p[i+1][j+1]=true;
p[i][j+1]=true;
p[i+1][j]=true;
p[i][j]=true;
}
char ch;
scanf("%d%d%d%d",&t.x,&t.y,&fx,&fy);
cin >>ch;
t.x++;
t.y++;
fx++;
fy++;
if (ch=='N') t.dic=0;
else if (ch=='E') t.dic=1;
else if (ch=='S') t.dic=2;
else if (ch=='W') t.dic=3;
book[t.x][t.y][t.dic]=true;
q.push(t);
while (!q.empty()){
now=q.front();
q.pop();
if (now.x==fx&&now.y==fy){
printf("%d\n",now.ans);
return 0;
}
node next=now;
next.ans++;
next.dic=now.dic-1;
if (next.dic<0) next.dic=3;
if (!book[now.x][now.y][next.dic]){
book[now.x][now.y][next.dic]=true;
q.push(next);
}
next.dic=now.dic+1;
if (next.dic>3) next.dic=0;
if (!book[now.x][now.y][next.dic]){
book[now.x][now.y][next.dic]=true;
q.push(next);
}
for (int i=1;i<=3;i++){
next=now;
next.x=now.x+cmp[now.dic][0]*i;
next.y=now.y+cmp[now.dic][1]*i;
next.ans=now.ans+1;
if (check(next)){
book[next.x][next.y][next.dic]=true;
q.push(next);
}
else break;
}
}
printf("-1\n");
return 0;
}

洛谷1123 取数游戏

  • 对于所有要大暴搜的$dfs$,一定要把能剪得枝都剪了,不然很容易爆空间、爆时间。
  • 直接大暴搜即可,只要在选点的时候进行判断是否合法即可。
  • Code:
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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,data[20][20],ans,T;
bool book[20][20];
bool check(int x,int y){
if (!book[x][y+1]&&!book[x][y-1]&&!book[x+1][y]&&!book[x+1][y+1]&&!book[x+1][y-1]&&!book[x-1][y]&&!book[x-1][y+1]&&!book[x-1][y-1])
return true;
return false;
}
void dfs(int x,int y,int sum){
ans=max(ans,sum);
int ty=y+1,tx=x;
if(ty>m){
tx=x+1;
ty=1;
if(tx>n) return;
}
if(check(tx,ty)){
book[tx][ty]=true;
dfs(tx,ty,sum+data[tx][ty]);//选这个点
book[tx][ty]=false;
}
dfs(tx,ty,sum);//不选这个点
return;
}
int main(){
scanf("%d",&T);
while(T--){
ans=0;
memset(book,0,sizeof(book));//初始化
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>data[i][j];
book[1][1]=true;
dfs(1,1,data[1][1]);//注意第一个点也要考虑!
book[1][1]=false;
dfs(1,1,0);
printf("%d\n",ans);
}
return 0;
}

题面

  • 我真是太菜了,所以只能求助于题解,这并不是一道真正的模板题啊QAQ
  • 数据是$10^6$级别的,很显然$O(n^2)$的普通最长公共子序列并不能满足这道题的。但是这道题有一个非常关键的线索:序列是$1$~$n$的全排列,也就是说两个串所包含的元素都相同,但是顺序不同。
  • 所以我们可以再用一个数组来保存第一个串在第二个串中所对应的各元素的位置。这时你会惊奇的发现,最长子序列竟然是这个数组的最长上升子序列的长度!!因为只有在位置保持上升时,这才能在原串中组成子序列。既然这个问题转换成最长上升子序列了,那么肯定就可以想到$O(n \log n)$的算法了~~
  • Code:
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
#include<iostream>
#include<cstdio>
#define INF 999999999
using namespace std;
int a[100005],b[100005],data[100005],stack[100005];
int n,top;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
data[a[i]]=i;
}
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for (int i=1;i<=n;i++)
stack[i]=INF;
stack[0]=0;
for(int i=1;i<=n;i++){
int l=0,r=top,mid;
if(data[b[i]]>stack[top]) stack[++top]=data[b[i]];
else{
while(l<r){
mid=(l+r)>>1;
if(stack[mid]>data[b[i]]) r=mid;
else l=mid+1;
}
stack[l]=min(data[b[i]],stack[l]);
}
}
printf("%d\n",top);
return 0;
}

题面

  • 哈哈哈哈,这道题我水过去了,很显然用标准的最长公共子序列是会爆空间的。但是!!只要你把它改成$short$类型的5000*5000的$dp$数组,就可以水过去了,哈哈哈哈,我不知道是不是数据真的没那么强,还是C++有什么玄学自适应^ _ ^。突然觉得我好机智(逃。
  • Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
short dp[5005][5005],len1,len2;
string a,b;
int main(){
cin >>a>>b;
len1=a.size();
len2=b.size();
memset(dp,0,sizeof(dp));
for(int i=1;i<=len1;i++)
for(int j=1;j<=len2;j++)
if(a[i-1]==b[j-1])
dp[i][j]=max(dp[i][j],short(dp[i-1][j-1]+1));//因为字符串是从0开始的,循环又是从1开始的
else//所以都-1
dp[i][j]=max(dp[i][j-1],dp[i-1][j]);//哪边长接哪边
printf("%d\n",dp[len1][len2]);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×