分析 发现题面就是要我们求这个东西 。这个显然显然单次枚举是 。我们考虑我们维护了一个上凸壳。所以我们只需要找到凸壳的顶点就好了，而考虑到是凸壳，那么考虑三分法解决。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 ...

分析 这场比赛较难的一道题。我们可以根据坐标建一根线段树，然后在线段树上二分。这样就可以做到 ，而并不是题解的 。没有太大思维量，根据题意把线段树建出来，然后对于每一个节点模拟一下就好了。主要还是考察了代码能力吧。要注意是按输入顺序来考虑的，而不是坐标的从左向右。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7; int read() { int x = 0,f = 0;char ch = getchar(); while(!i...

分析 对于加法我们可以考虑为，两个为 ，那么该位变为 ，下一位 。而异或满足两个为 ，那么该位变为 。而下一位 ，则可以考虑哪些位要进位，所以我们得到第一个式子 。但是我们要考虑到进位之后 和 要没有同一个位为 ，这才是可行的方案。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL read() { LL x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();} while(i...

分析 我们发现对于任意一对括号都满足，括号中的现有答案乘上括号后的数字。那么我们先将括号进行匹配，然后通过递归处理。时间复杂度为 ，因为我们读入的是字符串，所以对于数字的处理要用类似快读的方法。主要是要注意一下细节就可以了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 100; #define LL long long int pos[N],st[N],top,n; char ch[N]; LL solve(int l,int r) { LL tot = 0; // cout <&lt...

分析 对于博弈问题我们可以把从一个必胜状态和必败状态进行推导。我们已经知道 是个必败节点，那么 则是必胜节点，从而可以得到 也是必败节点。把图画出来，我们发现出现了一个很显然的分形结构，而最小单元是个 的图，把表打出来就可以了，时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while(isdigit(c...

分析 我们可以求出单次抛出 的概率为 ，所以赢的概率为 ，那么输掉的概率为 ，快速幂计算，时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while(isdigit(ch)) {x = x*10 + ch - '0';ch = getchar();} return f?-x:x; } const int ...

分析 刚学生成函数，来试试水。我们先把每一种的生成函数写出来，并转化为封闭性式。          全部相乘之后 。如何转化为幂级数的形式。因为 所以 所以最后的答案为 。代码  #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10,inf = 0x3f3f3f3f,mod = 10007; #define LL long long LL read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f ...

[TJOI/HEOI2016] 求和 所以我们现在可以 求出 了。因为后面的式子已经是卷积形式了 了。 代码 #include<bits/stdc++.h> using namespace std; const int p = 998244353,Gi = 3,N = 1e6 + 10; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getch...

多项式乘法逆 给你多项式 ，寻找一个多项式满足 。考虑倍增求解。 如果我们已知 ，而根据 。那么显然 ,两式相减那么 ,左右相减 。考虑左右都乘上一个 ，那么 移项 。那我们的递归出口为 。 代码 #include<bits/stdc++.h> using namespace std; #define int long long const int p = 998244353,Gi = 3,N = 2e6+100; #define LL long long int read() {int x;scanf("%lld",&x);return x;} int...

分析 我们发现，对于一个序列进行旋转操作，其实可以等同于只对一个序列进行操作。然后加上改变量所以题意其实就是要我们求 。 我们先把中间的式中拆开 。变成了这个式子。那么我们可以考虑枚举 。那么现在就只有 是没法很快求出来的了。可以令一个数组 ，保证 ，那么现在，就是要求 ，这个就是个标准的卷积形式了。我们把 破环成链。现在就只需要让 做一次多项式乘法就好了。那我们取那一部分的答案呢？ 考虑到我们是把 倍长了的。所以我们实际需要的答案应该在 到 这些项中去寻找。其实可以不用枚举 ，因为我们已经转换为一个二次函数了，那么我只需要考虑二次函数的对称轴。但是这个不是实数，所以要考虑 和 。两个可能的最...

分析 我们先引入一个概念，置换。这里我简单的说一下，就是把 个元素的其它排列与原排列的映射关系。 可以用一个数组表示 。而这个道题就是给出一个置换，求有多少个不同的循环。为什么置换存在循环。不难发现，如果把每个数字看作一个节点，那么每个节点都有一个后驱节点和一个前驱节点，所以出度和入度都为 ，那么这个图必然构成若干个环。如果每个循环的长度为 ，那么在 次变化之后，置换一定变回原样。既然这道题要求有多少个循环，其实就是求 可以分解为多少个数的 的种类数。因为 。所以我们只需要在转移时，保证转移时 这样，可以不用考虑 的影响。定义状态 为考虑前 个质数，最后 的值 。那么答案为 。因为最后你总可以...