当前位置: 首页 > news >正文

day 8

今天收获颇丰,长春邀请赛我们至少能开4题,题目思维不难,实现上细节比较多。
今天单切一道1400div3的E题,有点guess的成分;
题目:https://codeforces.com/contest/2033/problem/E
题目大意,给你一个数组,若数组第i位上是i或者第i位和第j位分别是j和i(即交换位置),那么这个数组好;
我们可以选择两个索引i和j并交换ai和aj,这是一次操作,求最少几次操作使得数组好。
对于ai == i,我们不必操作,观察发现,找数字时必然会循环,对于一定的循环次数貌似也有最小操作次数;
举例发现循环次数x和操作次数y的关系:
x y
1 0
2 0
3 1
4 1
5 2
6 2
猜测是y = (x - 1) / 2;
提交发现猜测正确。
另外,以后写题一定加输入输出流控制,今天想了好久才发现是没加这个导致超时
代码:
———————————

include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1000010;

int a[N];
bool vis[N];

int dfs(int i,int k)
{
if (vis[i])
{
return k;
}

vis[i] = true;if (a[i] == i) 
{return 0; 
} 
else 
{return dfs(a[i], k + 1);
}

}

void solve()
{
int n,ans = 0;
cin >> n;
for(int i = 1;i<=n;i++)
{
cin >> a[i];
vis[i] = 0;
}
for(int i = 1;i<=n;i++)
{
ans += (dfs(i,0) - 1) / 2;
}
cout << ans << endl;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
return 0;
}

http://www.hskmm.com/?act=detail&tid=36163

相关文章:

  • OI 笑传 #21
  • Day1文本格式化标签
  • 【C语言学习记录】你好世界
  • 1021
  • 24信计2班 17曾向嵩 pytorch66页实验题
  • 解答这些常见的智能合约安全问题,并提供相应的防护措施
  • Day1排版标签,标题与段落
  • 读AI赋能05消费者盈余
  • 解答这些 Solidity 开发中的重要问题
  • grpc 哼哈二将,你值得拥有
  • 解释这些 Solidity 智能合约的核心概念
  • C++编程练习
  • 数据结构练习
  • newDay14
  • L07_在RuoYI项目中添加自己的接口并实现CRUD功能(轻松+AI版)
  • 10
  • 大二to大三暑假大三上前半学期总结
  • 2025.10.18 刷题
  • 低代码如何推动企业敏捷创新与业务赋能
  • hevc解码器下载
  • 低代码如何成为企业数字化转型的加速器
  • 10.18测试
  • 删除链表的倒数第N个结点-leetcode
  • NOI 八
  • Day1标签的关系与vs的注释
  • 软件工程学习日志2025.10.21
  • [PaperReading] DeepSeek-OCR: Contexts Optical Compression
  • Win10安装WindowsCamera相机
  • 简易的本地部署OI-Wiki方法 for CCSP
  • Say 题选记 (10.19 - 10.25)