关键词:
传送门:https://acm.ecnu.edu.cn/contest/126/
C. 唐纳德先生与这真的是签到题吗
单测试点时限: 6.0 秒
内存限制: 1024 MB
唐纳德先生在出月赛的过程中,准备了一个签到题:给定一个长度为 n 的非负整数序列 a1,a2,…,an,对于所有的 i,j (1≤i<j≤n),求出 ai+aj,并对这 n(n?1)2 个数进行排序输出。
很不幸的是,唐纳德先生把题目的输入搞丢了,现在只剩下输出。你能把输入还原出来吗?
输入
输入共 t (1≤t≤300) 组测试数据。
每组测试数据有两行,第一行是一个整数 n (3≤n≤300)。
第二行含有 n(n?1)2 个整数 b1,b2,…,bn(n?1)/2 (b1≤b2≤?≤bn(n?1)/2),用空格隔开。
输入保证所有 t 组数据 n 的和不超过 300。
输出
对于每组数据,输出一行 n 个整数 a1,a2,…,an,用空格隔开,表示答案。
输入保证存在至少一组解满足 0≤ai≤109 对 1≤i≤n 成立,但是你输出的解可以不在这个范围内:只要满足 ai 都是非负整数,且与题目要求相符,就视为正确。如有多解,输出任意一解。
样例
2 3 3 5 6 4 3 4 5 5 6 7
1 2 4 1 2 3 4
解题思路:
原题:BZOJ 2797
a1+a2, a1+a3 肯定是给出的 b 序列里最小的那两个。
即 a1+a2 = b1, a1+a3 = b2;
但是三个未知数,我们还需要一条方程才能解。
那么 a2+a3 到底是第几个 b 呢?
暴力枚举 第 3 ~ N 个 b,找出正解 a2+a3;
得到 a2+a3 = bi ( 3 <= i <= N);
如何判断当前枚举的 b 是不是正解 a2+a3 呢?
通过上面三条方程我们可以 解出当前 a2+a3 = bi 情况下的 a1, a2, a3.
那么 把 b 序列中的 a1+a2, a1+a3, a2+a3删掉,最小的肯定是 a1+a4 了
已知 a1 可以求出 a4, 继续把 b 序列里的 a1+a4, a2+a4, a3+a4 删掉,最小的肯定是 a1+a5 了
已知 a1 可以求出 a5。。。。。。。。。
如果这其中任何一个过程出现了 求得的 a 为 负数,说明当前的 a2+a3 不是正解。
如果这其中任何一个过程出现了 在 b 序列里找不到要删除的数,说明当前的 a2+a3 不是正解。
那么怎么维护这个可以删除元素 并且 能自动排序的 b 序列呢
运用 C++ stl 里的 multiset ,一个默认将元素从小到大排序,支持查找 删除的二叉树数据结构。
通过枚举 a2+a3 只要找到一个 可行的 a2+a3 把答案输出即可。
(这道题只需要求一组可行的答案即可,BZOJ 2797 要求所有满足条件的答案,其实就是找到就行 和 全部暴力的区别)
AC code:
1 #include <set> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #define INF 0x3f3f3f3f 7 #define LL long long 8 using namespace std; 9 const int MAXN = 301; 10 int N, len; 11 LL num[MAXN*MAXN]; 12 multiset<LL>s; 13 LL ans[MAXN]; 14 15 bool check(LL A23) 16 17 s.clear(); 18 //printf("len:%d ", len); 19 for(int i = 3; i <= len; i++) ///把 题目给的 b 序列 丢进 multiset 20 //printf("%lld ", num[i]); 21 s.insert(num[i]); 22 23 24 s.erase(s.find(A23)); //删除 a2+a3 25 26 //puts("zjy"); 27 if((num[1]+num[2]+A23)&1LL) return false; 28 LL tmp = (num[1]+num[2]-A23)/2LL; 29 //printf("tmp:%lld ", tmp); 30 ans[1] = tmp; //a1 31 ans[2] = num[2]-tmp; //a2 32 ans[3] = A23-ans[2]; //a3 33 //printf("A23:%lld tmp:%lld ans3:%lld ", ans[3]); 34 if(ans[1] < 0 || ans[2] < 0 || ans[3] < 0) return false; ///前三个答案有其中一个为 0 即不满足条件 35 //if(!(ans[1] <= ans[2] && ans[2] <= ans[3] && ans[1] <= ans[3])) return false; 36 37 38 LL value = 0; 39 LL it = 0; 40 for(int i = 4; i <= N; i++) ///算出 ai 的答案 41 value = *s.begin(); 42 ans[i] = value-ans[1]; 43 if(ans[i] < 0) return false; 44 45 for(int j = 1; j < i; j++) ///删除掉 ai+a1, ai+a2,这类, 保证 b 序列里最小的是 a1 + ai+1 46 it = ans[i]+ans[j]; 47 if(s.find(it) == s.end()) return false; /// b 序列里没有 ai+aj 这个数, 即 当前的这组结果无法算出答案序列里的值 48 s.erase(s.find(it)); ///把 ai+aj 从 b 序列里删除 49 50 51 return true; 52 53 54 55 int main() 56 57 int T_case; 58 scanf("%d", &T_case); 59 while(T_case--) 60 scanf("%d", &N); 61 len = (N*(N-1))/2; 62 for(int i = 1; i <= len; i++) 63 scanf("%lld", &num[i]); 64 65 66 for(int i = 3; i <= len; i++) 67 if(i == 3 || num[i] != num[i-1]) 68 if(check(num[i])) 69 //printf("A23:%lld ", num[i]); 70 break; 71 72 73 74 //puts("zjy"); 75 //printf("N:%d ", N); 76 77 for(int i = 1; i <= N; i++) 78 //printf("i:%d ans:%lld ",i, ans[i]); 79 printf("%lld ", ans[i]); 80 81 puts(""); 82 83 84 85 return 0; 86
eojmonthly2021.9sponsoredbytusimple(a)(代码片段)
EOJMonthly2021.9SponsoredbyTuSimpleA.Amazing.Discovery题意:思路:解法1:解法2:EOJMonthly2021.9SponsoredbyTuSimpleA.Amazing.Discovery题意:给出a,b,na,b,n 查看详情
2019.1筑基
2018.12.14 名言佳句:1 理论表述:1 核心词汇:1 申论感悟:1 查看详情
eojmonthly2018.2(goodbye2017)
23333333333333333由于情人节要回家,所以就先只放代码了。 此题是与我胖虎过不去。 【E.出老千的xjj】#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>usingnamespac 查看详情
eojmonthly2018.2
A.坑爹的售票机题意用(1,5,10,25,50,100)的纸币买(n)张单价为(p)的船票,且一次性最多买(k)张,求钱数恰好时最少需要多少张纸币。Hard:(n,k,pleq10^9)思路Easy:dpHard:dp+瞎搞当钱数过大或者张数过多时,(由直觉)其中的大部分都是遵循一... 查看详情
intellijidea安装ideaiu-2019.1
eojmonthly2021.9sponsoredbytusimple——a.amazing.discovery(分治or二次剩余)(代码片段)
EOJMonthly2021.9SponsoredbyTuSimpleA.Amazing.Discovery题意:思路:解法1:解法2:EOJMonthly2021.9SponsoredbyTuSimpleA.Amazing.Discovery题意:给出a,b,na,b,n 查看详情
2019.1的idea的pulgins无法使用解决
第一步第二步 查看详情
eojmonthly2018.12f.日落轨迹
题解:对于任何一个串的前x字符内的本质不同子串我们可以直接在SAM树上得到然后我们考虑循环串的性质(设循环节长度为l)则大于2*l的位置为等差数列即每增加一个字符则增加l个本质不同的子串所以对于2*l我们在后缀树上处理处... 查看详情
eojmonthly2018.1f最小or路径
题目链接Description给定一个有(n)个点和(m)条边的无向图,其中每一条边(e_i)都有一个权值记为(w_i)。对于给出的两个点(a)和(b),求一条(a)到(b)的路径,使得路径上的边权的(OR)(位或)和最小,输出这个值。(也就是说,如果将路径... 查看详情
唐纳德·特朗普不应该抛弃欧洲
也许唐纳德·特朗普总统的外交政策议程上的任何项目都不清楚他新政府对欧洲与美国关系的态度。有一些明显的原因。在不同的时刻,在竞选中,他似乎质疑了对安全和经济政策支持的美国政府和欧洲政府近七十年的大西洋共... 查看详情
eojmonthly2020.7sponsoredbytusimplee.因数串数学/构造(代码片段)
给定一个n表示a的质因数个数。接下来n行给出质数及其指数。按要求输出其因数,满足如下要求:当前数是前一个数通过乘一个质数或者除以一个质数得到。 反正就是构造嘛。对于每一个i,必然要遍历前面的所有情况。其... 查看详情
eojmonthly2020.7sponsoredbytusimplec题(二维前缀和)(代码片段)
模板:ditu[x1][y1]++;ditu[x2+1][y1]--;ditu[x1][y2+1]--;ditu[x2+1][y2+1]++;for(inti=1;i<=a;i++)for(intj=1;j<=b;j++)dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+ditu[i][j];题目:思路:给你了n,m的布偶矩阵,每个1点对应在a,b 查看详情
idea升级到2019.1之后注解生成的代码无法提示和自动完成
idea升级到2019.1之后注解生成的代码无法提示和自动完成遇到这种问题不要慌,只是lombok插件需要更新到对应的版本而已 查看详情
idea升级到2019.1之后注解生成的代码无法提示和自动完成
idea升级到2019.1之后注解生成的代码无法提示和自动完成遇到这种问题不要慌,只是lombok插件需要更新到对应的版本而已 查看详情
g唐纳德与子串(华师网络赛---字符串,后缀数组)
Timelimitpertest: 1.0secondsMemorylimit: 256megabytes子串的定义是在一个字符串中连续出现的一段字符。这里,我们使用 s[l…r] 来表示 s 字符串从 l 到 r(闭区间)的子串。在本题中,字符串下标从 ... 查看详情
eojmonthly2020.7a.打字机(代码片段)
题面CuberQQ长期在网络上与他人对线,一天,他发明了一台神奇的打字机。这台打字机只能处理由a,b,X构成的字符串。具体来说,打字机能够执行如下三种操作。操作:将任意一个X替换为aX。操作:将任意一个X替换为aXbX。操作:... 查看详情
[eojmonthly2018.10][c.痛苦的01矩阵](代码片段)
题目链接:C.痛苦的01矩阵题目大意:原题说的很清楚了,不需要简化_(:з」∠)_题解:设(r_i)为第(i)行中0的个数,(c_j)为第(j)列中0的个数,(f_i,j)代表对应格子是否为0,则有(cost(i,j)=r_i+c_j-f_i,j),((cost(i,j))^2=r_i^2+c_j^2+f_i,j+2r_ic_j-2f_i,... 查看详情
eojmonthly2019.2(代码片段)
题解A 回收卫星#pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#pragmaGCCoptimize(4)#include<bits/stdc++.h>usingnamespacestd;#definey1y11#definefifirst#definesesecond#definepiacos(-1.0)#defineLLlonglong//#definempmake_pair#definepbpush_back#definelsrt<<1,l,m#definersrt<<1|1,m+1... 查看详情