分析 牛牛和牛可乐的赌约     代码  #include<bits/stdc++.h> #define ll long long using namespace std; const int mod=1e9+7; int t; ll n,m; inline ll get(ll a,ll b) { ll res=1; for (;b;b>>=1,a=a*a%mod) if(b&1) res=(res*a)%mod; return res; } int main() { scanf("%d",&t); while(t--) { scanf("%lld%ll...

分析  题目中说只有距离为2的点才能产生联合权值，让我们画画图理解一下   这个时候我们发现所有的联合权值之和其实就是以每个点为根，其所有子树的权值两两的乘积之和。假设其中一个点为j，他对答案的贡献就是当前根的出j以外的儿子的权值总和乘节点j的权值   for (int i=head[x];i;i=e[i].nex) { int v=e[i].to; ans=(ans+a[v]*(sum-a[v]+MOD)%MOD)%MOD; //a[v]是每个节点的权值，sum是当前根所有子节点的权值和 } 至于最大值，还记得怎么求树的直径的吗，同理，我们记录一个ma与m，表示次大值与最大值，用一个变量记录...

分析  根据题目可以看出这是一棵典型的01字典树，要求树上路径的异或最大值，n<=1e5。我们不可能O(n^2)扫过，我们画个图分析一下: 当我们要求3与4之间的异或路径，第一个方法是倍增，但会超时。但是如果我们记录一个dis[i]表示i->1路径上的异或权值，那么3,4之间的异或权值就是dis[ 3 ] ^ dis[ 4 ] = 6 ^ 5 ^ 5 ^ 7,最近公共祖先的上面部分相当于被抵消了。    直接枚举每个点，在字典树上跑，求出答案。我们从高到低存入每一位的值，根据我们的贪心策略以及异或的性质，只要当前位数为c，在当前层数中存在一个权值为(bool)(c^1)的节点,那么...

前言 刚开始什么思路都没有，但是突然想到了一道题——换教室，似乎也是二分，然后运用到这一道题，似乎就明了了 分析  这道题的话，通过二分最小的w，是每一盆花的a[i]>=w，并且浇的天数小于等于m。这就是主要思路。  实现  题目中给出了一个w(刚开始我也不知所措啊QwQ)，然而我们想一想，设一个f[i]表示将[i,i+w-1]区间浇水的天 数，那么之后对于一个j，因为之前的第j-w盆肯定浇过，那么就可以减去那一盆的贡献，然后求出对于第j盆是否 还需要再浇。  代码 /*二分加差分*/ /* 每次二分一个最小值，算出使每一个a 都大于它至少要浇多少次，而之前(i-w)如果 有浇过，那么可...

题意  求1到n的所有路中的最小的第k+1长的路。  分析  题目中说，可指定免费修k条路，而最终的费用就取决于边权值第k+1大的边。所以可以二分其值，每次二分出一个mid，跑spfa，求出到n最少要免费牵多少根线。如果小于等于k条，说明这条边还可以更小。  代码 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<queue> #d...

解法一   看数据范围，以及一点分析，能够确定这是单源最短路，可选DJ与SPFA，但是图中存有负权边，只能SPFA了。 However   so，这里要用一个江湖人称“SLF”的优化，即当前节点到起点距离小于队首的时候，将此点插入队首，否则，正常插入队尾。感觉这种优化可能被用到的机会很少，但很可能正好解决掉了专门卡spfa的数据以及网格图。  解法一代码 #include<deque> #include<algorithm> #include<cstring> #include<string> #include<cstdio> usi...

题目分析  我的第一个想法是bfs(QwQ),不用说，肯定凉凉。 思考，对于一个点( i , j )，如果和小B的切比雪夫距离大于D，那么肯定可以转移到 ( i , j )的四个方向， 也可以停留原地。但是如果小于等于D时，肯定只能单方向转移或是停留原地 这样我们就可以写出dp方程了 设f[ t ] [ dir ][ i ][ j ]为第 t 秒，上一次从 dir 方向走到了点( i , j ),这样是500* 5 * 200 * 200,采用滚动数组 if(get(i,j)<=d) {//在范围内 for (int k=0;k<=4;k++) {//向四个方向扩展 if(k!=0...

翻译(口胡)  有一个n*m大小的健身房，每走到一个点(i,j)，都会消耗a[i][j]大小的卡路里，小西从(1,1)出发走到(n,m)，只 能向右走或向下走，小瓜从(n,1)出发走到(1,m),只能向右走或向上走,他们两人决定在某一个点会面且只进行一次 会面，那个点的卡路里不计入总卡路里。求出小西和小瓜可以消耗的最大总卡路里值。并且他们健身的速度不 同，即假设小西走了5步，小瓜可能只走了一步     分析  因为他们要会面，所以我们可以针对每个点。即如果在这个点会面，能消耗最多的卡路里。但是之后不能再会面 并且还要从这个点出发，那么我们可以定义四个方向——左上到右下，左下到右上，右上到左下，...

前言  初，遇题甚恐，不知何以解之。一暴以试，得AC，作此篇  分析  别学数据结构学傻了 我们对于每一个点，可以向左扩展最长能满足条件的区间，然后再向右扩展。但是如果不作些许操作，万一这个序列是10000个1，这样跑就是n^2，直接飞起(但是数据不太强，也可以过)。于是可以记录一个lm[i],rm[i]。lm[i]:下标i的数向左扩展的最远点的下标 rm[i]:下标i的数向右扩展的最远点的下标 原因就是，a|b,b|c,则a|c,就像我们当前求i点向左扩展，找到了j点，且a[j]%a[i]=0。那么满足a[k]%a[j]=0的点也一定满足a[k]%a[i]=0,所以这个时候就可以直接跳到lm...

前言  初见此题，便一贪为敬，不曾想，数据过强，需dp，作此篇，解此题QwQ   分析  可以发现，如果这个人要加入团队，一定是和[1,i],[2,i]...[i-a[i],i]这些人组队，并且当前的a[i]要小于等于i，那这里就可以记下一笔  dp[i]=max(dp[1~(i-a[i])])+1; 但是n>1e4,n^2肯定凉凉,于是我们开始思考，能不能去掉一重循环。可以知道如果我们存下dp[1~(i-a[i])]的最大值，就可以不用循环了  代码  #include<bits/stdc++.h> const int N=1e5+10; using namespace s...

翻译(qwq,看了好久的题)   输入n组数据,p,x,y,将其处理为x^=las,y^=las,las是上一次输出的答案，初始为1   1. 1 x y 将一个权值为y的新节点加到x节点的后面   2. 2 x y 求从点x到根节点的路径上求出最长的不下降子序列，且满足它的和不大于y(像下面这样)    分析  首先是因为他既可能加到1,节点后面，也可能会加到0节点后面，很难确定谁是根节点，所以在处理的时候，将所有询问的x统统加1。 对于二操作，因为他要求从一个节点到根节点的最长不下降子序列，那么说明在x点之前权值小于y的点都没用，那这时候我们就找到第一个权值大于等于y的节点，并将它作为x的...

A 数字计数  分析  较为基础，因为要最大最小，次大次小，可以先想到排序，但是不要忘了，数值中有重复的，所以还要去重。去重的方法有两种，一种是直接调用unique函数，另一种是遍历一遍将出现一次的计入数组   int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); n=unique(a+1,a+n+1)-a-1; printf("%d %d %d %d\n",a[n]-a[n-1],a[n]-a[2],a[n-1]-a[2],a[n-1]-a[1]);...

前言  看到这道题，如果范围稍小一点，可以尝试将两串构造出来，然后连在一起，运用后缀排序求出hei数组进行求解，但很可惜的是，l和r太大了。  思考  我们先手造一下串1 a2 aba3 abacaba4 abacabadabacaba...会发现中点左右的串是一样的，比如[1,7]=[9,15],[4,6]=[12,14] (下标从一开始)，也就是说如果左区间大于了某一个k，我们完全可以将其平移到左区间。如果要求的区间的右端点没有大于某一个中点，直接搜下去就可以了。如果和中点有交叉的话，这个时候就要分左右搜索，取最大值  代码  #include<iostream> #inclu...

前言(划重点)  1.题目要求n*(n-1)/2对，即不能重复2.答案是 max(v[i],v[j]) × dis(i,j) 的求和  解决方案   既然不能n方，那我们只好单独算出每头牛对于答案的贡献。所以可以按照v从小到大排序，这样可以直接通过求出这头牛与之前的牛的总距离求出答案。 总距离想一想我们怎么拆这个绝对值,因为我们只按照v的大小排序，没保证下标的有序。这时，我们试着拆一拆,假设有L头奶牛比当前i坐标小，R头比他的坐标大(R=i-1-L),用树状数组每次维护个数，以及坐标之和，求出小于当前下标的距离之和   代码  //#pragma GCC optimize(3,"inline"...