当前位置:网站首页>【集训DAY9】Rotato【暴力】【思维】
【集训DAY9】Rotato【暴力】【思维】
2022-07-21 07:15:00 【VL——MOESR】
思路:
我们考虑一个点i,把它转到它的对应点,肯定有一个转的轴。
我们不妨把每个轴能贡献多少的固定点给算出来,然后一个个去枚举当前轴的贡献,用前缀和算出不转的最大值,然后和轴的贡献加起来去最大值。
c o d e code code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 1e6 + 10;
int n, ans;
int s[MAXN];
vector<int> q[MAXN];
int main() {
freopen("rotate.in", "r", stdin);
freopen("rotate.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
int x;
scanf("%d", &x);
if(x == i) s[i] = s[i - 1] + 1;
else s[i] = s[i - 1];
if(x > i) q[i + x].push_back(x);
else q[i + x].push_back(i);
}
for(int i = n * 2; i >= 1; i --) {
sort(q[i].begin(), q[i].end());
for(int j = 0; j < q[i].size(); j ++) {
ans = max(ans, s[i - q[i][j] - 1] + s[n] - s[q[i][j]] + j + 1);
}
}
printf("%d", ans);
return 0;
}
边栏推荐
- Mysql06(序列)
- LeetCode 10. 正则表达式匹配
- Introduction to common interfaces of vector
- The sandbox teamed up with agoria to build agoriaverse
- uniapp,微信小程序input正则校验只能输入为数字和小数点位数限制
- [dongle vulnerability notification] Apache spark command injection vulnerability scheme
- Mysql05 (view)
- 【JVM】垃圾收集器的选择
- 查看IAR工程所用版本号
- Learn the necessary tools of automation selenium think about automated testing in the pit again
猜你喜欢
随机推荐
Mysql05 (view)
Check the version number of IAR project
Can multithreading optimize program performance?
Appium获取和点击坐标,元素不方便定位时非常好用
What is the difference between int *const p= & I and int const *p= & I
[terminal _1]-xshell 5 the hottest terminal software!
【JVM】垃圾收集器的选择
开源demo| ARCall 小程序开源示例发布
SPA单页面学习理解
删除远程分支和本地分支
音频自动增益控制 AGC 解决的问题及原理解析
mysql数据恢复
uniapp 使用 u-view 框架小程序的样式问题集合
Share 50 free cloud disk and online disk Services - with unlimited storage space
硬核Fiddler抓包工具大型攻略(完)Fiddler终极篇
Solve the problem that the uploaded file of ftpclient is empty and 0 bytes are displayed
word2vec简单总结
mysql docker安装 主从部署
PO模式在Selenium自动化测试中怎么应用
【sciter】:窗口通信