目录:A B C D E
标签: 数学(math)
题目大意
酸奶价格, a 元一份,b元两份n
问:买n份最少多少钱
思路
a元一份,b元两份,总有一个比较低,一份一份买或两份两份买取小的一个即可,特判n为奇数多买一个a
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <bits/stdc++.h> using namespace std;void solve () { int n, a, b; cin >> n >> a >> b; cout << min (n * a, n / 2 * b + n % 2 * a) << endl; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 构造算法(constructive algorithms)数据结构(data structures)实现问题,编程技巧,模拟(implementation)排序算法(sortings)
题目大意
一个 n × n阵。三个整数 a1,1 、 c 和 d 并按照以下规则构造一个累进正方形:
ai+1,j = ai,j + c
ai,j+1 = ai,j + d
即:每一行每一列都是等差数列,公差分别为c,d
问题:给n,c,d 和一个长n × n的数组,问此数组是否是个累进正方形
思路
找到数组中最小值一定被作为a1,1,知道a1,1,c,d直接将累进正方形计算出 与 给定数组比较即可
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <bits/stdc++.h> using namespace std;const int N = 250010 ;int a[N], b[N];void solve () { int n, c, d; int idx = 0 ; cin >> n >> c >> d; for (int i = 0 ; i < n * n; i++) cin >> a[i]; sort (a, a + n * n); int t = a[0 ]; for (int i = 0 ; i < n; i++) for (int j = 0 ; j < n; j++) b[idx++] = t + i * c + j * d; sort (b, b + n * n); for (int i = 0 ; i < n * n; i++) if (a[i] != b[i]) { cout << "NO" << endl; return ; } cout << "YES" << endl; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 贪心策略(greedy)实现问题,编程技巧,模拟(implementation)数学(math)
题目大意
n 艘飞船编号从 1 到 n ,依次递增;第 i 艘飞船的耐久度为 ai。
攻击次数 :k 次
攻击力 : 1
攻击顺序 :攻击第一艘飞船,然后是最后一艘,接着又是第一艘,以此类推。
当船只的耐久度下降到 0时,它就会沉没,不再受到攻击
问 :攻击k此后沉没几艘飞船
思路
分两种情况
1、攻击次数大于等于耐久度和,那么全部飞船都会沉没
2、攻击次数小于耐久度和,那么左边飞船共被攻击(k / 2 + k % 2)次,右侧飞船共被攻击k / 2次
枚举计算攻击次数能击沉左边多少艘,右边多少艘即可
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> #define LL long long using namespace std;const int N = 200010 ;int a[N];void solve () { LL n, k, cnt = 0 ; cin >> n >> k; for (int i = 1 ; i <= n; i++){ cin >> a[i]; cnt += a[i]; } if (k >= cnt){ cout << n << endl; return ; } LL t1 = k / 2 + k % 2 ; LL t2 = k / 2 ; int l = 1 , r = n; while (l <= n && t1 >= a[l]) t1 -= a[l++]; while (r >= 1 && t2 >= a[r]) t2 -= a[r --]; cout << l - 1 + n - r << endl; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 数据结构(data structures)双指针算法(two pointers)
题目大意
有一个由 n 个整数组成的数组 a 和一个由 m 个整数组成的数组 b ( m ≤ n )。
好数组定义 :如果数组 c 中的元素可以重新排列,使得其中至少有 k 个元素与数组 b 中的元素匹配,那么认为长度为 m 的数组 c 是好数组。
问 :选择长度为 m 的数组 a 的每个子段作为数组 c 的元素,计算有多少个数组是好的
换句话说,求元素 al,al+1,…,al+m−1构成一个好数组的位置1 ≤ l ≤ n − m + 1 的个数。
思路
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <bits/stdc++.h> #define LL long long using namespace std;const int N = 200010 ;int a[N], b[N];void solve () { int n, m, k; cin >> n >> m >> k; for (int i = 1 ; i <= n; i++) cin >> a[i]; map<int , int > mp1, mp2; for (int i = 1 ; i <= m; i++) { cin >> b[i]; mp1[b[i]] ++; } int cnt = 0 , res = 0 ; for (int i = 1 ; i <= n; i++) { if (i <= m) { if (mp2[a[i]] < mp1[a[i]]) cnt ++; mp2[a[i]] ++; } else { if (cnt >= k) res ++; if (mp2[a[i]] < mp1[a[i]]) cnt ++; mp2[a[i]] ++; if (mp2[a[i-m]] <= mp1[a[i-m]]) cnt --; mp2[a[i - m]] --; } } if (cnt >= k) res ++; cout << res << endl; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
标签: 暴力枚举(brute force)贪心策略(greedy)实现问题,编程技巧,模拟(implementation)排序算法(sortings)
题目大意
给出长度为 n 的仅由字符 “1 “和 “0 “组成的字符串 s。
选择一个整数 k ( 1 ≤ k ≤ n),然后任意多次执行以下操作:
选择字符串中连续的 k 个字符并将其反转,即用 “1 “替换所有 “0”,反之亦然。
通过这些操作,您需要使字符串中的所有字符都等于 “1”。
求:k 的最大值
思路
两步一起可交换或反转每相隔为k + 1位置的数字
例如k = 3如图1,反转红线和黑线,即交换和反转相隔为k + 1位置的数字
那么如图2中的相连的数字都可以任意交换位置
一种做法:用以上方法将1全部移到前1 ~ k 个字符上,然后将其反转,判断能否全部反转即可
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/stdc++.h> using namespace std;const int N = 200010 ;int a[N], b[N], n; string s;bool check (int x) { int res = 0 ; for (int i = 0 ; i < x; i++) { int cnt = 0 ; for (int j = i; j < n; j += x) if (s[j] == '0' ) cnt ++; res += cnt % 2 ; } return res % x; }void solve () { cin >> n >> s; int k = n; while (check (k)) k--; cout << k << endl; }int main () { int T; cin >> T; while (T--) solve (); return 0 ; }
logo