第五题，树上染色问题。每个节点有一个值，初始状态树上节点全部为白色，每次只能选取两个相邻的节点染成红色，并且这两个节点的值的乘积是完全平方数。求最多能将多少个节点染红 #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), a[x]=a[i], 复杂度是O(n^2)的改进：dp[i]表示[1,i]中最大分割次数；trans[i-1]堆维护第i个字母后面一个位置（假设是x）dp[x]的最大值；dp[i]的转移位置由trans[a[i]]来维护，转移的过程中必须得保证转移的位置合法。（今天才发现不用堆也行，只要最大值就行）这题确实有点东西，第一次感受到笔试编程题带来的压迫感#include<bits/stdc++.h>using namespace std;const int maxn=2e5+100;priority_queue<int> trans[26];//以a[i]后面一格的最大dp值string s;int a[maxn];int dp[maxn],n;int main(){cin>>s;for(int i=1;i<=s.size();i++){a[i]=s[i-1]-'a';}n=s.size();memset(dp,-1,sizeof(dp));dp[0]=0;for(int i=1;i<=n;i++){if(trans[a[i]].empty()){if(dp[i-1]!=-1){//身后元素是合法状态trans[a[i]].push(dp[i-1]);}continue;}int mx=trans[a[i]].top();dp[i]=mx+1;if(dp[i-1]!=-1){//身后元素是合法状态trans[a[i]].push(dp[i-1]);}}cout<<dp[n]<<endl;

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