当前位置:网站首页>CF1634E Fair Share
CF1634E Fair Share
2022-07-05 05:31:00 【solemntee】
The question : Yes m m m An array , The number of numbers in each array is even . Divide each array in half to the set A 、 B A、B A、B Make the final resettable same, judge whether it is legal, and give the scheme .
First of all, I probably only think of Euler circuit on the court , But because there is no demolition point to build a map , We can only do the case of non re set , Later, I had no choice but to broadcast .
The method is to create a bipartite map , Left m m m Dots represent each array , Right c n t cnt cnt( Number of digital categories ) A little bit .
Numbers from the left to the right i i i The directed edge of represents i i i among A A A aggregate , On the contrary, it means to give B B B aggregate . It is easy to know that the original problem is equivalent to searching Euler circuits on bipartite graphs .
Then because there is no need to output the path , Just dye the edges with black and white , Then keep searching the ring .
Then finding a ring will not affect the Euler circuit property of the complementary graph , It is also obvious that Euler can definitely search a ring , That's it .
By the way, please enjoy the new one l a m b d a lambda lambda function
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int m;
scanf("%d",&m);
vector<vector<int>>a(m+1),ans(m+1);
map<int,int>mp,cnt;
int asdf=0;
for(int i=1;i<=m;i++)
{
int n;
scanf("%d",&n);
a[i].resize(n+1);
ans[i].resize(n+1,-1);
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(mp[a[i][j]]==0)mp[a[i][j]]=++asdf;
cnt[mp[a[i][j]]]++;
}
}
for(int i=1;i<=asdf;i++)if(cnt[i]%2==1)
{
printf("NO");
return 0;
}
vector<vector<pair<int,int>>>gra(4e5+5);
vector<int>cur(4e5+5);
const int MX=2e5;
for(int i=1;i<=m;i++)
{
for(int j=1;j<a[i].size();j++)
{
gra[i].push_back({
mp[a[i][j]]+MX,j});
gra[MX+mp[a[i][j]]].push_back({
i,j});
cur[i]++;
cur[MX+mp[a[i][j]]]++;
}
}
function<void(int,int)>dfs=[&](int now,int flag)
{
int u=now;
while(cur[u])
{
cur[u]--;
auto [to,pos]=gra[u][cur[u]];
while(ans[min(u,to)][pos]<0)
{
ans[min(u,to)][pos]=flag;
dfs(to,1-flag);
}
}
};
for(int i=1;i<=m;i++)dfs(i,0);
printf("YES\n");
for(int i=1;i<=m;i++)
{
for(int j=1;j<ans[i].size();j++)
{
if(ans[i][j]==0)printf("L");
else printf("R");
}
printf("\n");
}
return 0;
}
边栏推荐
- Use of room database
- Reader writer model
- Codeforces Round #715 (Div. 2) D. Binary Literature
- ssh免密登录设置及使用脚本进行ssh登录并执行指令
- [interval problem] 435 Non overlapping interval
- [merge array] 88 merge two ordered arrays
- 剑指 Offer 53 - II. 0~n-1中缺失的数字
- Maximum number of "balloons"
- Little known skills of Task Manager
- 读者写者模型
猜你喜欢
lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
远程升级怕截胡?详解FOTA安全升级
剑指 Offer 05. 替换空格
第六章 数据流建模—课后习题
YOLOv5-Shufflenetv2
To be continued] [UE4 notes] L4 object editing
Sword finger offer 05 Replace spaces
Sword finger offer 04 Search in two-dimensional array
一个新的微型ORM开源框架
剑指 Offer 53 - II. 0~n-1中缺失的数字
随机推荐
What is the agile proportion of PMP Exam? Dispel doubts
Zzulioj 1673: b: clever characters???
Haut OJ 1243: simple mathematical problems
使用Electron开发桌面应用
To the distance we have been looking for -- film review of "flying house journey"
[to be continued] [UE4 notes] L1 create and configure items
Yolov5 adds attention mechanism
二十六、文件系统API(设备在应用间的共享;目录和文件API)
Romance of programmers on Valentine's Day
Time complexity and space complexity
Pointnet++的改进
Fragment addition failed error lookup
Reflection summary of Haut OJ freshmen on Wednesday
Add level control and logger level control of Solon logging plug-in
Chapter 6 data flow modeling - after class exercises
Haut OJ 1321: mode problem of choice sister
lxml.etree.XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
[to be continued] [UE4 notes] L3 import resources and project migration
常见的最优化方法
[sum of two numbers] 169 sum of two numbers II - enter an ordered array