题目描述
有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。
输入
输入n人数<1000000 每个人的aim
输出
你要求最后死亡数目的最小和最大可能
样例输入
8
2 3 2 2 6 7 8 5
样例输出
3 5 题解
这道题……说来话长了这就。考试的时候，一画样例明显是个图论题，出了环明显要缩点，缩了点明显还有一堆什么玩意，打着打着就忘了还有疯子自杀来着= =。不算自杀的，环里最多n-1最少n/2；链里用随便什么数据结构一个一个存，最大可能有入度的点都会死，这些东西还算好说。如果环又带了链，最小值怎么处理呢？当时没想清楚，直接用非常错误的取较大处理了，心里也觉得不对劲，但是没什么办法。
把图分成三种情况：自环一定死、独立环直接n-1和n/2处理、还有最小值需要一步步处理的。最大值除了独立的环会每环活下1个人，所有有入度的人都会死。自环输入时就把它标记为已死，最大最小都+1。考虑最小的情况，最后一种需要一个数据结构(栈或队列，我直接用的tarjan剩下的栈)，每当一个点没有入度了就把它放进去，在栈里的人他的子节点是必死无疑了(敌人的安全就是自己的危险)，他的孙节点入度-1，如果孙节点入度为0且没有死就把他也放进栈里。在栈里出现过或作为栈的子节点被杀死的点，它们的环都已经被拆开了，所以只有剩下的完整的环依然按照独立环去处理(改题的时候一直卡在这里)。有入度的环未必不独立，单纯看入度并不能判断最小杀死几个人。
做这道题的时候由于很多前面的数组不再有用，稍微废物利用了一下。但是一开始的bool型数组被来回来去用，导致自己的思路也很含混不清。数组尽量见名知意，确实有利于提高编程的准确程度。话说回来，这样计算死了几个人总有些草菅人命的感觉啊……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<cmath>
using namespace std;
const int sj=;
int n,ai[sj],e,low[sj],c[sj],size[sj],a1,dfn[sj];
int a2,xt[sj],rh[sj],zd,zx,rd[sj];
stack<int> z;
bool r[sj],zh[sj],ww[sj],ded[sj];
int bj(int x,int y)
{
return x<y?x:y;
}
void tarjan(int x)
{
low[x]=dfn[x]=++e;
r[x]=;
z.push(x);
if(!dfn[ai[x]])
{
tarjan(ai[x]);
low[x]=bj(low[x],low[ai[x]]);
}
else if(r[ai[x]])
low[x]=bj(low[x],dfn[ai[x]]);
if(low[x]==dfn[x])
{
a1++;
do
{
a2=z.top();
z.pop();
r[a2]=;
c[a2]=a1;
size[a1]++;
}while(a2!=x);
}
}
void init()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&ai[i]);
if(ai[i]==i)
{
zx++,zd++;
ded[i]=;
}
rd[ai[i]]++;
}
for(int i=;i<=n;i++)
if(!dfn[i]) tarjan(i);
while(!z.empty()) z.pop();
for(int i=;i<=n;i++)
{
if(c[i]!=c[ai[i]])
{
xt[c[i]]=c[ai[i]];
rh[c[ai[i]]]++;
}
if(i==ai[i]) zh[c[i]]=;
}
for(int i=;i<=n;i++)
if(!rd[i]) z.push(i);
while(!z.empty())
{
a2=z.top();
ww[c[a2]]=;
z.pop();
ww[c[ai[a2]]]=;
if(!ded[ai[a2]])
{
zx++;
ded[ai[a2]]=;
a2=ai[ai[a2]];
rd[a2]--;
if(rd[a2]==&&!ded[a2]) z.push(a2);
}
}
for(int i=;i<=a1;i++)
{
if(size[i]!=&&!ww[i])
{
if(size[i]&) a2=(size[i]+)>>;
else a2=size[i]>>;
zx+=a2;
}
if(size[i]!=&&!rh[i]) zd+=size[i]-;
if(size[i]!=&&rh[i]) zd+=size[i];
if(size[i]==&&rh[i]&&!zh[i]) zd++;
}
printf("%d %d",zx,zd);
}
int main()
{
init();
return ;
}
maf
题外话
大暑假集训转眼也过去一周了啊。日子过得很快，也很快乐。从一两天假期的放松里回来，集训的生活其实更充实更有意义。meaty和lyc两位学长讲课，学会了网络流的最小割最大流和最小费用最大流的板子，知道了概率期望题的一些新做法，今天在打Splay的板子。考了5场试，大概只有第二天真正打得比较好，其他都是骗分；最近两天题目相对简单些，思路更接近正解，但往往打挂很多分。面对考试题一筹莫展的情况变少了，心态也没什么波动，但是还是有实现不了想法的时候，也就是学长们说的码力不够吧。通过考试慢慢用熟了很多以前学的板子，思路也越来越开阔，搜索题虽然可能拿不了多少分依然乐在其中。最弱的方面大概还是数据结构和数学，昨天讲的卡特兰数还没有做过题；对51Nod很好奇，但是仿佛大多数题目都很高级，不知道应该怎么做。感觉还是没有平常学期里紧张，花在生活琐事上的时间更多，到位晚进入状态也晚。晚上整理题目还好些，早上想着上午要考试，总觉得时间不够想题打题，转眼间就吃饭了。改题改得时间长了，话也很多，做完一道题总是要过很长时间才能开始下一题。如果想实现更高的目标，总得付出更多的努力才行。 谁终将声震人间，必长久深自缄默。谁终将点燃闪电，必长久如云漂泊。