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;
}