思路 典型的区间染色问题。离散化区间端点（注意非连续区间中间要加点隔开），就可以建线段树了。倒序每一次询问，查看该区间是否被覆盖，如果没有就ans++,然后顺便把区间覆盖掉。 代码 #include<iostream> #include<vector> #include<algorithm> #define MID int mid=(p->l + p->r)>>1 using namespace std; struct Post{ // 海报 int l,r; } pst[10100]; int nodenum,cnt,ans...

思路 线段树板子。 代码 #include<iostream> #define pushup(x) (tree[x]=tree[x<<1]+tree[x<<1|1]) #define MID int mid=(start+end)>>1 using namespace std; const int maxn=1e6+7; typedef long long ll; ll tree[maxn<<2],lazy[maxn<<2]; int n,q,a,b,c,arr[maxn]; int ch; void pushdown(...

思路 询问1：快速幂就可以了。询问2：可以转化为求解同余方程，使用扩展欧几里得就可以求解，在gcd(y,p)|z的时候有解。询问3：重点要讲的BSGS算法(我习惯叫北上广深)。我们要求满足同余式的最小非负数x，暴力枚举x在[0,p)的范围内，在p非常大的情况下是会爆的。可以令x=mi-j，那么式子转化为了。为什么要这样转换？因为我们固定了m的情况下，i和j的取值都在，就可以把所有的x都表示出来，首先跑一遍j，用map存储所有，然后再从小到大跑i，找到同余的情况直接跳出即可。复杂度开了个根号。 代码 #include<bits/stdc++.h> using namespace st...

思路 这道题中，图的遍历起点必然是可控制的，如果起点不可控制，答案肯定是NO,NO的情况只需要从1~n找到第一个没被遍历过的数输出就可以了。因此，我们记录下每个节点的入度，那么就相当于从图中所有入度为0（且可以控制）的点开始拓扑排序，并记录访问节点即可。但是题目不保证是有向无环图，因此我们需要对环进行缩点处理。这个环有可能是途中的环，也有可能称为一个起点。对于中途的环，缩点之后我们并不需要知道这个点的花费，因为他们都可以从起点开始被控制。不确定起点的环，我们可以随意从一个点出发tarjan遍历，然后将该连通分量所需支付金额替换成环中最小的支付金额即可。（可在退栈中实现） 代码 #include...

思路 没学过数论的同学估计一开始是不会想到欧拉函数的。那么我们怎么去联想到这东西呢。这道题，我们只需要计算y>x的点（上三角），然后答案就是2*ans+1了。(上三角+下三角+斜率为1的点)我们现在通过找规律来看看n不同时斜率的一个情况(y/x):n=1,ans=0;n=2,ans=1,k=1/2n=3,ans=2,k=1/3,2/3n=4,ans=2,k=1/4,3/4（k=2/4已经被数过了）...凡是分子分母能约分的，前面都已经出现过，所以我们每次添加的数，分子分母都是互质的，那么我们可以把问题转化为对于一个数n,求小于n且与n互质的数的个数，即求欧拉函数。这样，我们就把二者结合起...

思路 没啥思考过程，照着题目跑bfs就过了。大概就是跑的时候记格子的花费和是否用过魔法。记录颜色时+1是因为比较方便区分白色。剪枝直接把同一格子花费大的剪掉就行了。正确性的大概考虑：若经过同一格子两次，用魔法的状态肯定是一样的，并且金币只会递增。（不知所云） 代码 #include<bits/stdc++.h> #define debug(x) cout<<"x="<<x<<endl #define int long long using namespace std; const int maxn=1e5+7; const i...

思路 在信息学奥赛数论一本通里面我愣是没搞懂题解的5544、14421、1288这些数是怎么来的，在网上找了很多博客才搞懂中国剩余定理的原理。总结一下步骤：（方程组形式为mod m意义下与a同余）求大模数M->对每个小模数M/m，求模m意义下的逆元i，那么M/mia就是满足方程的一个最小数，然后将每一个方程的最小数相加模M即可。两份代码上面是一本通的，下面是我理解之后手打AC的，希望方便各位理解。 代码 生肉版 //UVA756 Biorhythms #include<iostream> using namespace std; int main(){ int p,...

代码 读懂代码前需要掌握的芝士： 唯一分解定理 任意正整数都有且只有一种方式写出其素因子的乘积表达式。 约数和方程 对于已经分解的整数 有A的所有因子之和为 我们先记录素因子，然后利用约数和方程求解。这里有一个二分加速的过程，推导在代码里面。牛客上面有三道Sumdiv大家可以顺便A了。 思路 #include<iostream> using namespace std; const int mod=9901; typedef long long ll; ll A,B,k=0; ll p[20005],n[20005]; ll fpow(ll p, ll n){ //快速幂 ...

思路 大概就是区间DP，先枚举区间长度，长度为1时就是这个节点的分数。对于每一个区间枚举根节点，同时计算得分，那么[l,r]的最高得分是可以确定的，数据量很小，f[1,n]就是我们要求得的最高得分。我们记录了每个区间的根节点，要求输出前序遍历正常求就好了。 注释给的很详细了应该。 代码 #include<bits/stdc++.h> using namespace std; int a[50],f[50][50],g[50][50]; //f[i][j]表示区间[i,j]最高加分 //g[i][j]表示区间[i,j]的最优根节点 void shuchu(int l,int r...

思路 学艺不精，交splay结果WA了，还找不到问题。所以我还是用了vector写。保持vector是有序的，插入和删除的时候二分，复杂度很优。记得要清空vector。 代码 #include<bits/stdc++.h> //#define int long long using namespace std; int t,n,m,x; string str; vector<int>vt; signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>t; ...

思路 根据题目列出式子：(x+mt)-(y+nt)=pL其中：t是跳的次数，p是圈数差转化为：(n-m)t+Lp=x-y令a=n-m,b=L,c=GCD(a,b),d=x-y 有at+b*p=d要求的是t的最小整数解，转化为扩展欧几里得，求解同余方程就能得出答案。 代码 #include<bits/stdc++.h> #define int long long using namespace std; int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return ...

思路 最小生成树的板子题，前置知识：并查集以及Kruskal算法；答案要求输出最小生成树的边数（那肯定是n-1啊）以及最大权值的边（那肯定是最后连的那一条啊）因为做过最小生成树的课件，代码注释解释了很多，大家可以看看。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=300,maxm=20005; struct E{ int from,to,dis,next; bool operator <(const E b)const{ //用于排序边 return dis&...

思路 通过求出dis的交集来得到公共路径。然后重新建一个图。对x1，y1,x2,y2分别进行一次求最短路，交集部分（点的dis相同）进行rebuild，生成一个可拓扑排序求最长路径的DAG.因为做了课件，代码的注释写得很详细，这里就不细讲了。 题解 #include <bits/stdc++.h> using namespace std; const int maxn = 1505; const int maxm =1505*1505; struct Edge{ int from,to,next,val; int tag; //对边进行标记 }edge[ma...