Codeforces Round 1061 (Div. 2) C. Maximum GCD on Whiteboard

题意给定一个整数 k 和写在白板上的 n 个正整数 a1​,a2​,…,an​其中 1≤ai​≤n。你可以执行以下操作删除Erase从白板上选择一个整数并删除。该操作最多可执行 k 次。拆分Split从白板上选择一个整数 x≥3将其拆分为三个正整数 x1​,x2​,x3​满足 x1​x2​x3​x 且 1≤x1​≤x2​≤x3​。然后从白板上删除 x并写下两个新整数 x1​ 和 x3​。注意x2​ 会被丢弃不会写回白板。该操作可执行任意次数。一个整数集合 b 的美观度定义为集合中所有元素的最大公约数。形式化地说它是最大的整数 d使得对于 b 中的每一个 xd 都能整除 x。你的任务是在执行最多 k 次删除操作和任意次数的拆分操作后确定白板上整数的最大可能美观度。输入每个测试包含多组测试用例。第一行是测试用例数 t1≤t≤104随后是各组测试用例的描述。每组测试用例的第一行包含两个整数 n 和 k1≤n≤2⋅1050≤k≤n−1—— 分别表示白板上初始的整数个数以及允许执行的最多删除次数。每组测试用例的第二行包含 n 个整数 a1​,a2​,…,an​1≤ai​≤n—— 初始写在白板上的整数。保证所有测试用例的 n 之和不超过 2⋅105。输出对于每组测试用例输出一个整数表示执行操作后白板上整数的最大美观度。思路用for循环从n到1找最大的美观度x这时候就要判断哪个数符合题意等于x2x3x的数可留大于等于4x的数可留那此时就能算出必须要删除的数如果个数小于等于k那么就找到了x求个数用前缀和前缀和来记小于等于此数的个数。#include iostream #include vector #include map using namespace std; #define int long long void solve() { int n,k;cinnk; vectorinta(4*n1,0); for(int i0;in;i) { int x;cinx; a[x]; } vectorintpre(4*n1,0); for(int i1;i4*n;i) { pre[i]pre[i-1]a[i]; } for(int in;i1;i--) { if(pre[i-1]pre[2*i-1]-pre[i]pre[3*i-1]-pre[2*i]pre[4*i-1]-pre[3*i]k) { coutiendl; return; } } cout1endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int t; cint; while(t--) { solve(); } return 0; }