B
题目大意：给定给定一个R行C列的地图
字符画中 1~9 表示炸弹（数字即炸弹的威力），# 表示墙，. 表示空地块。
如果一面墙到炸弹的曼哈顿距离小于等于该炸弹的威力，那么这面墙就会被炸弹炸毁。
请输出所有炸弹爆炸后的地图。
ans
直接模拟即可
码风奇丑 不喜勿喷 下同
#include<bits/stdc++.h>
using namespace std;
char t[200][200];
int r,c;
void bomb(int x,int y,int k)
{
t[x][y]='.';
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
if((abs(x-i)+abs(y-j))<=k&&t[i][j]=='#')t[i][j]='.';
}
}
return;
}
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>t[i][j];
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
if(t[i][j]!='.'&&t[i][j]!='#')
{
bomb(i,j,int(t[i][j]-48));
}
}
}
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
cout<<t[i][j];
}
cout<<endl;
}
return 0；
}
C
题目大意：给定n只袜子,第i只袜子的颜色为A[i]
颜色一样的两只袜子可以组成一双，求最多能组成多少双袜子
ans
N<=50w
直接开数组存
在排序一下
然后遍历即可
感觉比B题还简单
#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main()
{
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
{
if(a[i]==a[i+1]&&a[i]!=-1)
{
ans++;
a[i]=a[i+1]=-1;
}
}
cout<<ans;
return 0；
}
D
题面翻译： 对于一个长度为偶数的数字字符串，如果将其以某种方式重排列后可以让前半部分与后半部分相同，我们就说这个字符串是快乐的！
比如 20230322 可以重排列为 02320232，此时前后两部分都是 0232。所以我们可以认为 20230322 是快乐的。
现在给你一个数字字符串 S，求他有多少个子串是快乐的。
题目大意（简洁版）： 寻找区间（l,r）（l<r）使该区间中的数都出现了偶数次，求此类区间的个数
一开始想O(N*N)的做法 代码如下
#include<bits/stdc++.h>
using namespace std;
int a[500010];
struct node
{
int c[10];
}b[500010];
bool pd(int x,int y)
{
for(int i=0;i<=9;i++)if(b[x].c[i]+b[y].c[i]==1)return 0;
return 1;
}
int main()
{
string s;
long long ans=0;
cin>>s;
int n=s.size();
for(int i=1;i<=n;i++)
{
a[i]=s[i-1]-48;
b[i]=b[i-1];
b[i].c[a[i]]=(b[i].c[a[i]]+1)%2;
}
for(int i=0;i<=n;i++)
{
for(int j=i+2;j<=n;j+=2)
{
if(pd(i,j))ans++;
}
}
cout<<ans;
return 0;
}
然后...
TLE×28
∣S∣≤50w
所以必须用O(N)的算法
经过冥思苦想后发现
只要这两个数的c数组相同 就可以组成
所以只要记录每一种c数组的数量记做n
该种c数组的总排列方式为n(n-1)
即有n(n-1)个满足条件的区间
再加和即可
温馨提示：不开 long long 见祖宗
ans
#include<bits/stdc++.h>
using namespace std;
struct node
{
bool c[10];
}b[500010];
long long k[2000];//我就是因为这里没开long long 挂了整整 30 minutes
int p(int u)
{
int s=0;
for(int i=0;i<=9;i++)
{
s=s+b[u].c[i]*pow(2,i);
}
return s;
}
int main()
{
k[0]=1;
string s;
long long ans=0;
cin>>s;
long long n=s.size();
for(int i=1;i<=n;++i)
{
b[i]=b[i-1];
b[i].c[int(s[i-1]-48)]=(b[i].c[int(s[i-1]-48)]+1)%2;
k[p(i)]++;
}
for(int i=0;i<=1023;i++)
{
ans=ans+k[i]*(k[i]-1)/2;
}
cout<<ans;
return 0;
}
共 1 条回复
非常可以的！