第五题，树上染色问题。每个节点有一个值，初始状态树上节点全部为白色，每次只能选取两个相邻的节点染成红色，并且这两个节点的值的乘积是完全平方数。求最多能将多少个节点染红 #include <iostream> #include <bits/stdc++.h> const int maxn=1e5+100; #define int long long using namespace std; int dp[maxn][2];//dp[i][j], i,j 这个状态下能染红最多的节点 int a[maxn]; vector<int> g[maxn]; int n...

小红定义一个字符串是“好串”，当且仅当该字符串的长度不小于2，且首尾相同。一个仅包含小写字母的字符串，长度不超过200000。输出描述如果无法切割且该字符串本身不是好串，请输出-1。否则输出最终的好串数量。思路：正常dp转移是dp[i]=max(dp[i],dp[x]+1),&nbsp;a[x]=a[i],&nbsp;复杂度是O(n^2)的改进：dp[i]表示[1,i]中最大分割次数；trans[i-1]堆维护第i个字母后面一个位置（假设是x）dp[x]的最大值；dp[i]的转移位置由trans[a[i]]来维护，转移的过程中必须得保证转移的位置合法。（今天才发现不用堆也行，只要最大值就行）这题确实有点东西，第一次感受到笔试编程题带来的压迫感#includeusing&nbsp;namespace&nbsp;std;const&nbsp;int&nbsp;maxn=2e5+100;priority_queue&nbsp;trans[26];//以a[i]后面一格的最大dp值string&nbsp;s;int&nbsp;a[maxn];int&nbsp;dp[maxn],n;&nbsp;int&nbsp;main(){ cin>>s;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i=1;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]=s[i-1]-'a';&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;n=s.size();&nbsp;&nbsp;&nbsp;&nbsp;memset(dp,-1,sizeof(dp));&nbsp;&nbsp;&nbsp;&nbsp;dp[0]=0;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i=1;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(trans[a[i]].empty()){&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(dp[i-1]!=-1){//身后元素是合法状态&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;trans[a[i]].push(dp[i-1]);&nbsp;}continue;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;mx=trans[a[i]].top();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp[i]=mx+1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(dp[i-1]!=-1){//身后元素是合法状态&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;trans[a[i]].push(dp[i-1]);&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;cout<<dp[n]<<endl;

去年12月转去学算法，算法底蕴有点浅，只有一个还没做完的项目。获奖：ACM&nbsp;CCPC银以及很多华为比赛的奖，都和算法无关免笔试（不知道会不会影响最终成绩，早知道不偷懒了）5.22一面&nbsp;讲了项目，然后问我反向传播的原理。最后手撕算法，他问我平时刷不刷leetcode，我：？？？因为我是acm选手，所以不刷。然后他让我选一题写，我说直接上hard吧，他好像不信我，也不了解各种比赛，就选了一道中等题，我15分钟写完，调试4分钟通过。5.23主管面&nbsp;又讲了项目，这次讲得详细一点；然后就到了反问环节，问了一些华为开源项目的东西就结束了，30分钟左右。泡池子去了