速通挑战赛#8题解
2024-08-12 13:58:38
发布于：浙江
72阅读
0回复
0点赞
挑战赛#8
ヾ(≧▽≦*)o这次题目超有石粒，我也是耗费两天半才ak，实在难
暴力标记来判断0ms解决
现在来写
so,let's go
双倍经验
#include<iostream>
using namespace std;
int a[100005],cnt;
int main(){
int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
for(int i=l1;i<=r1;i++){
a[i]+=1;//先给蓝的做标记
}
for(int i=l2;i<=r2;i++){
a[i]+=2;//再给红的做标记
}
int n=max(l1,max(r2,max(l2,r1)));
int d=min(l1,min(r2,min(l2,r1)));
for(int i=d;i<=n;i++){
if(a[i]==3){
cnt++;
}
}
if(cnt!=0)
cout<<cnt-1;
else{
cout<<cnt;
}//判断一下是否重叠，如果不等于0cnt-1，否则输出cnt
}
这道题目是签到题so easy
but next two
卡我半小时的题目
开一个char数组来判断是不是dwl
双倍经验
#include <iostream>
using namespace std;
bool check(char a[1005][1005] , int n) {//wa了两个点后才发现check 有一个地方写漏了$恼$
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (a[i][j] == 'W' && a[j][i] != 'L') return false;
if (a[i][j] == 'L' && a[j][i] != 'W') return false;
if (a[i][j] == 'D' && a[j][i] != 'D') return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
char a[1005][1005];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >>a[i][j];
}
}
if (check(a, n)) {//判断check
cout << "correct" << endl;
} else {
cout << "incorrect" << endl;
}
return 0;
}
但这是一道非常优质的入门食材
现在来到😄q(≧▽≦q)
用map储存就行了也是一道水题，好奇？acgo前三道怎么都是大水题
双倍经验
//#include <bits/stdc++.h>
#include <iostream>
#include <map>
using namespace std;
int main() {
int n;
cin >> n;
map<string, int> mp;//定义mp
for (int i = 0; i < n; i++) {
string s;
cin >> s;
if (mp.find(s) == mp.end()) {//标记寻找输入的s是否和上一个相同
cout << s<< endl;
mp[s] = 1;
} else {
int cnt = mp[s];否则就输出
cout<<s<< "(" << cnt << ")" << endl;
mp[s]++;
}
}
return 0;
}//只要会stl容器这道题肯定会做出来
beautiful 现在来到了
这是一道dp题 嗯就是dp，我dp非常菜，我也是寻求老师才得到转移方程式
转移方程式如下:dp[i] = max(dp[i], dp[j] + suma[i] - suma[j+1]+sumb[i-j-1]);
双倍经验
#include <iostream>
using namespace std;
long long suma[100005], sumb[100005];//用前缀和优化否则会超是
long long dp[100005];
int main() {
int n, m;
cin >> n >> m;
long long a[100005],b[100005];
for (int i = 1; i <= n; i++) {
cin >> a[i];
suma[i] += suma[i - 1]+a[i] ; //没什么好说的
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
sumb[x] = y;
}
for (int i = 1; i <= 5000; i++) {
sumb[i] = sumb[i - 1]+sumb[i]; //这是给奖励b开的
}
for (int i = 1; i <= n; i++) {
dp[i] = suma[i] + sumb[i];//接下来就是快乐dp环节
for (int j = 1; j < i; j++) {
dp[i] = max(dp[i], dp[j] + suma[i] - suma[j+1]+sumb[i-j-1]);
}
}
cout << dp[n] << endl;
return 0;
}
ok，现在已经到了
这道题十分
有两种写法，就是转二进制或与非，但是会爆tm
所以我就就就用使用了dp大法也是开个三维dp来储存一个一个进行或与非运算就ok了（￣︶￣）虽然有亿点点毒瘤，但是能过就行
双倍经验
#include<iostream>
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我真哭死，竟然选了一道绿题，我一天半都在做那道题
so，就是一道归并排序逆序对，套个模版就行了，我真哭死，感觉阳寿耗尽😭😭😭😡( $ _ $ )
看代码
#include<bits/stdc++.h>
using namespace std;
//[双倍经验](https://www.luogu.com.cn/problem/AT_abc261_f)
#define ll long long
const int maxn=3e5;
int n,a[maxn+5],b[maxn+5],cnt[maxn+5],tmp[maxn+5],temp1[maxn+5],temp2[maxn+5];
ll ans;
void msort(int l,int r){//归并排序
if(l==r){
return;
}
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
for(int i=l;i<=r;i++){
cnt[b[i]]=0;
}
for(int i=l;i<=mid;i++){
cnt[b[i]]++;
}
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(a[i]<=a[j]){
cnt[b[i]]--;
tmp[k++]=i++;
}
else{
ans+=mid-i+1-cnt[b[j]];
tmp[k++]=j++;
}
}
while(i<=mid){
tmp[k++]=i++;
}
while(j<=r){
tmp[k++]=j++;
}
for(int i=l;i<=r;i++){
temp1[i]=b[i],temp2[i]=a[i];
}
for(int i=l;i<=r;i++){
a[i]=temp2[tmp[i]],b[i]=temp1[tmp[i]];
}
}
int main(){//我就是~~sb~~
cin>>n;
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
cin>>a[i];
}
msort(1,n);
cout<<ans;
return 0;
}
点个赞和评论再走呗
The end();
有帮助，赞一个