ARC125 ABCD

A.

题意

给定01序列(A),问能否通过如下三种操作生成序列(B)，满足(B = T)

将序列(A)整体右移一位
将序列(A)整体左移一位
将当前(A)的第一个元素复制到(B)的末尾

输出最少操作次数

分析

有一种显然的贪心方法:找到(A)中01分界的位置，然后每次在这个位置左右移动。这样答案的两部分分别是移动到分界处和左右移动，后半部分答案不会有区别，前半部分答案只需按照左移和右移讨论取min即可，这样就变成了一道模拟题

代码

int main(){
    int n = rd();
    int m = rd();
    VI a(n);
    VI b(m);
    int vis1[2] = {0};
    int vis2[2] = {0};
    for(int i = 0;i < n;i++)
	a[i] = rd(),vis1[a[i]]++;
    for(int i = 0;i < m;i++)
	b[i] = rd(),vis2[b[i]]++;
    if((vis2[0] && !vis1[0]) || (vis2[1] && !vis1[1])) {
	puts("-1");
	return 0;
    }
    if(!vis2[0]) {
	int mi = 1e9;
	for(int i = 0;i < n;i++)
	    if(a[i] == 1) {
		mi = i;
		break;
	    }
	for(int i = n - 1,j = 1;i > 0;i--,j++)
	    if(a[i] == 1){
		mi = min(mi,j);
		break;
	    }
	printf("%d",mi + m);
	return 0;
    }
    
    if(!vis2[1]) {
	int mi = 1e9;
	for(int i = 0;i < n;i++)
	    if(a[i] == 0) {
		mi = i;
		break;
	    }
	for(int i = n - 1,j = 1;i > 0;i--,j++)
	    if(a[i] == 0){
		mi = min(mi,j);
		break;
	    }
	printf("%d",mi + m);
	return 0;
    }

    int pos = -1;
    int mi = 1e9;
    for(int i = 0;i <= n - 1;i++){
	if(a[i] != a[(i + 1) % n]) {
	    pos = i;
	    if(a[i] != b[0]) pos++;
	    mi = min(mi,pos);
	    pos = n - i - 1;
	    if(a[(i + 1) % n] != b[0]) pos++;
	    mi = min(mi,pos);
	}
    }
    mi++;
    for(int i = 1;i < m;i++){
	if(b[i] != b[i - 1]) mi += 2;
	else mi++;
    }
    printf("%d",mi);
}

B.

题意

求满足(x^2 - y)是平方数的((x,y))个数

(1 leq x,yleq N),(1 leq N leq 10^{12})

分析

[x^2 - y = z^2\ (x+z)(x-z) = y ]

令(p = x + z,q = x - z)

有如下约束

(q leq p)
(p + q equiv 0 (mod 2))
(1leq frac{p+q}{2} leq N)
(1 leq pq leq N)

容易知道((p,q))的解和((x,y))一一对应

用第一个和最后一个约束可以知道(q leq sqrt{N}) ,因此只需要枚举(q)

代码

int main(){
    ll n = rd();
    int ans = 0;
    for(ll i = 1;(ll)i * i <= n;i++){
	ll r = n / i;
	add(ans,((r - i + 1) / 2) % MOD);
	if(((r & 1) ^ (i & 1)) == 0) add(ans,1);
    }
    printf("%d",ans);
}

C.

题意

给定长度为(k)的值域在([1,n])的递增序列，要求构造一个([1,n])的排列使得原序列是排列的一个(LIS)

[1 leq k leq n leq 2 imes 10^5 ]

分析

这题可以用Dilworth's theorem比较巧妙地构造，如果能够保证排列可以由k个极长递减子序列构成，就能保证排列的(LIS)长度为(k)，这样原序列一定会是一个(LIS)

于是只需要贪心构造，用原序列的每个元素来作为极长递减子序列的开头(最后一个特殊处理)，把未出现的元素中最小的数填到开头的后面。剩下的全放到最后一个那里就行了

代码

int main(){
    int n = rd();
    int k = rd();
    VI v(k + 1);
    VI vis(n + 1);
    for(int i = 1;i <= k;i++)
        v[i] = rd(),vis[v[i]] = 1;
    int now = 1;
    for(;now <= n && vis[now];now++);
    for(int i = 1;i < k;i++){
        printf("%d ",v[i]);
        if(now < v[i]) {
            vis[now] = 1;
            printf("%d ",now);
            for(;now <= n && vis[now];now++);
        }
    }
    for(int i = n;i > v[k];i--)
        if(!vis[i]) printf("%d ",i);
    printf("%d ",v[k]);
    for(int i = v[k] - 1;i >= 1;i--)
        if(!vis[i]) printf("%d ",i);
}

D.

题意

给定长度为(N)的数组(A)，求其中只出现过一次的子序列的个数

[1 leq N leq 2 imes 10^5,1 leq A_i leq N ]

分析

容易想到(dp),考虑(dp[i])表示([1,i])中以(a[i])为结尾的满足条件的子序列的个数，观察性质，当相同的数再次出现时，前一个数能构成的所有子序列都会重复，因此这里要减去贡献，显然减法的操作只会在这种情况产生。考虑(dp[i])时哪些是合法的转移，显然就是上一次出现的位置到当前位置的所有子序列都可以接上(a[i])，之前的不合法。

[dp[i] = sum_{j = lst}^{i-1} dp[j] ]

且(dp[lst] = 0)

支持区间询问，单点修改的数据结构即可

代码

struct BIT{
    int n;
    int c[maxn];
    inline void ADD(int pos,int x){
        for(;pos <= n;pos += pos & -pos){
            add(c[pos],x);
        }
    }
    inline int ask(int pos){
        int ans = 0;
        for(;pos > 0;pos -= pos & -pos)
            add(ans,c[pos]);
        return ans;
    }
    inline int ask(int l,int r){
        if(l > r) return 0;
        int ans = ask(r);
        add(ans,MOD - ask(l - 1));
        return ans;
    }
}bit;

int main(){
    int n = rd();
    bit.n = n + 5;
    VI v(n + 1);
    VI pre(n + 1);
    VI pos(n + 1);
    for(int i = 1;i <= n;i++){
        v[i] = rd();
        pre[i] = pos[v[i]],pos[v[i]] = i;
    }
    bit.ADD(1,1);
    for(int i = 2;i <= n;i++){
        int l = pre[i];
        int tmp = bit.ask(l,i - 1);
        if(l) bit.ADD(i,tmp);
        else bit.ADD(i,tmp + 1);
        int TMP = bit.ask(l,l);
        if(l > 0) bit.ADD(l,MOD-TMP);
    }
    printf("%d",bit.ask(n));
}