Codeforces Global Round 19思路分享
Codeforces Global Round 19
老天赏脸，又让我涨了一波分。。。
A. Sorting Parts
首先我们可以发现，如果序列本来就有序的话，那么无论我们选择哪个点重排最终还是有序的。考虑一个序列至少存在一个逆序对，那么我们完全可以将这个逆序对分开，这样的话，这个逆序对一定还存在，那么就是YES了。
B. MEX and Array
发现n才100，果断DP，直接设f[i]表示前i个数的答案即可，之后暴力枚举转移即可。
C. Andrew and Stones
首先考虑因为选择的中间的石头个数至少是偶数的话，那么它恰好就能分发到1和n中。倘若是奇数，那么它需要别人“施舍”个它一个石头，凑成偶数，这样的话，就可以恰好分完。考虑什么样的情况无解。2到n-1的石头中，无人可给予，且有奇数块的时候，这个时候无法完成。否则若存在石头可给予，那么整个中间的石头一定可以被送走完。注意特立n=3的情况，因为自己不能给予给自己。
点击查看代码
#include
#define ll long long
#define db double
using namespace std;
const int N=1e5+10;
int T,n,a[N],b[N];
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
if(n==3)
{
if(a[2]%2==1) puts("-1");
else printf("%lld\n",a[2]/2);
continue;
}
int cnt1=0,cnt0=0;
ll ans=0;
for(int i=2;i D. Yet Another Minimization Problem
我们把括号拆开的话，发现无论换与不换，平方项都是不变的，变得都是2ab的乘积项，通过这个我们可以发现，我们其实只需要保留前面的和即可。直接设dp，f[i][j]表示前i项，a的和为j的最小值。
暴力转移即可。
点击查看代码
#include
#define ll long long
#define db double
using namespace std;
const int N=110,M=10010,INF=1e9;
int T,n,a[N],b[N],sum[N],f[N][M];
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
scanf("%d",&b[i]);
sum[i]=sum[i-1]+a[i]+b[i];
}
for(int i=1;i<=n;++i)
for(int j=0;j<=sum[n];++j) f[i][j]=INF;
f[1][a[1]]=0;f[1][b[1]]=0;
for(int i=2;i<=n;++i)
for(int j=0;j<=sum[i-1];++j)
{
f[i][j+a[i]]=min(f[i][j+a[i]],f[i-1][j]+2*j*a[i]+2*(sum[i-1]-j)*b[i]);
f[i][j+b[i]]=min(f[i][j+b[i]],f[i-1][j]+2*j*b[i]+2*(sum[i-1]-j)*a[i]);
}
int ans=INF;
for(int j=0;j<=sum[n];++j) ans=min(ans,f[n][j]);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j) ans+=a[i]*a[i]+b[i]*b[i]+a[j]*a[j]+b[j]*b[j];
printf("%d\n",ans);
}
return 0;
}
E. Best Pair
结束前1分多钟交上去，没想到直接过了，始料未及....
首先我们肯定要将输入的数据进行整理，离散化，统计个数...统计每个数出现的个数即原本的值。之后考虑最大的f(u,v)，由于是(cntx+cnty)?(x+y).的关系，我们观察到，在cnt相等的情况下，本身的权值越大越好，所以我们可以想到将所有的数按照cnt分组，之后考虑这样分组的话，组数最多是sqrt(n)的。考虑答案一定是某一组内的两个数的结果，要么是某两个不同组内的两个数的结果过。先考虑第一个，同组内的话，我们依次枚举每一个数，考虑它的另一个数，直接按照权值从大到小枚举，找到第一个合法的之后就可以直接break了，因为后面的一定没这个优。同理，两组的也这么做。考虑这样做的复杂度，由于坏的匹配只有m个，所以我们最多把这m个匹配找完就不会做无用功了。总的复杂度为nlogn。由于我太懒，当时又太紧张，离散化，没有预处理，导致我写的代码是nlog^2,不过还是过了，谢天谢地...
点击查看代码
#include
#define ll long long
#define db double
using namespace std;
const int N=3e5+10;
int T,n,m,a[N],b[N],num,cnt[N];
struct wy{int val,cnt;}q[N];
mapmp[N];
inline int find(int x){return lower_bound(b+1,b+num+1,x)-b;}
vector >v[N];
inline bool cmp(wy a,wy b)
{
if(a.cnt==b.cnt) return a.val>b.val;
return a.cntx=v[i][j],y=v[i][k];
if(mp[find(x.first)].find(find(y.first))!=mp[find(x.first)].end()) continue;
ans=max(ans,(ll)(x.first+y.first)*(y.second+x.second));
break;
}
}
for(int j=i+1;j<=tot;++j)
{
for(int l=0;lx=v[i][l],y=v[j][k];
if(mp[find(x.first)].find(find(y.first))!=mp[find(x.first)].end()) continue;
ans=max(ans,(ll)(x.first+y.first)*(y.second+x.second));
break;
}
}
}
}
printf("%lld\n",ans);
}
return 0;
}
F. Towers
看到题，经过一番思索后发现这个题有几个关键的点：
1.最优答案一定是只在度数为1的点上设置塔楼。
2.整个树中权值最大的点比较关键。
首先我们可以想象出某个点x的权值最大为\(h_{max}\)，那么也就是说必定会有某两个度数为1的点，x在这两个点的路径中，这两个点的\(e_i\)都为\(h_{max}\)。我们可以干脆的以权值最大的点为根。那么对于当前树中某个点i，他能够收到信号的条件，他在某两个度数为1的路径中，且这两个点的\(h_i\)都大于等于\(h_i\)。考虑到我们在最开始时已经设置了两个点的权值为\(h_max\)。那么当前点\(i\)一定能通过某种路径到达其中某个点，接下来我们只要保证它在子树内的某个叶子节点的\(e\)>=\(h_i\)即可。最初我们可以将所有度数为1的地点都设为他们初始的\(h_i\)。之后网上做dp，保留当前节点x的所有叶子节点设定的最大的\(e_i\)，然后比大小，显然我们让原本中最大的\(h_i\)修改最优。至于初始确定的最大的两个节点。我们可以最后确定。
点击查看代码
#include
#define ll long long
using namespace std;
const int N=2e5+10;
int n,h[N],root,f[N],mx;
ll ans;
vectorson[N];
inline void dfs(int x,int fa)
{
int ch=0;
for(auto y:son[x])
{
if(y==fa) continue;
ch++;
dfs(y,x);
f[x]=max(f[x],f[y]);
}
if(x!=root&&h[x]>f[x])
{
ans+=h[x]-f[x];
f[x]=h[x];
}
if(x==root)
{
if(ch==1) ans+=((f[x]>=h[x])?0:(h[x]-f[x]))+h[x];
else
{
int mx1=0,mx2=0;
for(auto y:son[x])
{
if(f[y]>mx1) mx2=mx1,mx1=f[y];
else if(f[y]==mx1) mx2=mx1;
else mx2=max(mx2,f[y]);
}
ans+=((mx1>=h[x])?0:(h[x]-mx1))+((mx2>=h[x])?0:(h[x]-mx2));
}
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&h[i]);
if(h[i]>mx) mx=h[i],root=i;
}
for(int i=1;i