当前位置:网站首页>[noi simulation] regional division (conclusion, structure)
[noi simulation] regional division (conclusion, structure)
2022-07-07 06:50:00 【DD(XYX)】
Topic
1s , 512mb
Answer key
First , If there are two neighboring cities with the same party, there must be no solution .
We found that , The final plan must have three adjacent cities in a triangle , And after connecting this triangle , It is equivalent to removing the middle city , The rest is another sub problem .
therefore , We count the number of adjacent triples that can form triangles X X X( If a certain position i i i Satisfy a i a_i ai And its left and right positions just form a set { 0 , 1 , 2 } \{0,1,2\} { 0,1,2} , Can form a triple ), It's not hard to find out , When we connect One Three triangles , X X X The reduction is Odd number , And there is a scheme to make it greater than zero . In the end, there must be three cities left , just X X X Turn into 1 Of , therefore —— The answer is if and only if X > 0 X>0 X>0 And X X X And n n n The parity of is the same .
How to make X X X Constant is greater than zero ? In fact, just try to use Edge triples —— If and only if a certain triple is related to the left and right triples The central city is adjacent when , This triplet No Edge triples . If there is no triplet on the edge , Of course, it's OK to choose any one . Because we found that , If you choose a non edge triple , Will make X X X Reduce 3 3 3 , At this time, only when they are all non edge triples can we guarantee that there are triples .
So we use set And linked list maintenance triples , Time complexity O ( n log n ) O(n\log n) O(nlogn) .
After reading the solution , I found myself a XX.
First , If there is no adjacent same city , be X X X The parity of must be related to n n n identical . That is, as long as X > 0 X>0 X>0 There is a solution . And it's not difficult to prove , As long as it exists at the same time 0 , 1 , 2 0,1,2 0,1,2 , X X X Greater than 0 .
then , There is a very simple construction method :
CODE
Hit my stupid size , Avoiding my stupid responsibility
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
#define eps 1e-6
int xchar() {
static const int maxn = 1000000;
static char b[maxn];
static int pos = 0,len = 0;
if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
if(pos == len) return -1;
return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
LL f = 1,x = 0;int s = getchar();
while(s < '0' || s > '9') {
if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
while(s >= '0' && s <= '9') {
x = (x<<1) + (x<<3) + (s^48);s = getchar();}
return f*x;
}
void putpos(LL x) {
if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
if(!x) {
putchar('0');return ;}
if(x<0) putchar('-'),x = -x;
return putpos(x);
}
inline void AIput(LL x,int c) {
putnum(x);putchar(c);}
int n,m,s,o,k;
int a[MAXN];
int l[MAXN],r[MAXN];
set<int> st,sp;
bool che(int x) {
if(a[l[x]]^a[x]^a[r[x]]) return st.erase(x),0;
return st.insert(x),1;
}
bool che2(int x) {
if(!(a[l[x]]^a[x]^a[r[x]]) && ((a[l[l[x]]]^a[l[x]]^a[x]) || (a[x]^a[r[x]]^a[r[r[x]]]))) return sp.insert(x),1;
return sp.erase(x),0;
}
void del(int x) {
st.erase(x); sp.erase(x);
int s = l[x],o = r[x];
AIput(min(s,o)+1,' '); AIput(max(s,o)+1,'\n');
r[s] = o; l[o] = s;
che(s); che(o); che2(s); che2(o);
che2(l[s]); che2(r[o]);
}
int main() {
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
n = read();
for(int i = 0;i < n;i ++) a[i] = read()+1;
for(int i = 0;i < n;i ++) {
if(a[i] == a[(i+1)%n]) return printf("No\n"),0;
l[i] = (i+n-1)%n; r[i] = (i+1)%n;
}
for(int i = 0;i < n;i ++) che(i),che2(i);
if((st.size()&1) == (n&1) && !st.empty()) {
printf("Yes\n");
for(int i = 1;i <= n-3;i ++) {
int t = *st.begin();
while(!sp.empty() && !che2(*sp.begin()));
if(!sp.empty()) t = *sp.begin();
del(t); while(!st.empty() && !che(*st.begin()));
}
}
else printf("No");
return 0;
}
边栏推荐
- Stack and queue-p79-10 [2014 unified examination real question]
- 肿瘤免疫治疗研究丨ProSci LAG3抗体解决方案
- Leetcode T1165: 日志分析
- How to install swoole under window
- MATLAB小技巧(29)多项式拟合 plotfit
- FPGA课程:JESD204B的应用场景(干货分享)
- 【mysqld】Can't create/write to file
- Redhat5 installing vmware tools under virtual machine
- C interview encryption program: input plaintext by keyboard, convert it into ciphertext through encryption program and output it to the screen.
- LM small programmable controller software (based on CoDeSys) Note 23: conversion of relative coordinates of servo motor operation (stepping motor) to absolute coordinates
猜你喜欢
地质学类比较有名的外文期刊有哪些?
A program lets you understand what static inner classes, local inner classes, and anonymous inner classes are
企业如何进行数据治理?分享数据治理4个方面的经验总结
快速定量,Abbkine 蛋白质定量试剂盒BCA法来了!
大促过后,销量与流量兼具,是否真的高枕无忧?
如何给目标机器人建模并仿真【数学/控制意义】
MySQL卸载文档-Windows版
How can I check the DOI number of a foreign document?
MySQL的主从复制原理
项目实战 五 拟合直线 获得中线
随机推荐
偏执的非合格公司
Config分布式配置中心
拼多多败诉:“砍价免费拿”侵犯知情权但不构成欺诈,被判赔400元
软件测试到了35岁,真的就干不动了吗?
什么情况下考虑分库分表
Distributed ID solution
【luogu P1971】兔兔与蛋蛋游戏(二分图博弈)
品牌·咨询标准化
使用TCP/IP四层模型进行网络传输的基本流程
LM11丨重构K线构建择时交易策略
JWT certification
大促过后,销量与流量兼具,是否真的高枕无忧?
Performance comparison between Ceres solver and g2o
Abnova循环肿瘤DNA丨全血分离,基因组DNA萃取分析
SolidWorks的GB库(钢型材库,包括铝型材、铝管等结构)安装及使用教程(生成铝型材为例)
【mysqld】Can't create/write to file
MOS管参数μCox得到的一种方法
联合索引ABC的几种索引利用情况
2022 Android interview essential knowledge points, a comprehensive summary
A program lets you understand what static inner classes, local inner classes, and anonymous inner classes are