WORIA

https://ac.nowcoder.com/acm/contest/1084 B. Galahad   题意：给定数列，问区间和，特殊之处在于若区间有重复数字，该数只能算一次。 树状数组+离线处理 先处理出每个位置左边最近的和它相同的数的位置。 将询问按照右端点从小到大排序，逐渐增大当前点，每次增大时从树状数组中删去与这个位置上的数相等的左边最近的位置，这样就能保证每个数都在它所能在的最右边的位置，那么每个数也就一定会被包含到，且由于在不断删除，所以一定只会同时存在一个。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 5e5 + 10;const ll mod = 998244353;int n, m;int a[N], lst[N] ...

https://ac.nowcoder.com/acm/contest/1083 C. 勾股定理   题意：给出直角三角形其中一条边的长度n，要求构造剩下的两条边，使这三条边能构成一个直角三角形。 打表找规律。 12345678910111213141516171819#include <bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e5 + 10;int main() { ll n; cin >> n; if (n <= 2) { puts("-1"); return 0; } if (n & 1) printf("%lld %lld\n", (n*n - 1) / 2, (n*n - 1) / 2 + 1); else printf("%lld %lld\n", (n*n - 4) / 4, (n*n - ...

https://ac.nowcoder.com/acm/contest/1080 C. tokitsukaze and Soldier   题意：挑选一些士兵，每个人由战力，并且选了一个人后要满足他“总人数不超过 s[i]s[i]s[i] ”的要求，问最大总战力。 按照人数从小到大遍历，维护一个单调队列，满足队列里的人的s都大于等于目前人数。再贪心选战力最大的。 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e6 + 10;const int INF = 0x3f3f3f3f;int n;ll ans;typedef pair<int, int>pii;priority_queue<pii>q1;priority_queue<pii, vector<pii>, greater<pii> >q ...

https://ac.nowcoder.com/acm/contest/3006 题解 https://ac.nowcoder.com/discuss/366644?type=101&order=0&pos=1&page=2 这场是真的傻了，E题人名打错调了半个小时愣是没看见。最后一个半小时还差两题看一题是个大模拟直接跳了，还有一题看着像爆搜，但发现怎么过的人这么少，又想其它方法，结果最后还是写了个爆搜，处理僵尸的时候还特意优化了，结果数据水的不行，错的都能过90几，结束几分钟后发现少乘了个2，还真是爆搜，A完人傻了，早知道干嘛不早点搞。 B. 牛牛战队的比赛地   题意：平面上有几个点，要求在x轴上找一个点，到所有点的最大距离最小。 最大最小，又是二分。每个点到x轴上某点距离小于等于L，这些x轴上的点组成一个区间，如果所有点的区间有交集，那么就能找到一个答案。 12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using ...

https://ac.nowcoder.com/acm/contest/946 B. 筱玛爱阅读   题意：n本书，m个促销活动，买一个活动中的所有书可以免去活动中最便宜的那本，有n个价格标签，要求与书一一对应，使得买完所有书花钱最少。1≤n≤15,1≤m≤2n−11≤n≤15,1≤m≤2^n−11≤n≤15,1≤m≤2n−1 子集dp 要让总花费最少，就是要让免费的书总价格最大。 dp[S]dp[S]dp[S] 表示买了 S 状态的书，免费的书的总价格。 对于子集 t，如果存在 s^t 的促销活动，那么免费的书就增加了，但是并不知道最便宜的那本书的价格，所以考虑规定一个顺序，把所有标签从大到小排序，每次新买进一些书，就把这些书的价格规定为比之前买的书都便宜，假设原先有 jjj 本书，又买进了 iii 本书，新增加的免费书的价格就是 i+ji+ji+j 本书中最便宜的那本书的价格，一直这样操作，之前买的 jjj 本书一定是最贵的 jjj 本，才能使得最便宜的书最贵（贪心），而之前把标签从大到小排序了，所以新增加的书的价格就是 price[i+j]price[i+j]price[i+j] ...

https://ac.nowcoder.com/acm/contest/923 A. 小w的a+b问题   题意：两个32位整型的正数相加后溢出得到负数，现给出负数，求一组正数。 把负数加2*2147483648得到对应的正数，然后随便凑一组即可。 12345678910111213#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;ll x, ans;int main() { ans = 2147483647ll + 2147483647ll + 2ll; cin >> x; if (x == -1)puts("No solution"); else cout << ans + x- 2147483647ll << ' ' << 2147483647 << endl; return 0;
...

https://ac.nowcoder.com/acm/contest/3005 题解 https://ac.nowcoder.com/discuss/365889?type=101&order=0&pos=1&page=2 F. 树上博弈   题意：一棵树上两个人轮流走，不能走到对方在的点上，先不能走的人输，问有几种开局情况先手胜。 树形dp 画图发现两人距离为偶数时先手胜，所以找到每个点距离偶数的点数。 邻接表超时，换成前向星。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int maxn = 1e6 + 10;int n;inline int read() { char ch = getc ...

若执行某项操作后应立即跳出，那么后续任何操作都不应该对它再有影响。 除法分母不能取模 https://ac.nowcoder.com/acm/contest/3004 题解 https://ac.nowcoder.com/discuss/365306?type=101&order=0&pos=1&page=2 B. 牛牛的DRB迷宫II   题意：一个nm迷宫，每格为’R’,‘D’,‘B’，分别表示向右走，向下走，向右/向下走。从 (1,1)(1,1)(1,1) 出发，已知到 (n,m)(n,m)(n,m) 共有 kkk 种路径，要求构造出一个迷宫。 神奇的构造题 先构造出一个主对角线上都是’B’，主对角线上一个对角线都是’D’，主对角线下一个对角线都是’R’，主对角线以下没填的都放’D’，以上没填的都放’R’. BDRRRRBDRRDRBDRDDRBDDDDRBBDRRR\\ RBDRR\\ DRBDR\\ DDRBD\\ DDDRB\\ BDRRRRBDRRDRBDRDDRBDDDDRB 这样主对角线上的路径数分别是 1,2,4,8,16，都是2的幂次， ...

整数与浮点数存储方式不同，最好不要相互转化。 比如：开方时不用 i<=sqrt(n)i<=sqrt(n)i<=sqrt(n) 而是判断 i⋅i<=ni\cdot i<=ni⋅i<=n 整数判断大小时不用eps，两个原生的浮点数最好用eps https://ac.nowcoder.com/acm/contest/3003 题解 https://ac.nowcoder.com/discuss/364961?type=101&order=0&pos=9&page=3 C. 算概率   题意：每道题有正确率，问恰好作对K道题的概率。 dp dp[i][j]dp[i][j]dp[i][j] 表示到第 iii 题，做对了 jjj 题的概率。 dp[i][j]=dp[i−1][j−1]⋅a[i]+dp[i−1][j]⋅(1−a[i])dp[i][j]=dp[i-1][j-1]\cdot a[i]+dp[i-1][j]\cdot (1-a[i]) dp[i][j]=dp[i−1][j−1]⋅a[i]+dp[i−1][j]⋅(1−a ...

https://ac.nowcoder.com/acm/contest/3002/J 题意：f(1)=x,f(2)=y,f(i)=f(i−1)⋅f(i−2)⋅abf(1)=x,f(2)=y,f(i)=f(i-1)\cdot f(i-2)\cdot a^bf(1)=x,f(2)=y,f(i)=f(i−1)⋅f(i−2)⋅ab，求 f(n),1≤n,x,y,a,b≤1012f(n),1\leq n,x,y,a,b\leq 10^{12}f(n),1≤n,x,y,a,b≤1012，对 100000000710000000071000000007 取模。 矩阵快速幂，欧拉降幂 f(n)=xp⋅yq⋅(ab)mf(n)=x^p\cdot y^q\cdot (a^b)^mf(n)=xp⋅yq⋅(ab)m，其中 p,qp,qp,q 分别为斐波那契数列的第 n−2,n−1n-2,n-1n−2,n−1 项。mmm 为递归式 f(i)=f(i−1)+f(i−2)+1,f(1)=1,f(2)=2f(i)=f(i-1)+f(i-2)+1,f(1)=1,f(2)=2f(i)=f(i−1)+f(i−2)+1,f( ...