G题的构造方法
以下讨论建立在不存在0且至少存在一个-1的基础上:
记录1和-1的出现次数分别为a, b,注意到当a >= b的时候,一定可以构造(任意>0个1可以与1个 -1消掉)
当a < b的时候,可以发现两个-1也可以变成一个1, 相当于把b的一部分借给a,因此a < b也可能有解
let x := b借给a的数量
then a + x >= b - 2x
移项得 3x >= b - a
注意:b - 2x > 0 ——> x <= (b - 1) / 2(下取整)
同时x >= 0 , 故x范围是[0, (b - 1) / 2(下取整)]
则只需要 3 * ((b - 1) / 2) >= b - a 即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; void solve(){ int n, q; cin >> n >> q; vector<int> nums(n); for(auto& num : nums){ cin >> num; } for(int i = 0; i < q; i++){ int x; cin >> x; int cnt1 = count(nums.begin(), nums.end(), 1); int cnt0 = count(nums.begin(), nums.end(), 0); int cntn1 = count(nums.begin(), nums.end(), -1); if(cnt0 > 0 ){ cout << "Yes\n"; continue; }else if(cntn1 == 0){ cout << "No\n"; continue; }else{ int high = (cntn1 - 1) / 2; if(3 * high >= cntn1 - cnt1){ cout << "Yes\n"; }else{ cout << "No\n"; } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ solve(); } return 0; }