Codeforces Round #674 (Div. 3)(A~D)
本文最后更新于 857 天前,其中的信息可能已经有所发展或是发生改变。

A. Floor Number


Origional Link

题目大意

  • 给定目标房间编号 nn 及一层楼住户数量 xx
  • 第一层楼只有 22 个住户,求目标房间所在楼层。

思想

  • 签到题。
  • n2n\le2 时在第一层。
  • n>2n\gt 2 时:
    • xx 可以整除 n2n-2,则在 n2m+1\frac{n-2}{m} + 1 层;
    • 反之在 n2m+2\frac{n-2}{m} + 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;
}

B. Symmetric Matrix


Origional Link

题目大意

  • 给定 nn2×22\times 2 的矩阵,每个矩阵有无限多个。
  • 求这些矩阵是否可以组合成一个 m×mm\times m 的大矩阵,且使得大矩阵的元素关于主对角线对称。

思想

  • 思维题。
  • 可以构成的大前提条件是 22 可以整除 mm
  • 其次使得大矩阵的元素关于主对角线对称,只需要每个小矩阵的元素次对角线上的元素相同即可。

代码

#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;
}

C. Increase and Copy


Origional Link

题目大意

  • 给定一个序列 a=[1]a = [1]
  • 不限次数进行如下操作:
    • 选择 aia_i 使其变为 ai+1a_i+1
    • 选择 aia_i 将其复制并加入到 aa 的末尾。
  • 给定一个整数 nn,求最少经过多少次操作可以使得 aa 的元素之和至少是 nn

思想

  • 思维题。
  • 最快的方法是将 aia_i 不断变为 ai+1a_i + 1,之后不断执行复制操作,直到总和 sumnsum \ge n
  • 我们设 aia_i 通过 ii+1+1 操作最后得到的数为 xx,复制 xxjj 次后得到大于等于 nn 的数,即:
    • x×(j+1)nx \times (j+1) \ge n
  • i+ji+j 的最小值等价于先求 x+(j+1)x + (j+1) 的最小值,显然地,当 xxj+1j + 1 尽可能接近 n\sqrt{n} 时可以使得 x+(j+1)x+(j+1) 最小。
  • 综上所述,我们需要找到尽可能接近 n\sqrt{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;
}

D. Non-zero Segments


Origional Link

题目大意

  • 给定一个序列 aa,可以在任意相邻对中添加任意大小的数,最终使得不存在一个子序列的和为 00
  • 求最少的添加次数。

思想;

  • 前缀和,贪心。
  • 破坏所有连续的区间和为 00 的区间,可以使用前缀和预处理区间和。
  • 当区间 [l,r] 和为 00 时,有 a[l - 1] = a[r]
  • 从左往右扫描每个区间的左端点,用 map<LL, int> st 存储出现过的前缀。
  • 那么当出现相同的前缀和,说明存在和为 00 的子序列,此时需要在其区间加上一个数。
  • 保证在此之前的所有子序列没有存在和为 00 的前缀,则当前位置改变,其左边区间可以不再考虑,记录操作并且清空 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;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇