• D——POJ 3620  Avoid The Lakes(DFS深度优先搜索) Description Farmer John's farm was flooded in the most recent storm, a fact only aggravated by the information that his cows are ...
典型的搜索题，当时就混乱了，BFS还是DFS，之后果断选用DFS，事实证明我是对的。
但是由于对于DFS并不是很是熟练，虽然能够得出正确结果，但是总是超时。
我还是很想说这是道很简单的深搜题呀！痛心呢，怎么就没做出来呢？
D——POJ 3620 Avoid The Lakes(DFS深度优先搜索)

Description

Farmer John's farm was flooded in the most recent storm, a fact only aggravated by the information that his cows are deathly afraid of water. His insurance agency will only repay him, however, an amount depending on the size of the largest "lake" on his
farm.
The farm is represented as a rectangular grid with N (1 ≤ N ≤ 100) rows and
M (1 ≤ M ≤ 100) columns. Each cell in the grid is either dry or submerged, and exactly
K (1 ≤ K ≤ N × M) of the cells are submerged. As one would expect, a lake has a central cell to which other cells connect by sharing a long edge (not a corner). Any cell that shares a long edge with the central cell or shares
a long edge with any connected cell becomes a connected cell and is part of the lake.

Input

* Line 1: Three space-separated integers: N, M, and K
* Lines 2..K+1: Line i+1 describes one submerged location with two space separated integers that are its row and column:
R and C

Output

* Line 1: The number of cells that the largest lake contains.

Sample Input

3 4 5
3 2
2 2
3 1
2 3
1 1

Sample Output

4


展开全文
• #include #include #define maxn 101 int n, m, k, count; int buf[maxn][maxn]; int vis[maxn][maxn]; int dir[8] = {-1, 0, 1, 0, 0, -1, 0, 1}; void dfs(int x, int y){ ... int d; vis[x][y] = 1; +
#include
#include
#define maxn 101

int n, m, k, count;
int buf[maxn][maxn];
int vis[maxn][maxn];
int dir[8] = {-1, 0, 1, 0, 0, -1, 0, 1};
void dfs(int x, int y){
int d;
vis[x][y] = 1; ++count;
for(d = 0; d < 8; d+=2){
int nx = x+dir[d], ny = y+dir[d+1];
if(nx>=1 && ny>=1 && nx<=n && ny<=m && !vis[nx][ny] && buf[nx][ny]){
dfs(nx, ny);
}
}
}

int main(){
int max, i, j;
while(scanf("%d%d%d", &n, &m, &k)==3 && n){
max = 0;
memset(buf, 0, sizeof(buf));
memset(vis, 0, sizeof(vis));
while(k--){
scanf("%d%d", &i, &j);
buf[i][j] = 1;
}
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
if(!vis[i][j] && buf[i][j]){
count = 0;
dfs(i, j);
if(max < count) max = count;
}
printf("%d\n", max);
}
}


展开全文
• | Ticket(s) (<em>issue(s)) concerné(s) | #3620 | <h3>QA <ul><li>Créez un article/tuto via la fonction d'import, avec des images</li><li>Vérifier que les images sont bien insérées avec le lien...
• UPDATE LeTex好象又挂了 题目链接: https://www.luogu.org/problemnew/show/P3620 ...思路（来自《算法竞赛进阶...容易知道，最优解中配对的楼肯定是相邻的，于是我们把所有相邻楼之间的距离$$D_1$$,$$D_2$$,$$D_3$$....
UPDATE
LeTex好象又挂了
题目链接:
https://www.luogu.org/problemnew/show/P3620https://www.lydsy.com/JudgeOnline/problem.php?id=1150
思路（来自《算法竞赛进阶指南》）：
容易知道，最优解中配对的楼肯定是相邻的，于是我们把所有相邻楼之间的距离$$D_1$$,$$D_2$$,$$D_3$$...$$D_n$$记录下来，放进一个堆里。
很明显，每次都取堆中的最小值是不正确的。那么这就有个很妙的思路：假设$$D_i$$是最小值，那么我们就取出$$D_i$$，同时取出$$D_{i-1}$$和$$D_{i+1}$$,然后再把一个一个值$$D_{i+1}$$+$$D_{i-1}$$-$$D_i$$的数放进堆，如果下一步这个新节点是最小值，很明显这是最优解。
难点1：
删了$$D_{i+1}$$,$$D_{i-1}$$和$$D_{i}$$后插入一个新节点,那它的前驱和后继怎么确定呢？最简单的方式当然就是用链表。
难点2：
我们要让堆和链表建立一个映射关系，怎么搞呢？？？我就在这里卡了好久，其实我们可以用反函数的思想。用一个数组v[]记录外面链表数组在堆中的下标，这样映射就建立了(其实这应该蛮好想的，我还是太弱了)
代码：
/*By Rye_Catcher*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#define ll long long
using namespace std;
const int maxn=100005;
int a[maxn],pre[maxn],ne[maxn],v[maxn];
struct Small_Heap{
int heap[maxn],n;
inline void up(int s){
int fa=s>>1;
while(s>1){
if(a[heap[s]]<a[heap[fa]]){
swap(heap[s],heap[fa]);
swap(v[heap[s]],v[heap[fa]]);
s=fa;fa=s>>1;
}
else break;
}
}
inline void insert(int k){
heap[++n]=k;
v[k]=n;
up(n);
}
inline void down(int fa){
int s=fa<<1;
while(s<=n){
if(a[heap[s]]>a[heap[s+1]]&&s<n)s++;
if(a[heap[s]]<a[heap[fa]]){
swap(heap[s],heap[fa]);
swap(v[heap[s]],v[heap[fa]]);
fa=s,s=fa<<1;
}
else break;
}
}
inline void sub(int k){
heap[v[k]]=heap[n];
v[heap[n]]=v[k];
n--;
up(v[k]),down(v[k]);
}
}poi;
int n,k;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int main(){
int la,x;
ll ans=0;
for(int i=2;i<=n;i++){
a[i-1]=x-la;
poi.insert(i-1);
ne[i-1]=i,pre[i-1]=i-2;
la=x;
}
for(register int i=1;i<=k;i++){
x=poi.heap[1];ans+=a[x];
if(pre[x]==0)
{
poi.sub(x),poi.sub(ne[x]);
pre[ne[ne[x]]]=0;
}
else if(ne[x]==n)
{
poi.sub(x),poi.sub(pre[x]);
ne[pre[pre[x]]]=n;
}
else {
poi.sub(x);//poi.extract();
poi.sub(pre[x]),poi.sub(ne[x]);
a[x]=a[pre[x]]+a[ne[x]]-a[x];
poi.insert(x);
pre[x]=pre[pre[x]],ne[pre[x]]=x;
ne[x]=ne[ne[x]],pre[ne[x]]=x;
}
}
cout<<ans<<endl;
return 0;
}

转载于:https://www.cnblogs.com/Rye-Catcher/p/8834708.html
展开全文
• <ul><li><a href="https://jira.mesosphere.com/browse/DCOS_OSS-3620">DCOS_OSS-3620</a> Log stderr on failing command execution</li></ul> <h2>Related tickets (optional) <ul><li>...
• 正题 题目链接:https://www.luogu.com.cn/problem/P3620 题目大意 一条线上有nnn个位置，选出kkk对使得它们的距离差之和最小。...那么就可以删除这三个数然后加入一个dx−1+dx+1−dxd_{x-1}+d_{x+1}-d_xdx−1​+dx+
正题
题目链接:https://www.luogu.com.cn/problem/P3620

题目大意
一条线上有$n$个位置，选出$k$对使得它们的距离差之和最小。

解题思路
因为一定是连接相邻的最优，那么可以在差分数组上做，相当于我们在一个差分数组上选择一些不相邻的数使得它们和最小。
考虑贪心，我们对于一个最小的位置$x$选择了之后，更优的情况可能是选择$x$相邻的两个然后不选择$x$。那么就可以删除这三个数然后加入一个$d_{x-1}+d_{x+1}-d_x$。
用链表+堆维护即可。时间复杂度$O(n\log n)$

$code$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=1e5+10;
struct del_d{
priority_queue<pair<ll,ll> >q1,q2;
void push(pair<ll,ll> x)
{q1.push(x);return;}
void pop(pair<ll,ll> x)
{q2.push(x);return;}
pair<ll,ll> top(){
while(!q2.empty()&&q1.top()==q2.top())
q1.pop(),q2.pop();
return q1.top();
}
}q;
ll n,k,d[N],last[N],next[N],ans;
void del(ll x){
if(!x)return;
q.pop(mp(-d[x],x));
last[next[x]]=last[x];
next[last[x]]=next[x];
return;
}
int main()
{
scanf("%lld%lld",&n,&k);
ll las;
for(ll i=0;i<n;i++){
ll x;scanf("%lld",&x);
if(i!=0)d[i]=x-las,q.push(mp(-d[i],i));
las=x;
}
n--;
for(ll i=1;i<=n;i++)
last[i]=i-1,next[i]=i+1;
next[n]=0;d[0]=1e18;
while(k--){
ll x=q.top().second;ans+=d[x];
q.pop(q.top());d[x]=d[last[x]]+d[next[x]]-d[x];
del(last[x]);del(next[x]);q.push(mp(-d[x],x));
}
printf("%lld\n",ans);
return 0;
}



展开全文
• Avoid The Lakes Time Limit: 1000MS Memory Limit: 65536KB ...64bit IO Format: %I64d & %I64u Submit Status Description Farmer John's farm was floode...
• 算法竞赛进阶指南，85 页，堆排序 本题要点： 1、d[i] 表示公司 i 和 i - 1 之间的距离，选择k段距离，使得总和最小。...2、本题的结论：要么选择 d[i] + d[j], 要么选择 d[i - 1] + d[i + 1] 假如选择了d
• 我们不难发现，一个点连电缆肯定是要和他左侧第一个或者右侧第一个连，这样是最优的，但是可能存在a,b,c,d四个点，bc是目前可连得最短边，但是连接ab和cd更优，怎么办呢？我们可以在第一次用掉bc这条边后，将ab+cd-...
• HDKJ产品介绍 产品目录 HDKJ D3606 2 HDKJ D3609 3 ...HDKJ D3620 5 HDKJ D3625 6 HDKJ D3630 7 HDKJ D3009 8 HDKJ D3015 9 HDKJ DS3020 10 HDKJ DS3025 11 HDKJ S3090D 12 HDKJ S3150D 13 HDKJ S3315D 14
• <div><p><img width="672" alt="Screen Shot 2019-07-29 at 12 49 57 PM" src="https://img-blog.csdnimg.cn/img_convert/f0000b6531d3620d391430f357d5024c.png" /></p><p>该提问来源于开源项目：kaltura/...
• <div><p><img alt="Capture" src="https://img-blog.csdnimg.cn/img_convert/5772d2c6afbd084efbb17054e7d3620f.png" /> <p>Plugin to display ping in the corner of screen under fps. Currently it pings the ...
• <p><img alt="image" src="https://f.cloud.github.com/assets/1162544/1031598/d3620a04-0ee6-11e3-84b9-8d965aefbf9e.png" /></p><p>该提问来源于开源项目：FauxFaux/PuTTYTray</p></div>
• <img alt="image" src="https://img-blog.csdnimg.cn/img_convert/9eecb6920d1d3620de0423c5f26c2447.png" /> 问题2：对此构架没有匹配的工具链，之前没有报toolchain missing时也出现了这个问题</p><p>...
• BUILT $E135D5384EA42B4A771268CDA139D73D1C16A2C4~yutu,$A6E0F950CAC74AF867CA21976069529D6D4D3E30~HRMB,$4031460683AE9E0512D3620C2758D98758AC6C93~niftyeuropeanrabbit BUILD_FLAGS=NEED_CAPACITY PURPOSE&... • <img alt="pmahomme" src="https://img-blog.csdnimg.cn/img_convert/8d8da5a062effd34392326d3620c7fc2.png" /> <p>BTW，some end-sign notes where "end" are uppercase while others are lowercase... • 0x00007f61957d3620: 0000000000000004 ffffffff00000000 0x00007f61957d3630: 0000000200000006 00007f614c1ab6d0 0x00007f61957d3640: 0000000000000000 00007f61c83fc800 0x00007f61957d3650: ... • exporting config sha256:b17d37d3620f94fa2a8aef8df2ccbfe7e3474024be2dbab7c21418106f4abe15 0.0s => => exporting manifest sha256:66c2e950c4482383066bf13a5eef3745432dfe656ce2bab7ac5e722783... • <p>I believe the entire echarts package is included for webpack building due to this line from <a href="https://github.com/xieziyu/ngx-echarts/blob/5706b424070598ec1ddb236d267fcdfc5e0d3620/projects/... • <p><strong>Platform: Android 8.1 and 4.4 <strong>Mapbox SDK ...12-07 11:48:13.974 2258-21630/system_process I/WindowManager: Failed to capture screenshot of Token{d3620d4 ActivityRecord{4293627 u0 ... • 578 0 containerd-shim -namespace k8s.io -workdir /var/lib/rancher/k3s/agent/containerd/io.containerd.runtime.v1.linux/k8s.io/a6a750da7213027e8fa6c09531b6286bbef04431e2dec8dac3b3620d9ea11835 -address ... • at net.minecraft.server.v1_12_R1.PlayerConnection.a(PlayerConnection.java:2229) [craftbukkit.jar:git-Spigot-2086bb0-d0a3620] at net.minecraft.server.v1_12_R1.PacketPlayInCustomPayload.a(SourceFile:... • at org.bukkit.plugin.java.JavaPluginLoader.enablePlugin(JavaPluginLoader.java:337) [craftbukkit.jar:git-Spigot-2086bb0-d0a3620] at ... • 2020-03-11 13:46:07 Verification failed from peer: UnknownBlock: State already discarded for BlockId::Hash(0xcd4cc449851fff33ffba2a0e5b69e6d60bbe4a8f77748bc5c3620d7dd0d474d8) 2020-03-11 13:46:09 Idle ... • Kong，W.，Kim，C.，Zhang，D.，Guo，H.，Tan，X.，Jin，H.，Zhou，C.，Shuang，L.等。 （2018）。 通过对393个高粱双色BTx623×IS3620C重组自交系进行测序进行基因分型，提高了QTL检测的灵敏度和分辨率。 G3：基因... • d lean towards option #1 for the PR, so alternatives or arguments for/against either of the above (or a better solution altogether) are welcome!</p><p>该提问来源于开源项目：Azure/azure-sphere-... • [img]http://dl.iteye.com/upload/attachment/0061/8033/28bc3e99-fa04-3620-b6b9-0d8514ebe714.png[/img] [code="java"] import javax.xml.parsers.*; import java.io.*; import org.w3c.d... • #3 0x00304248 in std::rt::lang_start::_$u7b$$u7bclosureu7d$$u7d\$::h931ab8c3620c5b29 () #4 0x002f8d68 in main () </code></pre>该提问来源于开源项目：env-logger-rs/env_logger</p></div>

...