一个平面上有 n 个点，每个点有一个对应的权值，其他点的权值都是0，让你选一个矩形，要求矩形内所有点的权值最大。 枚举上边界，对于每一行的点，将他依此加入到线段树中，同时更新最大值。时间复杂度  大力区间和并，查询的时候还要同时查一下跨左右区间的最大值。 #include <bits/stdc++.h> #define lson left,mid,k<<1 #define rson mid+1,right,k<<1|1 #define imid int mid=(que[k].l+que[k].r)/2; #define ll long long #...

slove  2/12 rank  358 补题   5/10 --------------------------------------------------- link 6635 Nonsense Time 每次加入一个数字后求最长上升子序列长度 题目保证数据随机生成，就是说只有  的概率会选到在最上上升子序列上的值，所以每次暴力跑，存下最长上升子序列的值就可以 #include <bits/stdc++.h> #define sc scanf #define pr printf using namespace std; int n, t; int a[5...

存dls板子，dlstxdy 已知 x p，求满足  并且  并且 b 是最小正整数的最简分数。 #include <bits/stdc++.h> #define ll long long using namespace std; void fun(ll pa, ll pb, ll qa, ll qb, ll& x, ll& y) { ll z = (pa + pb - 1) / pb; if (z <= qa / qb) { x = z; y = 1; return; } pa ...

slove  4/11 rank  328 补题   7/11 -------------------------------------------------------- link A、String 贪心暴力跑最长符合条件的，签到 #include <bits/stdc++.h> using namespace std; char s[205]; int str[205]; string ans[205]; int num1[205], num0[205], num[205]; int main() { int T; scanf("%d&quot...

slove  3/10 rank  374 补题    -------------------------------------------------------- B、Beauty Values 一个区间的贡献为这个区间的不同数字的个数，求所有子区间的贡献和 反向思考，计算一个数字在子区间中出现的次数，当区间的左端点在这个数字上一次出现位置和当前位置之间，并且右端点在当前位置之后，这个数字都产生了贡献，所以当前位置的数字的贡献就是左端点数量*右端点数量，然后遍历一遍。 #include <bits/stdc++.h> #define ll long long ...

E、find the median https://ac.nowcoder.com/acm/contest/887/E 每次操作把一段连续的数字加入到数组中，每次求输出的中位数。 权值线段树维护区间个数，然后加上诡异的离散化。 1、首先将左端点，右端点加一，进行离散化，因为这里的询问要求中位数，所以不能和其他线段树题目一样离散化后每个点代表一个点，而是每个点需要代表一段区间。并且在建树的时候，每个叶子节点表示  到 之间的数字的个数。 2、更新操作，区间mark加一，并且区间的个数加上mark就可以。因为离散化后，叶子节点的区间一定是被连续更新的，不会出现更新叶子节点里面的一段数字...

A、Hotelier 暴力 #include<bits/stdc++.h> #define sc scanf #define pr printf using namespace std; int a[15]; int main() { int n; sc("%d", &n); getchar(); for (int i = 1; i <= n; i++) { char s = getchar(); if (s == 'L') { for (int i = 0; i <= 9; i++) { if...

有 n 个格子，每个格子有一个值，你没走到一个格子就获得这个格子的值，你现在在第 1 个格子，求你到达第 n 个格子的期望获得的值 这个题只能反着求，不能顺序，假设我们有案例  4   1 2 3 4 那么 4 的期望应该是前三个期望/3+第四个值，但是，走到前三个点的的概率相同吗？ 显然，从1走到1的概率是1，走到2的概率是1/3，走到3的概率是1/3+1/3*1/2，所以不能顺序直接累加求期望。 那么我们考虑反着求，对于每个点，他等概率走到他后面的六个点，那么以这个点作为起点走到点n的期望就等于他后面六个点作为起点走到n的期望/6+这个点的值。 #include <bit...

给一个数字，等概率选择一个这个数字的除数，然后将这个数字除以这个除数，直到这个数字等于1，求这个数字等于1的期望次数。 我们用  表示这个数字的期望次数，对于每一个数字 i ，有 ，化简后得  所以枚举每一个数字，暴力跑一下他的因数   #include <bits/stdc++.h> #define ll long long #define sc scanf #define pr printf using namespace std; double dp[100005]; void init() { for (int i = 2; i <= 100000; i...

当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；   当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有***丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”   当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西...

http://codeforces.com/contest/1203 ------------------------------------------------- 赛后两分钟，在F1后面加了一个判断，过了。。少了一题血亏 A - Circle of Students 从左往右，从右往左扫一遍 #include <bits/stdc++.h> #define sc scanf #define pr printf using namespace std; int a[205]; int main() { int T; sc("%d", &amp...

A - Choose Two Numbers 选最大的两个数 #include <bits/stdc++.h> #define sc scanf #define pr printf #define ll long long using namespace std; const int MAXN = 200005; int a[200005], b[200005]; int main() { int n, m, t; sc("%d", &n); for (int i = 0; i < n; i++) { sc("%d&qu...

slove  1/10 rank  419 补题   4/10 -------------------------------------------------------- Link A、The power of Fibonacci 给两个整数 n,m，求斐波那契的前N项的M次方的和 ex杜教BM，存板子 #include <bits/stdc++.h> using namespace std; #ifndef ONLINE_JUDGE #define debug(fmt, ...) fprintf(stderr, "[%s] " fmt ...

slove  4/10 rank  297 补题   5/10 -------------------------------------------------------- Link B、Coffee Chicken s[1]=“COFFEE”，S[2]=“CHICKEN"，s[i]=s[i-2]+s[i-1]，求第 n 个串的第 K - K+10 个字符 预处理一下所有小于等于1e12的长度，然后爆搜，大概就是如果查询的长度小于等于前一个串，那么就搜前一个串，否则，搜后一个串。 然后发现当 n 很大的时候，他的前缀（除了前13个是奇偶变换的）是等于他前面的前缀的...