小白月赛5std帖
写在前面：可能有些代码没有考虑到边界情况，但是数据应该都是对的，大家谅解下，不喜勿喷啊
ProblemA： 无关(relationship)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
inline LL read()
{
char c=getchar(); LL num=0,f=1;
while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
while (c<='9'&&c>='0') { num=num*10+c-'0'; c=getchar(); }
return num*f;
}
LL n,a[35],L,R,ans,bin[35];
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b)
{
return a/gcd(a,b)*b;
}
int main()
{
bin[0]=1; for (int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
L=read(); R=read(); n=read();
for (int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
for (int i=2;i<=n;i++)
{
bool exi=false;
for (int j=1;j<i;j++) if (a[i]%a[j]==0) { exi=true; break; }
if (exi) swap(a[i],a[n]),i--,n--;
}
ans=R-L+1;
for (int sta=1;sta<bin[n];sta++)
{
int cnt=0; LL tmp=1; bool exi=true;
for (int i=1;i<=n;i++)
if (sta&bin[i-1])
if (R/a[i]>=tmp) tmp*=a[i],cnt++;
else { exi=false; break; }
if (!exi) continue;
if (cnt&1) ans-=R/tmp-(L-1)/tmp;
else ans+=R/tmp-(L-1)/tmp;
}
printf("%lld",ans);
return 0;
}
ProblemB： 范围(range)
#include<cstdio>
#include<cmath>
using namespace std;
long long A,B;
double a,b,c,ans,ans1,ans2;
int main()
{
scanf("%lld%lld",&A,&B);
a=2.0;b=(double)(-2*A);c=(double)(A*A)-B;
ans=(b*b-4*a*c);
if(ans<0) printf("No Answer.\n");
else
{
ans1=(-sqrt(ans)-b)/(2*a);
ans2=(sqrt(ans)-b)/(2*a);
printf("%.2f %.2f\n",ans1,ans2);
}
return 0;
}
ProblemC： 水题(water)
#include <bits/stdc++.h>
using namespace std;
long long read()
{
long long num = 0;
char c;
bool flag = 0;
while ((c = getchar()) == '\t' || c == '\r' || c == '\n' || c == ' ');
if (c == '-')
flag = 1;
else
num = c - 48;
while (isdigit(c = getchar()))
num = num * 10 + c - 48;
return (flag ? -1 : 1) * num;
}
int read1()
{
int num = 0;
char c;
bool flag = 0;
while ((c = getchar()) == '\t' || c == '\r' || c == '\n' || c == ' ');
if (c == '-')
flag = 1;
else
num = c - 48;
while (isdigit(c = getchar()))
num = num * 10 + c - 48;
return (flag ? -1 : 1) * num;
}
long long ans;
int pos;
void nhh (int row,int lx,int rx)
{
int k,now;
if (row != pos)
{
now = pos & ~(row | lx | rx);
while (now)
{
k = now & -now;
now -= k;
nhh(row + k,(lx + k) << 1,(rx + k) >> 1);
}
}
else
ans++;
}
bool vis[101];
int cnt;
long long z,prime[101];
void sss(int m)
{
int i,j;
for (i = 2;i <= m;i++)
{
if (!vis[i])
prime[++cnt] = i;
for (j = 1;j <= cnt && prime[j] * i <= m;j++)
{
vis[prime[j] * i] = 1;
if (i % prime[j] == 0)
break;
}
}
}
long long n,f1,f2,t,num[101],num1[101];
int m,i;
int main()
{
//freopen("water.in","r",stdin);
//freopen("water.out","w",stdout);
n = read();
f1 = 1;
f2 = 1;
while (n > f2)
{
t = f2;
f2 += f1;
f1 = t;
}
if (n < f2)
{
m = min(13,read1());
m = n % m + 1;
pos = (1 << m) - 1;
nhh(0,0,0);
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
else
{
m = read1();
sss(m);
for (i = 1;i <= cnt;i++)
while (m % prime[i] == 0)
{
num[i]++;
m /= prime[i];
}
for (i = 1;i <= cnt;i++)
{
z = n;
while (z)
{
num1[i] += z / prime[i];
z /= prime[i];
}
}
ans = n;
for (i = 1;i <= cnt;i++)
if (num[i])
ans = min(ans,num1[i] / num[i]);
printf("%lld\n",ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
}
ProblemD： 阶乘(factorial)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <string>
#include <climits>
#include <ctime>
#include <queue>
#include <map>
#include <stack>
#include <vector>
using namespace std;
int read()
{
int num = 0;
char c;
bool flag = 0;
while ((c = getchar()) == '\t' || c == '\n' || c == '\r' || c == ' ');
if (c == '-')
flag = 1;
else
num = c - 48;
while (isdigit(c = getchar()))
num = num * 10 + c - 48;
return (flag ? -1 : 1) * num;
}
int a[15],u,n,k;
long long ans,t;
int main()
{
//freopen("factorial.in","r",stdin);
//freopen("factorial.out","w",stdout);
n = read();
k = n - n % 5;
t = 0;
if (n < 10)
{
if (n == 5) printf("1\n");
if (n == 6) printf("2\n");
if (n == 7) printf("3\n");
if (n == 8) printf("4\n");
if (n == 9) printf("5\n");
return 0;
}
for (int i = 10;i <= k;i += 5)
{
a[1]++;
u = 1;
if (a[1] % 5 == 0)
{
while(a[u] == 5)
{
a[u++] = 0;
a[u]++;
}
}
t += u;
ans += 5 * t;
}
a[1]++;
u = 1;
if (a[1] % 5 == 0)
{
while(a[u] == 5)
{
a[u++] = 0;
a[u]++;
}
}
t += u;
ans += t * (n % 5 + 1);
printf("%lld\n",ans);
//fclose(stdin);
//fclose(stdout);
}
ProblemE： 面积(area)
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
long long xx1,yy1,xx2,yy2,ans,M,N;
int main()
{
//freopen("area.in","r",stdin);
//freopen("area.out","w",stdout);
while(~scanf("%lld%lld%lld%lld%lld%lld",&M,&N,&xx1,&yy1,&xx2,&yy2))
{
ans=abs(xx1*yy2-xx2*yy1);
if(M*N==ans+2) puts("Yes");
else puts("No");
}
return 0;
}
ProblemF： 圆(circle)
#include<cstdio>
int main()
{
//freopen("circle.in","r",stdin);
//freopen("circle.out","w",stdout);
long long ans,n;
while(~scanf("%lld",&n))
{
ans=(n*(n-1)*(n-2)*(n-3))/24;
ans+=n*(n-1)/2;
ans+=1;
printf("%lld\n",ans);
}
}
ProblemG： 异或(xor)
#include<cstdio>
long long a;
int main()
{
//freopen("xor.in","r",stdin);
//freopen("xor.out","w",stdout);
while(~scanf("%lld",&a))
{
printf("%lld\n",((a+1)<<1)/3);
}
}
ProblemH： 最大公约数(lcm)
#include<cstdio>
#include<queue>
using namespace std;
int gcd(int a,int b)
{
return b==0? a:gcd(b,a%b);
}
int main()
{
int x,y;
scanf("%d%d",&x,&y);
printf("%lld",x*y/gcd(x,y));
return 0;
}
ProblemI： 区间(interval)
#include<cstdio>
long long a[1000001],c[1000001],n,m,l,r,p,q;
int main()
{
scanf("%lld%lld",&n,&m);
for(register int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(register int i=1;i<=m;i++)
{
scanf("%lld%lld%lld%lld",&q,&l,&r,&p);
if(q==1) p=-p;
c[l]+=p;c[r+1]-=p;
}
for(register int i=1;i<=n;i++)
{
c[i]+=c[i-1];
a[i]+=c[i]+a[i-1];
}
scanf("%lld%lld",&l,&r);
printf("%lld\n",a[r]-a[l-1]);
return 0;
}
ProblemJ： 时间(time)
#include<cstdio>
struct time{
int h,m;
};
time t[17];
void doit()
{
int tot=-1;
t[++tot].h=00;t[tot].m=00; t[++tot].h=01;t[tot].m=10;
t[++tot].h=02;t[tot].m=20; t[++tot].h=03;t[tot].m=30;
t[++tot].h=04;t[tot].m=40; t[++tot].h=05;t[tot].m=50;
t[++tot].h=10;t[tot].m=01; t[++tot].h=11;t[tot].m=11;
t[++tot].h=12;t[tot].m=21; t[++tot].h=13;t[tot].m=31;
t[++tot].h=14;t[tot].m=41; t[++tot].h=15;t[tot].m=51;
t[++tot].h=20;t[tot].m=02; t[++tot].h=21;t[tot].m=12;
t[++tot].h=22;t[tot].m=22; t[++tot].h=23;t[tot].m=32;
t[++tot].h=24;t[tot].m=60;
}
int main()
{
//freopen("time.in","r",stdin);
//freopen("time.out","w",stdout);
int a,b;
scanf("%d:%d",&a,&b);doit();
for(register int i=0;i<=15;i++)
{
if(a==t[i].h&&b==t[i].m){printf("%d:%d\n%d:%d",t[i-1].h%24,t[i-1].m%60,t[i+1].h%24,t[i+1].m%60);return 0;}
}
for(register int i=0;i<=15;i++)
{
if((a>t[i].h&&a<t[i+1].h)||(a==t[i].h&&b>t[i].m)||(a==t[i+1].h&&b<t[i+1].m))printf("%d:%d\n%d:%d",t[i].h,t[i].m,t[i+1].h%24,t[i+1].m%60);
}
}
