欢迎来到我的算法小屋
前言
| Task Name | |
| A | Children and Candies (ABC Edit) |
| B | Unhappy Hacking (ABC Edit) |
| C | Be Together |
| D | Unbalanced |
A
1）题目描述
2）题目分析
水题
3）参考代码(C++)
#include <bits/stdc++.h>
using namespace std;
/*宏定义*/
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.141592653589793238462
#define N 100010
#define mem(a,b) memset(a,b,sizeof(a))
#define x first
#define y second
typedef long long ll;
const double eps = 1e-8;
int t,n;
/*
* 常用函数
*/
//最大公约数
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
//最小公倍数
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
//lowbit运算
int lowbit(int x) {return x & (-x);}
//快速幂 a的b次，取mod
ll qmi(ll a,ll b,ll mod) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
//组合数学的初始化阶乘数组
ll fact[N];
void init_fact(){
fact[0] = 1;
for(int i = 1; i < N;i++){
fact[i] = 1ll*fact[i-1]*i % MOD;
}
}
//计算乘法逆元 —— 公式
ll inverse(ll a){
return qmi(a,MOD-2,MOD);
}
//计算组合数 —— 组合数的公式，分式部分用乘法逆元表示
ll C(ll n,ll m){
return(1ll * fact[n] * inverse(fact[m]) % MOD)* inverse(fact[n-m])%MOD;
}
//cin 、 cout 优化
void run(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
//快读
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int main(){
run();
int n;
cin >> n;
cout << (1+n)*n/2 ;
return 0;
}
4) 总结反思
暂无
B
1)题目描述
题目大意是，依次输入字符，假如是0和1，就从左到右的链接字符，假如输入的是B，就消去一个字符。
2)题目分析
常规模拟，注意能够消去一个字符的前提是有字符，也就是说，假如有一个指针在这个流程中，那么指针的值至少是等于1的时候，才能触发B的消去
3)参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
/*宏定义*/
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.141592653589793238462
#define N 15
#define mem(a,b) memset(a,b,sizeof(a))
#define x first
#define y second
typedef long long ll;
const double eps = 1e-8;
int t,n;
char ch[N],ans[N];
/*
* 常用函数
*/
//最大公约数
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
//最小公倍数
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
//lowbit运算
int lowbit(int x) {return x & (-x);}
//快速幂 a的b次，取mod
ll qmi(ll a,ll b,ll mod) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
//组合数学的初始化阶乘数组
ll fact[N];
void init_fact(){
fact[0] = 1;
for(int i = 1; i < N;i++){
fact[i] = 1ll*fact[i-1]*i % MOD;
}
}
//计算乘法逆元 —— 公式
ll inverse(ll a){
return qmi(a,MOD-2,MOD);
}
//计算组合数 —— 组合数的公式，分式部分用乘法逆元表示
ll C(ll n,ll m){
return(1ll * fact[n] * inverse(fact[m]) % MOD)* inverse(fact[n-m])%MOD;
}
//cin 、 cout 优化
void run(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
//快读
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int main(){
run();
cin >> ch;
// cout << ch;
int len = strlen(ch);
// cout << "len = " <<len <<'\n';
int idx = 0;
for(int i = 0;i < len;i++){
if(ch[i] == '0' || ch[i] == '1'){
ans[idx] = ch[i];
idx ++;
}else{
if(ch[i] == 'B' && idx != 0) idx --;
// printf("strlen(ans)=%d\n",strlen(ans));
else idx = 0;
}
}
// cout << ans;
for(int i = 0;i < idx;i++) cout << ans[i];
return 0;
}
4)总结反思
C
1)题目描述
找到一个数，这个数能够在和提供的所有数字做平方差之后的总和能够最小
2)题目分析
核心来说，就是这个数，一定是在提供的数字的形成的区间中的，要么是平均数，要么中位数，反正是脱离不了这n个数形成的区间，这个数据范围也小，直接暴力吧。
3)参考代码(C++版本)
#include <bits/stdc++.h>
using namespace std;
/*宏定义*/
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.141592653589793238462
#define N 110
#define mem(a,b) memset(a,b,sizeof(a))
#define x first
#define y second
typedef long long ll;
const double eps = 1e-8;
int a[N];
/*
* 常用函数
*/
//最大公约数
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
//最小公倍数
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
//lowbit运算
int lowbit(int x) {return x & (-x);}
//快速幂 a的b次，取mod
ll qmi(ll a,ll b,ll mod) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
//组合数学的初始化阶乘数组
ll fact[N];
void init_fact(){
fact[0] = 1;
for(int i = 1; i < N;i++){
fact[i] = 1ll*fact[i-1]*i % MOD;
}
}
//计算乘法逆元 —— 公式
ll inverse(ll a){
return qmi(a,MOD-2,MOD);
}
//计算组合数 —— 组合数的公式，分式部分用乘法逆元表示
ll C(ll n,ll m){
return(1ll * fact[n] * inverse(fact[m]) % MOD)* inverse(fact[n-m])%MOD;
}
//cin 、 cout 优化
void run(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
//快读
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
//在最大值和最小值之间枚举
int main(){
run();
int n;
int ans = INF;
cin >> n;
for(int i = 0;i < n;i++) cin >> a[i];
sort(a,a+n);
int minn = a[0];
int maxx = a[n-1];
if(minn == maxx){
ans = 0;
cout << ans;
return 0;
}else{
for(int i = minn;i <= maxx;i++){
int tmp = 0;
for(int j = 0;j < n;j++){
tmp += (a[j]-i)*(a[j]-i);
}
ans = min(tmp,ans);
}
cout << ans;
return 0;
}
}
4)总结反思
D
1)题目描述
给定一个字符串t，当且仅当t的长度至少为2，并且t中超过一半的字母是相同的，称其为不平衡例如，voodoo和melee都是不平衡的，而noon和a都不是。
判断一个由小写字母组成的字符串s是否存在一个不平衡的（连续的）s的子串。
2)题目分析
我感觉这个题有点矛盾，或者我没有理解题意，按照题意noon也是不平衡的吧。
参考大佬的题解吧，我后续再思考一下：
AtCoder Beginner Contest 043 题解
3)参考代码(C++版本)
4)总结反思