这里主要收录的是一些算法并不难然而自己没能很快AC的题目，也算是整理一下自己的粗心错误。从2017.12.12开始更新
题楼
这里主要收录的是一些算法并不难然而自己没能很快AC的题目，也算是整理一下自己的粗心错误。从2017.12.12开始更新
luogu1186 玛丽卡
这道题很容易看出来是spfa，先找出最短路，然后一条一条堵住找最短路。
一开始以为要求的是找出的这些最短路里面最小的值，但其实不是这样的。题目要求的其实可以概括为“给出一个时间，堵住特定的一条路，使得堵住后在这个时间内玛丽卡无法到达终点”，仔细思考一下，应该是最大值——假设使最短路达到最大值要堵住的这条边被堵死了，那么在这个最大的最短路之内的时间内是不可能到达终点的，而这个时间内也是包括其它那些堵住其它边的得到的较小的最短路。
这样只需要在spfa的过程中不走特定的某条边就行了。但是我这里疏忽了一件事，这也是让我把这道题添加到题楼里面的原因：我在记录最短路的每条边的编号的时候，用的是出发点来标记，但这样是不对的，因为有可能有多条最短路，而这个出发点也有可能在不同的最短路里面有不同的出边，所以不能标记出发点，但是标记到达点的话就不会有影响。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
struct node
{
int next,to,dis,cnt;
}ljb[1000001];
int n,m,cnt,dis[1001],head[1000001],pre[1001],per[1001],num[1001],nmu[1001],hh;
bool vis[1001];
queue<int> q;
inv add(int x,int y,int z)
{
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].dis=z;
ljb[cnt].cnt=cnt;
head[x]=cnt;
ljb[++cnt].next=head[y];
ljb[cnt].to=x;
ljb[cnt].dis=z;
ljb[cnt].cnt=cnt-1;
head[y]=cnt;
}
inv spfa(int cant)
{
for (rint i=1;i<=n;i++) dis[i]=big;
memset(vis,0,sizeof(vis));
dis[1]=0;vis[1]=1;q.push(1);pre[1]=1;
while (!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for (rint i=head[x];i;i=ljb[i].next)
{
int y=ljb[i].to;
if (dis[y]>dis[x]+ljb[i].dis && ljb[i].cnt!=cant)
{
dis[y]=dis[x]+ljb[i].dis;
pre[y]=x;
num[y]=ljb[i].cnt;
if (!vis[y])
{
q.push(y);
vis[y]=1;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (rint i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
spfa(0);
int x=n;
for (rint i=1;i<=n;i++) per[i]=pre[i];
for (rint i=1;i<=n;i++) nmu[i]=num[i];
int ans=dis[n];
while (x!=per[x])
{
spfa(nmu[x]);x=per[x];
if (dis[n]<big) ans=max(ans,dis[n]);
}
printf("%d",ans);
}
luogu 1078 文化之旅
S1
这道题第一眼是最短路，看到数据范围之后感觉是弗洛伊德。但是并不能用最短路做……因为这道题的后效性过于强烈，如果用弗洛伊德，即使两个部分都不冲突，两个部分也有可能互相冲突，SPFA也不行，因为dis是根据之前的dis来更新的，而最短路不一定是最优选择，所以这道题应该没法这么做。
S2
那么就只能用搜索了。这道题由于有不同边权，所以dfs和bfs的效率都差不多，就题论题dfs更舒坦一些。但是要加上记忆化搜索。
记搜怎么做呢，当然是用dis数组来保存，如果sum大于dis那么就退出就行了。
再让我们考虑优化的问题。肯定有的数据是输出-1但是数据贼大会把你卡飞的那种。我们可以在搜索之前先判断能不能到达终点。但是这样难道还要来一遍搜索？
S3
先不考虑这个问题，搜一波试试看。没有超时看来数据比较水，但是竟然wa了四个点？？
把数组调大了一点，然后把剪枝改成了大于等于，毫无卵用。
错的四个点都是输出了-1，看来是没有搜到t点，被剪掉的可能性微乎其微，看来搜索过程中出了问题。
最后检查出来了，是cnt没有清零……不知啥时候不小心删了……
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
int n,k,m,s,t,c[101],a[101][101],dis[101],head[200001],ans[101],cnt;
struct node
{
int next,to,dis;
}ljb[200001];
inv add(int x,int y,int z)
{
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
ljb[cnt].dis=z;
head[x]=cnt;
}
inv dfs(int x,int sum)
{
if (dis[x]<=sum) return;
dis[x]=sum;
for (rint i=head[x];i;i=ljb[i].next)
{
int y=ljb[i].to;bool flag=0;
for (rint j=1;j<=cnt;j++)
if (a[c[y]][c[ans[j]]])
{
flag=1;
break;
}
if (!flag)
{
ans[++cnt]=y;
dfs(y,sum+ljb[i].dis);
ans[cnt--]=0;
}
}
}
int main()
{
scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
for (rint i=1;i<=n;i++) scanf("%d",&c[i]);
for (rint i=1;i<=k;i++)
{
for (rint j=1;j<=k;j++) scanf("%d",&a[i][j]);
a[i][i]=1;
}
for (rint i=1;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
for (rint i=1;i<=n;i++) dis[i]=big;cnt=0;
ans[++cnt]=s;
dfs(s,0);
if (dis[t]>=big) printf("-1");
else printf("%d",dis[t]);
}
总结：
- 看着像某种算法，不一定真的是某种算法
- 玄学错误的时候在程序中间输出一下变量，说不定有意外收获。
luogu 1436 棋盘分割
S1
无聊的我决定跟着ASIA大佬做一道题。
这题第一眼其实是贪心……我八成是傻了，本来想的是把这玩意比作分苹果，分成两份，两份比较平均的话，它们的平方和肯定要小，这个倒是可以证明，但是如果分的份数超过两份，这样的贪心就不成立了，因为如果n=3，那么肯定是把总体分成三份比较平均的要好。
S2
然后就想到记忆化搜索，用f[i][j][k][l][dep]来记录，过程不多说，比较顺，但就是用前缀和来推s[i][j][k][l]的过程中出了一点小岔子，要记住如果在前缀和上操作，要留住第i行，减去的一定是第i-1行。
S3
这道题还有asia的DP做法，思想都是一样的，但是要五重循环(第五重分别枚举行列)，时间稍慢一点。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define big 1e9;
using namespace std;
int n,a[11][11],s[11][11][11][11],f[11][11][11][11][16];
inv dfs(int a,int b,int c,int d,int dep)
{
if (f[a][b][c][d][dep]) return;
int ans=big;
for (rint i=a;i<=c-1;i++)
{
dfs(a,b,i,d,dep+1);
dfs(i+1,b,c,d,dep+1);
ans=min(ans,min(s[a][b][i][d]+f[i+1][b][c][d][dep+1],f[a][b][i][d][dep+1]+s[i+1][b][c][d]));
}
for (rint i=b+1;i<=d;i++)
{
dfs(a,i,c,d,dep+1);
dfs(a,b,c,i-1,dep+1);
ans=min(ans,min(s[a][i][c][d]+f[a][b][c][i-1][dep+1],f[a][i][c][d][dep+1]+s[a][b][c][i-1]));
}
f[a][b][c][d][dep]=ans;
}
int main()
{
scanf("%d",&n);
for (rint i=1;i<=8;i++)
for (rint j=1;j<=8;j++)
{
scanf("%d",&a[i][j]);
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
}
for (rint i=1;i<=8;i++)
for (rint j=1;j<=8;j++)
for (rint k=1;k<=8;k++)
for (rint l=1;l<=8;l++)
{
s[i][j][k][l]=a[k][l]-a[k][j-1]-a[i-1][l]+a[i-1][j-1];
s[i][j][k][l]=s[i][j][k][l]*s[i][j][k][l];
f[i][j][k][l][n]=s[i][j][k][l];
}
dfs(1,1,8,8,1);
printf("%d",f[1][1][8][8][1]);
}
总结：
- 大胆尝试DFS的可能
- 贪心做法除非万不得已，否则最好证明了再打。
luogu 2672 推销员
S1
已经连续被12、14、17三年普及组的最后一题shut down了，希望这道别崩。
算法妥妥的贪心。最初确立了一个策略，就是先算出一个路程加上价值最大的，也就是只推销一家的话应该是哪一家。我们可以保证，肯定没有比他远还比他贵的。所以如果不选这个点，而去选比它远的，肯定不如选这个要划算。那么我们可以这样做，比它近的，权值就是本来的权值，比它远的，权值就是多出来的路程+本来的权值。排一下序，然后一个一个往上面加就行了。
S2
WTF??过了？？
终于没被PJ T4给shut down，心里还是比较欣慰的
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rint register int
#define inb inline bool
using namespace std;
int n,s[100001],a[100001],f[100001];
inb cmp(int x,int y)
{
return x>y;
}
int main()
{
scanf("%d",&n);
for (rint i=1;i<=n;i++) scanf("%d",&s[i]);
for (rint i=1;i<=n;i++) scanf("%d",&a[i]);
int m,maxx=0,cnt=0;
for (rint i=1;i<=n;i++)
if (2*s[i]+a[i]>maxx)
{
maxx=2*s[i]+a[i];
m=i;
}
for (rint i=1;i<=m-1;i++) f[++cnt]=a[i];
for (rint i=m+1;i<=n;i++) f[++cnt]=2*(s[i]-s[m])+a[i];
sort(f+1,f+cnt+1,cmp);
printf("%d\n",maxx);
for (rint i=1;i<=cnt;i++)
{
maxx+=f[i];
printf("%d\n",maxx);
}
}
总结：
- 当思路不清晰的时候，把它打出来，就会越来越清晰
- 开拓想象力，但也要理性贪心
- 排序要想好从小往大还是从大往小，不对的时候检查一下这里。
luogu 1330 封锁阳光大学
S1
这个题好迷啊。本来是打算练图论才进来的，没想到这是个搜索，或者说，图的遍历。
思考了一会，有一个初版的思路：因为都是无向图，所以可以互相通达，所以我可以随便找一个点，那么它的下一个点的下一个点，它的下一个点的下一个点的下一个点，也就是1,3,5，都可以走到，然后我再搜一下2,4,6，两种情况取最小值，如果两种都不行那么输出impossible。
S2
额，第一遍好像只有五十分，算法似乎没问题，但是错的几个点都输出了impossible。
一开始以为是清空vis数组的位置错了，不过改了好像没什么卵用。
发现这个题广搜似乎更加方便，自己莫不是傻了。
还有一点就是只要搜一遍就行了，如果行的通的话直接比较ans和(n-ans)就可以
S3
有突然想到一种思路
两者互相冲突的情况似乎不可能发生在无环图里面，那么有环图中的偶数边的环似乎也可存在，那么我可以先写一个dfs来判断有没有奇数环，然后如果没有就可以跑一个bfs来计算就可以了。
中途发现了一个问题：这个题并不是一个连通图，所以我们要进行多次广搜，还要把孤点排掉。一开始排孤点直接在n上减，但这样会导致后面的bfs操作错误，而且我们不能这样直接排，还是那句话，这个图不是联通的，所以每个不联通的小图都可以有不同的选法，我们要选每个小图里面较小的选法，把它们加起来，才能得出正确的结果（这个点卡了半天的60分）。
最后，初始化广搜队列的memset必须去掉，不然就得卡掉一个点……
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
int ans,sum,tot,answer,cnt,n,m,num[200001],head[200001],team[1000001][3],use[10001];
bool vis[10001],flag;
struct node
{
int next,to;
}ljb[200001];
inv add(int x,int y)
{
ljb[++cnt].next=head[x];
ljb[cnt].to=y;
head[x]=cnt;
}
inv dfs(int x,int dep)
{
vis[x]=1;use[x]=dep;
for (rint i=head[x];i;i=ljb[i].next)
{
int y=ljb[i].to;
if (use[y])
{
if ((use[x]+1-use[y])%2!=0)
{
flag=1;
return;
}
}
if (!vis[y]) dfs(y,dep+1);
}
}
inv bfs(int x)
{
team[1][1]=x;team[1][2]=1;vis[x]=1;
int hed=0,tail=1;
ans=0;sum=0;
while (hed<tail)
{
int now=team[++hed][1];
int bj=team[hed][2];
if (bj) ans++;sum++;
for (rint i=head[now];i;i=ljb[i].next)
{
int y=ljb[i].to;
if (!vis[y])
{
vis[y]=1;
team[++tail][1]=y;
team[tail][2]=bj^1;
}
}
}
answer+=min(ans,sum-ans);
}
int main()
{
scanf("%d%d",&n,&m);
int maxx=0,t1,t2;
for (rint i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
add(x,y);add(y,x);
num[y]++;num[x]++;
}
int tot=n;
for (rint i=1;i<=n;i++)
{
if (!vis[i])
{
memset(use,0,sizeof(use));
flag=0;
dfs(i,1);
if (flag)
{
printf("Impossible");
exit(0);
}
}
if (!num[i]) tot--;
}
memset(vis,0,sizeof(vis));
for (rint i=1;i<=n;i++)
if (!vis[i] && num[i])
bfs(i);
printf("%d",answer);
}
总结：
- 搜索之前先想好是dfs还是bfs
- 大胆尝试多种搜索方法结合的可能性
- 最重要的一点，我在做这个题的时候一开始以为用总的点减去每个小图的选择，再和每个小图的选择之和相比较就能出结果，这可以说是数学思维的欠缺……因为每个小图有可能选的是大的也有可能选的是小的方案，所以不能这么选。遇到这种分成子问题的情况一定要好好想一想。
luogu 2744 量取牛奶
S1
一开始看到这道题还是很好确定算法的，妥妥的是dfs+dp。先跑一遍完全背包，vis[i][j]表示体积为j的时候选不选i最优，可以把第一维压掉。如果vis[j-a[i]]选了i，那么vis[j]就不用再选一遍。这样可以确定出来一共选了多少种木桶，之后搜索，再跑布尔完全背包，因为已经把桶的大小排过序了，那么如果可以拼成体积为q的就直接输出结束程序就可以了。
S2
出了两个小错误。
第一个，从五十分改到六十分。在最初的那一遍完全背包中，如果f[j-a[i]]+value等于f[j]，那也要把vis[j]设为1，因为这样会最优——在同样的f[j]下，如果vis[j]=1，那么f[j+a[i]]的值会少加1，从而保证最终的结果最优。
第二个，从六十分改到一百分。这个真是无语，小错误害死人啊。在搜索完的那次完全背包中，我的初始化不是g[i]=big，而是g[q]=big……手一滑，三个人检查了一个小时，死活检查不出来，从网上下了数据才出来的……检查的时候一定要一个字一个字仔细看，不要因为语句简单就不看了，简单的语句也可能手滑打错。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
int p,q,a[101],f[20001],que[101],cnt;
bool use[101],vis[20001],g[20001];
inv dp()
{
for (rint i=0;i<=q;i++) g[i]=0;g[0]=1;
for (rint i=1;i<=f[q];i++)
for (rint j=a[que[i]];j<=q;j++)
if (g[j-a[que[i]]]) g[j]=1;
if (g[q])
{
printf("%d ",f[q]);
for (rint i=1;i<=f[q];i++) printf("%d ",a[que[i]]);
exit(0);
}
}
inv dfs(int x,int dep)
{
if (dep==f[q])
{
dp();
return;
}
if (f[q]-dep>p-x) return;
for (rint i=x+1;i<=p;i++)
{
que[dep+1]=i;
dfs(i,dep+1);
}
}
int main()
{
scanf("%d%d",&q,&p);
for (rint i=1;i<=p;i++) scanf("%d",&a[i]);
sort(a+1,a+p+1);
for (rint i=0;i<=q;i++) f[i]=big;f[0]=0;
for (rint i=1;i<=p;i++)
for (rint j=0;j<=q;j++)
{
vis[j]=0;
if (j>=a[i])
{
int value=vis[j-a[i]]^1;
if (f[j-a[i]]+value<=f[j])
{
f[j]=f[j-a[i]]+value;
vis[j]=1;
}
}
}
dfs(0,0);
}
总结：
- 要思考一下第一个搜出来的是不是最优解，是的话可以直接剪掉。
- 一定要注意细节，等于号加不加是个问题，仔细思考。出错的时候一句一句认真检查，千万不要嫌麻烦，发愁的时间比检查的时间长多了。
luogu 3045 牛券
S1
这道题第一眼是DP或者贪心，贪心的几率显然更大。对于这种题，显然的有两种贪心方案，第一种，差值最大的贡献最大，第二种，减价后最小的贡献最大。
S2
在这里我犯了一个错误，就是一个劲去证明第一种方案的不可行性，然后不管第二个方案……其实应该把不可行性写出来，然后发现不可以直接去想第二个。正在我瓶颈的时候zyc告诉我这题要联系生活实际，一下子茅塞顿开了。在生活中，我们肯定会先选用优惠劵之后价格最低的k个，然后再卖剩下的里面实际价格最小的，最后凑到m就行了。
因为没有把m开成long long 错了两个点，一定要细心啊。。。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define rint register int
using namespace std;
int n,k,p[50001],c[50001];
long long m;
bool vis[50001];
struct node
{
int p,c,id;
}a[50001];
bool cmp1(node a,node b)
{
return a.c<b.c;
}
bool cmp2(node a,node b)
{
return a.p<b.p;
}
int main()
{
scanf("%d%d%lld",&n,&k,&m);
for (rint i=1;i<=n;i++)
{
scanf("%d%d",&a[i].p,&a[i].c);
a[i].id=i;
}
sort(a+1,a+n+1,cmp1);
long long tot=0;
int num=0;
for (rint i=1;i<=k;i++)
{
if (tot+a[i].c>m)
{
printf("%d",i-1);
exit(0);
}
tot+=a[i].c;
vis[a[i].id]=1;
}
sort(a+1,a+n+1,cmp2);
for (rint i=1;i<=n;i++)
if (!vis[a[i].id])
{
if (tot+a[i].p>m)
{
printf("%d",k+num);
exit(0);
}
num++;
tot+=a[i].p;
}
printf("%d",n);
}
总结
- 有多种方案的时候证明不可行性，要把它写出来，把各个方案都想一下。
- 这种买东西的贪心题，如果题目不是太扯淡，可以联系一下生活实际，也就是在生活中我该怎么做，说不定能有意外的收获。
- 开long long ，开 longlong ，开long long 。
后记
这种做法被这组数据hack掉了
8 3 10
2 1
2 1
2 1
10000000 2
10000000 2
10000000 2
10000000 2
10000000 2
只能说是数据太水。实际上这题需要三个优先队列来进行骚操作才能AC……等有能力做的时候再补上正解吧。
luogu 1983 车站分级
S1
一开始看这个题题意还是没有看懂的，主要是没看见每一条路都有自己的起点和终点站……一定要注意认真读题。然后想算法，这个题题意就是一个拓扑排序，数据也小，可以浪。
S2
中间出了几个小细节的问题：
第一个，还是忘了每条线路都有起点和终点站，预处理的时候从1到n循环的，出了大错。
第二个，把tot加了两遍……
第三个，每一遍都把sum[i]=0的点入队，而没有把访问过的标记掉。
去掉这三个小错误就从十分变成了一百分，所以一定要注意细节！
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
int n,m,map[1001][1001],sum[1001],a[1001],que[1001],s[1001];
bool vis[1001];
int main()
{
scanf("%d%d",&n,&m);
for (rint q=1;q<=m;q++)
{
scanf("%d",&s[0]);
for (rint i=1;i<=n;i++) vis[i]=0;
for (rint i=1;i<=s[0];i++)
{
scanf("%d",&s[i]);
vis[s[i]]=1;
}
for (rint i=s[1];i<=s[s[0]];i++)
if (!vis[i])
for (rint j=1;j<=s[0];j++)
if (!map[i][s[j]])
{
map[i][s[j]]=1;
sum[s[j]]++;
}
}
int ans=0,num=0;
for (rint i=1;i<=n;i++) vis[i]=0;
while (num<n)
{
int tot=0;
for (rint i=1;i<=n;i++)
if (!sum[i] && !vis[i])
{
que[++tot]=i;
vis[i]=1;
num++;
}
for (rint i=1;i<=tot;i++)
for (rint j=1;j<=n;j++)
if (map[que[i]][j])
{
map[que[i]][j]=0;
sum[j]--;
}
ans++;
}
printf("%d",ans);
}
总结
- 一定要认真读题，结合样例来读，还有就是看题图很重要。
- 注意细节，冷静打代码，除非万不得已不要飚手速。
