【CodeChef】December Challenge 2019 Div1 解题报告

点此进入比赛

这次比赛本来想好好打的，但不幸的是，这周先是要认真复习准备月考，考完又是发烧在床上躺了一个周末，所以最终没能打完。

我还是好弱啊。

\(T1\)：Binary XOR（点此看题面）

大致题意： 给定两个长度为\(n\)的\(01\)串，你能任意打乱两个字符串中的字符顺序，求所能得到的异或值个数。

设第一个字符串中有\(t1\)个\(1\)，第二个字符串中有\(t2\)个\(1\)。

我们枚举有恰好\(i\)位满足两个字符串该位都是\(1\)，则异或所得串中就有\(t1+t2-2\times i\)位是\(1\)。

则此时有\(i+t1+t2-2\times i=t1+t2-i\)位是已占用的。

因此\(i\)显然要满足：\(t1+t2-i\le n\)且\(0\le i\le min(t1,t2)\)。

则对于每一个合法的\(i\)，我们都可以将答案加上\(C_n^{t1+t2-2\times i}\)。

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

#define X 1000000007

#define C(x,y) (1LL*Fac[x]*IFac[y]%X*IFac[(x)-(y)]%X)//组合数

using namespace std;

int n,Fac[N+5],IFac[N+5];char s[N+5];

I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}

int main()

{

	RI i;for(Fac[0]=i=1;i<=N;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘

	for(IFac[N]=Qpow(Fac[N],X-2),i=N-1;~i;--i) IFac[i]=1LL*IFac[i+1]*(i+1)%X;//预处理阶乘逆元

	RI Tt,t1,t2,ans;scanf("%d",&Tt);W(Tt--)

	{

		scanf("%d",&n),t1=t2=ans=0;//初始化清空

		for(scanf("%s",s+1),i=1;i<=n;++i) t1+=s[i]&1;for(scanf("%s",s+1),i=1;i<=n;++i) t2+=s[i]&1;//统计两个串中1的个数

		for(i=0;t1+t2-i>n;++i);for(;i<=min(t1,t2);++i) ans=(C(n,t1+t2-2*i)+ans)%X;//枚举i，统计答案

		printf("%d\n",ans);

	}return 0;

}

\(T2\)：Addition（点此看题面）

大致题意： 给定两个数\(A,B\)，问将会执行下述函数中的循环多少次：

function add(A, B):

    while B is greater than 0:

        U = A XOR B

        V = A AND B

        A = U

        B = V * 2

    return A

考虑两个数二进制下的同一位，若满足：

皆为\(1\)：在\(V\)中这一位会是\(1\)，则新的\(B\)中这位的左一位将会变成\(1\)。
一个为\(0\)，一个为\(1\)：在\(U\)（\(A\)）中这一位会是\(1\)。

因此我们可以发现，初始状态下，对于每个\(A,B\)该位上都为\(1\)的一位，设它的向左\(t\)位首次不满足\(A,B\)中一个为\(0\)、一个为\(1\)，要想把这一位消干净，就需要循环\(t+1\)次（可以自己举例验证，这里偷懒了）。

注意，找到向左\(t\)位后，可以直接从这一位继续操作，所以时间复杂度是\(O(n)\)的。

还有，由于一开始两个数的位数不一定相同，注意先补齐。

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

using namespace std;

int n,m;char s1[N+5],s2[N+5];

int main()

{

	RI Tt,i,j,p,t;scanf("%d",&Tt);W(Tt--)

	{

		scanf("%s",s1+1),scanf("%s",s2+1),n=strlen(s1+1),m=strlen(s2+1);

		if(m==1&&s2[1]==48) {puts("0");continue;}//特判B=0

		if(n<m) {for(i=1;i<=n;++i) s1[m-i+1]=s1[n-i+1];for(i=1;i<=m-n;++i) s1[i]=48;n=m;}//补齐

		else {for(i=1;i<=m;++i) s2[n-i+1]=s2[m-i+1];for(i=1;i<=n-m;++i) s2[i]=48;m=n;}//补齐

		for(p=min(n,m),t=1,i=n;i;--i) if(s1[i]==49&&s2[i]==49)//枚举某一位两个字符串都为1

			{j=i-1;W(j&&s1[j]+s2[j]==97) --j;t<(i-j+1)&&(t=i-j+1),i=j+1;}//找到向左首个不满足条件的位置，更新答案，并从该位继续扫描

		printf("%d\n",t);

	}return 0;

}

\(T3\)：Chefina and Ranges（点此看题面）

大致题意： 给定若干区间，求至少删去多少区间，才可以把所有区间分成两个集合，使得所有相交的区间分在同一集合中。

考虑可以枚举一个分界点\(i\)，使得分界点左边所有区间右端点\(\le i\)，分界点右边所有区间左端点\(>i\)，并且满足分界点左、右都满足存在至少一个完整区间。

通过上面的限制，我们可以发现，\(i\)其实就是从所有区间中最小的右端点，一直枚举到所有区间中最大的左端点减\(1\)。

而对于每一个分界点，要删去的区间个数就是跨过这个分界点的区间个数。

这可以直接差分+前缀和求。

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

using namespace std;

int n,dc,x[N+5],y[N+5],s[2*N+5],dv[2*N+5];

int main()

{

	RI Tt,i,l,r,t;scanf("%d",&Tt);W(Tt--)

	{

		for(l=1e9,r=0,scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",x+i,y+i),

			l>y[i]&&(l=y[i]),r<x[i]&&(r=x[i]),dv[2*i-1]=x[i],dv[2*i]=y[i];

		if(l>r-1) {puts("-1");continue;}//所有区间有交集，判无解

		for(sort(dv+1,dv+2*n+1),dc=unique(dv+1,dv+2*n+1)-dv-1,i=1;i<=dc;++i) s[i]=0;//离散化

		#define GV(x) (lower_bound(dv+1,dv+dc+1,x)-dv)

		for(i=1;i<=n;++i) ++s[GV(x[i])],--s[GV(y[i])];for(i=1;i<=dc;++i) s[i]+=s[i-1];//差分+前缀和

		for(t=n,i=GV(l),r=GV(r);i^r;++i) t>s[i]&&(t=s[i]);printf("%d\n",t);//枚举分界点，计算答案

	}return 0;

}

\(T4\)：Sticky Notes（点此看题面）

大致题意： 给定一棵树，可以免费交换点权和边权，或者花费\(1\)的代价把某个点权改成任意值，求最小代价使得所有点的点权大于等于与其相连边的边权。

考虑要修改某个点权，一定贪心地把它改成\(INF\)。

假设我们完成了修改，然后将点权\(a_{1\sim n}\)和边权\(b_{1\sim n-1}\)从小到大排序，当且仅当满足\(1\le i\le n-1\)的每一个\(a_i\ge b_i\)，此时存在一种构造方式符合题目要求。

这可以自己考虑证明，应该还是比较简单的，这里懒得证了。

考虑接下来怎么做，其实就是将\(a\)和\(b\)分别排序，方便起见让\(b_n=b_{n-1}\)。

枚举\(a_i\)，记录当前\(b\)数组中匹配到第\(j\)个，已经花费了\(t\)的代价。

如果\(a_i\ge b_j\)，那么将\(j\)加\(1\)，否则说明必须要花费\(1\)的代价将\(a_i\)修改成\(INF\)，因此将\(t\)加\(1\)。

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

using namespace std;

int n,a[N+5],b[N+5];

int main()

{

	RI Tt,i,j,t;scanf("%d",&Tt);W(Tt--)

	{

		for(scanf("%d",&n),i=1;i^n;++i) scanf("%d%d%d",&t,&t,b+i);

		for(i=1;i<=n;++i) scanf("%d",a+i);sort(a+1,a+n+1),sort(b+1,b+n);//排序

		for(b[n]=b[n-1],t=0,i=j=1;i<=n;++i) a[i]>=b[j]?++j:++t;printf("%d\n",t);//枚举，计算并输出答案

	}return 0;

}

巴特西

【CodeChef】December Challenge 2019 Div1 解题报告

\(T1\)：Binary XOR（点此看题面）

\(T2\)：Addition（点此看题面）

\(T3\)：Chefina and Ranges（点此看题面）

\(T4\)：Sticky Notes（点此看题面）

\(T5\)：Test Generation（占坑待填）

\(T6\)：(Challenge) Cubical Virus（占坑待填）

\(T7\)：Scoring Pairs（题解待补）

\(T8\)：Binomial Fever（占坑待填）

最新文章

热门文章