130721UVA组队练习赛

本文主要是介绍130721UVA组队练习赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B. Bits Equalizer

昨天一开始是两个人看题，听别的组说B题是编辑距离裸题，就看了一下，发现不是编辑距离，但也是道水题，就直接敲了。但是连WA5发。。。最后debug才发现是记录‘0’和‘1’的标记变量在下面写反了，一直各种WA，，，而且之前也发现了各种小错误（ps：之前样例居然一直过，不得不说样例太猥琐了）。就直接上代码了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
int a1,b1,a2,b2,a3,b3;
int c,i,j,cas,n,h,m,l;
char x[101],y[101];
void work(char *p,char *q)
{n=strlen(p);a1=a2=b1=b2=0;for(i=0; i<n; ++i){if(p[i]=='0'){a1++;}if(p[i]=='1'){b1++;}if(q[i]=='0'){a2++;}if(q[i]=='1'){b2++;}}if(b1>b2){printf("Case %d: -1\n",cas);}else{l=a2-a1;h=b2-b1;m=l+h;for(i=0; i<n; ++i){if(p[i]=='?'){if(q[i]=='1'&&h>0){p[i]='1';h--;}else if(q[i]=='0'&&l>0){p[i]='0';l--;}}}if(l>0){for(i=0; i<n; ++i){if(p[i]=='?'){p[i]='0';}}}if(h>0){for(i=0; i<n; ++i){if(p[i]=='?'){p[i]='1';}}}a3=b3=0;for(i=0; i<n; i++){if(p[i]!=q[i]){if(p[i]=='0'){b3++;}else{a3++;}}}printf("Case %d: %d\n",cas,b3+m);}
}
int main()
{scanf("%d",&c);cas=0;while(c--){cas++;scanf("%s%s",&x,&y);work(x,y);}return 0;
}

C. LCM Pair Sum

这题一开始是队友敲的，但是后来交了一次发现RE，才发现复杂度绝对爆了，后来我也看这题，对第一个样例进行一下简单的分配解析（1,2,2,3,3,6,6,6,6）而且给出的因数都是质数，所以最小公倍数必然是(p1^a1)*(p2^a2)*(p3^a3)*...*(pn^an)，再结合多项式相乘的项数系数就可以初步得到如下的等式：

sum=(1+p1+p1^2+...+(a1+1)*p1^a1)*(1+p2+p2^2+...+(a2+1)*p2^a2)*...(1+pn+pn^2+...+(an+1)*(pn^an))；

CE了一次，发现bnu上面貌似用不了__int64，，最后改long long了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#define N 1000000007
using namespace std;
int main()
{int t,n,a[22],b,k[22],ge,cas=0,i;long long sum,num,x,y;scanf("%d",&t);while(t--){cas++;scanf("%d",&n);sum=1;num=1;for(i=0;i<n;++i){scanf("%d%d",&a[i],&k[i]);x=1;y=0;ge=k[i];k[i]++;while(ge--){y=(y+x)%N;x=(x*a[i])%N;}y=(y+x*k[i])%N;sum=(sum*y)%N;num=(num*x)%N;}printf("Case %d: %lld\n",cas,(sum+num)%N);}return 0;
}

这篇关于130721UVA组队练习赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---