A. Diverse Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Permutationpis an ordered set of integersp1,p2,…,pn, consisting ofndistinct positive integers not larger thann. We’ll denote asnthe length of permutationp1,p2,…,pn.
Your task is to find such permutationpof lengthn, that the group of numbers|p1-p2|,|p2-p3|,…,|pn-1-pn|has exactlykdistinct elements.
Input
The single line of the input contains two space-separated positive integersn,k(1≤k<n≤105).
Output
Printnintegers forming the permutation. If there are multiple answers, print any of them.
Sample test(s)
input
3 2
output
1 3 2
input
3 1
output
1 2 3
input
5 2
output
1 3 2 4 5
Note
By|x|we denote the absolute value of numberx.
构造题。
我们首先让序列有k-1个不同的，，然后剩下全是1即可。
如何有k-1个不同的？
一头一尾即可~
比如n=10 那么1，10，2，9，3，8…..
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;int main(){int n,k;scanf("%d%d",&n,&k);int la=1,l=1,r=n+1,now=n-1;cout<<l;for (int i=1;i<k;i++){if ((i&1)==0){l=r-now;now–;la=l;cout<<" "<<l;}else {r=l+now;la=r;cout<<" "<<r;now–;}}if (la==l){for (int i=la+1;i<r;i++)cout<<" "<<i;}else{for (int i=la-1;i>l;i–)cout<<" "<<i;}cout<<endl;return 0;}
B. Interesting Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
We’ll call an array ofnnon-negative integersa[1],a[2],…,a[n]interesting, if it meetsmconstraints. Thei-th of themconstraints consists of three integersli,ri,qi(1≤li≤ri≤n) meaning that valueshould be equal toqi.
Your task is to find anyinterestingarray ofnelements or state that such array doesn’t exist.
Expressionx&ymeans the bitwise AND of numbersxandy. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".
Input
The first line contains two integersn,m(1≤n≤105,1≤m≤105)— the number of elements in the array and the number of limits.
Each of the nextmlines contains three integersli,ri,qi(1≤li≤ri≤n,0≤qi<230) describing thei-th limit.
Output
If theinterestingarray exists, in the first line print "YES" (without the quotes) and in the second line printnintegersa[1],a[2],…,a[n](0≤a[i]<230)decribing theinterestingarray. If there are multiple answers, print any of them.
If theinterestingarray doesn’t exist, print "NO" (without the quotes) in the single line.
Sample test(s)
input
3 11 3 3
output
YES3 3 3
input
3 21 3 31 3 2
output
NO
每一位分别做。
这道题一定要考虑清楚再写！！
枚举每一位，如果一个区间的这一位为1，那么这一段必须全是1；如果这一位是0，那么这个区间至少有一个0。
我们先把必须是1的赋值为1，用前缀和判断是否有0即可。
而只有在充满了艰辛的人生旅途中，始终调整好自己观风景的心态，
