//505最长回文子串2.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://oj.daimayuan.top/course/22/problem/698给定一个长度为n的数组a1,a2,…,an，问其中的最长回文子串长度。定义子串al,al+1,…,ar为回文子串，当且仅当这个子串正着看和反着看是

NKOJ2110美丽的星空思路洪水填充(BFS)+多边形全等的判定。实现方法这道题比较复杂，分为三个步骤。用BFS求出有哪些星座并编号。两两判全等。多边形的全等判定定理：如果两多边形每两个点之间的距离和相等，则它们全等。如果两个多边形全等，就将新的打上旧的的标记。

题目问题描述小明和小芳出去乡村玩，小明负责开车，小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。例如：有5个路口，1号路口到2号路口为

51nod1051最大子矩阵和可以用前缀和容斥优化到\(O(n^4)\)，但是不够进行如下图操作：将每一列的数值都压缩到一维的数组上，就转换为求最大字段和问题，时间复杂度\(O(n^3)\)。看看代码就知道了。#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,m;

赛场上想到了n方枚举n方检验的4方做法，提前想好了实现细节一点点实现，最后一遍过了样例，还是很感动的赛场上超时了，但是交到Codeforces上能以900ms通过正解的确是n^3的，考虑优化枚举，确定1号节点在A后，对于每个1->x->y->1的三元环，要么x在B，y在C，要么x,y都在A，无论如何，x和y都不用被访问第

他说：O(n^3)是过不了滴一搜……6代码和题解没有实质区别：#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;inta[505][505],b[505][505],c[505][505];intmain(){ srand(time(NULL)); intn; ios::sync_with_stdio(0); cin.tie(0); while(cin

原题链接题解首先，考虑如何分配卫星电话使得\(D\)最小是比较困难的，所以我们考虑怎样的D可以使得卫星电话个数不小于联通块个数由于D越小，联通块个数也就越小，所以具有单调性，考虑二分优化：最后的答案，一定是所有连通块内部，距离最长的树边（即失去该边之后，联通块变得不连通），由此

link这里讲两种做法，一个在线，一个离线。在线我们分别考虑前缀和后缀。有一个比较重要的结论，就是把\(s\)按照字典序排序以后，相同前缀的出现位置（其实就是rank）是连续的。\(s\)翻过来，相同后缀的也是连续的。这样我们就可以求出每一个询问前缀和后缀对应的区间是什么，然后就要求

#include<bitsstdc++.h>#definelllonglong#definemaxn1000005usingnamespacestd;structnod{ intl,r,v; nod(){} nod(inta,intb,intc){l=a;r=b;v=c;}};intn,q;intnum[505][505];lldp[505][505];vector<nod>now;lldfs(intl,intr

思路这道题的思路其实是根据样例图片来的。首先第一张：这张图片可以得知$n$个点没有环的时候最少需要$n-1$个点。再看第二张：这个图确实很难思考，但稍微思考一下如果我们把含有一个强连通分量的图变成一整个强连通图。这个图的边数不就变成$n$了吗？来推一下

原题链接题解说用k种颜色，没说用少于k种code#include<bits/stdc++.h>usingnamespacestd;vector<int>G[505];intvis[505]={0};intcolor[505]={0};intv,e,k,n;intsolve(){for(inti=1;i<=v;i++){for(autonext:G[i]){

原题链接题解复杂图论题做多了这种题不会做了直接模拟即可，标记被摧毁的城市，然后遍历所有城市，能一次性搜索到的城市是一个城市群，累积有几个城市群code#include<bits/stdc++.h>usingnamespacestd;vector<int>G[505];intvis[505]={0};intdes[505]={0};voidss(intnow

原题链接题解确定起点和终点，求救援人数最长，路径最短的路径，只需要集群算法中优先队列中重载比较符修改一下就就行，由于数据量很小，所以输出路径的时候搜索就行（最优解唯一）code#include<bits/stdc++.h>usingnamespacestd;structnode{intto,val;};vector<node>G[505

思路首先想到一个\(n^{4}\)的dp，观察数据范围，发现这应该是一个\(n^{3}\)的算法，考虑如何优化。首先把转移方程写出来\(dp_{i,j}=\sum_{0\leii\lei-1,0\lejj\lej-1,\overline{a_{ii+1}...a{i}}\le\overline{b_{jj+1}...b{j}}}dp_{ii,jj}\),发现都不太好优化。首先枚举\(i\),\(

做题顺序：\(\texttt{B}\to\texttt{A}\to\texttt{C}\to\texttt{D}\to\texttt{E}\)A.牛奶首先可以发现，除了全部都是\(\texttt{L/R}\)的情况，其他的情况一定可以把数组分割成几段全部都是\(\texttt{L,R}\)的段。像是这样：\(\texttt{RRRLLRLLL}\)如果当前段是\(\texttt

五505.火柴排队(归并排序|离散化)思路：先将两组数组按(2314->2013;3214->2103)规则排序，然后使用c数组建立双方的映射，从c[ai[i]]=bi[i]，接着就是使用归并排序求c数组的逆序对即交换次数。importjava.util.*;publicclassMain{privatestaticint

这套题我答的很失败。没有按照题目的难度去答题，前期浪费了不少时间。题目：A-字符画题解：思维、模拟。这道题我的通过率为62.5，没有过的原因是因为对细节的处理和把控不到位，对一些点忽视，我也记录了搜索的过程，但没有把搜索过的点消掉，而且没有找到最好的顺序去解答这道题，我是按照横的

原题链接题解非常抽象的缩点大概思路：搜索缩点成有向图，求该点的入度和出度，最后答案一定是\(max(in,out)\)总之很抽象code#definelllonglong#include<bits/stdc++.h>usingnamespacestd;inlinevoidread(ll&x){x=0;llflag=1;charc=getcha

原题链接题解1.当存在某个矩阵符合题意时，所有小于该矩阵的矩阵都符合题意这是我们就可以想到用双指针code#include<bits/stdc++.h>usingnamespacestd;inta[505][505]={0},sum[505][505]={0};intn,m,k;intcheck(intdown,intright,intup,intleft){returnsu