Codeforces Round 627 (Div. 3)
A. Yet Another Tetris Problem
解题思路:
最终所有位置减去的数是相同的，也就是说能否通过\(+2\)的方式使所有数相同。
即如果存在两个数之间的差为奇数，那么就不可能同时为\(0\)。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
scanf("%d",&n);
vector<int> a(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i = 1;i<=n;i++)
{
for(int j = i + 1;j<=n;j++)
{
if(abs(a[i] - a[j]) & 1)
{
puts("NO");
return;
}
}
}
puts("YES");
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
B. Yet Another Palindrome Problem
解题思路:
如果存在两个相同数不相邻，即有解。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
scanf("%d",&n);
vector<int> a(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
}
vector<int> f(n + 1,0);
for(int i = 1;i<=n;i++)
{
if(f[a[i]])
{
if(i - f[a[i]] > 1)
{
puts("YES");
return;
}
}
else
{
f[a[i]] = i;
}
}
puts("NO");
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
C. Frog Jumps
解题思路:
想要跳到终点只能通过\(R\),如果存在两个相邻的\(R\)无法跳到，那么一定跳不到\(n + 1\)。
所以取相邻\(R\)距离的最大值即可。
注意:起点和终点也可算作\(R\)。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
string s;
cin>>s;
s = 'R' + s + 'R';
n = s.size();
int last = 0;
int ans = 0;
for(int i = 0;i<=n;i++)
{
if(s[i] == 'R')
{
ans = max(ans,i - last);
last = i;
}
}
printf("%d\n",ans);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
}
D. Pair of Topics
解题思路:
\[\begin{align*}
a_i + a_j > b_i + b_j\\ \tag{1}
a_i - b_i > b_j - a_j\\ \tag{2}
b_i - a_i < a_j - b_j
\end{align*}
\]
由公式\((1)\)可知，我们分别记录\(a_i - b_i,b_i - a_i\)，对\(b_i - a_i\)进行排序后，二分即可求取对于\(a_i-b_i\)有多少个合法对。
注意，若\(a_i > b_i\)，那么答案要去除自己那一个。
本题要求\(i < j\).
根据公式\((2)\),我们不难发现，在全局二分取答案的时候，如果我们统计到了更小编号\(k,(k < i)\)对自身的贡献，那么其实讨论\(k\)的时候，一定有\(i\)对\(k\)的贡献。
也就是说，如果每个位置都讨论全局二分取答案，那么统计出来的总贡献一定是对于\(i < j\)的答案的两倍。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
scanf("%d",&n);
vector<int> a(n + 1),b(n + 1);
vector<int> v;
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i = 1;i<=n;i++)
{
scanf("%d",&b[i]);
v.push_back(b[i] - a[i]);
}
sort(v.begin(),v.end());
ll ans = 0;
for(int i = 1;i<=n;i++)
{
int res = a[i] - b[i];
ll l = -1;
ll r = v.size();
while(l + 1 < r)
{
int mid = l + r >> 1;
if(v[mid] < res)
{
l = mid;
}
else
{
r = mid;
}
}
l ++;
if((a[i] - b[i]) > (b[i] - a[i]))
{
l --;
}
// cout<<i<<' '<<l<<endl;
ans += l;
}
printf("%lld\n",ans / 2);
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
}
E. Sleeping Schedule
解题思路：
\(f[i][j]:为前i次睡眠中，提前一个小时醒来了j次的好睡眠数量\)。
我们可用前缀和\(s[i]\)记录正常睡眠\(i\)次的时间，如果早起了\(j\)次，那么当前时间\(-j\)即可。
状态转移子集有两种，早起和没早起。
早起:\(f[i][j] = max(f[i][j],f[i-1][j-1] + check(s[i] - j))\)；
没早起:\(f[i][j - 1] = max(f[i][j-1],f[i-1][j-1] + check(s[i] - (j - 1)))\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n,h,l,r;
void solve()
{
scanf("%d %d %d %d",&n,&h,&l,&r);
vector<int> a(n + 1),s(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i] = s[i-1] + a[i];
}
auto check = [&](int x) -> int
{
int t = x % h;
if(t >= l && t <= r)
{
return 1;
}
return 0;
};
vector<vector<int>> f(n + 1,vector<int>(n + 1));
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=i;j++)
{
//Ìáǰ˯
f[i][j] = max(f[i][j],f[i-1][j-1] + check(s[i] - j));
//²»Ìáǰ˯
f[i][j-1] = max(f[i][j-1],f[i-1][j-1] + check(s[i]- (j - 1)));
}
}
ll ans = 0;
for(int i = 0;i<=n;i++)
{
ans = max(ans,(ll)f[n][i]);
}
printf("%lld\n",ans);
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
}
F. Maximum White Subtree
解题思路:
换根DP。
第一次\(dfs\)求取一个有根树中每个结点的最大贡献。得到\(ans[1]\)。
\[ans[u] = (a[u]?1:-1) + \sum_\limits{v \in children(u)} max(0,ans[v])
\]
第二次\(dfs\)换根，将已得到答案的父节点转换为子节点。
\[\begin{align*}
ans[v] = ans[v] + max(0,(ans[u] - max(ans[v],0))
\end{align*}
\]
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
int n;
int k;
void solve()
{
scanf("%d",&n);
vector<int> a(n + 1);
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
}
vector<vector<int>> adj(n + 1);
for(int i = 1;i<n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> ans(n + 1);
auto dfs1 = [&](auto self,int u,int p) -> void
{
if(a[u])
{
ans[u] = 1;
}
else
{
ans[u] = -1;
}
for(auto v : adj[u])
{
if(v == p)
{
continue;
}
self(self,v,u);
if(ans[v] > 0)
{
ans[u] += ans[v];
}
}
};
dfs1(dfs1,1,-1);
auto dfs2 = [&](auto self,int u,int p) -> void
{
for(auto v : adj[u])
{
if(v == p)
{
continue;
}
int t = 0;
if(ans[v] > 0)
{
ans[u] -= ans[v];
t = ans[v];
}
if(ans[u] > 0)
{
ans[v] += ans[u];
}
self(self,v,u);
ans[u] += t;
}
};
dfs2(dfs2,1,-1);
for(int i = 1;i<=n;i++)
{
printf("%d ",ans[i]);
}
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
}