Codeforces Round #244 (Div. 2) ABCE

野性酷女 2022-08-27 03:38 220阅读 0赞

比赛链接 http://codeforces.com/contest/427

D和E两题最后也没能自己搞出来，参考了 http://blog.csdn.net/hongrock/article/details/24894731

D要用后缀数组，这东西好久没用了，倍感生疏，最近拿起来再练练吧，先不贴代码了，上面的参考博客中有代码。

E感觉这题出的非常好，上面博客中的递归写法真是没想到，学习了。E的分析转自上面的博客

**A Police Recruits**

题意：按照时间顺序给出N个整数ai代表N个事件，ai大于0时代表增加ai个警察，否则代表出现一次事件。一个警察一生只能解决一个事件。

当出现犯罪时，如果警察数量大于0，那么就派一个警察过去调查这个案子，否则这个案子就没有人调查。

问题是统计有多少个案子没有被调查。

#include <cstdio>
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        int a,n=0,cnt=0;
        while (T--)
        {
    
            scanf("%d",&a);
            if (a>0) n+=a;
            else
            {
                if (n>0) n--;
                else cnt++;
            }
        }
        printf("%d\n",cnt);
        return 0;
    }

**B Prison Transfer**

题意：给定N个数，从中选择连续的c个数出来，并且这c个数都不大于一个给定的t，问有多少种选择。

#include <cstdio>
    
    int main ()
    {
        int n,t,c;
        scanf("%d%d%d",&n,&t,&c);
        int a,cnt=0,all=0;
        for (int i=0;i<n;i++)
        {
            scanf("%d",&a);
            if (a<=t) cnt++;
            else cnt=0;
            if (cnt>=c) all++;
        }
        printf("%d\n",all);
        return 0;
    }

**C Checkposts**

题意：给定一个N个点的有向图，在i点建造保安亭会有wi的花费，建造之后这里就会有警察站岗啦，然后对于一个j点，这个警察能够保护j点的情况只有两种：1是j就是i点；2是存在i到j的路径，并且还要能从j回到i。

求能够保护到所有点的花费最少的建造方案，并且建造的点也必须最少，输出这个最少花费，同时要输出这个最少花费的不同方案数模10^9+7，两种方案只要有一个点选择不同，就视为不同方案。

显然，同一个强连通分量中的点可以互相保护，所以统计有多少个强连通分量，每个里面选一个花费最小的点建造个数就肯定最少，同时统计花费都是最小值的点的个数。

把每个强连通分量里面统计到的个数乘起来就是方案数了。

#include <cstdio>
    #include <cstring>
    #include <stack>
    #define min(x,y) ((x)<(y)?(x):(y))
    #define max(x,y) ((x)>(y)?(x):(y))
    using namespace std;
    
    const int nPoint=100005;
    const int nEdges=300005;
    const int INF=0x3fffffff;
    
    class Qiangliantong
    {
    public:
    	struct Edge
    	{
    		int v,next;
    	}edges[nEdges];
    
    	int dfn[nPoint],low[nPoint],head[nPoint];
    	bool visit[nPoint];   //标记是否在栈中
    	int color[nPoint];   //color[]保存各强连通分量包含的节点数
    	int DAG[nPoint];             //储存新图,有向无环图DAG,也即每个结点所对应的强连通分量标号数组
    	int n,e,id,colornum;         //colornum强连通分量的个数
    	stack<int> S;
    
    	void DFS (int u)
    	{
    		int i,top,v;
    		dfn[u]=low[u]=++id;  //id为时间戳
    		S.push(u);
    		visit[u]=true;
    		for (i=head[u];i!=-1;i=edges[i].next)
    		{
    			v=edges[i].v;
    			if (!dfn[v])
    			{//未被访问
    				DFS(v);//继续向下找
    				low[u]=min(low[u],low[v]);//更新u节点所能到达的最小层数
    			}
    			else if (visit[v])
    				low[u]=min(low[u],dfn[v]);
    		}
    		if (dfn[u]<=low[u])   //  ==
    		{//如果节点v是强连通分量的根
    			colornum++;   //连通分量标号+1
    			do
    			{
    				top=S.top(); //
    				S.pop();
    				visit[top]=false;
    				DAG[top]=colornum; //出栈节点top属于colornum标号的强连通分量
    				color[colornum]++;
    			}while (top!=u);  //直接将u从栈中退出
    		}
    	}
    
    public:
    
    	void Init (int _n)
    	{
    		n=_n;
    		id=colornum=e=0;
    		memset(head,-1,sizeof(head));
    		memset(visit,false,sizeof(visit));
    		memset(dfn,0,sizeof(dfn));
    	}
    
    	void Add (int u,int v)
    	{
    		edges[e].v=v;
    		edges[e].next=head[u];
    		head[u]=e++;
    	}
    
    	int Tarjan ()  //返回强连通分量的个数
    	{
    		int i;
    		while (!S.empty())   //清空栈
    			S.pop();
    		for (i=1;i<=n;i++)  //枚举每个节点,搜索连通分量
    			if (!dfn[i])   //未被访问
    				DFS(i);   //则找该节点的连通分量
    		return colornum;
    	}
    }ob;
    
    int val[nPoint];  //存储每个点的费用
    int minval[nPoint]; //每个连通分量花费的最小值
    int tot[nPoint];    //每个连通分量具有最小花费的点的个数
    
    int main ()
    {
    	int n,m,i;
    	scanf("%d",&n);
    	ob.Init (n);
    	for (i=1;i<=n;i++)
    	{
    	    scanf("%d",&val[i]);
    	    minval[i]=INF;
    	}
        scanf("%d",&m);
        while (m--)
        {
            int u, v;
            scanf("%d%d",&u,&v);
            ob.Add(u,v);
        }
        int num=ob.Tarjan();  //求强连通分量
        memset(tot,0,sizeof(tot));
        for (i=1;i<=n;i++)
        {
            int color=ob.DAG[i]; //属于哪个连通分量
            if (minval[color]>val[i])
            {
                minval[color]=val[i];
                tot[color]=1;
            }
            else if (minval[color]==val[i])
                tot[color]++;
        }
        __int64 cnt=1; //方案数
        __int64 sum=0; //总花费
        for (i=1;i<=num;i++)
        {
            sum+=minval[i];
            cnt=cnt*tot[i]%1000000007;
        }
        printf("%I64d %I64d\n",sum,cnt);
    
    	return 0;
    }

[CF \#244 (Div. 2) D Match & Catch (后缀数组 仅出现一次最短公共子串) - whyorwhnt的专栏][CF _244 _Div. 2_ D Match _ Catch _ _ - whyorwhnt]

**E Police Patrol**

题意：在x轴上面有N个犯罪现场（呃。。。今晚的罪犯跟警察真多。。。），然后呢，你要在x轴上面选择一个点作为根据地，接着你要开着你的宝马出去抓罪犯~~可是呢，你的车一次最多只能载M个罪犯，并且每次逮捕完都必须回到根据地。这里说到的点坐标值都是整数（包括你的根据地）。

然后问题就来了，你要选择一个合适的地方，使得你的宝马跑的距离最少，要注意你的距离都是往返两次的，输出最短的距离。题目中说了同一地点可能会有多个犯罪者。

由于题目输入的坐标已经从小到大排好序了，所以我们省去排序的工作。

最一开始的区间就是\[0,n-1\]这个区间，那么最左边坐标是a\[0\], 最右边是a\[n-1\]，抓到这两个，首先你必须让你的据点在他们中间，但是，无论你选择在哪，你要抓到他们的距离都是2(a\[n-1\]-a\[0\])，这个可以稍微证明下，假设选择了(x,0)这个点，那么左边的距离就是2(x-a\[0\]),右边2(a\[n-1\]-x)，加起来就是上面的距离了。既然无论选在哪，要抓到他们都得跑2(a\[n-1\]-a\[0\])，那就干脆多拉几个人咯，最多拉几个呢？往左边最多可以m个人，往右边最多可以m个人，所以这里左右跑下来可以去掉2m个人，这个区间就变成\[l+m,r-m\]，如果l+m > r-m了，那就说明这个区间的人抓光了。

所以，这个问题可以通过这样逐步缩小区间解决，采用递归应该是比较方便的写法。

#include<cstdio>
    
    int n,m;
    int a[1000000];
    
    __int64 Cal (int l,int r)
    {
        if(l>r)	return 0;
        int len = r-l+1;
        if (len<=m)	return (__int64)(a[r]-a[l]);
        return (__int64)(a[r]-a[l])+Cal(l+m, r-m);
    }
    
    int main ()
    {
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++)
            scanf("%d", a+i);
        printf("%I64d\n",Cal(0,n-1)*2);
        return 0;
    }

[CF _244 _Div. 2_ D Match _ Catch _ _ - whyorwhnt]: http://blog.csdn.net/whyorwhnt/article/details/34555017