codeforces 996 E. Leaving the Bar (随机化+贪心，向量相加)

2019-04-14 08:58发布

站内文章 / 模拟电子
9646 0 1147
题目：http://codeforces.com/contest/996/problem/E 题意：有n个向量，对这些向量的操作有 + 或者 - ，要求最终得到的向量的模 leq 1.5cdot 10^{6} 。输出对每个向量的操作"1"或者"-1" 思路：贪心思路，没取一个向量，分别算出两个操作下，总向量的模的大小，取总向量模最小的那种方案。 显然像上面那么直接贪，肯定是错的。例：(0,5)，(0,3)，(0,8) 若照上面的思路，答案是：1，-1，-1 （最终模为-6）；而更好的方案是：1，1，-1（最终模为0）。 那是因为涉及到取这些向量时的顺序。ps：但不知道怎么处理取向量的顺序，怀疑是不是不能用贪心，但dp也不可行，数据范围很大。 看题解后发现，可以通过 随机化 random_shuffle() ，不断排列向量的顺序，直到最终得到的向量的模符合要求 leq 1.5cdot 10^{6} 为止   leftarrow 因为答案是必然存在的： 已知 left | v_{i}^{} ight |leq 10^{6} ， left | mathbf{a+b} ight |^{2}=left | mathbf{a} ight |^{2}+left | mathbf{b} ight |^{2}+2cdot left | mathbf{a} ight |cdot left | mathbf{b} ight |cdot cosTheta leq left | mathbf{a} ight |^{2}+left | mathbf{b} ight |^{2} leq 2cdot 10^{12} ，所以 left | mathbf{a+b} ight | leq sqrt{2}cdot 10^{6}< 1.5cdot 10^{6} 其他博文中的一句话 ： “是因为每次我贪心原则是一样的.最后的结果有可能大于1.5e6。  我们需要加一些随机性，多次贪心,直到结果满足题意” #include //#pragma GCC optimize(3) //#pragma GCC optimize("unroll-loops") //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define pb push_back #define mkp(a,b) make_pair(a,b) #define PII pair #define PLL pair #define fi first #define se second #define lc (d<<1) //d*2 #define rc (d<<1|1) //d*2+1 #define eps 1e-9 #define dbg(x) cerr << #x << " = " << x << " "; #define mst(a,val) memset(a,val,sizeof(a)) #define stn(a) setprecision(a)//小数总有效位数 #define stfl setiosflags(ios::fixed)//点后位数:cout<>=1;}return ans;} int inline sgn(double x){return (x>-eps)-(x,greater > qu; //up priority_queue,less > qd; //dn const int inf = 0x3f3f3f3f; //9 const ll inff = 0x3f3f3f3f3f3f3f3f; //18 ll n; int ans[100010]; struct Pos { ll x,y; int id; }pos[100010]; int main() { fio; cin>>n; for(int i=0;i>pos[i].x>>pos[i].y;pos[i].id=i;} while(1) { random_shuffle(pos,pos+n); ll nowx=pos[0].x,nowy=pos[0].y; ans[pos[0].id]=1; for(int i=1;i  

热门文章