牛客小白月赛65（C，D，E，F）
果然人是不能太得意，上一次打的还没有那么惨，沾沾自喜，结果这一次就翻车了，o(╥﹏╥)o
C
这个题我先前好像看过类似的，不过具体的忘记了
这个题我有两种写法
第一种是用set，第二种是用数组，用一个类似链表的东西（好像是的吧）
set要找一个x的前一个，我们可以用set自带的lower_bound,由于题目告诉我们找x的前一个时，x一定在数组，那么这个函数返回的一定是x的位置，我们可以使用prev来输出前一个位置的数
数组是我们每一个数都需要记录下他的左边的数和右边的数
每次删除一个数，他左边的右端点会改变成这个数的右边，他右边的左端点会改变成这个数的左边
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn=1e6+10;
int n,k;
int l[maxn],r[maxn];
int main ()
{
ios;
set<int>ans;
cin>>n>>k;
for (int i=0;i<=n;i++)
{
// ans.insert(i);注释的是第一种写法
l[i]=i-1,r[i]=i+1;//第二种写法
}
while (k--)
{
int op,x;
cin>>op>>x;
if (op==1)
{
int ll=l[x],rr=r[x];
r[ll]=rr;//改变左右端点
l[rr]=ll;
//ans.erase(x);
}
else
{
cout<<l[x]<<'\n';
//auto pos=ans.lower_bound(x);
// cout<<*(prev(pos))<<'\n';
}
}
return 0;
}
D
这是一个博弈论的问题（显而易见）
我一直不太喜欢博弈论（其实是我太菜了，感觉每一次在做这一类的题都感觉是在猜谜语）
我们知道一共只有两种取石子的方式
1, 第一堆取1个，第二堆取2个
2, 第一堆取2个，第二堆取1个
x,y(x是较小的那个，y是较大的那一个)
如果x=1,只有y=1的时候是必败点，其他的都是必胜点，牛牛第一步把x变成0，下一步牛妹不可以操作了
如果x=2,所以的都是必胜点，牛牛第一步把x变成0，下一步牛妹不可以操作了
如果x=3,那么这个一定是两步，（牛牛第一步选1，牛妹下一步选2，那么轮到牛牛的时候这一堆为0，牛牛败）
如果x%3=0,每一轮，牛牛选1，牛妹选2，每一个回合，都会减3个（这个小的堆会先到0,我们只需要判断哪个较小的堆），必败
如果x=y&&x%3=1,那么最后一定会变成1,1的情况（必败），也是必败
其他的都是必胜点
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout<<"niuniu\n"
#define no cout<<"niumei\n"
int t,a,b;
void solve()
{
cin>>a>>b;
int x=min(a,b),y=max(a,b);
if (x==1&&y==1)
{
no;
}
else if (x<=2)
{
yes;
}
else if (x%3==0)
{
no;
}
else if (x==y&&x%3==1)
{
no;
}
else yes;
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
E
这个题大意是给你n个数（1到n),我们要构造一个数组，ai-aj=2^x,(i<j),我们需要出现这样的对数只要k个，如果可以构造成功，就输出那一个数组，否则则输出-1
对于x,他前面的1到x-1一定可以组成log2(x-1)+1对数，把这个记录下来
具体实现看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,k;
int main ()
{
cin>>n>>k;
vector<int>f(n+1);//f[i]比i小的数和i的差是2的x次方
int now=1;
for(int i=2;i<=n;i++)//1的时候是没有可能比1小的数还满足条件
{
f[i]=f[i-1];
if(i-1==now) //上一个刚好是2的x次方，那么这一个就多出了一个，可以慢慢体会
{
f[i]++;
now*=2;
}
}
vector<int>l,r;
for (int i=n;i>=1;i--)
{
if (k>=f[i])//如果i的贡献小于k,那么我们就让i和j(比i小的数)的f[i]对数满足条件
{
l.push_back(i);
k-=f[i];
}
else //否则，把i放在后面，这样i的后面都是比i大的数（r这样原本是从小到大，我后面会翻转，就变成了从大到小，这样这个r里面的每一个数都不会存在一个数和它配对满足是2的x次方的条件
{
r.push_back(i);
}
}
if (k)
{
cout<<-1<<'\n';
return 0;
}
reverse(r.begin(),r.end());
for (auto x:l)
{
cout<<x<<" ";
}
for (auto x:r)
{
cout<<x<<" ";
}
return 0;
}
F
这里我是看了大佬的题解，下面是我自己的理解
用了一个piar<int,int>来存单开和双开的复习时间
我们从第一个开始dfs，每次搜索，都会一个更新，（不过这个建图是反着的，我的理解，u到v是，要预先v,后面才能预先v,我觉得这样的话，可能是一个树的形状，一个点可以到达多个点，而不是多个点到达一个点）
到达x的时候，x.first代表单开所用的时间，x.second代表双开所用的时间
下一个搜索到y
我们需要对ans进行更新，我这里是add函数
pair <int,int>add(pair<int,int>x,pair<int,int>y)
{
if (x.first>y.first)//我们要让双开尽量的多，对于两个状态，我们要让单开小的尽量接近单开大的，这样可能我们就会双开会增加小的那一个单开
{
swap(x,y);//保证x是需要改变的那个
}
int cha=min((y.first-x.first)/2,x.second);//让小的单开尽量接近大的单开，不过也要有那么多双开可以转换
x.first+=cha*2;//把小的单开变大，从双开转移到单开，那么单开就会增大，双开就会减少
y.second-=cha;
pair<int,int>res;//新的状态
res.second=x.first+x.second+y.second;//原来的两个双开，加上改变小的单开后，这一定是那个小的单开（一定是原来小的单开改变后的值）的数量
res.first=y.first-x.first;//小的单开用完了，最后的单开只剩下那个大的单开还没有到双开的数量
return res;
}
搜索是从1开始，题目中说道1是最难的，所以1一定是根节点
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+10;
int n;
vector<int>e[maxn];
int c[maxn];
pair <int,int>add(pair<int,int>x,pair<int,int>y)
{
if (x.first>y.first)
{
swap(x,y);
}
int cha=min((y.first-x.first)/2,x.second);
x.first+=cha*2;
y.second-=cha;
pair<int,int>res;
res.second=x.first+x.second+y.second;
res.first=y.first-x.first;
return res;
}
pair<int,int> dfs(int u)
{
pair<int,int>ans;
ans.first=0,ans.second=0;
for (int i=0;i<e[u].size();i++)
{
ans=add(ans,dfs(e[u][i]));
}
ans.first+=c[u];
return ans;
}
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>c[i];
}
for (int i=2;i<=n;i++)
{
int u;
cin>>u;
e[u].push_back(i);
}
pair<int,int>ans=dfs(1);
cout<<(ans.first+ans.second)<<'\n';
return 0;
}