挑战赛#8题解
2024-08-12 09:06:20
发布于:浙江
挑战赛#8题解
T1:
题目要求求出数轴上被同时涂成红色和蓝色的部分的长度。
其中[L1,R1]为蓝色 [L2,R2]为红色
纯模拟或者直接算即可
模拟代码 不用思考非常适合我:
时间复杂度
#include<bits/stdc++.h>
using namespace std;
int ar[2002],br[2002],ans,a,b,c,d;
int main(){
cin>>a>>b>>c>>d;
for(int i=a;i<b;i++){
ar[i]=1;
}for(int i=c;i<d;i++){
br[i]=1;
}for(int i=0;i<=100;i++){
if(ar[i]&&br[i])ans++;
}cout<<ans;
}
但是可以简化为什么要写模拟
计算代码:
时间复杂度
#include<bits/stdc++.h>
using namespace std;
int ans,a,b,c,d;
int main(){
cin>>a>>b>>c>>d;
ans=max(b,d)-min(a,c)-abs(c-a)-abs(d-b);
if(ans>0)cout<<ans;
else cout<<0;
}
T2
题目要求判断给定的比赛结果是否存在矛盾。
因为数据很小 所以直接枚举每一个结果即可
有句话说得好:暴力出奇迹
代码如下:
时间复杂度
#include<bits/stdc++.h>
using namespace std;
char mapp[10001][10001];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mapp[i][j];
}
}for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mapp[i][j]=='D'&&mapp[j][i]!='D'||mapp[i][j]=='W'&&mapp[j][i]!='L'||mapp[i][j]=='L'&&mapp[j][i]!='W'){
cout<<"incorrect"<<endl;
return 0;
}
}
}cout<<"correct"<<endl;
}
T3
题目要求统计字符串出现的次数。
注意第二次出现的时候要输出的是1
用STL模版中的 map 会很简单
不会STL模版可以参考Macw07大佬的帖子
代码如下:
时间复杂度
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
string a;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a;
mp[a]++;//记录字符串a出现的频率
cout<<a;
//如果出现第二次或以上,输出字符串出现次数
if(mp[a]>1)cout<<"("<<mp[a]-1<<")";
cout<<endl;
}
}
后三题和前三题完全不是一个难度的,天才出题组
T4
先说算法:动态规划+前缀和
我们设dp[i]
表示i次抛硬币时能获取的最大价值
用sumA与sumB存储钱和额外奖金的前缀和
注意奖金的前缀和,sumB[i]指计数器到i时获得的额外奖金总数
我们假设在j次抛硬币选择反面,于是我们就能得到dp[i]的转移方程如下
dp[i]=max(dp[i],dp[j]+sumA[i]-sumA[j+1]+sumB[i-j-1]);
代码如下:
时间复杂度大约
#include<bits/stdc++.h>
using namespace std;
string s;long long a[10000],b[10000],sumA[10000],sumB[10000],dp[10000],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sumA[i]=a[i]+sumA[i-1];
}for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
b[x]=y;
}for(int i=1;i<5001;i++){
sumB[i]=b[i]+sumB[i-1];
}for(int i=1;i<=n;i++){
//第i次抛硬币
dp[i]=sumA[i]+sumB[i];
for(int j=1;j<i;j++){
//在第j次抛硬币选择反面
dp[i]=max(dp[i],dp[j]+sumA[i]-sumA[j+1]+sumB[i-j-1]);
}
}cout<<dp[n];
}
T5
这道题可以通过前缀位运算和动态规划来做
定义一个dp[i][0/1(j)][k]
表示第i位的数字一开始的值(j)经过k轮后的值。
则根据定义我们可以得到转移方程为dp[i][j][k]=dp[i][j][k-1]|x(&x,^x)
取a的第i位可以通过a>>i&1实现
例如二进制10110要取第三位的1
右移三(i)位得到00101发现第三位到了第一位上
我们在&1 即00101&00001
因为&运算是都为1时取1,其余取0
发现如果第一位是1是刚好取1,是0时刚好取0
其余位因为&的1都是0,所以得数也是0
答案就是a的第i位
初始化为 dp[i][j][0]=j
因为不经过变换时当前位的数字不变
最后将dp[][][k]
数组经过位运算还原
AC代码:
时间复杂度
#include<bits/stdc++.h>
using namespace std;
int x,n,a[200001],t[200001],dp[35][3][300005];
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>t[i]>>a[i];
}for(int i=0;i<30;i++){
for(int j=0;j<2;j++){
dp[i][j][0]=j;
for(int k=1;k<=n;k++){
bool x=(a[k]>>i)&1;
if(t[k]==1)dp[i][j][k]=dp[i][j][k-1]&x;
else if(t[k]==2)dp[i][j][k]=dp[i][j][k-1]|x;
else dp[i][j][k]=dp[i][j][k-1]^x;
}
}
}for(int i=1;i<=n;i++){
int ans=0,k=x;
for(int j=0;j<30;j++){
ans+=dp[j][k&1][i]*(1<<j);
k>>=1;
}cout<<ans<<endl;
x=ans;
}
}
T6
一道和逆序对很像的题
首先先讲述逆序对怎么做,题目 逆序对
对于一个数组 3 4 2 4 5 1 我们对它进行归并排序
当有序数组合并时,如果后半段大,则逆序对的数量加上前半段当前的长度
举个例子
比如:[2 3 4][1 4 5]时 后半段第一个 1 比前半段的第一个 2 大
因为归并排序的性质,数组的前半段和后半段都是有序的
则如果后半段第一个数比前半段第一个数小,则前半段所有的数都比他大
不难发现此时[2,1],[3,1][4,1]则前半段的所有数与后半段第一个都是逆序对
则此时让ans+=前半段的长度就是逆序对的答案
逆序对代码如下:
时间复杂度
#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],ans;
int sortf(int l,int r){
int mid=(l+r)/2;
if(r-l<1)return 0;
sortf(l,mid);sortf(mid+1,r);
vector<int>v;
for(int i=l,j=mid+1;;){
if(i>mid&&j>r)break;
if(i>mid)v.push_back(a[j++]);
else if(j>r)v.push_back(a[i++]);
else{
if(a[i]>a[j]){
v.push_back(a[j++]);
ans+=mid-i+1;
}else{
v.push_back(a[i++]);
}
}
}for(int i=l,j=0;i<=r;i++,j++){
a[i]=v[j];
}return 0;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}sortf(1,n);
cout<<ans;
}
回到这题来看,不难看出也是要求求出逆序对的数量,但是不同的是对于相同颜色的两个球不需要增加ans,那么我们考虑用一个cnt[]数组记录颜色的数量,在增加ans的时候减去cnt[后半段的颜色]。
AC代码如下:
时间复杂度
#include<bits/stdc++.h>
#define int long long
//十年OI一场空,不开longlong见祖宗
using namespace std;
int n,cnt[300005],ans;
struct node{
int a,b;
}a[300005];
//由于排序时候会改变球的顺序,但不会改变颜色
//所以选择结构体存储
int sortf(int l,int r){
int mid=(l+r)/2;
if(r-l<1)return 0;
sortf(l,mid);
sortf(mid+1,r);
for(int i=l;i<=r;i++){
cnt[a[i].b]=0;
}for(int i=l;i<=mid;i++){
cnt[a[i].b]++;
}vector<node>v;
for(int i=l,j=mid+1;;){
if(i>mid&&j>r)break;
if(i>mid)v.push_back(a[j++]);
else if(j>r)v.push_back(a[i++]);
else {
if(a[i].a>a[j].a){
//增加ans的时候减去前半段与后半段第一个数颜色相同的数量
ans+=(mid-i+1)-cnt[a[j].b];
v.push_back(a[j++]);
}else{
//移动走时去掉移动球的颜色
cnt[a[i].b]--;
v.push_back(a[i++]);
}
}
}
for(int i=l,j=0;i<=r;i++,j++){
a[i]=v[j];
}return 0;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].b;
}for(int i=1;i<=n;i++){
cin>>a[i].a;
}
sortf(1,n);
cout<<ans;
}
这里空空如也
有帮助,赞一个