Codeforces Round #789 (Div. 2)
A. Tokitsukaze and All Zero Sequence
一个小小的思维贪心，很容易知道如果有0，直接用0去和其他数处理，如果没有就先创造一个
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e9 + 7;
const int N = 2e6 + 9;
int a[N];
signed main()
{
int t;
cin>>t;
while (t--)
{
int n;
cin>>n;
int ff = 0;//有咩有0
int cou = 0;
int kk = 0;
map<int,int>mp;
for (int i=0;i<n;i++)
{
cin>>a[i];
if (a[i]==0) ff = 1;
else cou++;
if (mp[a[i]]) kk = 1;
mp[a[i]]++;
}
if (ff||kk) cout<<cou<<endl;
else cout<<cou+1<<endl;
}
}
B2. Tokitsukaze and Good 01-String (hard version)
B2覆盖了B1，所以直接发B2好了
这题当时没写出来，因为我最后写的这题，可能脑子不够用了，标签是dp，但是应该是可以贪心的。
首先，因为是偶数子串，所以a[i]==a[i+1]对于所有的奇数位应该成立，字符串可以分割成偶数个，两个一组，所以实际问题就转化成了去找1100或者0011问题，因为如果有0 10 1情况，中间变成谁都可以 1 10 01 01 10 0这种情况肯定是中间都变成一端最好
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e9 + 7;
const int N = 2e6 + 9;
int a[N];
string s;
signed main()
{
int t;
cin >> t;
while (t--)
{
int ans = 0,res = 0,n;
char ch = '3';
cin>>n>>s;
for (int i=0;i<n;i+=2)
{
if (s[i]!=s[i+1]) res++;
else if (ch!=s[i]) {ch = s[i],ans++;}
}
cout<<res<<" "<<max(1ll,ans)<<endl;
}
}
C. Tokitsukaze and Strange Inequality
这题算的上是一个树状数组的模板题，所以没啥好说的，会树状数组就会写
枚举b,c就行
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e9 + 7;
const int N = 2e6 + 9;
int tr1[N],tr2[N],n,a[N];
void add1(int x)
{
for (;x<=n;x+=(x&-x)) tr1[x]++;
}
void add2(int x)
{
for (;x<=n;x+=(x&-x)) tr2[x]++;
}
int sum1(int x)
{
int res = 0;
for (;x;x-=(x&-x)) res+=tr1[x];
return res;
}
int sum2(int x)
{
int res = 0;
for (;x;x-=(x&-x)) res+=tr2[x];
return res;
}
void init()
{
for (int i=0;i<=n;i++) tr1[i] = tr2[i] = 0;
}
signed main()
{
int t;
cin>>t;
while (t--)
{
cin>>n;
init();
int res = 0;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++)
{
for (int i=0;i<=n;i++) tr2[i] = 0;
for (int j=n;j>i;j--)
{
res+=sum1(a[j]-1)*sum2(a[i]-1);
add2(a[j]);
}
add1(a[i]);
}
cout<<res<<endl;
}
}
D. Tokitsukaze and Meeting
这题看起来复杂，因为进去一个人，所有人都要变，但可以转化一下，从两个维度看。
第一个就是对于行的贡献，每进去一个人去和上一行的这个位置的人进去的时候比较就行，如果中间确实有1，那这行就是有1的，如果没有就没有
列就更好算了，因为每个人都是对应的，1一定和m+1在同一列，所以这列没有1就加一个，如果有了就不管了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e9 + 7;
const int N = 2e6 + 9;
int a[N],n, m;
string s;
signed main()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> m >> s;
for (int i=1;i<=m;i++) a[i] = 0;
int f[n+1][m+1];
memset(f, 0, sizeof f);
//先处理了行的贡献
int cou = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
int w = (i-1) * m + j - 1;
if (s[w] == '1') cou = m;
f[i][j] = f[i - 1][j] + (cou > 0);
cou--;
}
//再处理了列的
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
int w = (i-1)*m + j - 1;
if (s[w]=='1'&&!a[j])
a[j] = 1,cnt++;
cout<<cnt+f[i][j]<<" ";
}
cout<<endl;
}
}
这div2 100多名不有手就行？
