小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

重要的逆向思维

作者：小小林熬夜学编程 | 2024-05-24 23:00:58

踩

重要的逆向思维

第一题

liouzhou_101住在柳侯公园附近，闲暇时刻都会去公园散散步。
很那啥的就是，柳侯公园的道路太凌乱了，假若不认识路就会走着走着绕回原来的那条路。
liouzhou_101就开始自己YY，假若给他当上那啥管理者，就会想尽量减少道路回圈的个数，但是大范围的改变道路终归不是什么良策。
经过调查，发现公园有N个景点，为了显示景点之间的优越性，我们按照1，2，…，N来把这N个景点编号，当然编号越小就说明越重要。
为了显示自己的英明决策，liouzhou_101决定，前K重要的景点最为重要，当然他们是标号为1…K了的。需要保证这K个景点不在任何一个环上，原因很简单，这前K个景点是很重要的景点，参观的人也很多，自然不会希望参观的人因为在兜圈子而迷路吧。
于是，我们所能够做的就是把之前建造好的一些道路清除掉，使得保证前K重要的景点不在任何一个环上。

输入格式 InputFormat

第一行包括三个正整数N，M和K，N表示景点的数量，M表示公园里的路径条数，K表示前K个景点最为重要。
再接下来M行，每行有两个正整数x和y，表示景点x和景点y之间有一条边。

输出格式 OutputFormat

仅一行，输出至少去除多少条路径，使得前K个重要的景点不在任何一个环上。

样例输入 SampleInput

11 13 5
1 2
1 3
1 5
3 5
2 8
4 11
7 11
6 10
6 9
2 3
8 9
5 9
9 10

样例输出 SampleOutput

数据范围和注释 Hint

我们的删边方案是，删除(2,3)(5,9)(3,5)这三条边，这样节点1到5都不在任何一个环上。
而且可知删除三条边已经是最少的了。

30%的数据，满足N≤10，M≤20；
60%的数据，满足N≤1,000，M≤10,000；
100%的数据，满足N≤100,000，M≤200,000。
注意：给出的无向图可能有重边和自环。

分析：

一道并查集，最开始的思想是从1-n加边，前k个点有环就删，后面的点有环的话就判断是否和前k个点任意一个在一个集合中，但这样是错的，因为可能后面的点有环又与前k个点相连，有可能不影响，于是转换一下思路吧，先把不会影响的环加上就好了。


#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<algorithm>  
using namespace std;  
  
const int maxn=100000+10,maxm=200000+10;  
  
int n,m,k,size=0;  
int u[maxm],v[maxm],first[maxn],next[maxm],f[maxn],color[maxn];  
bool vis[maxm],hash[9999999];  
  
void init()  
{  
    freopen("tyvj2066.in","r",stdin);  
    freopen("tyvj2066.out","w",stdout);  
}  
  
void insert(int x,int y)  
{  
    size++;  
    u[size]=x;  
    v[size]=y;  
    next[size]=first[x];  
    first[x]=size;  
}  
  
int wori(int x)  
{  
    int cnt=0;  
    while(x)  
    {  
        cnt++;  
        x/=10;  
    }  
    int ans=1;  
    for(int i=1;i<=cnt;i++) ans*=10;  
    return ans;  
}  
  
bool wocao(int x,int y)  
{  
    int z=x*wori(y)+y,z1=y*wori(x)+x;  
    if(hash[z] || hash[z1]) return false;  
    else return true;  
}  
  
void readdata()  
{  
    memset(next,0xff,sizeof(next));  
    memset(first,0xff,sizeof(first));  
    scanf("%d%d%d",&n,&m,&k);  
    for(int i=1;i<=m;i++)  
    {  
        int x,y;  
        scanf("%d%d",&x,&y);  
        if(x==y || !wocao(x,y)) continue;  
        insert(x,y);  
        insert(y,x);  
        hash[x*wori(y)+y]=true;  
        hash[y*wori(x)+x]=true;  
    }  
    for(int i=1;i<=n;i++) f[i]=i;  
    for(int i=1;i<=k;i++) color[i]=1;  
    for(int i=k+1;i<=n;i++) color[i]=2;  
}  
  
int find(int x)  
{  
    return f[x] == x ? x : f[x]=find(f[x]);  
}  
  
void work()  
{  
    int ans=0;  
    for(int i=k+1;i<=n;i++)  
    {  
        for(int e=first[i];e!=-1;e=next[e])  
        {  
            if(color[v[e]]==1) continue;  
            if(vis[e] || vis[e+1]) continue;  
            vis[e]=true;vis[e+1]=true;  
            int fx=find(i),fy=find(v[e]);  
            if(fx!=fy) f[fx]=fy;  
        }  
    }  
    for(int i=1;i<=k;i++)  
    {  
        for(int e=first[i];e!=-1;e=next[e])  
        {  
            if(vis[e] || vis[e+1]) continue;  
            vis[e]=true;vis[e+1]=true;  
            int fx=find(i),fy=find(v[e]);  
            if(fx!=fy) f[fx]=fy;  
            else ans++;  
        }  
    }  
    printf("%d\n",ans);  
}  
  
int main()  
{  
    init();  
    readdata();  
    work();  
    return 0;  
}

第二题

3.图上的游戏

【问题描述】

方老师在无聊时很喜欢玩这样一个游戏：

在一个有n个点的有向带权图上，每两个点之间在两个方向都有一条边。

现在进行以下操作n次：

1、删掉图中的一个顶点xi;

2、定义在删掉xi这个点之前u到v的最短距离是d(i,u,v)

3、计算所有点对(u,v)的d(i,u,v)之和（注意因为是有向图(u,v)和(v,u)视为两种不同组合）

考试时用了一个老师不能理解的n^4的算法，说实话，考试时有点想到了floyd求最小环，但由于很久没用过floyd求最小环了和没想到逆序什么的，就只有60的纯朴素分，实际上因为删掉一个点后不恢复，于是把点从后往前加即可。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
 
int n;
LL map[510][510];
LL a[510],ans[510];
 
void init()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
}
 
void readdata()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%I64d",&map[i][j]);
		}
	}
	for(int i=1;i<=n;i++)scanf("%d",&a[n-i+1]);//倒序读入
}
 
void work()
{
    for(int k=1;k<=n;k++)//k=1时表示只有一个点可以拿去松弛其他店
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                map[i][j]=min(map[i][a[k]]+map[a[k]][j],map[i][j]);
            }
        }
        ans[k]=0;
        for(int i=1;i<=k;i++)//只有k个点
           for(int j=1;j<=k;j++)  
              ans[k]+=map[a[i]][a[j]];
    }
    for(int i=n;i>1;i--) printf("%I64d ",ans[i]);
    printf("%d\n",ans[1]);
}
 
int main()
{
	init();
	readdata();
	work();
	return 0;
}

第三题

岛屿

【问题描述】

从前有一座岛屿，这座岛屿是一个长方形，被划为N*M的方格区域，每个区域都有一个确定的高度。不幸的是海平面开始上涨，在第i年，海平面的高度为t[i]。如果一个区域的高度小于等于海平面高度，则视为被淹没。那些没有被淹没的连通的区域够成一个连通块。现在问第i年，这样的连通块有多少个。

例如：第一年海平面高度为1，有2个连通块。

第二年海平面高度为2，有3个连通块。

考试时写的纯朴素，过了3组，T了两组，B了5组（dfs递归过深），想过写并查集，但没有想到逆序，因为题给的是二维的图，要用并查集的话最好要转化成一维的，开个结构体，记录下每个点的高度和原坐标（后面拓展时有用），并按照高度排序，关于淹没就倒着来，相当于每次退潮新加入一些点，这时就可以利用并查集的快速性了。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
struct node
{
    int x,y,h;
}a[1000010];
 
int n,m,k,size=0;
int high[100010],ans[1000010],f[1000010];
bool vis[1000010];//true表示该点当前是没有被淹没的
 
void init()
{
	freopen("island.in","r",stdin);
	freopen("island.out","w",stdout);
}
 
void readdata()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[++size].h);
            a[size].x=i,a[size].y=j;
        }
    }
    for(int i=1;i<=size;i++) f[i]=i;
    scanf("%d",&k);
    for(int i=1;i<=k;i++) scanf("%d",&high[i]);
}
 
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
 
int cmp(node i,node j)
{
    return i.h > j.h;
}
 
int find(int x)
{
    return f[x] == x ? x : f[x]=find(f[x]);
}
 
void work()
{
    int sum=0,pos=1;
    sort(a+1,a+1+size,cmp);//按高度降序排列
    for(int p=k;p>=1;p--)
    {
        for(int i=pos;i<=size;i++)
        {
            int h=a[i].h,x=a[i].x,y=a[i].y;
            if(h <= high[p]) {pos=i;break;}
            if(h > high[p] && !vis[(x-1)*m+y])
            {
                sum++;
                vis[(x-1)*m+y]=true;
                for(int j=0;j<4;j++)
                {
                    int nx=x+dx[j],ny=y+dy[j];
                    if(nx>0&&nx<=n&&ny>0&&ny<=m&&vis[(nx-1)*m+ny]&&find((nx-1)*m+ny)!=find((x-1)*m+y))
                    {
                        f[find((nx-1)*m+ny)]=find((x-1)*m+y);
                        sum--;//这个部分表示一个没有被淹没的点周围的也没被淹没的点，并且还没被合并到同一集合，就合并到同一集合，并且联通块的数目-1.这就是高效的并查集，不用遍历每个点。
                    }
                }
            }
        }
        ans[p]=sum;
    }
    for(int i=1;i<=k;i++) printf("%d ",ans[i]);
    printf("\n");
}
 
int main()
{
	init();
	readdata();
	work();
	return 0;
}

观光公交

风景迷人的小城 Y 市，拥有n 个美丽的景点。由于慕名而来的游客越来越多，Y 市特

意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0 分钟出现在1

号景点，随后依次前往2、3、4……n 号景点。从第i 号景点开到第i+1 号景点需要Di 分钟。

任意时刻，公交车只能往前开，或在景点处等待。

设共有 m 个游客，每位游客需要乘车1 次从一个景点到达另一个景点，第i 位游客在

Ti 分钟来到景点Ai，希望乘车前往景点Bi（Ai<Bi）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。

假设乘客上下车不需要时间。

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一

辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司

机ZZ 给公交车安装了k 个氮气加速器，每使用一个加速器，可以使其中一个Di 减1。对于

同一个Di 可以重复使用加速器，但是必须保证使用后Di 大于等于0。

那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

【输入输出样例说明】

对 D2 使用2 个加速器，从2 号景点到3 号景点时间变为2 分钟。

公交车在第 1 分钟从1 号景点出发，第2 分钟到达2 号景点，第5 分钟从2 号景点出发，

第7 分钟到达3 号景点。

第 1 个旅客旅行时间 7-0 = 7 分钟。

第 2 个旅客旅行时间 2-1 = 1 分钟。

第 3 个旅客旅行时间 7-5 = 2 分钟。

总时间 7+1+2 = 10 分钟。

【数据范围】

对于 10%的数据，k=0；

对于 20%的数据，k=1；

对于 40%的数据，2 ≤ n ≤ 50，1 ≤ m≤ 1,000，0 ≤ k ≤ 20，0 ≤ Di ≤ 10，0 ≤ Ti ≤ 500；

对于 60%的数据，1 ≤ n ≤ 100，1 ≤ m≤ 1,000，0 ≤ k ≤ 100，0 ≤ Di ≤ 100，0 ≤ Ti ≤ 10,000；

对于 100%的数据，1 ≤ n ≤ 1,000，1 ≤ m ≤ 10,000，0 ≤ k ≤ 100,000，0 ≤ Di ≤ 100，

0 ≤ Ti ≤ 100,000。

此题需用到贪心，dp，以及倒序的思想，倒序的思想用在找贪心的依据上，具体的我也说不清楚。。。看代码吧，容易看懂。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int maxn=1010,maxm=10010;
 
int st[maxn],last[maxn],d[maxn],sum[maxn],cao[maxn];
int n,m,k,ans=0;
 
void init()
{
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
}
 
void readdata()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<n;i++) scanf("%d",&d[i]);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		sum[c]++; last[b]=max(last[b],a); ans-=a;
	}
	for(int i=1;i<=n;i++) st[i]=max(last[i-1],st[i-1])+d[i-1];
}
 
void work()
{
	for(int i=1;i<=k;i++)
	{
		for(int i=n;i>1;i--)
		{
			if(!d[i-1]) cao[i-1]=0;
			else 
			{
				cao[i-1]=sum[i];//就这个地方要用倒序加dp
				if(st[i]>last[i]) cao[i-1]+=cao[i];
			}
		}
		int gan=0,w;
		for(int j=1;j<n;j++)
		{
			if(gan < cao[j])
			{
				gan=cao[j];
				w=j;
			}
		}
		if(!gan) break;
		d[w]--;
		for(int k=1;k<=n;k++) st[k]=max(st[k-1],last[k-1])+d[k-1];
	}
	for(int i=1;i<=n;i++) ans+=st[i]*sum[i];
	printf("%d",ans);
}
 
int main()
{
	init();
	readdata();
	work();
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/619460