AGC 008 D K-th K

AGC 008 D K-th K

​​ Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 800 点

問題文 長さ N の数列 x が与えられます。 次の条件をすべて満たす数列 a が存在するか判定し、存在するならば a を 1 つ構成してください。

a は長さ N2 であり、整数 1, 2, …, N をそれぞれちょうど N 個ずつ含む。 各 1≤i≤N について、a に含まれる整数 i のうち左から i 番目に位置するものは、a 全体では左から xi 番目に位置する。 制約 1≤N≤500 1≤xi≤N2 xi はすべて相異なる。 入力 入力は以下の形式で標準入力から与えられる。

N x1 x2 … xN 出力 条件をすべて満たす数列 a が存在しないならば、No を出力せよ。 存在するならば、1 行目に Yes を出力し、2 行目に a を空白区切りで出力せよ。

入力例 1 Copy 3 1 5 9 出力例 1 Copy Yes 1 1 1 2 2 2 3 3 3 たとえば、a に含まれる整数 2 のうち左から 2 番目に位置するものは、a 全体では左から 5 番目に位置しています。 整数 1, 3 についても同様に条件が成り立っています。

入力例 2 Copy 2 4 1 出力例 2 Copy No Score : 800 points

Problem Statement You are given an integer sequence x of length N. Determine if there exists an integer sequence a that satisfies all of the following conditions, and if it exists, construct an instance of a.

a is N2 in length, containing N copies of each of the integers 1, 2, …, N. For each 1≤i≤N, the i-th occurrence of the integer i from the left in a is the xi-th element of a from the left. Constraints 1≤N≤500 1≤xi≤N2 All xi are distinct. Input The input is given from Standard Input in the following format:

N x1 x2 … xN Output If there does not exist an integer sequence a that satisfies all the conditions, print No. If there does exist such an sequence a, print Yes in the first line, then print an instance of a in the second line, with spaces inbetween.

Sample Input 1 Copy 3 1 5 9 Sample Output 1 Copy Yes 1 1 1 2 2 2 3 3 3 For example, the second occurrence of the integer 2 from the left in a in the output is the fifth element of a from the left. Similarly, the condition is satisfied for the integers 1 and 3.

Sample Input 2 Copy 2 4 1 Sample Output 2 Copy No leoly给我们的作业题可以简单分析这个构造题不是特别难

心疼zhx&jpy两位大佬 他们的作业分别是e&f

题目非常拗口

给一个长度为n的数列 x[i] 然后要求 我们构造一个长度为n*n的数列满足如下要求

我第x[i]个位置需要填入i且 我x[i]个位置前面有i-1个i出现

好了 首先我们按照x对他们排序 然后贪心的从小到大开始试着满足他们的条件 如果小的范围都无法满足 大的范围一定也无法满足 所以我贪心的满足所有范围 然后最后再从头到尾扫一遍 按照他的要求去满足题目要求即可

#include#include#define N 550using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int num,pos;}data[N];inline bool cmp(node a,node b){ return a.num0){printf("No");return 0;} } int id=0; for (int i=1;i<=nn;++i){ if (!ans[i]){id=0; if (!cnt[id]){ for (int j=1;j<=n;++j){ if(mark[j]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。