题意： 给你一个数n，要你找一个数>0并且它的位数等于n，并且不能被它自己的数整除(比如23，不能被2,和3整除)。 思路： 一开始构造了一个2222(n-1个2)3,wa了两发(哭了)。后面想起一个定理，只有各位数之和能被3整除这个数才能被3整除，于是我们构造这样一个数233333(n-1个3)即可。因为2只能被偶数整数，排除，各位数之和永远不能被3整除，因为永远多了个2.然后提交就行了。 代码： #include<bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 1...

题意： 给你一个n* n的矩阵，还有一个k，要你找一个起点坐标，然后上下左右四个方向走k步，然后计算他们的和，使得这个和最大化。 思路： 一开始写了一个bfs，O(n^4)超时，然后改了一下。然后观察了一下最后我们要求的和是一个菱形，如果这个菱形内的和可以O(1)计算这题O(n ^ 3)就过了，但是菱形的和不太好算，我们让坐标轴旋转45°，这样就变成这个矩形，然后前缀和就可以计算了。旋转45度怎么弄？(x,y) -> (x + y - 1, n - x + y)，这样就可以了，通俗的讲坐标轴旋转45度就是让矩阵中所有对角线旋转45度，矩阵中所有对角线元素满足x + y 相等，然后相加他们...

题意： 给你n个饭店在横坐标轴上的位置，要你在这些饭店旁边建立k个仓库，使得所有饭店到最近的仓库距离之和最短，要你输出这个值。 思路： 这个题可以认为是管道问题的扩展版本，也可以认为是矩阵链乘的变种。 定义dp[ i ] [ j ]:表示一共i个仓库在[1, j] 这些饭店的最短距离和 转移方程：dp[ i ][ j ] = min(dp[i - 1] [k - 1] + dis[ k ] [ j ]) i取值[1,k]，j取值[i , j]，k取值[i , j]。 这里用到了dis[ i ] [ j ]:表示从第i个饭店到第j个饭店最短路径和(中位数原理即可) 注意： j不能取i + 1(j...

思路： 单调栈维护一个递增序列，需要处理一些小细节，比说前导0等等，具体思路写在代码上了。 代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; char s[maxn]; void solved(){ int k; scanf("%s",s + 1); int len = strlen(s + 1); cin>>k; stack<char>st; int cnt = 0; int i; for(i = 1; i <= len; i++...

题目描述： shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。 输入描述: 第一行两个整数n，k代表点数和颜色数； 接下来n-1行，每行两个整数x,y表示x与y之间存在一条边； 输出描述: 输出一个整数表示方案数（mod 1e9+7）。 示例1 输入 4 3 1 2 2 3 2 4 输出 39 备注: 对于30%的数据，n≤10, k≤3； 对于100%的数据，n,k≤300。 思路： 组合数学做法: 从[1,k]枚举所有联通块(联通块满足要求),然后求出每种联...

最近公共祖先LCA(lowest common ancestor) 在图论和计算机科学中，最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。 最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。 (取自维基百科对最...

题目描述  每年的BNU校赛都会有两次赛前培训，为此就需要去借教室，由于SK同学忙于出题，这个事情就由小Q同学来跑腿。SK同学准备从宿舍出发，把借教室的单子交给小Q同学让他拿去教务处盖章，但是何老师突然发现SK同学好像借错教室了，想抢在借教室的单子被送到教务处之前拦截下来。 现在把校园抽象成一棵n个节点的树，每条边的长度都是一个单位长度，从1到n编号，其中教务处位于1号节点，接下来有q个询问，每次询问中SK同学会从B号节点出发，到C号节点找到小Q同学并将借教室的单子交给他，然后小Q同学再从C号节点出发前往教务处，何老师会从A号节点出发开始拦截。 所有人在一个单位时间内最多走一个单位距离，只要何...

题意很好懂，就是一个长度为n的序列，s[i] 只可能是r,g,b，要你要满足就 j - i != k - j,并且s[i],s[j],s[k]两两不相同，并且i < j < k，的个数有多少个。 思路： 暴力O(n^3)模拟一遍铁超时，j - i != k - j 一开始一直在观察这个式子看能不能优化一下，事实上可以不管这个式子就一个区间[i,k]={B,R},那么我们在[i + 1,k - 1]这个区间找有多少个G就行了，需要考虑一下中点是否需要减掉，然后把所有的情况枚举出来就行了。这里用前缀和维护sum [ i ] [ 1 - 3 ]:表示从1到i有多少个R,B,G。 感觉写的...

题意：给你三个区间，要你在这三个区间选三条边使得它成为一个三角形。 思路：签到题，直接输出一个等腰三角形，b,c,c即可。 时间复杂度O(1) 代码： #include<bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 1e5 + 10; void solved(){ int t;cin>>t; while(t--){ ll a,b,c,d;cin>>a>>b>>c>>d; cout<<b<<...

题目大意： 给你一个长度为n的序列，要你找出形如aba这样的回文，其中a,b 可以等于0，并且最多只能出现两个不同字符。 思路： 注意到字符很少，只有200，可以从这里下手，先把[1,200]每个字符的前缀和求出来，再把相同字符的位置存起来，然后枚举200个数，再枚举每个数的长度的一半，然后在当前枚举数的中间找一个最多的一个单的字符这样就行了。需要预处理一下b=0这种情况，也就在只有一个字符时最多的是哪个字符。 代码： #include<iostream> #include<vector> #include<algorithm> using namespac...

思路：并查集基本操作了。。。c为1的先把他们并到同一个集合中，然后再检查c=0的情况，如果他们在同一个集合c又等于0说明矛盾。做这题的时候，出现好多小问题(上次写并查集是去年)，首先因为输入量很大，cin会超时，要用scanf，其次因为每次读入两个点所以maxn需要开两倍。就这个两个坑。另外注意到b=1e9这个数很多，开不了这么大，所以需要提前离散化一下。 代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 7; typedef long long int ll; struct node{ ...

思路：我觉得这个题目有点意思。。。。用一个简单的数学公式展开可以将O(n^2)降到O(n)实属牛皮。 sum1是ai的前缀和，sum2是ai ^ 2的前缀和     <mstyle displaystyle="true" scriptlevel="0"> <munderover>  ∑    i   =   1    n  </munderover> </mstyle>   \displaystyle\sum_{i=1}^{n}   i=1∑n​     <mstyle displaystyle=&q...

这是一个悲伤的夜晚，做题太慢了，导致d题甚至都没时间做了，早上起来发现C还被踩了。   题目大意： 给你一个n，还给你一个等式x + 2x + 4x + 8x + …+2^(k - 1)x = n,其中k(>1) 思路： 一个水题，因为题目保证答案有解，直接枚举k解这个一元方程即可。（一个水题写了20多分钟啊啊。。。还是做题太少） 代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; typedef long long int ll; void solved(){ int t;c...

代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; int a[1010]; bool vis[maxn]; int path[maxn]; int k,m; stack<char>st; bool flag = false; void dfs2(int dep,int s){ if(s == m){ stack<char>cur = st; stack<char>now; while(!cur.empty()){ now.push(cur.top...