本文最后更新于 857 天前,其中的信息可能已经有所发展或是发生改变。
Origional Link
题目大意:
- 给定目标房间编号 n 及一层楼住户数量 x。
- 第一层楼只有 2 个住户,求目标房间所在楼层。
思想:
- 签到题。
- n≤2 时在第一层。
- n>2 时:
- 若 x 可以整除 n−2,则在 mn−2+1 层;
- 反之在 mn−2+2 层。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 3; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| int a[N]; |
| |
| void solve(){ |
| |
| int n, x; |
| |
| cin >> n >> x; |
| |
| if(n <= 2) cout << 1 << endl; |
| else{ |
| int t = (n - 2) / x + 1; |
| if((n - 2) % x != 0) t ++; |
| cout << t << endl; |
| } |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| cin >> _; |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
Origional Link
题目大意:
- 给定 n 个 2×2 的矩阵,每个矩阵有无限多个。
- 求这些矩阵是否可以组合成一个 m×m 的大矩阵,且使得大矩阵的元素关于主对角线对称。
思想:
- 思维题。
- 可以构成的大前提条件是 2 可以整除 m。
- 其次使得大矩阵的元素关于主对角线对称,只需要每个小矩阵的元素次对角线上的元素相同即可。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 3; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| void solve(){ |
| |
| int n, m; cin >> n >> m; |
| |
| bool flag = 0; |
| |
| for(int i = 0; i < n; i ++){ |
| int a, b, c, d; |
| cin >> a >> b >> c >> d; |
| if(b == c) flag = 1; |
| } |
| |
| if(flag && m % 2 == 0) cout << "YES" << endl; |
| else cout << "NO" << endl; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| cin >> _; |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
Origional Link
题目大意:
- 给定一个序列 a=[1]。
- 不限次数进行如下操作:
- 选择 ai 使其变为 ai+1;
- 选择 ai 将其复制并加入到 a 的末尾。
- 给定一个整数 n,求最少经过多少次操作可以使得 a 的元素之和至少是 n。
思想:
- 思维题。
- 最快的方法是将 ai 不断变为 ai+1,之后不断执行复制操作,直到总和 sum≥n。
- 我们设 ai 通过 i 次 +1 操作最后得到的数为 x,复制 x 共 j 次后得到大于等于 n 的数,即:
- x×(j+1)≥n
- 求 i+j 的最小值等价于先求 x+(j+1) 的最小值,显然地,当 x 和 j+1 尽可能接近 n 时可以使得 x+(j+1) 最小。
- 综上所述,我们需要找到尽可能接近 n 的最大整数。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 3; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| void solve(){ |
| |
| int n; cin >> n; |
| int t = sqrt(n); |
| if(t * t == n) cout << 2 * (t - 1) << endl; |
| else if(t * (t + 1) >= n) cout << 2 * t - 1 << endl; |
| else cout << 2 * t << endl; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| cin >> _; |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
Origional Link
题目大意:
- 给定一个序列 a,可以在任意相邻对中添加任意大小的数,最终使得不存在一个子序列的和为 0 。
- 求最少的添加次数。
思想;
- 前缀和,贪心。
- 破坏所有连续的区间和为 0 的区间,可以使用前缀和预处理区间和。
- 当区间
[l,r]
和为 0 时,有 a[l - 1] = a[r]
。
- 从左往右扫描每个区间的左端点,用
map<LL, int> st
存储出现过的前缀。
- 那么当出现相同的前缀和,说明存在和为 0 的子序列,此时需要在其区间加上一个数。
- 保证在此之前的所有子序列没有存在和为 0 的前缀,则当前位置改变,其左边区间可以不再考虑,记录操作并且清空
st
。
- 注意,由于子区间有可能在端点处重合,这种情况不属于有重复部分,所以清空
st
以后还需要插入当前位置左侧一位置的前缀和。
代码:
| #include <iostream> |
| #include <cstring> |
| #include <cstdio> |
| #include <algorithm> |
| #include <cmath> |
| #include <sstream> |
| #include <vector> |
| #include <queue> |
| #include <stack> |
| #include <map> |
| #include <set> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| using namespace std; |
| |
| #define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr) |
| #define re register |
| #define fi first |
| #define se second |
| #define endl '\n' |
| |
| typedef long long LL; |
| typedef pair<int, int> PII; |
| typedef pair<LL, LL> PLL; |
| |
| const int N = 1e6 + 3; |
| const int INF = 0x3f3f3f3f, mod = 1e9 + 7; |
| const double eps = 1e-6, PI = acos(-1); |
| |
| LL a[N]; |
| |
| void solve(){ |
| |
| map<LL, int> st; |
| |
| int n; cin >> n; |
| for(int i = 1; i <= n; i ++){ |
| cin >> a[i]; |
| a[i] += a[i - 1]; |
| } |
| |
| LL cnt = 0; |
| |
| for(int i = 1; i <= n; i ++){ |
| if(st[a[i]] > 0){ |
| cnt ++; |
| st.clear(); |
| } |
| st[a[i - 1]] ++; |
| } |
| |
| cout << cnt << endl; |
| |
| } |
| |
| int main(){ |
| |
| IOS; |
| |
| int _ = 1; |
| |
| |
| |
| while(_ --){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |