E
题意
给定一个矩阵,你可以对这个矩阵进行上下左右移动,不限制次数,然后你可以选择矩阵中任何一点进行^1的操作。
求出最少需要多少步能够把矩阵变成一个除了对角线之外都是0的矩阵。
分析
首先我们可以得知这个矩阵上下左右方向移动的意义其实是一样的,所以我们枚举这个矩阵向右移动了多少步,看对角线上最多会有多少个1.
同时我们统计一共有多少个1.最后的答案就是我需要的 1 的个数 - 我已经有的1的个数 +我所有的1的个数-我已经有的1的个数.
void solve()
{
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>w[i];
}
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(w[i][j]=='1')
{
sum++;
}
}
}
int res=0;
for(int i=0;i<n;i++)
{
int cnt=0;
for(int j=0;j<n;j++)
{
if(w[j][(i+j)%n]=='1')
{
cnt++;
}
}
res=max(res,cnt);
}
cout<<sum-2*res+n<<endl;//合并之后的答案
}
D
题意
给定一个数组,你有两种操作:1.删除一段前缀,2删除一段后缀。求乘积最大需要删除的L和R。[其中空字符的大小为1,-2<=$a_i$<=2].
分析
- 首先空的序列的乘积为1,所有不难想到以每个0为左右边界,因为如果你把0加到集合中的话,还不如全删了。
- 对于负数而言,如果是偶数的话,直接计算。
- 如果是奇数的话,找到这个负数的左右端点,也就是第一个负数和最后一个负数。把区间分成四部分:[L,a1-1], [a1+1,R] [an+1,R] [L,an-1]
#include<bits/stdc++.h>
#define x first
#define y second
#define int long long// define int 真的只有一次和无数次
#define endl '\n'//防止卡!
using namespace std;
typedef pair<int,int>pi;
const int N=2e5+100;
int a[N],ans;
int v[N];
int L,R;
int n;
void cal(int l,int r)
{
int res=0;
for(int i=l;i<=r;i++)
{
if(abs(a[i])==2)
{
//因为只有2的权值会给答案带来影响,所以统计二的个数就能表示这个数字的大小.
res++;
}
}
//cout<<l<<" "<<r<<" "<<res<<endl;
if(res>ans)
{
ans=res;
L=l-1;
R=n-r;
}
}
void get(int l,int r)
{
int cnt=0;
for(int i=l;i<=r;i++)
{
if(a[i]<0)
{
v[cnt++]=i;
}
}
// 统计有多少个负数
if(cnt%2==0)
{
cal(l,r);//如果是偶数个直接处理
}
else
{
//四个部分
cal(l,v[0]-1);
// !注意边界
if(v[0]+1<=r)cal(v[0]+1,r);
cal(l,v[cnt-1]-1);
//!注意边界
if(v[cnt-1]+1<=r)cal(v[cnt-1]+1,r);
}
}
void solve()
{
cin>>n;
ans=0;
int l=1;
L=n,R=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
//我们记录一下当前的区间的左右端点。
//如果碰到0直接夹断。
if(a[i]==0)
{
get(l,i-1);
l=i+1;
}
}
//记得最后处理一下剩下的部分!
get(l,n);
cout<<L<<" "<<R<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _;
_=1;
cin>>_;
while(_--)solve();
}
F
题意
给定一个长度为n只含有 + -的字符串,同时规定两个连续的 - 可以变成一个+。求有多少个子序列可以通过任意次操作满足+ - 数量相同.
分析
设x为-的数量 y为+的数量.
- x-2*k=y+k.
- 上面这个式子成立的条件我觉得是鸽巢原理,首先先将+ - 连续排列,是一种满足条件的情况,然后往中间加 - ,保证能够凑到相邻的- - .
所以题目变成了:如果我统计的是前缀和,那么我就相当于求,i 前面的下标中有多少个下标对应的值x,满足 (s[i]-x)%3==0,s表示前缀和。
现在我们来处理这个前缀和数组。
- 我先把 + 看成-1,-看成1,因为不出意外的话,- 肯定比 + 多,之后我为了防止出现负数的前缀和,我会将所有的值+ ($mn$+1),所以为了减少我加的大小,我这样映射。
- 树状数组,要建造三棵树,分别表示余数为0 1 2的情况。
- 我对于每个点而言我要做一遍求前面的所有的余数和当前数余数相同的个数,这个地方我用的是树状数组进行存储,要记住把0丢进去,因为 a[n]-a[0]代表前n个符号,也可能是和法解。
- 理论存在,开始编造。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int>pi;
const int N=5e5+100;
int pre[N];
char s[N];
int a[N];
// 学习了YGG的板子,狠狠的爱住了。
struct T
{
const static int maxnum = 5e5 + 10;
int tr[N];
int lowbit(int x) {
return (x)&(-x);
}
void add(int x,int c)
{
for(int i=x;i<maxnum;i+=lowbit(i))
{
tr[i]+=c;
}
}
int que(int n)
{
int res=0;
for(int i=n;i;i-=lowbit(i))res+=tr[i];
return res;
}
void init(int n)
{
for(int i=0;i<=n+2;i++)
{
tr[i]=0;
}
}
}tr[3];
void solve()
{
int n;cin>>n;
cin>>s+1;
int mn=0;
for(int i=1;i<=n;i++)
{
a[i]=(s[i]=='+'?-1:1);
}
pre[0]=0;
for(int i=1;i<=n;i++)
{
pre[i]=pre[i-1]+a[i];
mn=min(mn,pre[i]);
}
mn=-mn;
//cout<<mn<<endl;
pre[0]=0;
for(int i=0;i<=n;i++)pre[i]+=mn+1;
//for(int i=1;i<=n;i++)cout<<pre[i]<<" ";
//cout<<endl;
for(int i=0;i<3;i++)tr[i].init(n+mn+1);
//mn+1的原因是防止出现0,导致TLE
int res=0;
for(int i=0;i<=n;i++)
{
int mo=pre[i]%3;
res+=tr[mo].que(pre[i]);//前pre[i]个中余数为mo的个数。
//cout<<pre[i]<<" ";
tr[mo].add(pre[i],1);//添加一个数
}
cout<<res<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _;
_=1;
cin>>_;
while(_--)solve();
}