Codeforces Round 853 (Div. 2)（C,D)
C
题目大意就是给你\(n\)个数，我们可以按顺序得到接下来的\(m\)个序列，每一个操作是对前面一个序列的第\(p\)个数变成\(v\)，保证每次变化后的序列里面的每一个数两两不同，然后我们找到两个序列\(A_i\)和\(A_j\),并且保证\(j>i\),我们可以得到这两个序列里面的数的种类的数量，然后对于每一对序列，求出这个值的和
这个想着还真是麻烦
然后再知乎上看到了大佬的题解
既然直接求出比较麻烦，正难则反
我们可以知道假如每一对都是完全不同时的值，即总值 ,用\(ans\)表达
\[ans=\frac{(m+1)\times m}{2}\times(2\times n) \]然后我们只要减去那些重复的数
怎么计算那些重复的数,那些数重复出现了多少次呢
对于每一个出现的数，我们都把它存进\(cnt\)里面，然后对于这一个数在多少个序列出现过呢
我们可以记录每一个位置最后一次变化时的序列编号，也是变化后的数第一次出现在的序列的编号，用\(lst\)数组存储，那么如果在下一次如果这一个位置又一次出现变化，那么变化前的数\(a_x\)出现了\(i-lst_x\),\(i\)是此时的序列编号，\(lst_x\)是这个位置的上一次变化的序列编号，那么变化之前的那个数\(a_x\)就出现了\(i-lst_x\)次
然后我们可以得出每一个数出现的在那些不同的序列的次数
对于这些数，只有当两个序列都在这些序列里面，选择的两个序列都出现了同一个数字\(x\),那么\(x\)的贡献就需要减一，则有多少种这样的搭配，就要减少多少个\(1\)
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
const int maxn=2e5+10;
#define int long long
int t,m,n;
struct node
{
int p,v;
}b[maxn];
int a[maxn];
unordered_map<int,int>cnt;
int lst[maxn];
void solve()
{
cin>>n>>m;
cnt.clear();
for (int i=1;i<=n;i++)
{
cin>>a[i];
lst[i]=0;
}
for (int i=1;i<=m;i++)
{
cin>>b[i].p>>b[i].v;
}
for (int i=1;i<=m;i++)
{
cnt[a[b[i].p]]+=i-lst[b[i].p];
lst[b[i].p]=i;
a[b[i].p]=b[i].v;
}
int ans=n*m*(m+1);
for (int i=1;i<=n;i++)
{
cnt[a[i]]+=m+1-lst[i];
}
for (auto [x,y]:cnt)
{
ans=ans-y*(y-1)/2;
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这个题大意是给你两个二进制字符串，我们需要通过下面两种操作把第一个字符串变成第二个字符，最后输出操作步骤
有以下两种操作
所谓左移，右边补\(0\),那么对于左移\(k\)再对原来的数进行异或，那么最后面\(k\)个都只是和\(0\)进行异或，没有影响
右移，左边补\(0\),那么最前面的\(k\)个都是和\(0\)异或，那么这些字符也没有影响
我们需要把\(a\)变成\(b\),我先是找到\(b\)的第一个\(1\)的位置\(p\)，以\(p\)为界限分别对这两边的不同的位置进行一一变成相同的字符
那么我们可以先把\(p\)左边的字符变成和\(b\)一样的字符
我们从\(p\)往前遍历，把出现不同字符变成应该变成的位置，那么如果我们这个已经匹配好了，后面的操作一定不能影响这个已经匹配好的，然后这也和左移不会影响后面的字符，那么哪一个位置可以实现这样的操作呢？
那就是\(a\)最后一个出现\(1\)的位置，我们需要把这个位置上的\(1\)位移到这个不匹配的位置上去，而且这个位置后面的都是\(0\),所以我们正好改变了这个位置的符号，而且还不会影响这个位置后面的字符
然后对于\(p\)的右边我们也需要进行配对，如果这个没有匹配成功的，我们需要把这个位置的字符变化，并且还不影响左边已经匹配好的字符，我们可以用到右移，我们也是寻找从左边第一个\(1\)的位置匹配（左边是\(00001\)这样的形式，那么左边第一个\(1\)一定是\(p\),不用寻找了）到这个位置上去
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int maxn=2e5+10;
int a[maxn],b[maxn];
int t,n;
vector<int>ans;
void change(int len)
{
ans.push_back(len);
if (len>0)
{
for (int i=1;i+len<=n;i++)//保证a[i+len]是未经过变化的，左移右边补0，后面len个不变
{
a[i]=a[i]^a[i+len];//i>len-n后面的这一部分不变
}
}
else
{
len=-1*len;
for (int i=n;i>=len+1;i--)//保证a[i-len]是未经过变化的，右移左边补0，前len个不变
{
a[i]=a[i]^a[i-len];//len前面的不变
}
}
return ;
}
void solve()
{
cin>>n;
string aa,bb;
cin>>aa>>bb;
if (aa==bb)
{
cout<<0<<'\n';
return ;
}
aa=" "+aa,bb=" "+bb;
ans.clear();
int cnta=0,cntb=0;
for (int i=1;i<=n;i++)
{
int x=aa[i]-'0';
a[i]=x;
if (x)
{
cnta++;
}
int y=bb[i]-'0';
b[i]=y;
if (y)
{
cntb++;
}
}
if ((cnta&&!cntb)||(cntb&&!cnta))
{
cout<<-1<<'\n';
return ;
}
int p=0;
for (int i=1;i<=n;i++)//左边匹配
{
if (b[i])
{
p=i;
break;
}
}
for (int i=p;i>=1;i--)//左边匹配
{
if (a[i]==b[i]) continue;
for (int j=n;j>=1;j--)//寻找最右边的1
{
if (a[j])
{
change(j-i);
break;
}
}
}
for (int i=p+1;i<=n;i++)//右边边匹配
{
if (a[i]!=b[i])
{
change(p-i);//p是最左边的1
}
}
int cnt=ans.size();
if (!cnt)
{
cout<<0<<'\n';
return ;
}
cout<<cnt<<'\n';
for (auto x:ans)
{
cout<<x<<" ";
}
cout<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}