精选文章 HDU - 5495

HDU - 5495

作者:青烟绕指柔! 时间: 2021-07-06 09:41:30
青烟绕指柔! 2021-07-06 09:41:30
【摘要】
                    
                        
                    
                    题目链接:HDU - 5495 
 
其实就是每一列可以重排,然后问LCS。 
我们可以发现,把 b 看成 a 的置换,那么每个环的贡献都是环的大小 - 1 。特判环为1,贡献为1。 
 
AC代码: 
#pragma...

题目链接:HDU - 5495


其实就是每一列可以重排,然后问LCS。

我们可以发现,把 b 看成 a 的置换,那么每个环的贡献都是环的大小 - 1 。特判环为1,贡献为1。


AC代码:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
//#define int long long
using namespace std;
const int N=1e5+10;
int vis[N],a[N],b[N],res,cnt,n;
void solve(){
	scanf("%d",&n); res=0;
	for(int i=1;i<=<>n;i++)	scanf("%d",&a[i]),vis[i]=0;
	for(int i=1;i<=<>n;i++)	scanf("%d",&b[a[i]]);
	for(int i=1;i<=<>n;i++)	if(!vis[i]){
		int now=i; cnt=0;
		while(!vis[now])	vis[now]=1,cnt++,now=b[now];
		res+=max(1,cnt-1);
	}
	printf("%d\n",res);
}
signed main(){
	int T; cin>>T; while(T--) solve();
	return 0;
}
勿删,copyright占位
您找到想要的结果了吗?
HDU - 5495
提交成功!非常感谢您的反馈,我们会继续努力做到更好
分享文章到微博
分享文章到朋友圈

上一篇:拉钩大数据开发高薪训练营首月体验

下一篇:pycharm中显示cannot run git

您可能感兴趣

  • HDU 1176

    免费馅饼,题目:http://acm.hdu.edu.cn/showproblem.php?pid=1176 其实就是数塔,一开始没注意,从0秒开始做,相当于从数塔的顶端往下走,结果wa到荼蘼,后来从打后ac了 1 #include<stdio.h> 2 #include<string.h> 3 int dp[15][11...

  • HDU 3008

    Problem Description Have you ever played the Warcraft?It doesn't matter whether you have played it !We will give you such an experience.There are so many Heroes in it...

  • hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重背包+dp)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2191 思路分析:该问题为多重背包问题;假设状态dp[i][v]表示在前i件物品中选择物品放入大小为v的背包的最大的重量,则可以第i件物品可以选择0~n[i]件,所以可以得出状态方程 dp[i][v] = Max{dp[i-1][v – k * ...

  • hdu 1856 More is better

    Problem Description Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. Of course there a...

  • hdu 1196

    Problem Description Given an positive integer A (1 <= A <= 100), output the lowest bit of A. For example, given A = 26, we can write A in binary form as 11010, so the...

  • Problem - 2111 Saving HDU

    Saving HDU Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8306    Accepted Submission(s): 3810 Problem De...

  • HDU Problem 1312 Red and Black 【DFS】

    Red and Black Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17430    Accepted Submission(s): 10577 Pr...

  • HDU Problem 1811 Rank of Tetris【拓扑排序+并查集】

      Rank of Tetris Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8484    Accepted Submission(s): 2429 Probl...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。
HDU - 5495介绍:华为云为您免费提供HDU - 5495在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多HDU - 5495的相关内容。| 移动地址: HDU - 5495 | 写博客