当前位置:网站首页>【NOI模拟赛】区域划分(结论,构造)
【NOI模拟赛】区域划分(结论,构造)
2022-07-07 02:33:00 【DD(XYX)】
题面
1s , 512mb
题解
首先,如果有相邻两城党派相同一定无解。
我们发现,最终的方案一定得有相邻的三座城市是在一个三角形里的,而把这个三角形连上后,相当于把中间的城市去掉,剩下的部分就又是一个子问题。
于是,我们统计相邻的能组成三角形的三元组个数 X X X(若某位置 i i i 满足 a i a_i ai 和其左右两个位置刚好构成集合 { 0 , 1 , 2 } \{0,1,2\} { 0,1,2} ,则可构成三元组),不难发现,当我们连上一个三角形时, X X X 减少量为奇数,且存在方案使其大于零。而最终一定是剩三个城,刚好 X X X 变为 1 的,所以——答案有解当且仅当 X > 0 X>0 X>0 且 X X X 与 n n n 的奇偶性相同。
如何使得 X X X 恒大于零呢?其实只需要尽量使用边缘的三元组——当且仅当某个三元组与左右两个三元组的中心城市相邻时,该三元组不是边缘三元组。若没有边缘的三元组,当然随便选一个连都没问题。因为我们发现,若选了一个非边缘三元组,会使得 X X X 减少 3 3 3 ,这时只有全都是非边缘三元组的时候能保证还存在三元组。
于是我们用 set 和链表维护三元组,时间复杂度 O ( n log n ) O(n\log n) O(nlogn) 。
看了题解后,我发现我是个XX。
首先,若无相邻相同城市,则 X X X 的奇偶性一定与 n n n 相同。也就是说只要 X > 0 X>0 X>0 就有解了。而且不难证明,只要同时存在 0 , 1 , 2 0,1,2 0,1,2 , X X X 就大于 0 。
然后,有很简单的构造法:
CODE
打着我的小笨码,逃避着我的小笨责任
#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;
}
边栏推荐
- 博士申请 | 上海交通大学自然科学研究院洪亮教授招收深度学习方向博士生
- 化工园区危化品企业安全风险智能化管控平台建设四大目标
- MySQL卸载文档-Windows版
- POI export to excel: set font, color, row height adaptation, column width adaptation, lock cells, merge cells
- matlab / ENVI 主成分分析实现及结果分析
- String (explanation)
- mobx 知识点集合案例(快速入门)
- 哈趣投影黑馬之姿,僅用半年强勢突圍千元投影儀市場!
- 品牌电商如何逆势增长?在这里预见未来!
- unity3d学习笔记
猜你喜欢
随机推荐
docker-compose启动redis集群
一条慢SQL拖死整个系统
A program lets you understand what static inner classes, local inner classes, and anonymous inner classes are
企業如何進行數據治理?分享數據治理4個方面的經驗總結
Ha Qu projection dark horse posture, only half a year to break through the 1000 yuan projector market!
ICML 2022 | explore the best architecture and training method of language model
雷特智能家居龙海祁:从专业调光到全宅智能,20年专注成就专业
C面试24. (指针)定义一个含有20个元素的double型数组a
js装饰器@decorator学习笔记
Prompt for channel security on the super-v / device defender side when installing vmmare
服装门店如何盈利?
Networkx绘图和常用库函数坐标绘图
MYSQL binlog相关命令
港科大&MSRA新研究:关于图像到图像转换,Fine-tuning is all you need
学术报告系列(六) - Autonomous Driving on the journey to full autonomy
RuntimeError: CUDA error: CUBLAS_STATUS_ALLOC_FAILED when calling `cublasCreate(handle)`问题解决
What books can greatly improve programming ideas and abilities?
Redhat5 installing vmware tools under virtual machine
Overview of FlexRay communication protocol
大促过后,销量与流量兼具,是否真的高枕无忧?