A.Hossam and Combinatorics
算法本质
思维
题目大意
找出相差值最大的元素对（ij和ji算2对）数目。
思路推演
找最大值个数*最小值个数。
最大值 == 最小值情况特殊考虑。
B.Hossam and Friends
算法本质
思维
题目大意（改）
有n个人[1~n]，其中m对人有仇。
请问[l r]中无仇家的数组数目。
n、m <= 1e5思路推演
对于每个左端点，检查右端点的可行范围。
对于每对仇人，先初步确立一些左端点的范围。
然后从n~1，依次取小。
最后就得到了真实的可行范围，都加到ans里即可。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int R[maxn];
inline void solve()
{
//init
cin>>n>>m;
rep(i,1,n) R[i]=n;
while (m--)
{
int u, v;
cin>>u>>v;
if (u>v) swap(u, v);
R[u] = min(R[u], v-1);
}
//cal
int ans=0;
for (int i=n-1; i>=1; i--)
{
R[i] = min(R[i], R[i+1]);
ans += R[i] - i + 1;
}
cout<<ans+1<<endl; //因为i==n的还没加
return;
}C.Hossam and Trainees
算法本质
思维
题目大意
n个数字之间是否存在一对不互质。
n <= 1e5
元素 <= 1e9思路推演
直接可以想到用分解质因数来判断。
但是根号级别的判断方法是无法满足的，于是先处理部分素数（<=1e9根号），再分解质因数来优化。
值得注意的是，为了卡掉根号的做法，时间设置相对极限。
当时粗略地将1e5作为1e9根号替代，最后超时。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn];
map<int, int> mp;
void f(int x)
{
for (int su:prime) //prime用埃氏筛得到的，手动筛也是可行的
{
if (x%su==0)
{
while (x%su==0) x/=su;
mp[su]++;
}
}
if (x>1) mp[x]++;
}
inline void solve()
{
//init
cin>>n;
mp.clear();
rep(i,1,n)
cin>>a[i];
//cal
flag=0;
for (int i=1; i<=n; i++)
f(a[i]);
for (auto it:mp)
if (it.second>=2)
flag=1;
if (flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return;
}D.Hossam and (sub-)palindromic tree
算法本质
思维、dp
题目大意
具有n个节点的树，每个节点有一个字符，求树任意路径的最长回文子序列的最长值。
n <= 2e3思路推演
字符串的最长回文子序列是一个较为经典的dp问题。
二维dp：dp[l][r]表示l~r的字符串的最长回文子序列长度。
转移公式：s[l]==s[r] --> dp[l][r]=dp[l+1][r-1]+2s[l]!=s[r] --> dp[l][r] = max(dp[l+1][r], dp[l][r-1])
复杂度：O(n^2)
现在需要转移到树上，主要考虑的就是一手复用。
这样的不确定情况下，通常用记忆化搜索，而不是预处理。
思考：树上实现的较为困难的地方：方向。
前面的l+1 r-1在树上不明确，于是需要对每个点都预处理：对于任意点，如果其想向u靠近，其下一步应该如何走。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<int> edges[maxn];
int dp[maxn][maxn]; //dp[l][r]表示 l r的最长回文子序列长度
int nxt[maxn][maxn]; //nxt[]
int f(int l, int r)
{
if (l==r) return 1; //单个字符就是1
if (nxt[l][r] == r) return 1+(s[l]==s[r]); //2个字符也直接处理了
if (dp[l][r]>0) return dp[l][r]; //记忆化搜索
dp[l][r] = max(f(nxt[l][r], r), f(l, nxt[r][l])); //常规丢左丢右
if (s[l]==s[r]) //相等情况另算
dp[l][r] = max(dp[l][r], f(nxt[l][r], nxt[r][l]) + 2);
return dp[l][r];
}
void gravity(int u, int fr, int yuan) //gravity译为重力
{
nxt[u][yuan] = fr;
for (auto v:edges[u])
if (v!=fr)
gravity(v, u, yuan);
}
inline void solve()
{
//init
cin>>n>>s;
s = " " + s;
rep(i,1,n) edges[i].clear(); //清空
rep(i,1,n) rep(j,1,n) dp[i][j]=0;
rep(i,1,n-1)
{
int u, v;
cin>>u>>v;
edges[u].push_back(v);
edges[v].push_back(u);
}
//cal
for (int i=1; i<=n; i++) //预处理nxt[][]
gravity(i, 0, i);
int ans=0;
for (int u=1; u<=n; u++)
{
for (int v=1; v<=n; v++)
ans = max(ans, f(u, v));
}
//out
cout<<ans<<endl;
return;
}
评论 (0)