↓ 跳过正文
  1. Posts/

codeforces 509 B. Painting Pebbles (构造)

·382 字·1 分钟

题目链接

题意:n堆石子,每堆a[i]个,k种颜色。给每个石子涂色,要求对于每种颜色,任意两堆中该颜色石子的个数最多差一个。问是否有解,有解输出一组方案。

思路:我们发现有解与否只和最大值最小值有关。

设mn为最小值,mx为最大值。

当mx>mn+k时无解,否则有解。

如果有解。。。输出方案就好了。。。

代码实现
 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年10月04日 星期二 02时40分20秒
 4File Name :code/cf/problem/509B.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <deque>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <bitset>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34int n,k;
35int a[105];
36int main()
37{
38	#ifndef  ONLINE_JUDGE
39	freopen("code/in.txt","r",stdin);
40  #endif
41
42	cin>>n>>k;
43	int mn = 101;
44	int mx = -1;
45	for ( int i = 1 ; i <= n ; i++)
46	{
47	    cin>>a[i];
48	    mn = min(mn,a[i]);
49	    mx = max(mx,a[i]);
50	}
51	if (mx>mn+k)
52	{
53	    puts("NO");
54	}
55	else
56	{
57	    puts("YES");
58	    for ( int i = 1 ; i  <= n ; i++)
59	    {
60		for ( int j = 1 ; j <= a[i] ; j++) printf("%d ",j%k+1);
61		printf("\n");
62	    }
63	}
64
65  #ifndef ONLINE_JUDGE
66  fclose(stdin);
67  #endif
68    return 0;
69}

相关文章

codeforces 468 A. 24 Game (构造)

·618 字·2 分钟
题目链接 题意:给出n,有1..n n个数,可以选择两个数进行加,减,乘,三种操作,操做完得到一个数放回。 n-1次操作后只剩下一个数。现在要求剩下的数为24.问方法。 思路:我们发现。。。两个数相减可以为1.。那么只要找到4个数的方案和5个数的方案就好了。。。

codeforces 623 A. Graph and String (构造)

·708 字·2 分钟
题目链接:题目链接 题意:给出一个无向图,该图是通过仅包含‘a’ ‘b’ ‘c’三个字母,以规则“i,j之间有边,当且仅当s[i]和s[j]相同,或者s[i]和s[j]在字母表中相邻”(也就是只有’a’和’c’是没有边相连的)得到的,现在问能否还原这个字符串,如果能,输出任意一个解。

codeforces #368 div 2 C. Pythagorean Triples (构造,数学)

·953 字·2 分钟
题目链接 题意:给出一个数,问包含这个数三个数组成的勾股数,输出另外两个数。 思路: 所谓勾股数,就是当组成一个直角三角形的三边长都为正整数时,我们就称这一组数为勾股数. 那么,组成一组勾股数的三个正整数之间,是否具有一定的规律可寻呢?下面我们一起来观察几组勾股数: 规律一:在勾股数(3,4,5)、(5,12,13)、(7,24,25)(9,40,41)中,我们发现 由(3,4,5)有:32=9=4+5 由(5,12,13)有:52=25=12+13 由(7,24,25)有:72=49=24+25 由(9,40,41)有:92=81=40+41. 即在一组勾股数中,当最小边为奇数时,它的平方刚好等于另外两个连续的正整数之和.因此,我们把它推广到一般,从而可得出以下公式: ∵(2n+1)²=4n²+4n+1=(2n²+2n)+(2n²+2n+1) ∴(2n+1)²+(2n²+2n)²=(2n²+2n+1)²(n为正整数) 证明(略) 勾股数公式一:(2n+1,2n²+2n,2n²+2n+1)(n为正整数) 规律二:在勾股数(6,8,10)、(8,15,17)、(10,24,26)中,我们发现 由(6,8,10)有:62=36+2×(8+10) 由(8,15,17)有:82=64=2×(15+17) 由(10,24,26)有:102=100=2×(24+26) 即在一组勾股数中,当最小边为偶数时,它的平方刚好等于两个连续整数之和的二倍,推广到一般,从而可得出另一公式: ∵(2n)2=4n2=2[(n2-1)+(n2+1)] ∴(2n)2+(n2-1)2=(n2+1)2(n≥2且n为正整数) 证明(略) 勾股数公式二:(2n,n²-1,n²+1)(n≥2且n为正整数) 利用以上两个公式,我们可以快速写出各组勾股数.

codeforces 652 B. z-sort (简单构造)

·306 字·1 分钟
题目链接 题意:给出n个元素的序列,问能否得到一个新的序列,使得奇数位置非递减排列,偶数位数非递增排列。 思路:感觉一定可以啊。。。排序以后直接构造。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年03月31日 星期四 14时05分11秒 4File Name :code/cf/problem/652B.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E3+7; 34int a[N]; 35int ans[N]; 36int n ; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 43 cin>>n; 44 for ( int i = 1 ; i <= n ; i++) cin>>a[i]; 45 sort(a+1,a+n+1); 46 int cnt = 0 ; 47 for ( int i = 1 ; i <= n ; i+=2) 48 { 49 ans[i] = a[++cnt]; 50 } 51 52 for ( int i = n/2*2 ; i >= 1 ; i-=2) 53 { 54 ans[i] = a[++cnt]; 55 } 56 57 for ( int i = 1 ; i < n ; i++) cout<<ans[i]<<" "; 58 cout<<ans[n]<<endl; 59 60 #ifndef ONLINE_JUDGE 61 fclose(stdin); 62 #endif 63 return 0; 64}