文章关键词:cf1444D Rectangular Polyline

[cf1444D]Rectangular Polyline

作者:神秘网友 发布时间:2021-10-13 07:24:08

[cf1444D]Rectangular Polyline

由于两种线段要交替出现,有解的必要条件即为$h=v$(以下均记为$n$)

进一步的,再假设两种线段依次对应于向量$(a_{i},0)$和$(0,b_{i})$,根据题意要求向量长度为给定值且和为0,那么也即有$|a_{i}|=l_{i},|b_{i}|=p_{i}$且$\sum_{i=1}^{n}a_{i}=\sum_{i=1}^{n}b_{i}=0$

使用背包判定是否存在这样的$a_{i}$和$b_{i}$,若不存在即无解,若存在则再求出任意一组

(可以证明此时一定有解,以下即为构造)

若$a_{i}$中的负数少于$b_{i}$则将两者全部取相反数,再将两者分别从大到小排序(其实只需要保证正数在负数前),最后将$(a_{i},b_{i})$作为一个整体极角排序,并依次选择$(a_{1},0),(0,b_{1}),(a_{2},0),...,(b_{n},0)$即可

(代码实现上通过将两边分别合理排序使得其已经极角排序)

不难发现,以此法最终方案一定是形如下图的形式,即合法

时间复杂度为$o(\frac{nC^{2}}{\omega})$,可以通过

 1 #includebits/stdc++.h
 2 using namespace std;
 3 #define N 1005
 4 bitsetN*Nf[N];
 5 int t,n,m,a[N],b[N];
 6 int calc(int *a){
 7     int m=0;
 8     for(int i=1;i=n;i++)m+=a[i];
 9     if (m1)return 0;
10     m=1;
11     for(int i=1;i=n;i++)f[i]=((f[i-1])|(f[i-1]a[i]));
12     if (!f[n][m])return 0;
13     for(int i=n;i;i--)
14         if (!f[i-1][m]){
15             m-=a[i];
16             a[i]=-a[i];
17         }
18     return 1;
19 }
20 int main(){
21     f[0][0]=1;
22     scanf("%d",t);
23     while (t--){
24         scanf("%d",n);
25         for(int i=1;i=n;i++)scanf("%d",a[i]);
26         scanf("%d",m);
27         for(int i=1;i=m;i++)scanf("%d",b[i]);
28         if ((n!=m)||(!calc(a))||(!calc(b))){
29             printf("No\n");
30             continue;
31         }
32         int cnt=0;
33         for(int i=1;i=n;i++)cnt+=(a[i]0)-(b[i]0);
34         if (cnt0){
35             for(int i=1;i=n;i++)a[i]=-a[i],b[i]=-b[i];
36         }
37         sort(a+1,a+n+1),reverse(a+1,a+n+1);
38         sort(b+1,b+n+1),reverse(b+1,b+n+1);
39         for(int i=1;i=n+1;i++)
40             if ((in)||(a[i]0)){
41                 reverse(b+1,b+i);
42                 break;
43             }
44         for(int i=n;i=0;i--)
45             if ((!i)||(b[i]0)){
46                 reverse(a+i+1,a+n+1);
47                 break;
48             }
49         printf("Yes\n");
50         for(int i=1,x=0,y=0;i=n;i++){
51             x+=a[i],printf("%d %d\n",x,y);
52             y+=b[i],printf("%d %d\n",x,y);
53         }
54     }
55     return 0;
56 } 
View Code

本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

[cf1444D]Rectangular Polyline 相关文章

  1. CF1444D Rectangular Polyline[题解]

    构造 题目大意 给定 \(h\) 条长度分别为 \(l_1,l_2,……,l_h\) 的水平线段以及 \(v\) 条长度分别为 \(p_1,p_2,…….p_v\) 的竖直线段,将这些线段 水平竖直交替 地 首尾相连 组成一个多边形,满足任意两条线段 不相交 或交点为各自的端...

  2. cad.net 替换Polyline2d的点

    Polyline2d的点更改,它和其他的图元处理起来不一样,因为它是一个复杂实体. 需要通过枚举值来处理. 提取点集 先看一个通用的提取点集的做法, GetStretchPoints可以作用在:轻多段线/二维多段线/三维多段线 你只需要将Polyline2d改成其...

  3. vue+高德地图AMap.Polyline画折线+大量数据渲染优化+echarts图表

    vue+高德地图AMap.Polyline画折线+大量数据渲染优化+echarts图表自适应容器 零、本文主要分享内容预先浏览, 1.vue中使用高德地图,画折线,以及给折线定义点击事件。 2.大量数据加载时,边加载边渲染到页面。 3.vue中,echarts图表...

  4. 手把手教你,如何在小程序上面画地图的polyline

    手把手教你,如何在小程序上面画地图的polyline 最终效果 做这个之前需要很多前戏,比如申请腾讯地图key和用户定位、引入qqmap-wx-jssdk.js等 这些小儿科前戏就不在这里说了,主要说一下怎么划线的 第一步建好对应文件之后,引...

  5. 2021.1.27训练题解(CF1017D,CF1015E2,CF1012C)

    \(2021.1.27\)训练题解\((CF1017D,\space CF1015E2,\space CF1012C)\) \(1.CodeForces\space \space CF1017D\)题解 本题目提供\(2\)种解法。 题解:解法一(我的zzt的) 在想不出来解法的时候,仔细观察题目。 我们发现\(n\le12\),而题目又是围绕\(01\)串展

  6. 玩CF卡怎么办解决玩CF卡的办法

    《穿越火线》是一款大型的网络射击游戏,由玩家扮演一名持枪战斗人员,与其他玩家进行械斗。现在这款游戏非常的火爆,也越来越多人在玩,人多了导致玩游戏的时候会很卡。那么,该怎么办呢?接下来就跟小编一起去看看...

  7. 电脑玩cf提示“cf file watcher”怎么解决

    最近有喜欢玩CF游戏的玩家反映,在玩CF游戏的过程中遇到了提示CF File Watcher,导致游戏无法继续进行,玩家不知道这是什么原因导致的,也不知道要怎么解决,这让CF玩家十分头疼。其实,会出现这一问题是因为移动等网络本身...

  8. [CF] CF1311E Construct the Binary Tree

    Description \(Link\) Solution 注意到深度和最小的情况就是完全二叉树,最大的就是链。那么我们先构造出一棵完全二叉树,再一步步调整节点变成链。 不妨令最初的链为\(1,2,4,...,2^k\)。设当前考虑到了点\(i\),链底为\(now\),目前深度...

  9. CF卡是什么CF卡数据丢了还能找回吗

    CF卡是什么,CF卡数据丢了还能找回吗 虽然现在SD卡出现并且日益流行,但是CF卡(Compact Flash)作为一种存储设备,仍然是专业数码相机的主流标准。不仅是数码相机,CF接口还广泛用于PDA、笔记本电脑和包括台式机在内的各种设...

  10. CF烟雾头怎么调最清楚N卡CF最新烟雾头调法

    CF烟雾头怎么调最清楚?玩过CF的用户一定了解,发现烟雾弹扔过来一定要躲避,否则用户怎么扑街的都不知道,而调整烟雾头之后,就算对方放烟雾弹,也可以很清楚的看见到敌人,具体方法请看下文N卡CF最新烟雾头调法。 N卡...

  11. CF怎么调烟雾头Win10系统下CF烟雾头怎么调最清楚

    CF相信大家都非常熟悉了,那么大家知道CF烟雾头是什么吗?通过烟雾头我们可以更清晰的看清敌人所在的位置。而Win10作为新系统,很多用户都不知道CF烟雾头怎么调最清楚?下面小编给大家分享 Win10系统下CF烟雾头的设置方法 ...

  12. [CF1479B2/CF1480D2] Painting the Array II

    [CF1479B2/CF1480D2] Painting the Array II Description 将一个序列拆成两个子序列,然后每个子序列中相邻相同的元素只保留一个,最小化剩下元素的个数。 Solution 贪心,决定每个元素 \(a[i]\) 放在哪里,需要考虑 \(a[i]\),下个和 \(a[i]\) 相等...

  13. [CF1479B1/CF1480D1] Painting the Array I

    [CF1479B1/CF1480D1] Painting the Array I Description 将一个序列拆成两个子序列,然后每个子序列中相邻相同的元素只保留一个,最大化剩下元素的个数。 Solution 贪心,决定每个元素 \(a[i]\) 放在哪里,取决于 \(a[i],a[i+1]\) 和当前两个已有子...

  14. [CF1479A/CF1480C] Searching Local Minimum - 二分

    [CF1479A] Searching Local Minimum - 二分 Description 藏一个排列,\(n \le 10^5\),最多 100 次询问,找到任意一个局部最小值 \(a_ia_{i+1},a_ia_{i-1}\) Solution 先把一些容易判的判掉,比如 \(n\le 100\),\(a_1,a_n\) 之类 类似二分,维护两个端点,

  15. 玩cf卡屏一顿一顿的怎么办Win10玩cf卡屏一顿一顿的解决方法

    cf是现在很多用户都在玩的竞技游戏,最近很多玩家在玩耍我们的CF的时候,表示自己的电脑玩CF非常的卡顿,屏幕就是一卡一卡的,使用起来非常的不舒服,电脑运行非常不流畅,这个问题怎么去解决呢,这里小编为大家带来详...

  16. CF生化金字塔

    2056年12月25日下午3时25分 “救命

  17. CF穿越火线

    自从上次被Blitz埋伏而任务失败之后,总部命猎狐者率领斯沃特、赛斯、奥摩再次闯入剧

  18. CF生化金字塔

    2056年12月25日下午3时25分 “救命

  19. CF穿越火线

    自从上次被Blitz埋伏而任务失败之后,总部命猎狐者率领斯沃特、赛斯、奥摩再次闯入剧

  20. 2021Win7cf烟雾头怎么调Win7cf烟雾头最新调法2021

    2021年win7cf烟雾头最新调法如何调?CF是一款非常火热的枪战竞技游戏,最近很多小伙伴经常询问小编关于Win7烟雾头最新调法的相关问题,其实烟雾头的调法很简单,这里小编为大家带来2021年烟雾头最新的参数设置和调法!有需...

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词