刷题记录（240613）

aliyun0512

1. 小红定义一个数组是好数组，当且仅当所有奇数出现了奇数次，所有偶数出现了偶数次。现在小红拿到了一个数组，她希望取一个该数组的非空子序列(可以不连续)，使得子序列是好数组。你能帮小红求出子序列的方案数吗?由于答案过大，请对1e9+ 7取模。

示例：

输入：
4
1 2 3 2
输出: 7

思路：数学问题

设奇数出现x次，那么所有可能的情况就是:

但也可能一次不出现，所以还要加一

设一个偶数出现x次，那么所有可能的情况就是

那么要求的结果就是全部情况相乘，再减1，剪掉空串的情况（题中要求了是非空子串）

1.将数组 a[i] 元素输入map = < a[ i ] , 出现次数>

2.遍历map，计算乘积，最后减1

3.取模mod

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int a[100010],pow2[100100];
map<int,int>mp;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    pow2[0]=1;
    int ans=1;
    for(int i=1;i<=n;i++)pow2[i]=pow2[i-1]*2%mod;
    for(auto i:mp){
        if(i.first%2!=0)
        ans=ans*(pow2[i.second-1]+1)%mod;
        else ans=ans*pow2[i.second-1]%mod;
    }
    cout<<ans-1;
}

2.定义一个01串为“交错串”，当且仅当任意两个相邻的字符都是不同的。例如，"10101"是交错串. 现在小红拿到了一个01串，她有若干次询问，每次询问一个区间，你需要回答将该区间代表的连续子串修改为“交错串”的最小修改次数。每次修改可以修改任意一个字符。

示例：

输入：
6 3
101101
1 3
3 5
1 6
输出：
0
1
3

输入描述

第一行输入两个正整数n,q，代表字符串长度和询问次数。
第二行输入一个长度为n的、仅由'0'和'1'组成的字符串。
接下来的q行，每行输入两个正整数l,r，代表询问的是第l个字符到第r个字符组成的子串,
1≤n,q≤1e5
1<=l,r<=n

输出描述

输出q行，每行输出一个整数代表询问的答案。

思路：

只有两种形式：101010和010101

1. 两个数组sum1，sum2统计前缀和

sum1---101010--遍历字符串，统计不满足奇数位是1偶数位是0的数量

sum2---010101--遍历字符串，统计不满足奇数位是0偶数位是1的数量

2. 最后输出l-1和r差值较小的那个

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int sum1[100010],sum2[100010];
signed main(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    s=" "+s;
    for(int i=1;i<s.size();i++){
        sum1[i]=sum1[i-1];
        sum2[i]=sum2[i-1];
        if(i&1){
            if(s[i]!='1')sum1[i]++;
            if(s[i]!='0')sum2[i]++;
        }else {
            if(s[i]!='0')sum1[i]++;
            if(s[i]!='1')sum2[i]++;
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<min(sum1[r]-sum1[l-1],sum2[r]-sum2[l-1])<<endl;
    }
}

小红拿到了一棵树，她希望选挥两个不相邻且不相同的节点，满足编码的乘积为偶数。请你帮小红求出合法的方案数。我们认为 <x,y> 和<y,x>为同一种方案。

输入描述：

第一行输入一个正整数n，代表节应数量.
接下来的n-1行，每行输入2个正整数u,v.代表节点u和节点v有一条边连接。
1<=n<=1e5
1<=u,v<=n

输出描述：

一个整数，代表取点的方案数

示例

输入: 
3
1 3
2 3
输出: 
1

思路：

先算出总共的方案，然后拿总的减去相邻节点的方案。

总共的方案数 = 偶数点的数量 * 奇数点的数量 + 取两个偶数点的取法数量 - 相邻的乘积为偶数的情况

num0--偶数数量，num1--奇数数量，ans---计算树中节点值乘积为偶数的边的数量，负数

遍历当前节点的所有子节点 v，如果子节点 v 等于父节点 f，则跳过（避免回到父节点， 题目中写了<x,y> 和<y,x>为同一种方案）。如果当前节点 u 和子节点 v 的乘积是偶数，则减少 ans 的计数（因为不能取相邻节点）。最后，对每个子节点递归调用 dfs。

(num0 - 1) * num0 / 2---计算所有两个偶数节点组成的边的数量

涉及节点的题都会用dfs

所以上面的公式用变量表示为：

num0 * num1 + (num0 - 1) * num0 / 2 + ans

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int num0,num1,ans;
vector<int>e[100010];
void dfs(int u,int f){
    if(u%2==0)num0++;
    else num1++;
    for(auto v:e[u]){
        if(v==f)continue;
        if(u*v%2==0)ans--;
        dfs(v,u);
    }
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    ans+=num0*num1+(num0-1)*num0/2;
    cout<<ans;
}