挑战赛8题解
2024-08-12 09:00:22
发布于：浙江
12阅读
0回复
0点赞
//第一题题解
#include<bits/stdc++.h>
using namespace std;
int a[105],l,r,l2,r2;//因为r,r2小于等于100，所以我开了一个100的数组来模拟数轴
int main(){
cin>>l>>r>>l2>>r2;//简单输入
for(int i=l;i<=r-1;i++){//因为填涂颜色的数轴是不包括中点的，所以为r-1
a[i]++;//该区域为填涂了一次颜色
}
for(int i = l2;i<=r2-1;i++){//同理
a[i]++;
}
int cnt=0;//创建一个用来统计的变量
for(int i=min(l,l2);i<=max(r,r2);i++){//逐一判断,不漏掉任何一个区域
if(a[i]==2){//如果图了两遍，就使cnt+1
cnt++;
}
}
cout<<cnt;//最后输出结果
return 0;
}
//第二题题解
#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];//建立数组进行判断 ,a[i][j]表示第i位选手对第j位选手比赛的结果
int main(){
string s[1005];//因为该输入是用字符类型输入的，所以用string类型或char类型都一样
int n;//输入
cin>>n;
for(int i=0;i<n;i++){
cin>>s[i];
}
int f = 0;//f来判断是否冲突
for(int i=0;i<n;i++){//建立双重循环来对每次结果判断
if(f ==1){//如果冲突，就没必要继续了
break;
}
for(int j=0;j<n;j++){
if(i==j){//如果i j相等，则跳过
continue;
}
else if(s[i][j]=='W'){//如果选手i赢了j，就记录
a[i][j]=1;
if(a[j][i]!=0&&a[j][i]!=3){//如果a[j][i]已经记录，则判断是否和谐
f = 1;
break;//不和谐就标记并退出,这里也可以直接输出并结束程序
}
a[j][i]=3;//若没记录，则进行标记
}
else if(s[i][j]=='L'){//同理
a[j][i]=1;
if(a[i][j]!=0&&a[i][j]!=3){
f = 1;
break;
}
a[i][j] = 3;
}else{//同上
if(a[i][j]!=a[j][i]){
f = 1;
break;
}
a[i][j]=2;
a[j][i]=2;
}
}
}
if(f==1)cout<<"incorrect";//在遍历完毕后进行判定，根据结果输出
else cout<<"correct";
// fclose(stdin);
// fclose(stdout);
return 0;
}
//第三题题解
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;//该题要记录相同字符串的出现次数，而容器map正好能满足这个效果
int n;
int main(){
cin>>n;//简单输入
while(n--){//重复执行n次
string s;
cin>>s;//输入字符串
mp[s]++;//让·容器map中索引为s的数量+1
if(mp[s]==1){//如果只是第一个，就不用输出时打括号
cout<<s<<endl;
}else{//否则就带括号,又因重复的从1开始，所以要减一
cout<<s<<"("<<mp[s]-1<<")"<<endl;
}
}
return 0;
}
//第四题题解
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;//这道题是明显的动态规划题，因为n,m极大,若用深搜复杂度为O(2^n)次方肯定会遇上TLE
ll a[5005];//数组a为按第n次时的奖励
ll b[5005];//为数组a的前缀和，大大滴节省时间
ll q[5005];//数组q[i]为计数器为 i时获得的额外奖励
ll p[5005];//为数组q的前缀和,同样大大滴节省时间
ll dp[5005];//dp[i]代表总共抛n次硬币时最多能得多少钱
int main(){
cin>>n>>m;//简单输入
for(int i=1;i<=n;i++){
cin>>a[i];
b[i] = b[i-1]+a[i];//记录数组a的前缀和
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
q[x] = y;//记录对于计数器达到x时额外增加y元
}
for(int i=1;i<=n;i++){
p[i] = p[i-1]+q[i];//记录数组q的前缀和
}
dp[1] = a[1]+p[1];//记录只抛一次时最多获得多少钱
for(int i=2;i<=n;i++){//从2开始
ll maxx=0;//用long long 存储，防止不够
maxx = b[i]+p[i];//若全抛正面，则是a[1]到a[i]与q[1]到q[i]的前缀和
for(int j=1;j<=i-1;j++){//j代表直到第i次抛时，计数器的值为j
maxx = max(maxx,b[i]-b[j+1]+dp[j]+p[i-j-1]);//取最大
}
dp[i] = maxx;//将最大的值给dp[i]
}
cout<<dp[n];//简单输出
// fclose(stdin);
// fclose(stdout);
return 0;
}
//第五题题解
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[200005];//对于T的存储
int a[200005];//对于后面进行判断的数字的存储
bool dp[3][31][200005];//动态规划,第一位代表是这一位是0/1,第二位是位数,第三位代表经过运算了多少次 dp[i][j][k]数组代表第j位本来是i的值经过k次运算后这一位变成了多少
int main(){
cin>>n>>m;//输入
for(int i=0;i<31;i++){
dp[1][i][0]=1;//初始化
dp[0][i][0]=0;
}
for(int i=1;i<=n;i++){
cin>>f[i]>>a[i];//数据输入
}
for(int i=0;i<30;i++){//判断每一位
for(int j=0;j<=1;j++){//对于0或1分别判断
for(int k = 1;k<=n;k++){//判断经过k次后的结果
bool x = (a[k]>>i)&1;//左移i位后与1相与,代表a[k]的2进制中第i位是1或0
if(f[k]==1)dp[j][i][k] = dp[j][i][k-1]&x;//凭借上个计算处理的结果推出这次的结果
if(f[k]==2)dp[j][i][k] = dp[j][i][k-1]|x;
if(f[k]==3)dp[j][i][k] = dp[j][i][k-1]^x;
}
}
}
for (int i=1; i<=n; i++){//输出
int ans = 0, k = m;
for (int j=0; j<30; j++){//每个位数分别判断
ans += dp[k & 1][j][i] * (1 << j);//取k的第一位乘上2^j次方进行2进制转回10进制
k >>= 1;//将最后一位舍去
}
cout << ans << endl;//输出结果
m = ans;//继续接着输出
}
return 0;
}
//第六题题解
#include <bits/stdc++.h>
using namespace std;//这道题经过观察，发现这不就是逆序对吗，于是我就用暴力试了一下，发现只有74分（左右），于是我就用了归并排序
const int maxn = 3e5+9;//设定最大值
struct node{//定义结构体
int num;//该小球的数值
int c;//该小球的颜色
};
int cnt[maxn];
node a[maxn],c[maxn];
long long ans = 0;
void merge_sort(int l,int r){
if(l>=r){//若是相等，直接返回
return ;
}
int mid = l+r>>1;//取中间
merge_sort(l,mid);//将其分成两个更小的问题
merge_sort(mid+1,r);
int i = l,j = mid+1,k = l;//开始排序
for (int i=l; i<=r; i++){//初始化
cnt[a[i].c] = 0;
}
for (int i=l; i<=mid; i++){//记录有多少种颜色
cnt[a[i].c] += 1;
}
while(i<=mid && j<=r){
if(a[i].num<=a[j].num){//若不满足，将该颜色个数减一，并用c数组记录
cnt[a[i].c] -= 1;
c[k++] = a[i++];//将左端点往右移
}else{//若满足，使计数的变量增加
ans += (mid-i+1) - cnt[a[j].c];
c[k++] = a[j++];//使右端点往左移
}
}
while(i<=mid){//其他未存在数组c中的也存进去
c[k++] = a[i++];
}
while(j<=r){
c[k++] = a[j++];
}
for(int i = l;i<=r;i++){//将数组a(左端点到右端点中的所有数)全部覆盖为数组c（的值）
a[i] = c[i];
}
}
int main(){
int n;//简单输入
cin>>n;
for(int i = 1;i<=n;i++){//这里需要注意，本题是先输入颜色再输入数值的
cin>>a[i].c;
}
for(int i=1;i<=n;i++){
cin>>a[i].num;
}
merge_sort(1,n);//输入左，右端点，进行归并排序
cout<<ans;//最后输出结果
return 0;
}
有帮助，赞一个