Problem A. Grammy Wants to Earn Big Money
- 题意：今天是星期天，请计算之后的n天里，有多少天是星期一到星期五的
- 开局太急直接/7*5+余数就交了，WA了一发，没有考虑余数=6的情况
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
n--;
int ans = (n/7)*5+min(5,n%7);
cout<<ans<<"\n";
return 0;
}Problem C. Terrible Additive Number Theory Problem
- 数学计算，打表得到是个结论题
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
const int maxn = 1e5+10;
int main(){
LL x; cin>>x;
if(x<2431)cout<<0<<"\n";
else cout<<1<<"\n";
return 0;
}Problem D. Interstellar
- 题意：n个点，每个点只能往比他大的点走，代价是(j-i)^3*a[i]，求1号点走到n号点的最小代价
- 不难想到暴力dp，f[i]表示1号点到i号点的最小代价，转移就是枚举1~(i-1)所有的点，更新最小代价即可。
- 再考虑优化，因为100^3肯定大于数据1e6的范围，所以每次不需要从1开始枚举，直接从i-200左右开始枚举即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
const int maxn = 1e5+10;
LL a[maxn], f[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//cout<<pow(50,3);
int n; cin>>n;
for(LL i = 1; i <= n; i++)cin>>a[i];
f[1] = 0;
for(LL i = 2; i <= n; i++){
//f[i] = f[i-1]+a[i];
f[i]=1e18;
for(LL j = max(i-200,1LL); j <= i-1; j++){
f[i] = min(f[i], (LL)(f[j]+(i-j)*(i-j)*(i-j)*a[i]));
}
//f[i] = min(f[i], (i-1)*(i-1)*(i-1)*a[i]);
}
cout<<f[n];
return 0;
}Problem E. Recharge Cycle
- 题意：4个技能，每个技能需要消耗专属的ai点蓝，用完后会分别给四个技能补充ci点蓝，求能否无限放技能。
- 开始想复杂了，以为可以组合使用技能给所有技能回蓝，所以搜索所有的情况并且特判。
- 重新读题后发现，因为每4组用的技能都不一样，所以只要简单的把ci加起来判断一下够不够ai就行。
// //T5
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const double pi = acos(-1);
// const int maxn = 1e5+10;
// int c[10], a[10][10];
// int z[10], zz[10], ans=0;
// void dfs(int cur){
// if(ans)return ;
// if(cur==5){
// int ok = 1;
// for(int i = 1; i <= 4; i++){
// if(z[i]==1){
// if(zz[i]<c[i])ok = 0;
// }else{
// if(zz[i]==0)ok = 0;
// }
// }
// if(ok==1){
// ans = 1;
// }
// return ;
// }
// z[cur] = 1;
// for(int i = 1; i <= 4; i++)zz[i]+=a[cur][i];
// dfs(cur+1);
// z[cur] = 0;
// for(int i = 1; i <= 4; i++)zz[i]-=a[cur][i];
// dfs(cur+1);
// }
// int main(){
// for(int i = 1; i <= 4; i++)cin>>c[i];
// for(int i = 1; i <= 4; i++){
// for(int j = 1; j <= 4; j++){
// cin>>a[i][j];
// }
// }
// dfs(1);
// if(ans==1)cout<<"Yes\n";
// else cout<<"No\n";
// return 0;
// }
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
const int maxn = 1e5+10;
int c[10], a[10][10], cc[10];
int main(){
for(int i = 1; i <= 4; i++)cin>>c[i];
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
cin>>a[i][j];
cc[j] += a[i][j];
}
}
int ok = 1;
for(int i = 1; i <= 4; i++){
if(cc[i]<c[i])ok = 0;
}
if(ok==1)cout<<"Yes\n";
else cout<<"No\n";
return 0;
}Problem H. Minimum Edit Distance
- 题意：给出两个字符串，每次操作允许增删改，求构造一个字符串，让两串通过最少操作次数都等于这个串。
- 开始想复杂了，先是想到暴力所有的可行串然后每次dp编辑距离，更新最小值。发现会超时开始找规律，考虑最长公共子序列，发现有反例。
- 想到两个串可能就是一个串直接变成另一个串是最小的代价，直接输出就行。
// // //T8
// // #include<bits/stdc++.h>
// // using namespace std;
// // typedef long long LL;
// // const double pi = acos(-1);
// // const int maxn = 1010;
// // int f[maxn][maxn];
// // int main(){
// // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// // string s, t; cin>>s>>t;
// // int n = s.size(), m = s.size();
// // s = "0"+s, t = "0"+t;
// // for(int i = 1; i <= n; i++)f[i][0] = i;
// // for(int i = 1; i <= m; i++)f[0][i] = i;
// // for(int i = 1; i <= n; i++){
// // for(int j = 1; j <= m; j++){
// // f[i][j] = min(f[i-1][j]+1, f[i][j-1]+1);
// // if(s[i]==t[j])f[i][j] = min(f[i][j],f[i-1][j-1]);
// // else f[i][j] = min(f[i][j], f[i-1][j-1]+1);
// // }
// // }
// // cout<<f[n][m]<<"\n";
// // return 0;
// // }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const double pi = acos(-1);
// const int maxn = 1010;
// int f[maxn][maxn];
// int pp[maxn][maxn];
// string s, t;
// void Print(int i, int j){
// if(i==0||j==0)return ;
// if(pp[i][j]==0){
// Print(i-1,j-1);
// cout<<s[i-1];
// }else if(pp[i][j]==1){
// Print(i-1,j);
// }else{
// Print(i,j-1);
// }
// }
// int main(){
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// cin>>s>>t;
// int n = s.size(), m = t.size();
// //string d="";
// for(int i = 1; i <= n; i++){
// for(int j = 1; j<= m; j++){
// // if(s[i]==t[j])f[i+1][j+1] = f[i][j]+1;
// // else f[i+1][j+1] = max(f[i][j+1],f[i+1][j]);
// if(s[i-1]==t[j-1])f[i][j]=f[i-1][j-1]+1, pp[i][j]=0;
// else if(f[i-1][j]>=f[i][j-1])f[i][j]=f[i-1][j], pp[i][j]=1;
// else f[i][j]=f[i][j-1], pp[i][j]=-1;
// }
// }
// cout<<f[n][m]<<"\n";
// Print(n,m);;
// return 0;
// }
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
const int maxn = 1e5+10;
int main(){
string s, t; cin>>s>>t;
cout<<t<<"\n";
return 0;
}Problem J. Mountain
- 题意：1块钱可以走a步，b块钱可以走c步，初始一共有s块钱，求最多可以走几步。
- 直接分类讨论所有情况即可，因为规则是最后剩下的一块钱也可以走c步骤，所以尽可能把这个用上会更加划算。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
const int maxn = 1e5+10;
int main(){
int T; cin>>T;
while(T--){
LL a, b, c, s; cin>>a>>b>>c>>s;
LL x = max(a*s, (s-1)*a+c);
if(s%b==0){
x = max(x, s/b*c);
x = max(x, (s/b-1)*c+(b-1)*a+c);
}
else {
x = max(x, (s/b+1)*c);
x = max(x, s/b*c+(s%b)*a);
x = max(x, s/b*c+(s%b-1)*a+c);
}
cout<<x<<"\n";
}
return 0;
}Problem M. A Chinese Idiom
- 题意：一个半径为R1的球，往内半径距离d形成一个球壳，另一个半径为R2的球，求往内多少可以让两个球壳的体积相同。
- 直接推公式即可。
#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int main(){
int T; cin>>T;
while(T--){
int r1, r2, d; cin>>r1>>r2>>d;
double a = 4/3*pi*r1*r1*r1-4/3*pi*(r1-d)*(r1-d)*(r1-d);
double b = a-4/3*pi*pow(r2,3);
b = -b;
b /= (4/3*pi);;
double ans = r2-pow(b,1.0/3);
printf("%.10lf\n",ans);
}
return 0;
}附：
Tree Game
- 题意：如果一个黑色的点，周围有一个白的点并且不足两个黑点，那么他会自卑。
给出一棵树，初始n个白色的点，现在需要把k个点染成黑的，求染色方案使得最多只有1个点自卑。 - 不难想到，对于一颗都是黑的子树，有且仅有可能是根节点会自卑。对于一颗都是白的子树，他们肯定都不会自卑。所以开始直接暴力去找大小为k的子树作为分界点，如果不存在就-1。
- 实际上并没有-1的情况，只需要找到一个叶子（度为1的）节点作为根，往下dfs随便跑k个节点即可。对于链上的点，父亲和儿子都是黑的，所以不会自卑，最多跑到最后一个位置不能继续往下了，只有父亲是黑的，儿子又刚好是白的，可能会自卑一下，其他都不会。
Problem I. Rounding Master
- 题意：给出n和k，一个初始值为1，经过k轮，每轮*q然后四舍五入，最后要求大于等于n，求q的最小值。
- 开始一直在推除法公式，最后正解是二分答案，直接暴力二分q的值，每次跑k轮判断是否成立即可，k的数据那么大，没想到能跑的出来（，，实际上推导一下，哪怕q只有2，跑个60轮就是2^60，已经快爆int了，后面是指数级的，所以实际上k的大小是远远小于n的。