Codeforces round 900 （Div 3）D~F

D题：Reverse Madness

题意：

给你一串长为 n 的字符串 s，以及k个间隔 l , r 。l与r有以下特点。

l1=1;
rk=n;
li≤ri, for each positive integer i such that 1≤i≤k;
li=ri−1+1, for each positive integer i such that 2≤i≤k;

 之后给q个操作，每个操作给一个x，以下是x的特点以及操作解释：

Find an index i such that li≤x≤ri (notice that such i is unique).
Let a=min(x,ri+li−x) and let b=max(x,ri+li−x).
Reverse the substring of s from index a to index b.

题解：

可以用差分的方法消除重复翻转的区间。

有个关键是a到b区间的字符串中间位置是(r [ i ]+l [ i ])/2, 且 li≤x≤ri ，每次翻转行为都被固定在区间内，可以正常枚举题目给的区间进行翻转得到答案。

官方题解：将字符串拆分为k个特定区间，每次翻转都会在区间内且中间值为(r [ i ]+l [ i ])/2，在输入q次操作时将对应cnt【pos】++（记录操作数）。依旧是枚举k个区间，如果两个关于中间位置对称的位置的cnt和为偶数就是完全抵消，奇数就再做一次。但这种做法只能抵消翻转字符完全相同的情况，所以耗时会多一点。

参考：Codeforces Round 900 (Div. 3) A - G - 知乎 (zhihu.com)

代码：

#include
using namespace std;
typedef long long ll;
const int N=2e5+5;
typedef pairPII;
int l[N],r[N];
int d[N];void solve(){int n,k;cin>>n>>k;string s;cin>>s;s=" "+s;memset(d,0,sizeof d);for(int i=0;i>l[i];for(int i=0;i>r[i];int q;cin>>q;while(q--){int x;cin>>x;int pos=lower_bound(r,r+k,x)-r;//用函数查找对应区间int mid=(r[pos]+l[pos])/2;int b=r[pos]+l[pos]-x;if(b>x)swap(b,x);d[b]^=1;//确定区间if(mid+1<=n)d[mid+1]^=1;//注意判断数组有没有越界}for(int i=1;i<=n;i++){d[i]^=d[i-1];}for(int i=0;i=l[i];k--){if(d[k])swap(s[k],s[l[i]+r[i]-k]);}}cout<>t;//t=1;while (t--){solve();}return 0;
}

E题：Iva & Pav

题意：给你一串数和q个查询，每次查询都要找到最大的右边界使得al & al+1 &…ar大于等于k

题解：

      因为限制时间给得非常宽裕，所以完全可以把每个数转换为二进制，并且进行前缀和计算，也就是计算前i个数中有多少个数的二进制在某一位上为1，如果区间内此位置为1的个数与区间长度相同，必然在与操作后保留为1。

      因为与操作会使数越做越小，所以可以刚开始就将第l个数与k比较，如果小于k直接输出-1。在寻找时用二分查找，原因同上，且可以用一个check函数直接获取最终得到的数。

参考：Codeforces Round 900 (Div. 3) A~F_死性不改.的博客-CSDN博客

代码：

#include 
using namespace std;
typedef long long ll;
#define has1 __builtin_popcount
const int N = 2e5 + 5;
ll f[N][32];
ll a[N];void fun(int id) // 将给定的数化为32位二进制数
{ll x = a[id];for (int j = 0; j < 32; j++){f[id][j] = f[id - 1][j];if (x % 2 == 1){f[id][j]++;}x /= 2;}
}
ll ans, n, q, k;
ll check(ll l, ll r)
{ll x = 0, y = 1;for (int i = 0; i < 32; i++){int p = f[r][i] - f[l - 1][i];if (p == r - l + 1){x += y;}y *= 2;}return x;
}
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];fun(i);}int q;cin >> q;while (q--){ll l,k,mid,r;r=n;ans=-1;cin>>l>>k;if(a[l]=k){ans=mid;l=mid+1;}else{r=mid-1;}}cout<> t;while (t--){solve();}return 0;
}

F题：Vasilije Loves Number Theory

题意; 给你一个数n，做q次操作。第一种操作是给一个x，将n变为n*x，询问是否存在一个a使得a与n互质并且n*a有n个因数。第二种操作是将n变为最开始的n。

题解： 

        因为gcd(a,n)==1,所以d(n*a)=d(n)*d(a)。要使d(n*a)==n,即n%d(n)==0（就不用考虑a啦！）.

        d(n)求解方法为：先从1开始筛选n的因子并记录个数，因为这些因子可以自由组合为n的其他因子，所以通过乘他们的个数+1获得总因子个数。

        在判断n%d(n)是否为0时可以拆开成因数求余    (a*b)%c==((a%c)*(b%c))%c;

代码：

#include 
using namespace std;
typedef long long ll;
typedef pair PII;
#define has1 __builtin_popcount
const int N =505;
mapnow,org;//记录质因数ll qpow(ll a,ll b,ll m){a%=m;ll res=1;while(b>0){if(b&1)res=res*a%m;a=a*a%m;b>>=1;}return res%m;
}void solve(){now.clear();ll n,q,x;cin>>n>>q;x=n;for(int i=2;i*i<=x;i++){while(x%i==0){x/=i;now[i]++;}}if(x>1){now[x]++;}org=now;//记录最开始的因子情况while(q--){int op;cin>>op;if(op==1){ll s;cin>>s;for(int i=2;i*i<=s;i++){while(s%i==0){s/=i;now[i]++;}}if(s>1)now[s]++;ll ans=1;for(auto v:now){ans*=(v.second+1);//得出因子数量//每个因子可以不选或选<=v.second个}ll mod=1;for(auto v:now){mod=(mod*qpow(v.first,v.second,ans))%ans;}if(mod%ans==0)cout<<"YES"<> t;//t=1;while (t--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！