[CF]Codeforces Round #529 (Div. 3)
[CF]Codeforces Round #529 (Div. 3)
C.?Powers Of Two
Description
A positive integer?xx?is called a?power of two?if it can be represented as?x=2yx=2y, where?yy?is a non-negative integer. So, the?powers of two?are?1,2,4,8,16,…1,2,4,8,16,….
You are given two positive integers?nn?and?kk. Your task is to represent?nn?as the?sum?of?exactlykk?powers of two.
Input
The only line of the input contains two integers?nn?and?kk?(1≤n≤1091≤n≤109,?1≤k≤2?1051≤k≤2?105).
output
If it is impossible to represent?nn?as the sum of?kk?powers of two, print?NO.
Otherwise, print?YES, and then print?kk?positive integers?b1,b2,…,bkb1,b2,…,bk?such that each of?bibi?is a power of two, and?∑i=1kbi=n∑i=1kbi=n. If there are multiple answers, you may print any of them.
Examples
Input
9 4
Output
YES
1 2 2 4
Input
5 1
Output
NO
?
正確解法：
題目的意思是說，從2的次冪中找出k個(gè)，使他們相加等于n。
我剛開始想的暴搜，從1 1 1 2 2? 4 8 等等一個(gè)一個(gè)找。
我們只要貪心，從大到小就好，找到一個(gè)方案就可以。
于是只要滿足 n-? 2的次冪? >=k-1?
如果找到有k個(gè)，就可以了。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<algorithm> 8 #include<cmath> 9 #include<cstdlib> 10 using namespace std; 11 int a[40],f[200100],cnt=0; 12 int n, k; 13 int main() 14 { 15 a[0] = 1; 16 for (int i = 1; i <= 30; i++) 17 a[i] = 2 * a[i - 1]; 18 scanf("%d %d",&n,&k); 19 for (int i = 30; i >= 0; i--) 20 { 21 while (n - a[i] >= k - 1 &&n&&k) 22 { 23 n = n - a[i]; 24 f[++cnt] = a[i]; 25 k--; 26 } 27 } 28 if (n==0) 29 { 30 cout << "YES" << endl; 31 for (int i = cnt; i>1; i--) 32 printf("%d ",f[i]); 33 printf("%d\n",f[1]); 34 } 35 else cout << "NO" << endl; 36 return 0; 37 } 38 View Code?
D. Circular Dance
Description
There are?nn?kids, numbered from?11?to?nn, dancing in a circle around the Christmas tree. Let's enumerate them in a clockwise direction as?p1p1,?p2p2, ...,?pnpn?(all these numbers are from?11?to?nnand are distinct, so?pp?is a permutation). Let the next kid for a kid?pipi?be kid?pi+1pi+1?if?i<ni<n?and?p1p1?otherwise. After the dance, each kid remembered two kids: the next kid (let's call him?xx) and the next kid for?xx. Each kid told you which kids he/she remembered: the kid?iiremembered kids?ai,1ai,1?and?ai,2ai,2. However, the order of?ai,1ai,1?and?ai,2ai,2?can differ from their order in the circle.
Example: 5 kids in a circle,?p=[3,2,4,1,5]p=[3,2,4,1,5]?(or any cyclic shift). The information kids remembered is:?a1,1=3a1,1=3,?a1,2=5a1,2=5;?a2,1=1a2,1=1,?a2,2=4a2,2=4;?a3,1=2a3,1=2,?a3,2=4a3,2=4;?a4,1=1a4,1=1,?a4,2=5a4,2=5;?a5,1=2a5,1=2,?a5,2=3a5,2=3.You have to restore the order of the kids in the circle using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.
Input
The first line of the input contains one integer?nn?(3≤n≤2?1053≤n≤2?105) — the number of the kids.
The next?nn?lines contain?22?integers each. The?ii-th line contains two integers?ai,1ai,1?and?ai,2ai,2?(1≤ai,1,ai,2≤n,ai,1≠ai,21≤ai,1,ai,2≤n,ai,1≠ai,2) — the kids the?ii-th kid remembered, given in arbitrary order.
output
Print?nn?integers?p1p1,?p2p2, ...,?pnpn?— permutation of integers from?11?to?nn, which corresponds to the order of kids in the circle.?If there are several answers, you may print any?(for example, it doesn't matter which kid is the first in the circle). It is guaranteed that at least one solution exists.
Examples
Input
5
3 5
1 4
2 4
1 5
2 3
Output
3 2 4 1 5
Input
3
2 3
3 1
1 2
Output
3 1 2
?
正確解法：
題目是說，有n個(gè)小朋友轉(zhuǎn)圈，每個(gè)小朋友只記得自己后面的兩個(gè)小朋友，讓你找出來小朋友排列的正確次序。
搜索把，我不太喜歡這種排列問題。真要我寫可能會卡死。
（這個(gè)小朋友記得的第一個(gè)人，（記得的后面的兩個(gè)人其中之一））如果是（這個(gè)小朋友記得的第二個(gè)人），那么這個(gè)第一個(gè)人就在這個(gè)小朋友后面。
很明顯兩種情況。
排列嘛，無論從哪個(gè)小朋友開始都可以，后來我發(fā)現(xiàn)一個(gè)問題，如果你找的最后一個(gè)人是第一個(gè)小朋友，那么這個(gè)圈就結(jié)束了。如果不是，就不符合情況。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<algorithm> 8 #include<cmath> 9 #include<cstdlib> 10 using namespace std; 11 int n, a[200100][3],b[201000]; 12 int flag = 0; 13 void dfs(int x, int c) 14 { 15 if (x>=n) 16 { 17 if (flag==0&&c==b[0]) 18 { 19 for (int i = 0; i < n - 1; i++) 20 printf("%d ", b[i]); 21 printf("%d\n", b[n - 1]); 22 flag = 1; 23 } 24 return ; 25 } 26 if (a[a[c][0]][0] == a[c][1] || a[a[c][0]][1] == a[c][1]) 27 { 28 b[x+1] = a[c][0]; 29 dfs(x + 1, b[x+1]); 30 } 31 if (a[a[c][1]][0] == a[c][0] || a[a[c][1]][1] == a[c][0]) 32 { 33 b[x+1] = a[c][1]; 34 dfs(x + 1, b[x+1]); 35 } 36 } 37 int main() 38 { 39 scanf("%d",&n); 40 for (int i = 1; i <= n; i++) 41 scanf("%d %d",&a[i][0],&a[i][1]); 42 b[0] = 1; 43 dfs(0, 1); 44 45 return 0; 46 } 47 View Code?
轉(zhuǎn)載于:https://www.cnblogs.com/Kaike/p/10190876.html
總結(jié)
以上是生活随笔為你收集整理的[CF]Codeforces Round #529 (Div. 3)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： AR报表控件的常见问题汇总
- 下一篇： EasyUI datagrid 分页保持