Educational Codeforces Round 137 (Rated for Div. 2)(A~D)
本文最后更新于 847 天前,其中的信息可能已经有所发展或是发生改变。

A. Password


Origional Link

题目大意

  • 给定 nn090\sim 9 之间不能使用的数字,保证剩余的数大于 22
  • 任意两个数子组合,每个数字可使用两次,组成一个四位密码。
  • 求在剩余的可选数字中,能组成的密码数量。

思想

  • 签到题。
  • 任意两个数字可组成的密码数量固定为 66
  • 则总数量为剩余数字中的两两组合的数量乘 66
  • 即设剩余的数的数量为 x=10nx = 10 - n,总密码数为 x×(x1)2\frac{x\times (x - 1)}{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);
void solve(){
int n; cin >> n;
for(int i = 0; i < n; i ++){
int x; cin >> x;
}
n = 10 - n;
cout << 6 * n * (n - 1) / 2 << endl;
}
int main(){
IOS;
int _ = 1;
cin >> _;
while(_ --){
solve();
}
return 0;
}

B. Permutation Value


Origional Link

题目大意

  • 给定一个长度为 nn 的排列。
  • 定义其一个连续的子序列也为一种排列。
  • 构造一个排列使得满足上述条件的子序列的数量最少。
  • 输出任意满足条件的序列即可。

思想

  • 构造。
  • 只需要将 11 提到最前面,然后倒序输出剩余数即可。

#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;
cout << 1 << ' ';
for(int i = n; i >= 2; i --) cout << i << ' ';
cout << endl;
}
int main(){
IOS;
int _ = 1;
cin >> _;
while(_ --){
solve();
}
return 0;
}

C. Save the Magazines


Origional Link

题目大意

  • 给定一个长为 nn 且只包含 0,10,1 的字符串 ss11 表示 aia_i 有盖,反之则无。
  • 接下来给出 aia_i 个箱子内部所的含杂志数量,雨会淋湿没有盖盖子的箱子里的所有杂志。
  • 每个有盖子的箱子仅可操作一次,将盖子移动到 ai1a_i-1 上。
  • 求最佳方案下最大能保护的杂志数量。

思想

  • 贪心。
  • 对于某个连续的 11 的区间 (i,j)(i,j),我们可以移动的盖子范围在 ai1ja_{i-1}\sim j,那么在区间 (i1,j)(i-1,j) 中必然存在一个箱子没有盖子。
  • 故需要将区间 (i1,j)(i-1,j) 中所含杂志数量最少的箱子的盖子移除,提供给没有盖子的箱子。

代码

#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; cin >> n;
string s; cin >> s;
for(int i = 0; i < n; i ++) cin >> a[i];
LL sum = 0;
int pos = s.find("1");
// cout << pos << endl;
if(pos == -1){
cout << 0 << endl;
return ;
}
for(int i = pos; i < n; i ++){
if(s[i] == '1'){
int cnt = 1;
int t = a[i];
sum += t;
for(int j = i + 1; j < n; j ++){
if(s[j] == '0') break;
else cnt ++;
t = min(t, a[j]);
sum += a[j];
}
if(i - 1 >= 0){
int p = a[i - 1];
if(p > t) sum += p - t;
}
i += cnt - 1;
}
}
cout << sum << endl;
}
int main(){
IOS;
int _ = 1;
cin >> _;
while(_ --){
solve();
}
return 0;
}

D. Problem with Random Tests


Origional Link

题目大意

  • 给定一个只包含 0,10,1 的序列。
  • 可以通过一个字串与其按位“或”运算得到一个新的 0,10,1 序列。
  • 求如何操作使得该序列的二进制数最大。

思想

  • 贪心,枚举。
  • 该题的数据具有随机性。
  • 贪心发现,两个字符一定是从某一点位置开始,其中一个字符右移几个位置,然后或运算。
  • 那么我们需要从第一个出现的 00 的位置开始“或”运算,然后暴力匹配即可。

代码

#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; cin >> n;
string s; cin >> s;
s = " " + s;
int pos = 1;
bool flag = false;
for(int i = 1; i <= n ; i ++ ){
if(s[i] == '1') flag = true;
if(flag && s[i] == '0'){
pos = i;
break;
}
}
int st = pos;
int len = n - pos + 1;
string ans = s;
for(int i = 1; i < st ; i ++ ){
for(int j = i + len - 1; j <= n ; j ++ ){
string temp = s;
for(int k = n - len + 1, u = i ; u <= j ; u ++ , k ++ )
if(s[u] == '1') temp[k] = '1';
ans = max(ans, temp);
}
}
flag = false;
for(int i = 1; i <= n ; i ++ ){
if(ans[i] == '1') flag = true;
if(flag) cout << ans[i];
}
if(!flag) cout << 0;
cout << endl;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
暂无评论

发送评论 编辑评论


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