2015.11.29总结+部分题解（未完待续）

一、salesmen【题目分析】    这题乍一看是可以用贪心来解，但看到数据范围，n^2的算法是显然不行的，所以我们要换个角度看。    看数据范围我们可以想到应该是用n*log(n)的算法，那么有什么算法是n*log(n)的呢？不难可以想到用快排，但是又一个问题来了——我们排序什么呢？  没错，我们可以根据疲劳值的大小来排序并记住下标。  第一步：我们知道全部中选最大很好办，即扫一遍，输出最大的ai+2si的值；  第二步：根据疲劳值来排序，即sort(ai)，并sort一遍ai+2si的总值；  第三步：for循环不断拿出ai的下标，从下标+1开始找ai+2si的最大，如果是最后一个，那么往前找。   当然，这个算法中第三步是要有些变化的，这个根据调试情况来判断，因为已经去了后面的住户，那么再去前面时只用加上疲劳值即可。
【参考程序】（这个是乱写超时的）

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct tottt
{
int num,bian;
};
tottt a[100001],s[100001],tot[100001],nu[100001];
int n,ans,k,tmp,maxgo;
bool hehe[100001];

int cmp(tottt cc,tottt dd)
{
return cc.num>dd.num;
}

int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d",&s[i].num);
s[i].bian=i;
}
for(int i=0;i<n;++i)
{
scanf("%d",&a[i].num);
a[i].bian=i;
tot[i].bian=i;
tot[i].num=a[i].num+s[i].num*2;
}

for(int i=n-1;i>=0;--i)
{
if(nu[i+1].num<tot[i].num)
nu[i]=tot[i];
else
nu[i]=nu[i+1];
}//类似动归的思想 

sort(a+0,a+n,cmp);
sort(tot+0,tot+n,cmp);
printf("%d\n",tot[0].num);
hehe[tot[0].bian]=true;


for(int i=0;i<n-1;++i)
{
ans+=a[i].num;
hehe[a[i].bian]=true;//已用 
if(a[i].bian>maxgo)
maxgo=a[i].bian;
if(maxgo!=n-1)
printf("%d\n",ans+nu[maxgo+1].num);//如果是最后一个 
else
{
for(int j=0;j<=n;++j)
if(!hehe[a[j].bian])
{
printf("%d\n",ans+a[j].num+s[n-1].num*2);
break;
}
}
}
} 

 这个是正解：  第一步：找出所有中的最大值（参考前面），记录下标k  第二步：在k的前面找ai的最大值与下标记录，在k的后面找ai+di*2的最大值与下标记录  第三步：比较二者选较大值，如果值在k的后面则将k的值改变  第四步：打印当前答案  循环第二、第三、第四步共n-1次

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[100001];
int n,_max,k;
int d[100001],v[100001];
int tong[1001];
int k1,k2,i1,i2;

int main()
{
freopen("salesman.in","r",stdin);
freopen("salesman.out","w",stdout);

scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",&d[i]);
for(int i=0;i<n;++i)
scanf("%d",&v[i]);

_max=k=-1;
for(int i=0;i<n;++i)
{
if(v[i]+d[i]*2>_max)
{
_max=v[i]+d[i]*2;
k=i;
}
}
printf("%d\n",_max);

dp[n-1]=n-1;
for(int i=n-2;i>=0;--i)
{
if(d[i+1]*2+v[i+1]<d[i]*2+v[i])
dp[i]=i;
else
dp[i]=dp[i+1];
}

for(int i=0;i<k;++i)
++tong[v[i]];

for(int i=0;i<n-1;++i)
{
i1=k1=0;
if(k<n-1)
{
i1=dp[k+1];
k1=(d[i1]-d[k])*2+v[i1];
}
for(int j=1000;j>=1;--j)
if(tong[j]>0)
{
k2=j;
--tong[j];
break;
}
if(k1>k2)
{
_max+=k1;
k=i1;
printf("%d\n",_max);
}
else
{
_max+=k2;
printf("%d\n",_max);
}
}
return 0;
}

未完成：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[100001];
int n,_max,k,kk;
int d[100001],v[100001];
bool use[100001];

struct fff
{
int xia,vv;
};
fff s[100001];

int cmp(fff a,fff b)
{
if(a.vv==b.vv)
return a.xia>b.xia;
return a.vv>b.vv;
}

int main()
{
//freopen("salesman.in","r",stdin);
//freopen("salesman.out","w",stdout);

scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%d",&d[i]);
for(int i=0;i<n;++i)
{
scanf("%d",&v[i]);
s[i].xia=i;
s[i].vv=v[i];
}
sort(s+0,s+n,cmp);
_max=k=-1;
for(int i=0;i<n;++i)
{
if(v[i]+d[i]*2>_max)
{
_max=v[i]+d[i]*2;
use[k]=false;
k=i;
use[i]=true;
}
}
printf("%d\n",_max);

dp[n-1]=n-1;
for(int i=n-2;i>=0;--i)
{
if(d[dp[i+1]]*2+v[dp[i+1]]<d[i]*2+v[i])
dp[i]=i;
else
dp[i]=dp[i+1];
}

for(int i=0;i<n-1;++i)
{
kk=s[i].xia;
if(kk>k)
{
int tmp=dp[k+1];
int tmp2=v[tmp]+(d[tmp]-d[k])*2;
_max+=tmp2;
k=tmp;
use[tmp]=true;
printf("%d\n",_max);
}
else
if(k<n-1)
{
int tmp=dp[k+1];
int tmp2=v[tmp]+(d[tmp]-d[k])*2;
if(tmp2>s[i].vv||use[i])
{
_max+=tmp2;
k=tmp;
use[tmp]=true;
}
else
{
_max+=s[i].vv;
use[i]=true;
}
printf("%d\n",_max);
}
else
{
_max+=s[i].vv;
use[i]=true;
printf("%d\n",_max);
}
}
return 0;
}

二、stone
【题目分析】  这道题一般来说有两种做法，一是模拟，不断拿掉最小的值和另一个值之间的石头，因为n的范围并不算很大。但如果是每改变一次值排序一次，那也会超时，所以我们可以用胜者树维护，但这种做法有点复杂。  第二种就是二分答案的做法，这个不用多说，就是不断确认一个“最短跳跃距离”是否可以跳，如果不能就缩小，反之加大。
【参考程序】

#include<iostream>
#include<cmath>
using namespace std;

int l,n,m,i,stone[50001],f;
int mid;

int erfen(int begin,int end)
{
mid=(int)ceil((begin+end)/2.0);
if(begin==end)
return mid;
int last=0,total=0;
for (int i=1;i<=n;i++)
if (l-stone[i]<mid)
{
total+=n-i+1;
break;
}
else
if(stone[i]-stone[last]>=mid)
last=i;
else
total++;
if(total>m)
return erfen(begin,mid-1);
return erfen(mid,end);
}

int main()
{
cin>>l>>n>>m;
for (i=1;i<=n;i++)
cin>>stone[i];
cout<<erfen(1,l);
return 0;
}

 三、message
【题目分析】  这道题目看上去十分麻烦，实际上我们只要画一个图就可以很好地理解。  从图中我们可以看出，在第2、3、4个人之间是形成了一个长度为三的环，故答案就是三。 这题有很多种做法，我来说说其中的两种。第一种BFS：第一步：读入每个点，记录每个人有多少个入度，即有多少个信息来源。第二步：将没有入度的点放入队列中，进行BFS，将所有这些点指向的点的入度都减一第三步：用while找环这种方法看起来是很难看懂，虽然我会，但是讲不出来，所以......
第二种时间标记法：第一步：找一个没有用过的点进入第二步：DFS找它指向哪个点，每次找的时候时间标记+1，如果找到一个已经有时间标记的点，且这个点是此次DFS中走过的，那么就可以得到一个环。看个图吧：恩，这是一张很简洁明了的图。  

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;

int n,ans=666666,nowtime;
int peo[200001],ttime[200001];

void _find(int k)
{
ttime[k]=++nowtime;
int beg=nowtime;
for(;;)
{
if(ttime[peo[k]]==0)
{
k=peo[k];
ttime[k]=++nowtime;
continue;
}
else
if(ttime[k]>beg)
{
int tt=ttime[k]-ttime[peo[k]]+1;
ans=min(tt,ans);
return;
}
else
return;
}
}

int main()
{
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);

memset(ttime,0,sizeof(ttime));
scanf("%d",&n);

/*if(n==2500)
{
printf("1000\n");
return 0;
}
if(n==200000)
{
printf("12345\n");
return 0;
}*/

for(int i=1;i<=n;++i)
scanf("%d",&peo[i]);
for(int i=1;i<=n;++i)
if(ttime[i]==0)
_find(i);
printf("%d\n",ans);
return 0;
}

并查集做法：

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 200010;
const int INF = 10000000;
int father[MAXN];
int ssize[MAXN];
int findf(int x)
{
if(father[x]==x)
return x;
return findf(father[x]);
}

void merge(int a,int b)
{
if (findf(a) == findf(b)) return;
int sizea = ssize[findf(a)];
int sizeb = ssize[findf(b)];
if (sizea < sizeb)
{
father[findf(a)]=findf(b);
ssize[findf(b)]+=sizea;
}
else
{
father[findf(b)]=findf(a);
ssize[findf(a)]+=sizeb;
}
}

int n;
int next[MAXN];
bool visited[MAXN];

int RoundLen(int pos)
{
int len=0;
while(!visited[pos])
{
visited[pos]=true;
pos=next[pos];
++len;
}
return len;
}

int MinLen=INF;

int main()
{
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);
scanf("%d",&n);
for (int i=0;i<n;++i) 
{ 
ssize[i]=1; 
father[i]=i; 
}
for (int i=0;i<n;++i)
{
scanf("%d",&next[i]); 
--next[i];
if (findf(i)==findf(next[i]) && !visited[i] && !visited[next[i]])
MinLen = min(MinLen,RoundLen(i));
merge(i,next[i]);
}
printf("%d\n",MinLen);
}