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

A. YES or YES?


题目大意

Origional Link

  • 判断是否是yes顺序的不区分大小写的字符串
  • 是则输出YES,否则输出NO

思想

  • 读入暴力判断

代码

#include <bits/stdc++.h>
using namespace std;
void solve(){
string s;
cin >> s;
bool flag = 1;
if(s[0] != 'y' && s[0] != 'Y') flag = 0;
if(s[1] != 'e' && s[1] != 'E') flag = 0;
if(s[2] != 's' && s[2] != 'S') flag = 0;
if(s.size() == 3 && flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}

B. ICPC Balloons


题目大意

Origional Link

  • AZA \sim Z道题,第一次出现送出两个气球,后续出现送出一个气球
  • 求比赛共送出多少气球

思想

  • vis[i]标记是否出现过
  • 未出现的送出两个,出现过送出一个
  • 遍历字符串求和

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
bool vis[N];
void solve(){
memset(vis,0,sizeof vis);
int n;
cin >> n;
LL cnt = 0;
while(n--){
char a;
cin >> a;
if(!vis[a]){
cnt += 2;
vis[a] = 1;
}
else cnt ++;
}
cout << cnt << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}

C. Cypher


题目大意

Origional Link

  • 每个密码锁有nn个轮子,轮子上有090\sim 9
  • 给出最终位置显示的数字aia_i,和第ii个位置的bib_i次操作
  • 求原始的数字

思想

  • 模拟
  • ans[i]存储第ii位的最终数字,用flag存储操作的偏移量
  • 若为Uflag --,反之flag ++
  • 对于ans[i],加上其偏移量并取正整数模,即ans[i] = ( ans[i] + flag % 10 + 10 ) % 10即为原始数字

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int ans[N];
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> ans[i];
for(int i = 1; i <= n; i ++){
int m;
cin >> m;
int flag = 0;
while(m--){
char op;
cin >> op;
if(op == 'D') flag ++;
else flag --;
}
ans[i] = (ans[i] + flag % 10 + 10) % 10;
}
for(int i = 1; i <= n; i ++) cout << ans[i] << " ";
cout << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}

D. Double Strings


题目大意

Origional Link

  • 给定nn个长度不超过88的字符串ss
  • 若对于si=sj+sks_i = s_j + s_k成立,则sis_i标记为11,否则标记为00

思想

  • nn比较大,但sis_i较短
  • 对于sis_i,每次构造两个sis_i的字串si,sis_i',s_i'',对字串进行查询
  • 若两个字串都可以找到,则标记sis_i11,反之为00
  • 利用s[N]set<string> st同时存储所有的s[i]
  • 遍历s[i],第一个字串从s[0]开始,长度为1 <= j <= s[i].size() - 1 ,第二个字串从s[j]开始,长度为s[i].size() - j
  • 利用st.count(s)查询字串s

代码

#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
bool vis[n + 10];
memset(vis,0,sizeof vis);
set<string> st;
string s[n + 1];
for(int i = 0; i < n; i ++){
cin >> s[i];
st.insert(s[i]);
}
for(int i = 0; i < n; i ++){
if(s[i].size() == 1) continue;
for(int j = 1; j <= s[i].size() - 1; j ++){
string s1 = s[i].substr(0,j), s2 = s[i].substr(j,s[i].size() - j);
if(st.count(s1) == 1 && st.count(s2) == 1){
vis[i] = 1;
break;
}
}
}
for(int i = 0; i < n; i ++){
if(vis[i]) cout << 1;
else cout << 0;
}
cout << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}

E. Mirror Grid


题目大意

Origional Link

  • 给定由0011构成正方形数组
  • 将数组向右选择90度,180度,270度
  • 求如何改变原数组中的值,使得四种形态的数组里的值都一样的改变最少操作次数

思想

  • 原二维数组中的一个位置mp[i][j]旋转三次后,总共会出现在三个位置上
  • mp[j][n + 1 - i]mp[n + 1 - i][n + 1 - j]mp[n + 1 - j][i]
  • 统计原位置的值和这三个新位置的值变为相同的最小操作次数即可

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char mp[N][N];
bool st[N][N];
void solve()
{
int n;
cin >> n;
memset(st, 0, sizeof st);
for (int i = 1; i <= n; i++) cin >> mp[i] + 1;
int ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if(i == j && n % 2 == 1) continue;
if(!st[i][j]){
int cnt = 0;
if(mp[i][j] == '1') cnt++;
st[i][j] = 1;
if(mp[j][n - i + 1] == '1') cnt++;
st[j][n - i + 1] = 1;
if(mp[n - i + 1][n - j + 1] == '1') cnt++;
st[n - i + 1][n - j + 1] = 1;
if(mp[n - j + 1][i] == '1') cnt++;
st[n - j + 1][i] = 1;
ans += min(cnt, 4 - cnt);
}
}
}
cout << ans << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}

F. Yet Another Problem About Pairs Satisfying an Inequality


题目大意

Origional Link

  • 对于数列aa,找到满足ai<i<aj<j,1i,jna_i \lt i\lt a_j<j,1\le i,j\le ni,ji,j对数

思想

  • 对于ai<i<aj<j,1i,jna_i \lt i\lt a_j<j,1\le i,j\le n
    • 一定满足a[i] < i,将a[i] >= i的删去,不参与后续匹配
    • 一定满足i < a[j]{i,j}的对数为i之前的满足a[i] < i的数量
  • 枚举j,二分查找最小满足i < a[j]的位置,总数量加上i之前的所有满足a[i] < i的数量

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int a[N];
typedef long long LL;
LL cnt;
vector<int> st;
void solve(){
int n;
cin >> n;
st.clear();
cnt = 0;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++){
if (a[i] >= i) continue;
cnt += (lower_bound(st.begin(), st.end(), a[i]) - st.begin());
st.push_back(i);
}
cout << cnt << endl;
}
int main(){
int _;
cin >> _;
while(_--){
solve();
}
return 0;
}
暂无评论

发送评论 编辑评论


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