CodeChef December Challenge 2019 Division 2 小结_综合

背景

打完这场 $rating$ 终于上 $1800$ 了，下个月可以打 $Div~1$ 了~

虽然连 $Div~2$ 都不一定能 $AK$ ，但是打 $Div~1$ 总归要好一点吧。

这次做得比较急，最后一题然而根本没有看……但是最遗憾的还是 $T7$ ，一不小心就脑残了QAQ

在此记录一下前 $7$ 题的做法。

正题

T1

大水题，没啥好说的。

#include <cstdio>
#include <cstring>int T,n,score[20];
int max(int x,int y){return x>y?x:y;}int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);memset(score,0,sizeof(score));for(int i=1,x,y;i<=n;i++)scanf("%d %d",&x,&y),score[x]=max(score[x],y);int sum=0;for(int i=1;i<=8;i++)sum+=score[i];printf("%d\n",sum);}
}

T2

显然只有两个 $0$ 或者是两个 $2$ 可以满足 $a+b=a\times b$ ，所以统计一下 $0$ 的个数和 $2$ 的个数就可以了。

#include <cstdio>
#include <cstring>int T,n,zero,two;int main()
{scanf("%d",&T);while(T--){scanf("%d",&n);zero=two=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);if(x==2)two++;if(x==0)zero++;}printf("%d\n",(two-1)*two/2+(zero-1)*zero/2);}
}

T3

题目大意： 找出两个下标不完全相同的子序列，并且两个子序列完全相同，要使得两个子序列的下标中相同的数最多。

找到原序列中两个最接近的字母即可，设他们的下标分别为 $x,y$ ，那么答案就是 $x+(n-y)$ 。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int T,n,last[1010],ans;
char s[100010];int main()
{scanf("%d",&T);while(T--){scanf("%d %s",&n,s+1);ans=0;memset(last,0,sizeof(last));for(int i=1;i<=n;i++){if(last[s[i]]!=0)ans=max(ans,n-i+last[s[i]]);last[s[i]]=i;}printf("%d\n",ans);}
}

T4

要求整个 $B$ 序列都变为 $0$ 需要操作多少次，那么只需要找出 $B$ 序列中活最久的 $1$ 即可。

对于一个处于 $i$ 位置的 $1$
假如他要活过第一轮，就需要此时 $A_i=1$
假如他要活过第二轮，那么就需要此时 $A_{i-1}=1$ ，即原序列中 $A_{i-1}~xor~B_{i-1}=1$
假如他要活过第三轮，那么就需要此时 $A_{i-2}=1$ ，即原序列中 $A_{i-2}~xor~B_{i-2}=1$
……

所以我们只需要扫一遍就好了。

代码如下：

#include <cstdio>
#include <cstring>int T,n,m;
char s1[100010],s2[100010];
int max(int x,int y){return x>y?x:y;}int main()
{scanf("%d",&T);while(T--){scanf("%s %s",s1+1,s2+1);n=m=0;int len1=strlen(s1+1),len2=strlen(s2+1),tot=0,ans=0;for(int i=1;i<=len2;i++)if(s2[i]!='0'){ans=1;break;}if(len1>len2)//让短的序列向右对齐长的序列{for(int i=1;i<=len1-len2;i++)if(s1[i]=='1')tot++; else tot=0;for(int i=1;i<=len2;i++)if(s1[i+len1-len2]==s2[i]){if(s2[i]=='1')ans=max(ans,tot+2);tot=0;}else tot++;}else{for(int i=1;i<=len2-len1;i++)if(s2[i]=='1')tot++; else tot=0;for(int i=1;i<=len1;i++)if(s1[i]==s2[i+len2-len1]){if(s1[i]=='1')ans=max(ans,tot+2);tot=0;}else tot++;}printf("%d\n",ans);}
}

T5

这题要求出能异或出多少种不同的值，其实只需要关注 $A,B$ 序列中 $1$ 的个数即可。

不妨设异或出来的序列为 $C$ ，求出上面那个东西之后，我们就可以枚举 $C$ 序列中 $1$ 的个数，对于枚举出的每个个数 $i$ ，用基本的排列组合只是就可以算出，含有 $i$ 个 $1$ 的 $C$ 序列的个数为 $\frac {n!} {i!(n-i)!}$ ，然后全部加起来即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 200010int T,n,len,a,b;
char s[maxn];
ll ans=0;
ll ksm(ll x,int y)
{ll re=1;while(y){if(y&1)re=re*x%mod;x=x*x%mod;y>>=1;}return re;
}
#define inv(x) ksm(x,mod-2)
ll fac[maxn];
void work()
{fac[0]=1;for(int i=1;i<=maxn-10;i++)fac[i]=fac[i-1]*i%mod;
}int main()
{work();scanf("%d",&T);while(T--){scanf("%d %s",&n,s);len=strlen(s);ans=a=b=0;for(int i=0;i<len;i++)if(s[i]=='1')a++;scanf("%s",s);len=strlen(s);for(int i=0;i<len;i++)if(s[i]=='1')b++;//abs(a-b) 和 n-abs(a-(n-b)) 分别是C序列中1的个数的下限和上限for(int i=abs(a-b);i<=n-abs(a-(n-b));i+=2)//注意这里是+2，想想就能理解ans=(ans+fac[n]*inv(fac[i])%mod*inv(fac[n-i])%mod)%mod;printf("%lld\n",ans);}
}

T6

题目大意： 删掉最少的区间使得剩下的区间分成两块。（有交集的在同一块中）

你可以看作每个区间覆盖了一段点，然后你找到被覆盖次数最少的点，把覆盖这个点的所有区间删掉即可，但是要注意，删完之后要保证左边和右边分别都还有区间。

以及要维护的点是指相邻两个位置之间的那个空隙，感性理解一下就好。然后维护覆盖次数用差分数组或线段树即可。

还有一个坑点， $subtask3$ 不能对询问离散化，否则会超时，然后就只能用差分数组来维护。

代码如下：

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 2000010int T,n,b[maxn];
int l[maxn],r[maxn],f[maxn];
int sum1[maxn],sum2[maxn];
map<int,int>Map;int main()
{scanf("%d",&T);while(T--){Map.clear();scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d %d",&l[i],&r[i]),b[2*i-1]=l[i],b[2*i]=r[i];sort(b+1,b+2*n+1); int tot=0;if(b[2*n]<=1000000){for(int i=1;i<b[2*n];i++)sum1[i]=sum2[i]=f[i]=0;for(int i=1,x,y;i<=n;i++)x=l[i],y=r[i],f[x]++,f[y]--,sum1[x]++,sum2[y]++;for(int i=1;i<b[2*n];i++)sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1];int sum=0,ans=999999999;for(int i=1;i<b[2*n];i++){sum+=f[i];if(sum<ans&&sum2[i]>0&&sum1[i]<n)ans=sum;}if(ans>=n-1)printf("-1\n");else printf("%d\n",ans);}else{for(int i=1;i<=2*n;i++)if(b[i]!=b[i-1])Map[b[i]]=++tot;for(int i=1;i<tot;i++)sum1[i]=sum2[i]=f[i]=0;for(int i=1,x,y;i<=n;i++)x=Map[l[i]],y=Map[r[i]],f[x]++,f[y]--,sum1[x]++,sum2[y]++;for(int i=1;i<tot;i++)sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1];int sum=0,ans=999999999;for(int i=1;i<tot;i++){sum+=f[i];if(sum<ans&&sum2[i]>0&&sum1[i]<n)ans=sum;}if(ans>=n-1)printf("-1\n");else printf("%d\n",ans);}}
}

T7

题目大意： 给出一棵树，你有 $n$ 个点权和 $n-1$ 个边权，你可以用一枚硬币来修改一个点权，现在要求用最少的硬币，并且存在一种方案，将这些点权和边权分别放到点上和边上，满足对于任意一条边，它的权值小于等于它连接的两个点的权值。

我想了半天，觉得貌似难以构造，但是突然脑瓜子灵光一现：欸？莫不是二分答案？

发现这里有一个小贪心：消耗硬币肯定是把权值最小的给改成无穷大。也就是说，在消耗硬币数确定的情况下，我是已经知道要改那些点权的了。

想到这里更加激动：操作这么流畅，肯定是正解啊！

然后又想了半天：消耗硬币数已知的情况下，怎么判断是否存在一种放置方案呢？换言之，需要找到最优的放置策略。

十几分钟后，灵光二现——这个放置策略也是可以贪心的：首先找到度最大的点，然后在这上面放最大的点权，然后把他连向的点加入到一个堆里面，以后每次就选出堆里面度最大的点 $x$ ，然后重复上面的操作即可，然后对于连接 $x$ 和它的父亲之间的父子边，我们把最大的边权放上去。

这个策略有两个好处：

每次选的点的度都是最大的，所以可以让大的点权满足尽可能多的边
每次将最大的边权放到父子边上是必然的选择，假如这对父子不能满足这个边权，那么后面显然也不可能有能满足这个边权的父子了。

此时离比赛结束还有半小时，我一波操作之后反手一个 $Submit$ ， $50$ 分，ok，凉了，比赛结束。

我心想，这么优秀的一个 $O(nlog^2n)$ 做法，怎么给你 $10^5$ 的数据卡掉了呢？

然后第二天文化课上，我才发现我昨天脑子可能没水了——贪心策略都出来了，还二分个什么劲啊？？

到了上机的时候，随手就 $AC$ 了……

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
#define maxn 100010
#define inf 2000000000int T,n,l,r,st;
struct edge{int y,z,next;};
edge e[maxn<<1];
int first[maxn],len;
void buildroad(int x,int y)
{e[++len]=(edge){y,-1,first[x]};first[x]=len;
}
int w_v[maxn],w_e[maxn],du[maxn];
bool cmp(int x,int y){return x>y;}
struct par{int x,from;par(int y,int z):x(y),from(z){}bool operator <(const par b)const{return du[x]==du[b.x]?(x<b.x):(du[x]>du[b.x]);}
};
set<par> s;
bool v[maxn];
int work()
{int now_v=1,now_e=1,tot=0;s.clear();s.insert(par(st,-1));memset(v,false,sizeof(v));v[st]=true;if(w_e[1]>w_v[1])tot++; else now_v++;while(!s.empty()){par x=*s.begin();s.erase(s.begin());if(x.from!=-1){if(w_v[now_v]<w_e[now_e])tot++;else now_v++;now_e++;}for(int i=first[x.x];i;i=e[i].next)if(!v[e[i].y])v[e[i].y]=true,s.insert(par(e[i].y,x.x));}return tot;
}int main()
{scanf("%d",&T);while(T--){scanf("%d",&n); l=0;r=inf;st=len=1;memset(first,0,sizeof(first));memset(du,0,sizeof(du));for(int i=1,x,y;i<n;i++){scanf("%d %d %d",&x,&y,&w_e[i]);buildroad(x,y),buildroad(y,x);du[x]++;du[y]++; r=min(r,w_e[i]);if(du[x]>du[st])st=x;if(du[y]>du[st])st=y;}for(int i=1;i<=n;i++)scanf("%d",&w_v[i]);sort(w_e+1,w_e+n,cmp);sort(w_v+1,w_v+n+1,cmp);printf("%d\n",work());}
}