【构造】icpc 2022济南 E

缺乏、安全感 2024-03-22 23:04 74阅读 0赞

[Problem - E - Codeforces][]

题意：

给定两个整数N和K，是否存在一个排列使得，对于这个排列，每个长度为K的区间内奇数个数奇偶性是一样的

![078195c4bc094362be190a1152bc5fab.png][]

思路：

构造题，先从最特殊的情况开始考虑

当K=1时，显然不可能满足

当K=2时一定满足，显然奇偶交替摆放即可

推广得，K是偶数时，都是合法的

然后，我们猜一个结论，去猜该怎么特殊化

根据之前的特殊情况猜：区间内奇数和偶数的个数相同

然后就可能猜对了，确实是这样子构造的

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e3+10;
    const int mxe=5e5+10;
    
    int N,K;
    
    void solve(){
    	cin>>N>>K;
    	int tot_odd=(N+1)/2;
    	int tot_even=N/2;
    	int b=N/K;
    	int c=N%K;
    	int k_odd=(K+1)/2;
    	int k_even=K/2;
    	int r_odd=tot_odd-b*k_odd;
    	int r_even=tot_even-b*k_even;
    	if(r_even>=0&&r_odd>=0&&r_even+r_odd==c){
    		if(r_even<=k_even&&r_odd<=k_odd) cout<<"Yes"<<'\n';
    		else cout<<"No"<<'\n';
    		return;
    	}
    	cout<<"No"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/gym/104076/problem/E
[078195c4bc094362be190a1152bc5fab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ba0385e3984441cb828cb6113a41e51b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，74人围观）

还没有评论，来说两句吧...

相关阅读

相关【构造】CF1761 E

[Problem - 1761E - Codeforces][] 题意： ![0622cda9a5a44fcfbb3df51c5babd8bc.png][] 思路：

缺乏、安全感/ 2024年03月23日 22:53/ 0 赞/ 95 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 76 阅读

相关【长链剖分】icpc 2022西安 L

[Problem - L - Codeforces][] 题意： ![1223aff54a5d44cebad6e12b5daf02c7.png][] 思路： ![0d1

阳光穿透心脏的1/2处/ 2024年03月22日 23:32/ 0 赞/ 79 阅读

相关【枚举+结论】icpc2022 济南 A

[Problem - A - Codeforces][] 题意： ![57d5c493fcec44d2a7b7cfc37938be39.png][] 思路：本来的思路

╰+攻爆jí腚メ/ 2024年03月22日 23:07/ 0 赞/ 76 阅读

相关【构造】icpc 2022济南 E

[Problem - E - Codeforces][] 题意：给定两个整数N和K，是否存在一个排列使得，对于这个排列，每个长度为K的区间内奇数个数奇偶性是一样的 ![

缺乏、安全感/ 2024年03月22日 23:04/ 0 赞/ 75 阅读

相关【反悔贪心】2022ICPC南京 G

[Problem - G - Codeforces][] 题意 ![d90998478af246c99ef1811cc2a9b959.png][] 思路首先容易发现，

港控/mmm°/ 2024年02月21日 11:58/ 0 赞/ 60 阅读

相关 2018ICPC 沈阳 E

> https://cn.vjudge.net/problem/2057332/origin 题目的询问为L - R之间的两人曼哈顿距离最长将曼哈顿距离转切比雪夫距离，线

左手的ㄟ右手/ 2023年10月11日 13:27/ 0 赞/ 46 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 32 阅读

相关 ICPC Asia HongKong 2017-E题（二分）

题目：[https://www.jisuanke.com/contest/3820/255960][https_www.jisuanke.com_contest_3820_25

野性酷女/ 2023年08月17日 16:26/ 0 赞/ 114 阅读

相关济南大学c语言,C语言-济南大学2.pdf

第二章 C 语言程序设计基础【学习目标】掌握 C 语言的数据类型，常量和变量的使用。掌握常用的运算符和表达式的使用。掌握库函数 scanf()、printf()

小咪咪/ 2022年10月14日 14:48/ 0 赞/ 263 阅读