首页 > it技术 > >
考试|[NOIP模拟赛]吃糖果
2021-11-19
题目描述【考试|[NOIP模拟赛]吃糖果】 如果两张卡片上的数相等，那么他们之间边权为0，可以将他们看做一个顶点。于是我们只需要考虑卡片上的互不相等的情况。#include
#include
using namespace std;
const int N=1e5+10;
const int M=1e7;
int n, p[N], rot[N], h[N], cnt[M+5];
int Root( int x ) {
if( !rot[x] ) return x;
return rot[x]=Root( rot[x] );
}int realv[M+5];
//realv[i]:记录原值为i的位置被修改后的值
int pos[M+5];
//pos[i]:记录i这个值最先出现的标号
struct node{ int s, e;
node() {} node( int a, int b ) { s=a;
e=b;
} };
vector edge[M+5];
long long sum;
int main() {
scanf( "%d", &n );
for( int i=1;
i<=n;
i++ ) {
scanf( "%d", &p[i] );
realv[ p[i] ]=p[i];
if( !pos[ p[i] ] ) pos[ p[i] ]=i;
}
for( int i=M;
i>=0;
i-- )
if( !realv[i] ) realv[i]=realv[i+1];
for( int i=1;
i<=n;
i++ ) {
if( cnt[ p[i] ]++ ) continue;
if( realv[ p[i]+1 ] )//特殊处理第一个区间[ p[i], 2*p[i] )
if( realv[ p[i]*2 ]!=realv[p[i]+1] || p[i]*2>M )
edge[ realv[p[i]+1]-p[i] ].push_back( node( i, pos[ realv[p[i]+1] ] ) );
for( int j=p[i]*2;
j<=M && realv[j];
j+=p[i] )
if( realv[ j+p[i] ]!=realv[j] || j+p[i]>M )
edge[ realv[j]-j ].push_back( node( i, pos[ realv[j] ] ) );
}
for( int i=0;
i<=M;
i++ )
for( int j=0;
j<(int)edge[i].size();
j++ ) {
int s=Root( edge[i][j].s ), e=Root( edge[i][j].e );
if( s!=e ) {
if( h[s]
推荐阅读
