12.12基础个人赛(补题)
B题Brightness Begins
题意：
有n个电灯泡，在初始时全都是亮着的，接下来，每次操作i可以改变编号为i的倍数的灯泡的状态（开变关，关变开）。现在有k个灯泡是亮着的，问需要的最少灯泡数n是多少。
思路：
首先分析条件，操作i可以改变编号为i的倍数的灯泡，因此当第i个灯泡有奇数个数时，该灯泡会关闭（初始是1），偶数则打开。
因此，问题更新为求第k个数的非完全平方数是多少，这里结合一个数学理论:1~n中有|sqrt(n)|个完全平方数。即n-sqrt(n)=k，
所以通过打表可以得到最终的公式n=k+sqrt(k)
code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10,inf=INT_MAX;
int t;
//注意数据范围
long long k;
int main(){
ios::sync_with_stdio(0),cin.tie(0);cout.tie(0);
cin >>t;
while(t--)
{
cin >>k;
cout <<k+(long long)(sqrtl(k)+0.5)<<"\n";
}
return 0;
}
E题Green and Black Tea
题意：
有n包茶，a包是绿茶（G），b包是黑茶（B），对茶进行组合排序，使得连续相同的茶不能超过k包。
注:每包茶只能使用一次。
思路：
本题属于构建模拟题,首先可以得知,要使茶包的连续个数最小,肯定要使用最小的茶包个数b,对另一茶包a进行分割,分割次数越多,区间长度越小,所以每次数据能达到的最优茶包长度为a/(b+1)，且因为茶包不能舍弃,所以最终区间长度d为ceil(a/(b+1))。
由此可得,当d的长度大于k时,排列无法构建,而符合时,即可开始构建序列。
code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10,inf=INT_MAX;
int n,k,a,b;
//定义字符,避免写重复代码
char x='G',y='B';
int main(){
ios::sync_with_stdio(0),cin.tie(0);cout.tie(0);
cin >>n>>k>>a>>b;
if (a<b)
{
//swap():交换括号内的两个值
swap(a,b);
swap(x,y);
}
//假设每次取1个b进行阻隔,最多会有b+1个区间,相除后向上取整即可得到a每段区间最大的值
int res=ceil(1.0*a/(b+1));
//当每段的值超过k时,此时无法构建字符
if (res>k)cout <<"NO\n";
else
{
//取a以最大个数排列的次数
int ans=a%(b+1);
//ans=0,可以都以最大个数排完
int tmp=ans>0?1:0;
while(ans--)
{
//每次跑,a的长度减res
for (int i=1;i<=res;i++)cout <<x;
a-=res;
//以1个b进行阻隔
if (b)
{
cout <<y;
b--;
}
}
//如果ans有值,将接下来的排列个数减1
res-=tmp;
//将a和b剩余的值跑完
while(a>0 || b>0)
{
for (int i=1;i<=res;i++)cout <<x;
a-=res;
if (b)
{
cout <<y;
b--;
}
}
cout <<"\n";
}
return 0;
}
G题AGAGA XOOORRR
题意：
数组a中有n个数,每次操作可以将两个相邻的数异或,求能否将数组中的值都变为相同的值,且数组个数至少要有两个。
思路：
本题考验对异或的理解,首先异或的值为,同为0,不同为1,由此可以得到当对整个数组进行异或和后,如果数组为0,,则必然存在两个值是相同的,但还有一种情况,即如果相同的值为奇数个,此时异或和值也不为0,但依然符合条件,所以需要重新遍历数组,每当值与异或的最终值相同时,保留该值,重新开始记数。
code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10,inf=INT_MAX;
int t,n;
int a[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0);cout.tie(0);
cin >>t;
while(t--)
{
int ans=0;
cin >>n;
for (int i=1;i<=n;i++)
{
cin >>a[i];
ans^=a[i];
}
//当所有数异或后为0时,此时肯定存在两个数相同
if (!ans)cout <<"YES\n";
else
{
//当相同个数为奇数时,最后异或出来的结果也不为0
//因此对状态重新计数
int res=0,cnt=0;
for (int i=1;i<=n;i++)
{
res^=a[i];
//当异或和等于最终异或值时
if (res==ans)
{
//奇数相加
cnt++;
res=0;
}
}
//当个数大于等于2时,说明符合条件
if (cnt>=2)cout <<"YES\n";
else cout <<"NO\n";
}
}
return 0;
}
H题Passing the Message
题意：
有t组数据,给你n个孩子的身高的数组a,找每个孩子的左信使和右信使的下标。
左信使的条件:
- a[i]不能越过比它高的孩子去看其他人
- 信使是a[i]左边能看到的人里最高的
- 找不到信使则输出0
右信使与左信使条件相同,只是左右互换
思路：
本题可以使用单调栈，通过维护数组的形式找出每个单边的值，跑两遍数组就可以解决了。
code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10,inf=INT_MAX;
struct Index{
int num,id;
};
int t,n;
int a[N],l[N],r[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0);cout.tie(0);
cin >>t;
for (int text=1;text<=t;text++)
{
//清空数组
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
cin >>n;
for (int i=1;i<=n;i++)cin >>a[i];
stack<Index>q;
//从左到右,维护从大到小的单调栈,找出左信使
for (int i=1;i<=n;i++)
{
Index now;
//在栈空之前,找出比它矮的人
while(q.size())
{
now=q.top();
if (now.num>a[i])break;
//越往前数值将会越大
l[i]=now.id;
q.pop();
}
//每次存入的点都必然是比前一个点小的
q.push({a[i],i});
}
//清空栈
while(q.size())q.pop();
//从右到左,维护从大到小的单调栈,找出右信使
for (int i=n;i>=1;i--)
{
Index now;
//以下同理
while(q.size())
{
now=q.top();
if (now.num>a[i])break;
r[i]=now.id;
q.pop();
}
q.push({a[i],i});
}
cout <<"Case "<<text<<":\n";
for (int i=1;i<=n;i++)cout <<l[i]<<' '<<r[i]<<"\n";
}
return 0;
}
H题Stones
题意：
T和A轮流进行取石子的游戏，有n个石子和k个取出个数,每次拿取都要从k个拿取个数中选择一种进行拿取。
注:拿取个数时从小到大排的。
思路：
本题属于博弈+dp，最重要的就是推转移方程,状态方程怎么来的,已经在代码注释中给出,不做过多描述。
code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10,inf=INT_MAX;
long long n,k;
long long a[N],dp[N];
/*
条件:
T和A轮流拿取a[i]的石头
状态:
dp[i]:石头数为i时,能拿取的最大值
T先取数量变为i-a[j]
A后取,此时A能取到的最大为dp[i-a[j]]
所以游戏进行一轮时,T得到的收益为i-[j]+dp[i-a[j]]+a[j]
即i-dp[i-a[j]]
*/
int main(){
ios::sync_with_stdio(0),cin.tie(0);cout.tie(0);
cin >>n>>k;
for (int i=1;i<=k;i++)cin >>a[i];
//先手能取的最大值
for (int i=1;i<=n;i++)
{
for (int j=1;j<=k;j++)
{
if (i<a[j])break;
dp[i]=max(dp[i],i-dp[i-a[j]]);
}
}
cout <<dp[n]<<"\n";
return 0;
}
