淮安高端网站制作,济南行知网站制作,wordpress页眉登录,代理服务器ip地址和端口号【规律题】平方差
题目描述
给定 L, R#xff0c;问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 。
输入格式
输入一行包含两个整数 L, R#xff0c;用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的 x 的数量。
样例输入
1 5
样例输出
…【规律题】平方差
题目描述
给定 L, R问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 。
输入格式
输入一行包含两个整数 L, R用一个空格分隔。
输出格式
输出一行包含一个整数满足题目给定条件的 x 的数量。
样例输入
1 5
样例输出
4
提示 对于 40% 的评测用例LR ≤ 5000
对于所有评测用例1 ≤ L ≤ R ≤ 10^9 。 由得
令 则解得
要使y和z有整数解那么 为偶数
1偶数偶数偶数偶数-偶数偶数
2奇数奇数偶数奇数-奇数偶数
则m和n奇偶性相同即如果x有一对因子奇偶性相同那么一定可以找到y,z满足。
1若m,n都为偶数那么m是2的倍数n是2的倍数那么m*n一定是4的倍数。
2若m,n都为奇数那么由性质 奇数*奇数奇数 得m*n也一定为奇数。
综上 x 是四的倍数或者奇数。 #includeiostream
#includecstring
#includemap
#includevector
#includecmath
using namespace std;
typedef long long LL;
const int N10010;
int main(){LL L,R;cinLR;int cnt0;for(LL iL;iR;i){if(i%40||i%2){cnt;}}coutcntendl;return 0;
}
更小的数
题目描述 小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串下标从 0 到 n − 1你可以将其视作是一个具有 n 位的十进制数字 num小蓝可以从 num 中选出一段连续的子串并将子串进行反转最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew num请你帮他计算下一共有多少种不同的子串选择方案只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。
注意我们允许前导零的存在即数字的最高位可以是 0 这是合法的。 输入格式
输入一行包含一个长度为 n 的字符串表示 num仅包含数字字符 0 ∼ 9
从左至右下标依次为 0 ∼ n − 1。
输出格式
输出一行包含一个整数表示答案。
样例输入
210102
样例输出
8
提示
一共有 8 种不同的方案
1所选择的子串下标为 0 ∼ 1 反转后的 numnew 120102 210102
2所选择的子串下标为 0 ∼ 2 反转后的 numnew 012102 210102
3所选择的子串下标为 0 ∼ 3 反转后的 numnew 101202 210102
4所选择的子串下标为 0 ∼ 4 反转后的 numnew 010122 210102
5所选择的子串下标为 0 ∼ 5 反转后的 numnew 201012 210102
6所选择的子串下标为 1 ∼ 2 反转后的 numnew 201102 210102
7所选择的子串下标为 1 ∼ 4 反转后的 numnew 201012 210102
8所选择的子串下标为 3 ∼ 4 反转后的 numnew 210012 210102
对于 20% 的评测用例1 ≤ n ≤ 100
对于 40% 的评测用例1 ≤ n ≤ 1000
对于所有评测用例1 ≤ n ≤ 5000 。
#includeiostream
#includealgorithm
#includecstring
#includemap
#includevector
#includecmath
using namespace std;
typedef long long LL;
int main(){string s;cins;int ns.size();int cnt0;for(int i0;in-1;i){for(int jn-1;ji;j--){if(s[i]s[j]) cnt;else if(s[i]s[j]){for(int xi,yj;xy;x,y--){if(s[x]s[y]){cnt;break;}else if(s[x]s[y]) break;}}}}coutcntendl;return 0;
}
【DFS】颜色平衡树
题目描述
给定一棵树结点由 1 至 n 编号其中结点 1 是树根。树的每个点有一个颜色 Ci。
如果一棵树中存在的每种颜色的结点个数都相同则我们称它是一棵颜色平衡树。
求出这棵树中有多少个子树是颜色平衡树。
输入格式
输入的第一行包含一个整数 n 表示树的结点数。
接下来 n 行每行包含两个整数 Ci , Fi用一个空格分隔表示第 i 个结点的颜色和父亲结点编号。
特别地输入数据保证 F1 为 0 也即 1 号点没有父亲结点。保证输入数据是一棵树。
输出格式
输出一行包含一个整数表示答案。
样例输入
6
2 0
2 1
1 2
3 3
3 4
1 4
样例输出
4
提示
编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。
对于 30% 的评测用例n ≤ 200Ci ≤ 200
对于 60% 的评测用例n ≤ 5000Ci ≤ 5000
对于所有评测用例1 ≤ n ≤ 2000001 ≤ Ci ≤ 2000000 ≤ Fi i 。
#includeiostream
#includecstring
#includevector
#includemap
using namespace std;
const int N2e510;
int c[N];
int ans0;
int n;
vectorint g[N];
void add(mapint,int cnt,mapint,int cnt_nb){for(auto mp:cnt_nb){int xmp.first;int ymp.second;cnt[x]y;}
}
mapint,int dfs(vectorint *g,int *c,int i){int szg[i].size();mapint,int cnt;if(sz0){cnt[c[i]]1;ans;return cnt;}cnt[c[i]]1;for(int j0;jsz;j){int nbg[i][j];mapint,int cnt_nbdfs(g,c,nb);add(cnt,cnt_nb);}int numcnt[c[i]];for(auto mp:cnt){int countmp.second;if(count!num) return cnt;}ans;return cnt;
}
int main(){cinn;for(int i0;in;i){int f;cinc[i]f;if(f1) g[f-1].push_back(i);}dfs(g,c,0);coutansendl;return 0;
}
【DFS】(选不选)买瓜
题目描述
小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜每个瓜的重量为 Ai 。
小蓝刀功了得他可以把任何瓜劈成完全等重的两份不过每个瓜只能劈一刀。
小蓝希望买到的瓜的重量的和恰好为 m 。
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜请输出 −1 。
输入格式
输入的第一行包含两个整数 n, m用一个空格分隔分别表示瓜的个数和小蓝想买到的瓜的总重量。
第二行包含 n 个整数 Ai相邻整数之间使用一个空格分隔分别表示每个瓜的重量。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 10
1 3 13
样例输出
2
提示
对于 20% 的评测用例∑n≤10
对于 60% 的评测用例∑n≤20
对于所有评测用例1 ≤n≤301≤ Ai ≤ 10^9 1 ≤ m ≤ 10^9
#includeiostream
#includealgorithm
using namespace std;
typedef long long LL;
const int N35,INF0x3f3f3f3f;
LL p[N];
LL a[N];
int n;
LL m;
int ansINF;
void dfs(int u,LL sum,int cnt){if(summ){ansmin(ans,cnt);return ;}if(cntans||un||sump[u]m||summ) return ;dfs(u1,suma[u],cnt);dfs(u1,suma[u]/2,cnt1);dfs(u1,sum,cnt);
}
int main(){cinnm;m*2;for(int i1;in;i){cina[i];a[i]*2;}sort(a1,a1n,greaterint());for(int in;i1;i--) p[i]p[i1]a[i];dfs(1,0,0);if(ansINF) cout-1endl;else coutansendl;return 0;
}
网络稳定性X)
异或和之和
题目描述
给定一个数组 Ai分别求其每个子段的异或和并求出它们的和。或者说对于每组满足 1 ≤ L ≤ R ≤ n 的 L, R 求出数组中第 L 至第 R 个元素的异或和。然后输出每组 L, R 得到的结果加起来的值。
输入格式
输入的第一行包含一个整数 n 。
第二行包含 n 个整数 Ai 相邻整数之间使用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5
1 2 3 4 5
样例输出
39
提示
对于 30% 的评测用例n ≤ 300 对于 60% 的评测用例n ≤ 5000 对于所有评测用例1 ≤ n ≤ 1050 ≤ Ai ≤ 2^20 。 区间[l,r]的异或和可以表示为这样原问题就变成了求n1个数两两异或之和如果的二进制第 j 位为10我们只需知道 [0,i-1] 这个区间内的数二进制第 j 位为01的个数x这样s[i]的第 j 位的贡献值为x*2^j
#includeiostream
#includevector
#includemap
#define int long long
using namespace std;
const int N1e510;
int a[N][30];
signed main(){int n;cinn;int x;for(int i1;in;i){cinx;for(int j0;j20;j){a[i][j](xj)1;a[i][j]^a[i-1][j];}}int ans0;for(int j0;j20;j){mapint,int mp;mp[0];for(int i1;in;i){int xmp[a[i][j]^1];//与第i个数第j位不同的个数ans(1j)*x;mp[a[i][j]];}}coutansendl;return 0;
}
#includeiostream
#includevector
#includemap
#define int long long
using namespace std;
const int N1e510;
int a[N];
int s[N];
int cnt[N][30];
signed main(){int n;cinn;int x;for(int i1;in;i){cina[i];s[i]s[i-1]^a[i];}
//求n1个数第j位0和1的个数for(int j0;j20;j){for(int i0;in;i){if(s[i]j1) cnt[j][1];else cnt[j][0];}}int ans0;for(int i0;i20;i){
//每个1都可以和每个0异或等于1总数为cnt[i][0]*cnt[i][1]每个1的贡献值为2^ianscnt[i][0]*cnt[i][1]*(1i);}coutansendl;return 0;
}
像素放置(X)
翻转硬币(X)
