校赛小分队之我们有个女生队——这是我、ljh学长、zk大神组的队，我取得闪亮亮的队名！
第一场训练赛是水题（只要做前四题），但是我做的比较慢，zk可快了，于是我心塞了一晚上。
传送门 密码【123666】
A.【 CodeForces 633A 】Ebony and Ivory
给a、b、c(1 ≤ a, b ≤ 100, 1 ≤ c ≤ 10 000)三个正整数，求关于x和y的方程ax by=c的非负的整数解。
如果枚举x和y，那要枚举到10000，复杂度是n2 显然会超时。
但是只要枚举其中一个的倍数i，然后看看c-a*i能不能整除b。
或者直接枚举i=1到c，看看是否满足 i能整除a 且 c-i能整除b。
一开始想gcd(a,b)|c 就是gcd整除c，则x、y有整数解，再判断有没有非负整数的解（乱搞），但是失败了，不过后来研究了一下，扩展gcd可以做的（废话）。
因为x最小时，y就最大，只要求出x的最小非负数解，判断y是不是非负的，如果是那么xy就有非负整数解啦。如果不是，那么x更大时，y就更小了，那就不可能有了。
代码语言：javascript复制#include<cstdio>
int a,b,c,ok;
int main()
{
scanf("%d%d%d",&a,&b,&c);
for(int i=0; i<=c&&!ok; i )
if(i%a==0&&(c-i)%b==0)ok=1;
if(ok)printf("Yes");
else printf("No");
return 0;
}扩展gcd
代码语言：javascript复制#include<cstdio>
int a,b,c,x,y,ok;
int exgcd(int a,int b){
if(b==0){ x=1;y=0; return a;}
int r=exgcd(b,a%b);
int t=x;x=y;y=t-a/b*y;
return r;
}
int main()
{
scanf("%d%d%d",&a,&b,&c);
int g=exgcd(a,b);
if(c%g==0){
x*=c/g;//ax by=c的x的解
b/=g;
x=(x%b b)%b; //x的最小非负解
if(c-a*x>=0) ok=1;//对应的y也非负
}
if(ok)printf("Yes");
else printf("No");
return 0;
}B.【 CodeForces 629A 】A Trivial Problem
判断每行每列里共有几对‘C’。直接统计每行有几个，记为a[i]，每一列有几个，记为b[i]，然后ans =C(a[i],2) C(b[i],2)。
一个个字符读取，则每读一行字符前，要getchar吃掉前面一行的回车。
代码语言：javascript复制#include<cstdio>
#define N 105
int n,ans;
char c;
int a[N],b[N];
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i )
{
c=getchar();
for(int j=1; j<=n; j )
{
c=getchar();
if(c=='C')
{
a[i] ;
b[j] ;
}
}
}
for(int i=1; i<=n; i )
{
ans =a[i]*(a[i]-1)/2;
ans =b[i]*(b[i]-1)/2;
}
printf("%d",ans);
return 0;
}C.【 CodeForces 633B 】A Trivial Problem
求n！后面有m个零的n有几个，按顺序输出。
那就求出n！里面有几个因子5,因子2一定比5多，所以几个5末尾就有几个0。
可以用二分的方法求n，也可以直接求。
下面的代码具体为什么这样，就是这样，不想解释了。
代码语言：javascript复制#include<cstdio>
#define ll long long
ll m,l,r;
int main()
{
while(~scanf("%lld",&m))
{
l=m;
while(l l/5 l/25 l/125 l/625 l/3125 l/15625 l/78125 l/390625>m)l--;
if(l l/5 l/25 l/125 l/625 l/3125 l/15625 l/78125 l/390625<m)printf("0");
else
{
printf("5n");
for(ll i=5*l; i<5*l 5; i )
printf("%lld ",i);
}
}
return 0;
}二分，感觉这样挺好。
代码语言：javascript复制#include<cstdio>
#define ll long long
ll m,l,r;
int cnt(int a){
int tol=0;
//下面这个循环统计了a的阶乘的因子5的次数tol。
while(a){
tol =a/5;//1到a这些数里面有几个是5的倍数。
a/=5;//这a个能整除5的数都除以5，就变成了1到a/5，再看1到a/5里面有几个是5的倍数。
}
return tol;
}
int solve(){
int l=1,r=m*5 1;
while(l<r-1){
int mid=l r>>1;
int ans=cnt(mid);
if(ans<m){
l=mid;
}else if(ans>m){
r=mid;
}
else return mid;
}
return 0;
}
int main()
{
while(~scanf("%lld",&m))
{
int v=solve();
if(v){
while(v%5)v--;
printf("5n");
for(ll i=v; i<v 5; i )
printf("%lld ",i);
}
else printf("0");
}
return 0;
}D.【 CodeForces 629B 】Far Relative’s Problem
给你每个朋友有空的时间区间，求来的朋友里 min（男朋友，女朋友）最大的一天。直接统计每天的男女朋友个数。然后枚举每一天找最大值。
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#define N 5005
using namespace std;
int n,a[N],b[N],ans;
int l,r;
char c;
int main()
{
scanf("%d",&n);
for(int i=0; i<n; i )
{
getchar();
scanf("%c%d%d",&c,&l,&r);
if(c=='M')
{
for(int j=l; j<=r; j )
a[j] ;
}
else
{
for(int j=l; j<=r; j )
b[j] ;
}
}
for(int i=1; i<=366; i )
{
int t=min(a[i],b[i]);
if(t>ans)ans=t;
}
printf("%d",2*ans);
return 0;
}
