Codeforces Round #845 (Div. 2) and ByteRace 2023（A，B，C）
A
这个题目大意是有n个数，我们需要让ai和ai+1的奇偶性不一样
我们可以让相邻的两个数变成一个数，那个数就是这两个数相乘的结果
我们知道，对于两个奇偶性一样的，两个数相乘还是不能改变奇偶性，所以我们主要考虑那些多余1的同一性质的数，让其中的数量变成1个
#include <iostream>
using namespace std;
const int maxn=2e5+10;
#define int long long
int t,n;
void solve()
{
cin>>n;
int ans=0;
int cnt=0;
int flag=-1;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
if (i==1)
{
cnt=1;
flag=x&1;
}
else
{
int now=x&1;
if (now==flag)
{
cnt++;
}
else
{
ans+=cnt-1;
cnt=1;
flag=now;
}
}
}
ans+=cnt-1;
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
B
这个题大意是对于给出的一个n,我们可以得到一个排序，那么我们可以得到一个数组有原来的排序和翻转过来的排序，然后我们问n个数得到的n个阶乘个的排序得到的n个阶乘的数组的逆序对的个数
我发现不管是哪一种排序
对于一个数x,可以找到2（x-1)个逆序对，那么一个排序就有2（1+2+3+。。。+n-1)
这里我们可以用数组求和
s=2(n-1)(1+n-1)
总共有n的阶乘个排序
然后再乘
记得取模
#include <iostream>
using namespace std;
const int maxn=1e5+10;
#define int long long
const int mod=1e9+7;
int t,n;
int f[maxn];
void init()
{
f[1]=1;
for (int i=2;i<=1e5+5;i++)
{
f[i]=(f[i-1]*i)%mod;
}
return ;
}
void solve()
{
cin>>n;
int ans=f[n];
ans=(ans*n)%mod;
ans=(ans*(n-1))%mod;
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
init();
while (t--)
{
solve();
}
system ("pause");
return 0;
}
C
这个题是给你n个数，a[i]可以解决是a[i]的因子的数
我们需要解决1到m的数，那么我们可以选择任意个数，去解决1到m的数，我们要让我们选的数的差值最小
我们需要排序，我们只需要最大的那个数，最小的那个数，然后中间的数我们有没有都对答案没区别，为了更好的解决这m个数，我们让这种间的数都放进去
这个我们一个一个遍历l,找到最小的r，然后找最小的那个差值
这里的一个判断解决m个问题，和放a[i]可以解决那些问题，很撤销a[i]后解决问题会不会变少
这里的具体操作看代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m;
vector<int>factor[maxn];
int cnt[maxn];
int a[maxn],tot;
void del(int x)
{
for (int d:factor[x])
{
if (d>m) break;
--cnt[d];
if (!cnt[d]) ++tot;//只有删除完所有相关的因子，那么这一个数就算删除了
}
return ;
}
void add(int x)
{
for (int d:factor[x])
{
if (d>m) break;
if (!cnt[d])//只有cnt[d]==0才算是算一个，其他的因为每个数只能算一次
{
--tot;
}
cnt[d]++;
}
}
void solve()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cnt[i]=0;
}
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
int ans=1e9;
int l=1,r=0;
tot=m;
for (;l<=n;l++)
{
while (r<n&&tot!=0)
{
add(a[++r]);
}
if (tot>0) break;
ans=min(ans,a[r]-a[l]);
del(a[l]);
}
if (ans==1e9)
{
cout<<-1<<'\n';
}
else cout<<ans<<'\n';
return ;
}
void init()
{
for (int i=1;i<=1e5;i++)
{
for (int j=i;j<=1e5;j+=i)
{
factor[j].push_back(i);
}
}
return ;
}
signed main ()
{
int t;
cin>>t;
init();
while (t--)
{
solve();
}
system ("pause");
return 0;
}