A - Yet Another Tetris Problem
这题一开始看错题了啊啊啊啊啊
总的来说就是看所有 $a_i$ 的奇偶性相不相同就行......
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[105];
int b[105][105];
int main()
{
int Test;cin>>Test;
while(Test--)
{
cin>>n;
int mx=0;
for(int i=1;i<=n;++i)cin>>a[i];
int op=(a[1]&1);
bool flag=1;
for(int i=1;i<=n;++i)
{
if(op!=(a[i]%2))
flag=0;
}
if(flag)puts("YES");else puts("NO");
}
return 0;
}
B - Yet Another Palindrome Problem
做法比较多，$O(n)$ 或者 $O(n^2)$ 的都可以。我用的 $O(n^2)$，直接枚举每个数，看这个数出现在最左边或者最右边的位置，不相邻就行。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[5005];
int main()
{
int Test;cin>>Test;
while(Test--)
{
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
bool flag=0;
for(int i=1;i<=n;++i)
{
int L=-1,R=-1;
for(int j=1;j<=n;++j)
{
if(a[j]==i)
{
L=j;
break;
}
}
for(int j=n;j;--j)
{
if(a[j]==i)
{
R=j;
break;
}
}
if(R-L>=2)
{
flag=1;break;
}
}
if(flag)puts("YES");
else puts("NO");
}
return 0;
}
C - Frog Jumps
直接统计最长的连续L就行，答案就是长度+1
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
char s[200050];
int main()
{
int Test;cin>>Test;
while(Test--)
{
scanf("%s",s+1);n=strlen(s+1);
s[n+1]=s[n+2]=0;
int ans=0,tmp=0;
for(int i=1;i<=n+1;++i)
{
if(s[i]=='L')tmp++;
else ans=max(ans,tmp),tmp=0;
}
cout<<ans+1<<'\n';
}
return 0;
}
D - Pair of Topics
写了个离散化+BIT......cjj写了个Treap2333
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[200050],b[200050];
ll ans;
ll t[500050];
map <int,int> h;
vector <ll> vec;int tot;
inline int lowbit(int x){return x&(-x);}
inline void change(int x,int val){while(x<=400000){t[x]+=val;x+=lowbit(x);}}
inline int query(int x){int ret=0;while(x){ret+=t[x];x-=lowbit(x);}return ret;}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i)
{
vec.push_back(a[i]-b[i]);
vec.push_back(b[i]-a[i]+1);
}
sort(vec.begin(),vec.end());
for(auto i:vec)
{
if(h[i])continue;
h[i]=++tot;
}
for(int i=1;i<=n;++i)
{
ans+=query(h[a[i]-b[i]]);
change(h[b[i]-a[i]+1],1);
}
cout<<ans<<endl;
return 0;
}
E - Sleeping Schedule
一道比较裸的dp...
设 $dp(i,j)$ 表示当前到第 $i$ 个数，总和对 $h$ 取模为 $j$ 的最大值，然后转移就两种情况取最大值。当 $j$ 在 $[l,r]$ 内时 $dp(i,j)++$ 。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,h,l,r;
int dp[2050][2050],f[2050][2050];
int ans;
int a[2050];
int main()
{
scanf("%d%d%d%d",&n,&h,&l,&r);
for(int i=1;i<=n;++i)cin>>a[i];
f[1][0]=1;
for(int i=1;i<=n+1;++i)
{
for(int j=0;j<h;++j)
{
if(f[i][j]==0)continue;
if(i>1&&j<=r&&j>=l)dp[i][j]++;
dp[i+1][(j+a[i])%h]=max(dp[i][j],dp[i+1][(j+a[i])%h]);
dp[i+1][(j+a[i]-1+h)%h]=max(dp[i][j],dp[i+1][(j+a[i]-1+h)%h]);
ans=max(ans,dp[i][j]);
f[i+1][(j+a[i])%h]=f[i+1][(j+a[i]-1+h)%h]=1;
}
}
cout<<ans<<endl;
return 0;
}
F - Maximum White Subtree
比较板的换根dp辣
我们将这棵树转成有根树，以 $1$ 为根
设 $f_u$ 表示 $u$ 从 $u$ 开始往下的 $u$ 的子树的最大值，$g_u$ 表示从 $u$ 往父亲走（不包括 $u$ ）的最大值。
翻译一下就是把含 $u$ 的子树搞成两部分，一部分是 $u$ 的子树内（含 $u$ ），一部分是 $u$ 的子树外（不含 $u$ ），然后两次dfs，第一次统计 $f_u$，即 $f_u=\sum max(0,f_v)$ ，然后第二次dfs就统计 $g_u$，即 $g_u=max(f_{fa}+g_{fa}-max(f_u,0),0)$
最后答案就是 $f_u+g_u$。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200050;
int f[N],g[N];
int n;
struct edge
{
int v,nxt;
}e[N<<1];
int a[N];
int head[N],ecnt;
inline void ad(int u,int v)
{
e[++ecnt].v=v;e[ecnt].nxt=head[u];
head[u]=ecnt;
}
void dfs1(int u,int fa)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs1(v,u);
if(f[v]>=0)f[u]+=f[v];
}
}
void dfs2(int u,int fa)
{
if(fa)g[u]=max(f[fa]-f[u]*(f[u]>=0)+g[fa],0);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa)continue;
dfs2(v,u);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
ad(x,y);ad(y,x);
}
for(int i=1;i<=n;++i)
{
if(a[i]==0)f[i]=-1;
else f[i]=1;
}
dfs1(1,0);
dfs2(1,0);
// for(int i=1;i<=n;++i)
// {
// printf("f[%d]=%d\n",i,f[i]);
// printf("g[%d]=%d\n",i,g[i]);
// }
for(int i=1;i<=n;++i)
{
printf("%d ",f[i]+g[i]);
}
return 0;
}
Comments NOTHING