题目链接: A. Floor Number
题目大意: P 在 n 号房间,除第一层有两个房间外,之后每一层都有 x 个房间,算一下 P 在第几层？
考察点: 好像没什么好侃的。。。。。
Code:
#include <string> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; int t,n,x; int main(void) { cin >> t; while(t -- ) { cin >> n >> x; if(n <= 2) cout << 1 << endl; else cout << (n - 2) / x + 1 + ((n - 2 ) % x == 0 ? 0 : 1 )<< endl; } return 0; }题目链接: B. Symmetric Matrix
题目大意: 给 n 个 2 * 2 的小矩阵,问能不能通过这 n 个小矩阵组合成一个 m * m 的对称矩阵(关于对角线对称)。
考察点: 思维
侃侃:首先我们可以明确的一点是 m 是奇数的时候是必然组不成的,一个很简单的性质 偶数 + 偶数 = 奇数,所以我们只需要判断 m 是偶数的情况。那要怎么知道一个能不能组合成一个对称的矩阵呢？题目中说我们可以使用任何一个小矩阵任意次,如果一个小矩阵满足我们需要的条件,那么我们只用这一个就可以判断大矩阵是否满足了。观察样例我们可以发现:除了 m = 2 之外只要有小矩阵满足 右上角和左下角的值 相等,那么就可以组合成一个 m * m 的对称矩阵。(不明白的可以自己手动画一下)
Code:
#include <cstdio> #include <string> #include <iostream> #include <algorithm> using namespace std; int t,n,m; int main(void) { scanf("%d",&t); while(t --) { bool flag = false; int x1,x2,y1,y2; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i ++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x2 == y1) { flag = true; } } // m 是奇数一定组不成 if(m & 1) flag = false; if(flag) puts("YES"); else puts("NO"); } return 0; }题目链接: C. Increase and Copy
题目大意: 在原数组中有一个数 a[1] = 1,对于这个数组,有两个操作:
给某个位置的元素 + 1。将某个位置的元素 copy 一份追加到 数组 末尾。问最少要多少次能够使得整个数组的和 >= n。
考察点: 贪心、思维
侃侃: 题目让我们求最少的次数,那么如何才能使得次数最少,也就是说怎么才能最优呢？ 与其又增加又复制,我们不如直接增加 a[1] 到一定的程度之后,然后再复制(这时候就相当于是 * 了),这样的次数也是最少的,想一下,如果我们把数提前就复制了几份,那么我们再增加的话是该增加哪个,无疑增加了我们的次数, 总之: 乘是一次,加是一次,肯定优先用乘。 有了策略,剩下的就是具体实现啦。。。 如何知道 + 到什么时候转换成 * 呢？先采取最暴力的做法,我们从头开始枚举,算一下 + 到 2 的时候再 * 需要多少次, + 3 的时候需要多少次,但是这时候一看 n 的范围 10^9 ,还有个 t <= 1000，怎么降低时间复杂度呢？我们发现,没有必要从 1 枚举都 n ,因为我们枚举到一定地步的时候,后面的已经不是最优的啦。只需要枚举到 根号n 即可。
Code:
#include <string> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; int t,n; int main(void) { scanf("%d",&t); while(t --) { scanf("%d",&n); // sqrt 是为了降低时间复杂度,之后的枚举已经没有了意义 int len = sqrt(n),ans = INF; for(int i = 1; i <= len; i ++) { // 自增,自增所需要的次数就是 num - 1 int num = i; // 复制追加需要的次数(需要判断一下能否整除) int res = (n) / num + (n % num == 0 ? 0 : 1); ans = min(ans,num - 1 + res - 1); } printf("%d\n",ans); } return 0; }题目链接: D. Non-zero Segments
题目大意 : 给一个数组,可以向数组中的位置插入任意的数,求最少插入几次可以使得数组中没有 子区间和 为 0 的区间。
考察点: 前缀和、STL库函数的使用、思维。
侃侃: 这道题主要考察前缀和的性质,区间和为 0 ,如何求一个区间和呢？ 某个区间和 = sum[r] - sum[l - 1] ； 区间和为0 : sum[r] - sum[l - 1] = 0,即: sum[r] = sum[l - 1],所以我们求出每个前缀和 ,统计前缀和相等的个数即可。需要注意的两点是:
提前将 0 加入到要统计的序列中。当我们插入一个数的时候,后面的区间前缀和已经发生了改变,需要我们重新进行求取。Code:
#include <map> #include <string> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 2e5 + 10; long long a[maxn],sum[maxn]; int n; // 注意数据范围 map<long long,int>maps; int main(void) { scanf("%d",&n); for(int i = 1; i <= n; i ++) { scanf("%lld",&a[i]); } int ans = 0; maps[0] = 1; sum[1] = a[1]; maps[sum[1]] = 1; for(int i = 2; i <= n; i ++) { sum[i] = sum[i - 1] + a[i]; // 插入一个数后,需要重新进行统计 if(maps[sum[i]]) { ans ++; maps.clear(); sum[i] = a[i]; maps[sum[i]] = 1; maps[0] = 1; } else { maps[sum[i]] = 1; } } printf("%d\n",ans); return 0; }