solution：一看到这种题目就知道应该用线段树来做 #include <bits/stdc++.h> using namespace std; int n, m, arr[100001], tree[400001]; void build(int root, int l, int r) { if (l == r){ tree[root] = n + 1; return; } int mid = (l + r) >> 1; build(root << 1, l, mid); build(root << 1 | 1, mi...

这个题作为主席树的一道模板题，格式有问题，题目就不复制过来了 原题连接 solution：主席树即持久化线段树，如果不懂线段树建议先去看看我的线段树博客 #include <bits/stdc++.h> using namespace std; const int maxn = 1000001; int top = 0, a[maxn], root[maxn]; struct xjp{ int l, r, val; }tree[maxn * 20]; //建立新节点 int colne(int node){ ++top; tree[top] = tree[node];...

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 152485 Accepted Submission(s): 63311 Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,...

题意：有一面hw的墙，有n个大小为 1wi宣传单，每次贴都从最左最上能贴的位置开始贴，求每一宣传单被贴在哪一行。 solution：线段树以1-h划分成区间，每个区间存放着该区间能放下的最大长度，每次从最上面开始找，找到符合的区间并更新 #include <bits/stdc++.h> using namespace std; struct node{ int l, r, res; }tree[8000001]; int ans[2000001], h, w; void build(int root, int l, int r) { tree[root].l = l; ...

solution：区间更新区间查询的树状数组 #include <iostream> using namespace std; long long n,m; long long a[100005] = {0}; long long sum1[100005]; //(D[1] + D[2] + ... + D[n]) long long sum2[100005]; //(1*D[1] + 2*D[2] + ... + n*D[n]) long long lowbit(long long x){ return x & (-x); } void upd...

题目描述 如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数数加上x 2.求出某一个数的值 输入格式 第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。 接下来M行每行包含2或4个整数，表示一个操作，具体如下： 操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k 操作2： 格式：2 x 含义：输出第x个数的值 输出格式 输出包含若干行整数，即为所有操作2的结果。 输入输出样例 输入 #1 复制 5 5 1 5 4 2 3 1 2 4 2 2 3 1 1 5...

Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。 中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始...

solution：最开始是4个字符左下角那个和其余3个不一样，用最初的可以拼成第2个，把第2个分成4部分，左下角和第一个相反，也就是P变为C，C变为P，其余相同。 #include <bits/stdc++.h> using namespace std; char s[1025][1025]; void f(int k) { if(s[(int)pow(2,k-1)][(int)pow(2,k-1)]==0) { f(k-1); } for(int i=1;i<=(int)pow(2,k-1);i++) { fo...

7-23 还原二叉树 (25 分) 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。 输入格式: 输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。 输出格式: 输出为一个整数，即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 原题链接 solution：找到前序结点在中序中的位置，则在中序该位置左边都是左子树的结点，右边都是右子树，按照这个思路来建树获取它的高度 #include <bits/stdc++.h> usin...

solution：模拟，按照输入的顺序倒着输出，每输出一个就标记一下，遇到重复的就不再输出 #include <bits/stdc++.h> using namespace std; int arr[100001]; bool book[100001]; vector<int> a; int main() { int n, m, temp; cin >> n >> m; for (int i = 0; i < n; ++i){ cin >> arr[i]; } while (m--) { cin &gt...

题意：找出最小的值c使（a ^ c）&（b ^ c）最小。 solution：输出A&B，当（A&B == 0）时特判。 #include <stdio.h> #include <algorithm> using namespace std; int main() { long long a, b, c; int t; scanf("%d", &t); while(t--) { scanf("%lld%lld", &a, &b); if((a&b)==0)...

题意：给定一个正整数n，编写一个程序来找出n的非零倍数m，它的十进制表示只包含数字0和1。您可以假设n不大于200，并且对应的m不包含100小数位数。 典型的广搜思路超时了。。。。 于是改用深搜+一个记忆数组 solution： #include<cstdio> #include<iostream> #include<cstring> using namespace std; bool flag; unsigned long long int s[201], tot; void dfs(unsigned long long int x,int n,in...

初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。 示例: 输入: 3 输出: 1 解释: 初始时, 灯泡状态 [关闭, 关闭, 关闭]. 第一轮后, 灯泡状态 [开启, 开启, 开启]. 第二轮后, 灯泡状态 [开启, 关闭, 开启]. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。 来源：力扣（LeetC...

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。 亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。 示例： 输入：[5,3,4,5] 输出：true 解释： 亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 ...