当前位置: 代码迷 >> 综合 >> CodeChef December Challenge 2019 Division 2 小结
  详细解决方案

CodeChef December Challenge 2019 Division 2 小结

热度:3   发布时间:2024-01-24 06:46:52.0

背景

打完这场 r a t i n g rating 终于上 1800 1800 了,下个月可以打 D i v   1 Div~1 了~

虽然连 D i v   2 Div~2 都不一定能 A K AK ,但是打 D i v   1 Div~1 总归要好一点吧。

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

在此记录一下前 7 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 0 或者是两个 2 2 可以满足 a + b = a × b a+b=a\times b ,所以统计一下 0 0 的个数和 2 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,y ,那么答案就是 x + ( n ? 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 B 序列都变为 0 0 需要操作多少次,那么只需要找出 B B 序列中活最久的 1 1 即可。

  • 对于一个处于 i i 位置的 1 1
  • 假如他要活过第一轮,就需要此时 A i = 1 A_i=1
  • 假如他要活过第二轮,那么就需要此时 A i ? 1 = 1 A_{i-1}=1 ,即原序列中 A i ? 1   x o r   B i ? 1 = 1 A_{i-1}~xor~B_{i-1}=1
  • 假如他要活过第三轮,那么就需要此时 A i ? 2 = 1 A_{i-2}=1 ,即原序列中 A i ? 2   x o r   B 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 A,B 序列中 1 1 的个数即可。

不妨设异或出来的序列为 C C ,求出上面那个东西之后,我们就可以枚举 C C 序列中 1 1 的个数,对于枚举出的每个个数 i i ,用基本的排列组合只是就可以算出,含有 i i 1 1 C C 序列的个数为 n ! i ! ( n ? i ) ! \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

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

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

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

还有一个坑点, s u b t a s k 3 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 个点权和 n ? 1 n-1 个边权,你可以用一枚硬币来修改一个点权,现在要求用最少的硬币,并且存在一种方案,将这些点权和边权分别放到点上和边上,满足对于任意一条边,它的权值小于等于它连接的两个点的权值。

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

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

想到这里更加激动:操作这么流畅,肯定是正解啊!

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

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

这个策略有两个好处:

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

此时离比赛结束还有半小时,我一波操作之后反手一个 S u b m i t Submit 50 50 分,ok,凉了,比赛结束。

我心想,这么优秀的一个 O ( n l o g 2 n ) O(nlog^2n) 做法,怎么给你 1 0 5 10^5 的数据卡掉了呢?

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

到了上机的时候,随手就 A C 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());}
}