微网站怎么做百度关键词,广州天府路一栋楼外墙脚手架坍塌,doooor设计,国内5大搜索引擎A.Rectangle Cutting (模拟)
题意#xff1a;
给出一个长方形#xff0c;通过平行于原始矩形的一条边进行切割#xff0c;将该矩形切割成两个边长为整数的矩形。询问是否能通过旋转和移动这两个矩形#xff0c;得到新的矩形。
分析#xff1a;
可以发现拼成的新长方形…A.Rectangle Cutting (模拟)
题意
给出一个长方形通过平行于原始矩形的一条边进行切割将该矩形切割成两个边长为整数的矩形。询问是否能通过旋转和移动这两个矩形得到新的矩形。
分析
可以发现拼成的新长方形一定是原长方形的一条边减半一条边翻倍只要判断平分切开再拼接不会是正方形即可。
代码
#include bits/stdc.husing namespace std;void solve() {int n, m;cin n m;if ((n % 2 0 n / 2 ! m) || (m % 2 0 m / 2 ! n))cout Yes endl;elsecout No endl;
}int main() {int t;cin t;while (t--) {solve();}return 0;
}B.Equalize (双指针)
题意
给出一个长度为 n n n的数组 a a a将一个排列加到 a a a数组上之后统计所有数字的出现次数问怎样添加排列可以使得所有数字出现的次数中的最大值尽可能大。输出这个最大值。
分析
元素之间差值小于 n n n可以通过加上一个排列变成相同的值将题目转化成有多少不同元素满足它们之间的差值都小于 n n n。利用双指针快速计算。
代码
#include bits/stdc.husing namespace std;
setint s;
vectorint a;void solve() {int n;cin n;s.clear();a.clear();for (int i 0; i n; i) {int x;cin x;s.insert(x);}for (auto tmp: s)a.push_back(tmp);int maxval 1, ans 1, pos 0;for (int i 1; i a.size(); i) {if (a[i] - a[pos] n) {maxval max(maxval, ans);while (pos i a[i] - a[pos] n)pos;ans i - pos 1;} elseans;}maxval max(maxval, ans);cout maxval endl;
}int main() {int t;cin t;while (t--) {solve();}return 0;
}C. Physical Education Lesson (思维)
题意
定义一个数组 a a a a 1 1 , a 2 2 … a k k , a k 1 k − 1 , a k 2 k − 2 , … , a 2 k − 2 2 a_1 1,a_2 2 \dots a_k k,a_{k 1} k - 1, a_{k 2} k - 2, \dots ,a_{2k - 2}2 a11,a22…akk,ak1k−1,ak2k−2,…,a2k−22以 2 k − 2 2k - 2 2k−2为一组重复。给定 n , x n, x n,x询问使得 a [ n ] x a[n] x a[n]x的 k k k有多少个。
分析 n n n只有两种情况在递增的序列上和递减的序列上如果是递增序列那么 n − x n-x n−x是 2 × k − 2 2\times k-2 2×k−2的倍数如果是递减序列那么 n x − 2 n x - 2 nx−2是 2 × k − 2 2 \times k-2 2×k−2的倍数求出所有可能的 k k k判断第 n n n个数是否为 x x x即可。
代码
#include bits/stdc.husing namespace std;void solve() {int n, x;cin n x;int l n x - 2;int r n - x;setint s;for (int i 1; i l / i; i)if (l % i 0) {if (i % 2 0 (i 2) / 2 x)s.insert(i);if ((l / i) % 2 0 (l / i 2) / 2 x)s.insert(l / i);}for (int i 1; i r / i; i)if (r % i 0) {if (i % 2 0 (i 2) / 2 x)s.insert(i);if ((r / i) % 2 0 (r / i 2) / 2 x)s.insert(r / i);}cout s.size() endl;
}int main() {int t;cin t;while (t--) {solve();}return 0;
}D.Lonely Mountain Dungeons (思维)
题意
有 n n n个种族每个种族数量为 c i c_i ci。现在要组建军队每对处于不同小队的同一种族的生物都会为军队的总兵力增加 b b b个单位然而小队越多越不好管理 k k k个小队组成的军队总兵力会减少 ( k − 1 ) × x (k-1) \times x (k−1)×x。询问怎样组建军队能使得总兵力最大。
分析
假设当前有 k k k队某个种族有 x x x人当 x ≤ k x \le k x≤k时战力会增加 C ( x , 2 ) C(x,2) C(x,2)当 x k x k xk时会存在同一种族的人在相同的队伍中假设有 y y y人那么需要减去 C ( y , 2 ) C(y,2) C(y,2)。考虑到种族数量加起来为 2 e 5 2e5 2e5所以考虑暴力枚举 k k k。
代码
#include bits/stdc.husing namespace std;
typedef long long LL;
const int MAXN 2e5 5;
vectorLL num(MAXN, 0);void solve() {LL n, b, x;cin n b x;num.clear();mapLL, LL map1;LL maxval 0;for (int i 0; i n; i) {cin num[i];maxval max(maxval, num[i]);map1[num[i]];}LL ans 0;for (int i maxval; i 1; i--) {LL sum 0;for (auto tmp: map1) {LL x tmp.first / i;LL cnt tmp.first % i;sum (tmp.first * (tmp.first - 1) / 2 - (cnt * (x 1) * x / 2 (i - cnt) * x * (x - 1) / 2)) *tmp.second;}LL tmp1 b * sum;tmp1 - (i - 1) * x;ans max(ans, tmp1);}cout ans endl;
}int main() {int t;cin t;while (t--) {solve();}return 0;
}E.Modular Sequence (dp)
题意
给出两个整数 x , y x,y x,y询问是否存在一个序列 a a a满足 a 1 x a_1x a1x a i a i − 1 y a_ia_{i-1}y aiai−1y或者 a i a i − 1 % y a_ia_{i-1} \%y aiai−1%y。再给定 n n n和 s s s询问序列 a a a的前 n n n项和是否等于 s s s。
分析
可以发现序列 a a a中所有数的余数都是一个固定的数字 s s s先减去这个余数如果 s s s是合法的那么 s s s一定是 y y y的倍数将 s / y s/y s/y将问题转化成 a 1 x / y , a i a i − 1 1 a_1x/y,a_ia_{i-1}1 a1x/y,aiai−11或者 a i 0 a_i0 ai0。设 d p [ i ] dp[i] dp[i]表示总和为 i i i需要的最短长度。 d p dp dp可以用完全背包进行预处理。由于 a 1 a_1 a1不一定为 0 0 0所以需要枚举 a 1 a_1 a1往后加了多少位的 1 1 1。再用 d p dp dp判断是否有解。
代码
#include bits/stdc.husing namespace std;
const int MAXN 2e5 5;
vectorint dp(MAXN 1, 1e9);void init() {dp[0] 0;for (int i 1;; i) {int t i * (i 1) / 2;if (t MAXN)break;for (int j t; j MAXN; j) {dp[j] min(dp[j], dp[j - t] i 1);}}
}void solve() {int n, x, y, s;cin n x y s;int r x % y;if (1LL * r * n s) {cout NO endl;return;}s - r * n;if (s % y ! 0) {cout NO endl;return;}s / y;vectorint a(n 1);a[1] x / y;int pos -1;int sum a[1], k a[1];for (int i 1; i n sum s; i) {if (dp[s - sum] n - i) {pos i;break;}k 1;sum k;}if (pos -1) {cout NO endl;return;}for (int i 2; i pos; i) {a[i] a[i - 1] 1;}s - sum;int minval dp[s];for (int i 1; s 0; i) {int t i * (i 1) / 2;while (s 0 dp[s - t] i 1 minval) {s - t;minval - i 1;for (int j 0; j i; j) {pos;a[pos] j;}}}cout YES endl;for (int i 1; i n; i) {cout a[i] * y r ;}cout endl;
}int main() {init();int t;cin t;while (t--) {solve();}return 0;
}赛后交流
在比赛结束后会在交流群中给出比赛题解同学们可以在赛后查看题解进行补题。
群号 704572101赛后大家可以一起交流做题思路分享做题技巧欢迎大家的加入。
