Preface
这场巨水无比，难得是周六下午的场次但是没忍住跑出去玩了，有点可惜
A~E都是秒出思路切了，但是C一个细节没写好炸了好久，如果现场打感觉罚时起飞照样上不了分
A. Factorise N+M
SB题，输入\(n\)输出\(n\)即可，显然\(2n\)一定是合数
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t) scanf("%d",&n),printf("%d\n",n);
return 0;
}
B. Jumbo Extra Cheese 2
SB题，由于\(x\)轴上的边长不可能减少，因此我们把每个长方形的较短边放在\(x\)轴上
考虑\(y\)轴上相邻的两个长方形遮盖掉的部分是\(2\times \min(a_i,a_{i+1})\)，不难发现直接排个序后答案就是中最优的
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x,y,a[N]; long long ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (ans=0,scanf("%d",&n),i=1;i<=n;++i)
scanf("%d%d",&x,&y),ans+=2LL*(x+y),a[i]=max(x,y);
for (sort(a+1,a+n+1),i=1;i<n;++i) ans-=2LL*a[i];
printf("%lld\n",ans);
}
return 0;
}
C. Bricks and Bags
刚开始猪脑过载写呲了，后来发现自己是个弱智
考虑答案的表达形式\(|w_1 – w_2| + |w_2 – w_3|\)，考虑若两个绝对值内的符号相同，答案就是\(|w_1-w_3|\)
这种情况显然不是最优的，因为我们可以把最大数和最小数单独扔到两个包里，这样就可以保证答案至少大于极差
因此我们考虑最优时两个绝对值内的符号不同，因此答案为\(|w_1+w_3-2\times w_2|\)
考虑枚举\(w_2\)，不难发现答案一定只有两种情况：
- \(w_1,w_2\)中有一个为最小数，不妨设为\(w_1\)，则\(w_2>w_3\)，因此\(w_3\)为\(w_2\)的后继
- \(w_1,w_2\)中有一个为最大数，不妨设为\(w_1\)，则\(w_2<w_3\)，因此\(w_3\)为\(w_2\)的前驱
排个序之后暴枚即可
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,a[N],ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (ans=0,sort(a+1,a+n+1),i=1;i<n;++i) ans=max(ans,a[n]+a[i+1]-a[i]*2);
for (i=2;i<=n;++i) ans=max(ans,a[i]*2-a[1]-a[i-1]); printf("%d\n",ans);
}
return 0;
}
D. Knowledge Cards
首先我们从大到小考虑每个数，统计出包括它本身在它上面的数的个数，设为\(pre\)
我们发现除去\((1,1),(n,m)\)后的位置有\(n\times m-2\)个位置，不难发现只要这些位置中存在至少一个空位，我们就可以把任意一个数移动到\((n,m)\)（类似小时候玩的一款游戏，Windows7系统自带有的玩）
因此只要判断\(pre\)和\(n\times m-2\)的大小关系即可，维护\(pre\)的过程用树状数组即可
#include<cstdio>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,m,k,a[N],pos[N];
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline void add(int x,CI y)
{
for (;x<=k;x+=lowbit(x)) bit[x]+=y;
}
inline int get(int x,int ret=0)
{
for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
}
#undef lowbit
}T;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=k;++i)
scanf("%d",&a[i]),pos[a[i]]=i,T.add(i,1);
bool flag=1; for (i=k;i>=1;--i)
{
if (T.get(pos[i])>=n*m-2) flag=0; T.add(pos[i],-1);
}
puts(flag?"YA":"TIDAK");
}
return 0;
}
E. Hanging Hearts
很simple的思维题
首先不难发现当某个点子树内除它之外的所有点都被删去后，这个点的值就是子树内所有点的值的\(\min\)
因此我们发现统计LIS的时候，贡献要么来自于子树内某个叶节点到这个点之间的路径，要么来自于这个点的儿子直接的贡献的和（这种情况这个点本身就不产生贡献）
形式化地，我们设\(g_i\)表示点\(i\)到子树内最远叶节点的距离，\(f_i\)表示把\(i\)的子树都删去后带来的LIS最大贡献
分别考虑以上两种贡献计算，很容易得到转移方程：
直接DFS即可
#include<cstdio>
#include<vector>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,x,f[N],g[N]; vector <int> v[N];
inline void DFS1(CI now=1)
{
for (int to:v[now]) DFS1(to),g[now]=max(g[now],g[to]); ++g[now];
}
inline void DFS2(CI now=1)
{
for (int to:v[now]) DFS2(to),f[now]+=f[to]; f[now]=max(f[now],g[now]);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=2;i<=n;++i) scanf("%d",&x),v[x].push_back(i);
return DFS1(),DFS2(),printf("%d",f[1]),0;
}
原文地址：http://www.cnblogs.com/cjjsb/p/16853899.html
