Codeforces Round #831 (Div. 1 + Div. 2)
1.Problem - D - Codeforces
首先是一個結論就是如果除了起點終點以外你發現只要是還多一個格子你是可以把所有牌都任意移動的，
然后這個問題就很好解決了，你每次需要把最大的牌移動到終點所以你得把這些他上面的牌都移動開即可，
const int N = 1e5 + 100;
int n, m ,k;
int a[N];
void slove()
{
cin >> n >> m >> k;
for(int i = 1; i <= k; i++)
{
cin >> a[i];
a[i] = k - a[i];
}
vector<bool>st(k);
int sz = 0;
for(int i = 1, j = 0; j < k; j++)
{
while(!st[j]){
st[a[i++]] = true;
sz++;
}
if(sz > n * m -3){
cout <<"TIDAK"<< "\n";
return;
}
st[j] = false;
sz--;
}
cout << "YA" << "\n";
}
2.Problem - E - Codeforces
首先大值往上給肯定是更好的，
任意一個點的值肯定是子樹中的最小值的時候才是可以取的，
然后考慮父親是否會產生價值，首先如果是一條鏈，整條鏈肯定是都可以產生價值的，
如果是有多個兒子，父親是肯定不產生價值的，這很好理解，你父親最后一個取還是最小值，
一開始我認為整棵子樹都能產生價值但是第一個例子就是錯的，
所以就考慮子樹的貢獻，子樹的貢獻很明顯是可以相加的，這是很好理解的，你賦值的時候肯定是從最左子樹到最右子樹從小到大賦值
嘛，所以這以此點為根的另一個可以產生的價值就是所有子樹價值相加，然后兩者取最大值即可，
const int N = 1e5 + 100;
int n, f[N], d[N];
vector<int>b[N];
void dfs(int u)
{
d[u] = 1;
for(auto v : b[u])
{
dfs(v);
d[u] = max(d[v] + 1, d[u]);
f[u] += f[v];
}
f[u] = max(f[u], d[u]);
}
void slove()
{
cin >> n;
for(int i = 2; i <= n ; i++)
{
int fa;
cin >> fa;
b[fa].pb(i);
}
dfs(1);
cout << f[1] << endl;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/523188.html
標籤：其他