第十三届蓝桥杯省赛

刷题统计

水题不解释

#include
#include
#include using namespace std;typedef long long LL;int main()
{LL a, b, n;cin >> a >> b >> n;LL s &＃61; 5 * a &＃43; 2 * b;LL res &＃61; n / s * 7;n %&＃61; s;LL d[] &＃61; {a, a, a, a, a, b, b};for (int i &＃61; 0; n > 0; i &＃43;&＃43; ){n -&＃61; d[i];res &＃43;&＃43; ;}cout << res << endl;return 0;
}

修建灌木

规律题&＃xff0c;手动模拟两边就可以了

#include
#include
#include using namespace std;int main()
{int n;cin >> n;for (int i &＃61; 1; i <&＃61; n; i &＃43;&＃43; )cout << max(i - 1, n - i) * 2 << endl;return 0;
}


X进制

贪心的题目&＃xff0c;可是当时比赛的时候没有证明出来自己的方法是对的&＃xff0c;为了稳妥就直接写了个暴力&＃xff0c;麻了

猜想就是&＃xff0c;两个数那一位的进制就是max(2, max(a, b) &＃43; 1)

证明&＃xff1a;

设D &＃61; A - B则

这里的di不一定是正数&＃xff0c;有可能是负数&＃xff0c;然后要让式子最小&＃xff0c;就能看出来是让每个的位权重最小
我们任取其中一项di&＃xff0c;把包含di的拿出来&＃xff0c;如下图&＃xff0c;后半部分不包含&＃xff0c;先不用管

提取公因子&＃xff0c;所有包含pi的项就变成了

然后因为A大于B&＃xff0c;所以括号中的大于等于0&＃xff0c;后边是权重也要大于0&＃xff0c;所以pi越小这个数越小

这样是证明的每一个pi影响的是一个正数&＃xff0c;所以要尽量都越小越好

#include
#include
#include using namespace std;typedef long long LL;const int N &＃61; 100010, MOD &＃61; 1000000007;int n, m1, m2, m;
int a[N], b[N];int main()
{scanf("%d", &n);scanf("%d", &m1);for (int i &＃61; m1 - 1; i >&＃61; 0; i -- ) scanf("%d", &a[i]);scanf("%d", &m2);for (int i &＃61; m2 - 1; i >&＃61; 0; i -- ) scanf("%d", &b[i]);int m &＃61; max(m1, m2);int res &＃61; 0;for (int i &＃61; m - 1; i >&＃61; 0; i -- )//从高位向低位求res &＃61; (res * (LL)max({2, a[i] &＃43; 1, b[i] &＃43; 1}) &＃43; a[i] - b[i]) % MOD;printf("%d\n", res);return 0;
}

统计子矩阵

前缀和 和 双指针&＃xff0c;这里的前缀和可以用一维也可以用二维&＃xff0c;二维前缀和有超时的风险&＃xff0c;能用一维尽量用一维

数据范围是500&＃xff0c;意味着不能超过立方的复杂度

优化&＃xff1a;上下可以不优化&＃xff0c;枚举一个上边界一个下边界&＃xff0c;上下固定之后&＃xff0c;就变成了一个一维的问题

因为矩阵中的每个数都是大于等于0的&＃xff0c;意味着这个题目有单调性&＃xff0c;就是包含的数越多&＃xff0c;这个子矩阵和就越大&＃xff0c;也就是我们可以使用双指针&＃xff0c;而不是去直接暴力

L一般是R的函数&＃xff0c;这里的L定义为&＃xff0c;当R固定&＃xff0c;L可以取到的最左的边界&＃xff0c;然后证明一下&＃xff0c;这个题目中的证明大概就是&＃xff0c;当R向右的时候&＃xff0c;假设&＃xff0c;L可以往左或者不变&＃xff0c;那么说明L不是之前R固定能取到的最左边&＃xff0c;有矛盾&＃xff0c;所以&＃xff0c;当R向右走&＃xff0c;L一定单调向左

这时候&＃xff0c;双指针只枚举R就行&＃xff0c;所以枚举的时候也是枚举的每一列的前缀和&＃xff0c;预处理也就只按列处理就行了

双指针用法&＃xff1a;先定义好左指针是什么东西&＃xff0c;左指针一般是右指针的函数&＃xff0c;也就是左指针是取决于右指针的&＃xff0c;定义完之后&＃xff0c;再判断&＃xff0c;当右指针往右走的时候&＃xff0c;左指针是不是单调往左或者往右&＃xff0c;证明出来单调性之后&＃xff0c;就可以用双指针来做了

如果这个题里面每一项不一定是正数的话&＃xff0c;那就需要用到平衡树&＃xff0c;线段树或者树状数组这些东西啦

这个题目里面&＃xff0c;矩阵和不会爆int&＃xff0c;但是方案数&＃xff0c;太多了C(2, 501) * C(2, 501)过大&＃xff0c;要用ll

C(2, 501)是长度为1有500种选择&＃xff0c;长度为2有499…以此类推&＃xff0c;行跟列两个还要相乘