网站赚钱思路,快速做效果图的网站叫什么,软件技术方案范例,广州网站设计出名 乐云践新思路#xff1a; 这道题第一眼来看以为是动态规划类型的题目#xff0c;然而尝试了用dp的方法做#xff0c;然而超时了#xff0c;过了差不多一半的测试店#xff0c;显示的是超时。那么应该来说动态规划是可以做的#xff0c;但数据卡的比较严。在看其他同学的评论后 这道题第一眼来看以为是动态规划类型的题目然而尝试了用dp的方法做然而超时了过了差不多一半的测试店显示的是超时。那么应该来说动态规划是可以做的但数据卡的比较严。在看其他同学的评论后使用KMP算法也会使得部分测试点超时。
听完讲解后发现大佬是通过区间合并的方法实现的。
由题意可知若a[i]等于a[j]则b[i]和b[j]也必须是相同的而数组b是非递减的此时数组b中第i到j项的元素必须是相同的才能符合题目要求。所以我们要统计这样的区间的个数。运用区间合并的方法得出最后的区间数为k。两个相邻区间之间有2种变化方式因此总可能数是2的k-1次方个。
参考代码
#includebits/stdc.h
#includeunordered_map
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
vectorpairint, int v;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;unordered_mapint, int l(300000), r(300000);int num[200005];for (int i 0; i n; i){cin num[i];r[num[i]] i;}for (int i n - 1; i 0; i--)l[num[i]] i;for (auto it l.begin(); it ! l.end(); it){v.push_back({ it-second, r[it-first] });}sort(v.begin(), v.end());int cnt 0;int bg -1e9, ed -1e9;for (int i 0; i v.size();i) //区间合并{if (ed v[i].first){if (ed ! -1e9) cnt;bg v[i].first, ed v[i].second;}else if (ed v[i].second){ed v[i].second;}}if (bg ! -1e9 ed ! -1e9) cnt;int res 1;for (int i 1; i cnt; i){res res * 2 % 998244353;}cout res;return 0;
}
