Hackforces Round 938 (Div. 3)(A~H）

本文主要是介绍Hackforces Round 938 (Div. 3)(A~H），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Yogurt Sale

题意：需要购买n个物品，a元买1个，b元买两个，求恰好购买n个物品的最少花费。

模拟

void solve() 
{cin >> n;int a, b;cin >> a >> b;int cost =  a * n;for(int i = 0 ; i < n ; i ++){int t = a * i;int res = n - i;if(res & 1) continue;else t += res / 2 * b;cost = min(cost , t);}	cout << cost << endl;
}

B - Progressive Square

题意：

思路：通过观察发现给定的 $n^{2}$ 个数中，最小的那个就是 $a_{1,1}$ 。同时已知 $c,d$ 。因此可以将整个矩阵所有的数求出来，然后跟给出的 $n^{2}$ 个数匹配。匹配方法很多，可以从小到大排序或者直接用map。

void solve() 
{int n , c , d;cin >> n >> c >> d;int a[n * n];for(int i = 0 ; i < n * n; i ++){cin >> a[i];}sort(a , a + n * n);map<int,int>mp;int st = a[0];for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < n ; j ++){mp[st + c * i + d * j]++;}}for(int i = 0 ; i < n * n ; i ++){mp[a[i]]--;}int f = 1;for(auto it : mp){if(it.second != 0){cout <<"NO\n";return;}}cout <<"YES\n";
}

C - Inhabitant of the Deep Sea

题意：

思路：从左侧攻击跟从右侧攻击的次数都是已知的，因此双指针来模拟两边即可。

void solve() 
{LL n , k;cin >> n >> k;for(int i = 0 ; i < n ; i ++){cin >> a[i];}	LL right = k / 2;LL left = k - right;int l = 0 , r = n - 1;LL cnt = 0;while(left){if(left >= a[l]){left -= a[l];a[l] = 0;cnt++;l++;}else{a[l] -= left;left = 0;break;}if(l > r){break;}}while(right){if(right >= a[r]){right -= a[r];a[r] = 0;cnt++;r--;}else{a[r] -= right;right = 0;break;}if(l > r){break;}}cout << min(n , cnt) << endl;
}

D - Inaccurate Subsequence Search

题意：

思路：从左到右暴力枚举所有长度为 $m$ 的连续子串，每次只需要将最左边的一个数剔除以及右侧的数进入即可。因此我们需要知道被剔除的数还剩多少个以及加进来的数有多少个。用map来维护这些信息即可。

void solve() 
{int n , m , k;cin >> n >> m >> k;int a[n] , b[m];unordered_map<int,int>mp;unordered_map<int,int>st;int pi = 0;int cnt = 0;for(int i = 0 ; i < n ; i ++){cin >> a[i];}	for(int i = 0 ; i < m ; i ++){cin >> b[i];mp[b[i]]++;}auto add = [&](int x){st[x]++;if(mp.count(x)){if(st[x] <= mp[x]){pi++;}}};auto del = [&](int x){st[x]--;if(mp.count(x)){if(st[x] < mp[x]){pi--;}}};for(int i = 0 ; i < n ; i ++){if(i - m >= 0)del(a[i - m]);add(a[i]);if(i >= m - 1 && pi >= k){cnt++;}}cout << cnt << endl;
}

E - Long Inversions

题意：

思路：从大到小暴力枚举 $k$ ,每一轮从左到右，碰到0则翻转一次。由于是区间修改，需要使用差分数组/树状数组/线段树。

还有一种思路，对相邻两个位置进行翻转操作，等价于将该位置跟 $k$ 以后的位置进行一次翻转。

void solve() 
{//选择 k 等价于使得a[i] 与 a[i + k] 交换int n;cin >> n;string s;cin >> s;for(int i = n ; i >= 1 ; i --){vector<int>diff(n + 5 , 0);int add = 0;for(int j = 0 ; j <= n - i ; j ++){add += diff[j];if( ( (s[j] - '0') + add)  % 2 == 1){continue;}else{add++;diff[j + i]--;				}}	int f = 1;for(int j = n - i + 1; j < n ; j ++){add += diff[j];if(((s[j] - '0') + add) & 1){continue;}else{f = 0;			}}if(f){cout << i << endl;return;}}
}

F - Unfair Game

题意：

思路：可以发现，共有两种情况能使得Bob赢得比赛

1、{1、2、3、4}的个数都为偶数

2、{1、2、3}的个数模2 以后都一样，且4的个数为偶数

若我们始终构造第二种情况，那么{1,2,3}对答案的贡献为 $min(a_{1} , a_{2} , a_{3})$ ,而构造第一种情况时，{1、2、3}的贡献为 $\left \lfloor \frac{a_{1}}{2} \right \rfloor + \left \lfloor \frac{a_{2}}{2} \right \rfloor + \left \lfloor \frac{a_{3}}{2} \right \rfloor$ ,显然这是大于第二种情况的。因此我们全程只需要构造第一种情况，其方案数为 $\left \lfloor \frac{a_{1}}{2} \right \rfloor + \left \lfloor \frac{a_{2}}{2} \right \rfloor + \left \lfloor \frac{a_{3}}{2} \right \rfloor + \left \lfloor \frac{a_{4}}{2} \right \rfloor$ 。当{1、2、3}的个数都为奇数时，会使得开局满足第二种情况，因此答案需要+1.

void solve() 
{int a[4];int ans = 0;for(int i = 0 ; i < 4 ; i ++){cin >> a[i];ans += a[i] / 2;} ans += (a[0] & 1 && a[1] & 1 && a[2] & 1);cout << ans << endl;
}

G - GCD on a grid

被Hack了

H - The Most Reckless Defense

题意：

思路：注意到防御塔的攻击力不会超过500，因此答案一定不会特别大。因此 $r$ 的范围可以缩小到12以下。可以直接状压DP解决问题。

// Problem: H. The Most Reckless Defense
// Contest: Codeforces - Codeforces Round 938 (Div. 3)
// URL: https://codeforces.com/contest/1955/problem/H
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
#define int long long
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL inv[12];
LL dis(int x , int y , int tx , int ty){LL q = (tx - x) * (tx - x) + (ty - y) * (ty - y);for(int i = 1 ; i < 12 ; i ++){if(i * i >= q){return i;}}return 14;
}
vector<int>tot(1 << 12 , 0);
void solve() 
{int n , m , k;cin >> n >> m >> k;vector<array<int,3>>ta;vector< vector<int> > diss(k , vector<int>(15 , 0));char mp[n + 5][m + 5];for(int i = 1 ; i <= n ; i ++){string s;cin >> s;for(int j = 1 ; j <= m ; j ++){mp[i][j] = s[j - 1];}}for(int i = 0 ; i < k ; i ++){int x , y , t;cin >> x >> y >> t;ta.pb({x , y , t});}	for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= m ; j ++){if(mp[i][j] == '#'){for(int t = 0 ; t < k ; t ++){diss[t][dis(i , j , ta[t][0] , ta[t][1])] += ta[t][2];}}}}for(int t = 0 ; t < k ; t ++){for(int j = 1 ; j < 12 ; j ++){diss[t][j] += diss[t][j - 1];}}vector< vector<int> >mask(2 , vector<int> (1 << 12 , -inf));mask[0][0] = 0;for(int i = 0 ; i < k ; i ++){for(int j = 0 ; j < 1 << 12 ; j ++){if(__builtin_popcount(j) > i)	continue;for(int t = 0 ; t < 12 ; t ++){if( (j >> t) & 1){mask[1][j] = max(mask[1][j] , mask[0][j]);continue;}else{mask[1][j + (1 << t)] = max(max(mask[0][j + (1 << t)] , mask[1][j + (1 << t)]) , mask[0][j] + diss[i][t]); }}}swap(mask[0] , mask[1]);}int ans = 0;for(int i = 0 ; i < 1 << 12 ; i ++){ans = max(ans , mask[0][i] - tot[i]);}cout << ans << endl;
}            
signed main() 
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;inv[0] = 1;for(int i = 1 ; i < 12 ; i ++){inv[i] = inv[i - 1] * 3;}inv[0] = 0;for(int i = 0 ; i < 1 << 12 ; i ++){for(int j = 0 ; j < 12 ; j ++){if((i >> j) & 1){tot[i] += inv[j];}}}cin>>t;while(t--){solve();}return 0;
}

这篇关于Hackforces Round 938 (Div. 3)(A~H）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！