文章目录
A. Tokitsukaze and All Zero Sequence
A. Tokitsukaze and All Zero Sequence
题意：给定一个数列，我们可以进行如下操作：
1.选择两个相等的数，把一个变0
2.选择数，让这两个数变成两个数中最小的那个
问，让整个数组变全0需要多少次操作
思路：可行的变0办法为：选择0和另一个数进行操作2或者选择两个相等数，发现只要有0之后一直进行操作2就可以了，思维问题。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+100;
int a[N];
int main()
{
int t;
for(cin>>t;t;t--)
{
int n;
cin>>n;
int zero=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==0)
{
zero++;
}
}
sort(a+1,a+1+n);
bool falg=false;
for(int i=1;i<=n;i++)
{
if(a[i]==a[i+1])
{
falg=true;
break;
}
}
if(zero==0)
{
if(falg)
{
cout<<n-2+2<<endl;
}
else
{
cout<<n-2+3<<endl;
}
}
else
{
cout<<n-zero<<endl;
}
}
return 0;
}
B1. Tokitsukaze and Good 01-String (easy version)
B1. Tokitsukaze and Good 01-String (easy version)
题意：给定一个01字符串，问，如果把连续1和0子段剖分出来都是偶数的话，最少要改变原串的几个位置
思路：模拟,由于这个思路不是很好拓展到b2，所以正式思路看b2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10000;
char s[N];
int main()
{
int t;
cout.tie(0);
ios::sync_with_stdio(0);
for(cin>>t;t;t--)
{
int n;
cin>>n;
cin>>s+1;
int len=1,ans=0;
for(int i=1;i<=n;i++)
{
if(s[i]==s[i+1])
{
len++;
}
else
{
if(len&1)
{
len++;
s[i+1]=s[i];
ans++;
}
else
{
len=1;
}
}
}
cout<<ans<<'\n';
}
return 0;
}
B2. Tokitsukaze and Good 01-String (hard version)
B2. Tokitsukaze and Good 01-String (hard version)
题意：在b1的基础上我们还要求，在改变完成之后，剖分出来的子串个数最少
思路：既然题目要求子串是偶数，我们不妨直接两个两个的来看
首先 当两个两个的字符不相等时，我们可以吧这两个字符变成 00或者11
如果两个字符相等，我们可以和上一个两个字符相等的串作比较，如果不一样的话子串个数就要+1
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10000;
char s[N];
int main()
{
int t;
cout.tie(0);
ios::sync_with_stdio(0);
for(cin>>t;t;t--)
{
int n;
cin>>n;
cin>>s+1;
int ans=0,minn=0;
char p='2';
for(int i=1;i<=n;i+=2)
{
if(s[i]!=s[i+1])
{
ans++;
}
else
{
if(p!=s[i])
minn++;
p=s[i];
}
}
cout<<ans<<" "<<max(minn,1)<<endl;
}
return 0;
}
C. Tokitsukaze and Strange Inequality
C. Tokitsukaze and Strange Inequality
题意：给定一个排列，问：选的顺序的abcd四个下标令s[a]<s[c]&&s[b]>s[d]的数有多少
根据题目的暗示：我们知道这题可以n2处理，也就是对每个位置都可以考虑一遍整个数组，很容易的就想到了对于每个位置统计是否小于等于a[i]，然后枚举出bc下标之后就累加
但是这样会达到n3的复杂度，所以还需要进行前缀和优化
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5000+100;
int a[N];
int small[N][N];
signed main()
{
int t;
for(cin>>t;t;t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<=n+10;i++)
for(int j=0;j<=n+10;j++)
small[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=n;j++)
small[i][j]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
small[i][j]+=small[i-1][j];
int ans=0;
for(int b=1;b<=n;b++)
for(int c=b+1;c<=n;c++)
ans+=small[b-1][a[c]-1]*(small[n][a[b]-1]-small[c][a[b]-1]);
cout<<ans<<endl;
}
return 0;
}
D之后的今天没时间写了，最近有些死线要赶，今天就vp这么多了
