制作网站要多少钱,法律推广网站,二手网站建设论文,商机互联做网站怎么样Problem - D - Codeforces
题目大意#xff1a;有一个长度为n的数组a#xff0c;同时有一个n个点的图#xff0c;编号与数组的编号对应#xff0c;初始没有边#xff0c;如果当前连通块的中a[i]的和某一个点a[j]连通块的一个点i*某一个点j*c#xff0c;那么就可以连…Problem - D - Codeforces
题目大意有一个长度为n的数组a同时有一个n个点的图编号与数组的编号对应初始没有边如果当前连通块的中a[i]的和某一个点a[j]连通块的一个点i*某一个点j*c那么就可以连通i和j问能否使所有点在一个连通块内。
2n2e5;0a[i]1e12
思路令当前已有的一个连通块为s我们要找一个点j和s连通那么我么肯定选择连通块中编号最小的一个点i使i*j*c最小如果s内的和a[j]i*j*ci和j就可以连通既然i*j*c已经小于等于当前连通块的和那么对于小于j的所有编号i*j*c都一定小于等于。
那么既然要选最小的i那么我们就令a[1]是最小的连通块因为反正要所有点联通也要连1那不如从1开始连这样就从1到n遍历检查符不符合连通条件如果到n时也符合那么就是能连通
#include bits/stdc.h
//#include__msvc_all_public_headers.hpp
using namespace std;
const int N 2e5 5;
typedef long long ll;
const ll MOD 1e9 7;
ll a[N];
int n;
void solve()
{ll c;cin n;cin c;for (ll i 1; i n; i){cin a[i];}int ma 1;//最大的能联通的位置ll sum a[1];//前缀和ll nsum a[1];//当前连通块的和for (ll i 2; i n; i){sum a[i];if (nsum a[i] i * c){//满足连通条件nsum sum;ma i;}}cout (ma n ? YES : NO) \n;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin t;while (t--){solve();}}
