A 牛牛去购物
循环枚举买多少个篮球,剩下的钱能买多少足球就买多少即可,时间复杂度 。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,a,b;
cin>>n>>a>>b;
int ans=n;
for(int i=0;i*a<=n;i++){
ans=min(ans,(n-i*a)%b);
}
cout<<ans;
return 0;
}
B 牛牛写情书
定义一个字符串 ,遍历 ,如果当前位 ,就把当前位加到 中,这样就获得了原始牛牛的情书,之后循环 枚举起点, 检验 与 是否相等即可,时间复杂度 。
#include <bits/stdc++.h>
using namespace std;
int n,m;
string s,k,p;
bool check(int x){
for(int i=x;i<x+m;i++){
if(p[i]!=k[i-x]) return false;
}
return true;
}
int main(){
cin>>n>>m>>s>>k;
for(auto i:s){
if(i>='a'&&i<='z') p+=i;
}
for(int i=0;i+m<=p.length();i++){
if(check(i)){
cout<<"YES";
return 0;
}
}
cout<<"NO";
return 0;
}
C 牛牛排队伍
题目相当于有一个 到 的序列 ,存在删除操作,求 。对于三个数 ,删除 后对该序列的影响本质其实就是 的前一项变成了 , 的后一项变成了 ,其他相邻的元素前后对应关系都不变,所以可以用两个数组表示元素的前一项以及后一项是多少,初始化 ,删除 的操作可以等价于 ,这样删除操作时间复杂度变为 ,查询也只需要输出 即可,查询时间复杂度也是 ,整体时间复杂度为 。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,op,x;
int qian[N],hou[N];
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++){
qian[i]=i-1;
hou[i]=i+1;
}
while(k--){
cin>>op>>x;
if(op==1){
qian[hou[x]]=qian[x];
hou[qian[x]]=hou[x];
}else{
cout<<qian[x]<<'\n';
}
}
return 0;
}
D 牛牛取石子
除了 的特例牛牛会输掉以外,只要 ,牛牛都可以把少的那堆直接拿完导致牛妹拿不了而赢得比赛。除此之外观察取石子的 种方案可知,不管牛牛选择哪种方案,牛妹都可以拿另一种使得 两堆的石子数量同时 ,因此只要 中较小的那个数是 的倍数 ,牛妹一定能把那一堆拿到 个使得牛牛无法行动,而对于 的情况,牛妹也一定可以最后把两堆石子拿到都只剩 个从而赢得比赛。
#include <bits/stdc++.h>
using namespace std;
void solve(){
long long n,m;
cin>>n>>m;
if(n>m) swap(n,m);
if(n==1&&m==1) cout<<"niumei\n";
else if(n<3) cout<<"niuniu\n";
else if(n%3==0) cout<<"niumei\n";
else if(n==m&&n%3==1) cout<<"niumei\n";
else cout<<"niuniu\n";
}
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int _=1;
cin>>_;
for(int i=1;i<=_;i++){
solve();
}
return 0;
}
E 牛牛做构造
对于任意一个已经构建好的长度为 的数组,在数组开头插入一个 ,都会新增 个满足题意的二元组 ,
x | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 |
先 预处理出每一个 放在 的排列开头能新增多少, 之后从 到 每个数考虑贡献,对于每次考虑的数 : 假如 ,那就把这个 放在接下来所有数的开头,然后令 ,代表这个数给整个数组贡献了 的价值。 假如 ,那就把这个 放在接下来所有数的后面,代表这个数给整个数组贡献了 的价值。 所有数都处理完如果 ,代表不存在解,输出 。 所有数都处理完如果 ,只需要新建两个数组 ,对于遍历过程中 时,把 放进 数组,否则把 放进 数组,顺序输出 数组,逆序输出 数组即可。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,f[N];
int k;
vector<int>a,b;
int main(){
cin>>n>>k;
int now=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1];
if(i-1==now) {
f[i]++;
now*=2;
}
}
for(int i=n;i>=1;i--){
if(k>=f[i]) {
a.push_back(i);
k-=f[i];
}else b.push_back(i);
}
if(k) cout<<"-1";
else {
reverse(b.begin(),b.end());
for (auto i:a) cout << i << " ";
for (auto i:b) cout << i << " ";
}
return 0;
}
F 牛牛的考试
题意可以简化成给定一颗根节点为 的树,每次可以花费 的时间让任意两个或一个叶子结点的值都 ,如果一个结点的值 ,那么这个结点就消失了,如果一个结点的所有子节点都消失了,这个结点就变成了叶子结点,直到所有结点都消失的最小总时间。 用dfs自底向上遍历这棵树,对于每个结点,用一个pair<int,int>来表示这个结点的状态,第一维是以这个结点为子树的最大双开时间,第二维是以这个结点为子树的对应单开时间。
假如现在有一颗这样的树,从1号点开始dfs遍历时先遍历到3,3的对应状态是 ,4的对应状态是 ,5的对应状态是 ,因为它们都是单独的一个结点,单看的话都只能单开学习,这三个点都遍历完dfs回到1号点,1号点刚开始是 ,遇到3号的数据汇上来变成 ,然后遇到4号点的数据 ,相当于把3号点和4号点各自单开的3分钟拿来双开,之后遇到5号点的数据 ,,这里把 变成 的原因在于,新汇上来的结点的单开时间>当前单开时间,那么从贪心的角度来看,应该通过减少当前的双开时间,让当前的单开时间尽可能接近新汇上来结点的单开时间,这样最后结合起来尽可能使单开时间=0,以达到能双开就双开的最优解。最后 再加上自身的1分钟变成 ,返回当前状态。 因此只需要dfs遍历这棵树,每次把子节点的状态合并,pair<int,int>的第二维再加上当前结点的时间,一层层向上返回状态即可。因为每次维护的单开时间尽量去合并,保证单开的时间是最少的,一直在双开,所以时间总花费最小,时间复杂度 。
#include <bits/stdc++.h>
#define int long long
const int N=1e6+10;
using namespace std;
typedef pair<int, int> PII;
int n,a[N];
vector<int>v[N];
PII add(PII x,PII y){
if(x.second>y.second) swap(x,y);
int cha=min((y.second-x.second)/2,x.first);
x.first-=cha;
x.second+=2*cha;
x.first+=x.second;
x.second=y.second-x.second;
x.first+=y.first;
return x;
}
PII dfs(int now){
PII ans=PII(0,0);
for(auto i:v[now]){
PII v=dfs(i);
ans=add(ans,v);
}
ans.second+=a[now];
return ans;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=2;i<=n;i++){
int x;
cin>>x;
v[x].push_back(i);
}
PII ans= dfs(1);
cout<<ans.first+ans.second;
return 0;
}
全部评论
(2) 回帖