【个人邀请赛】洛谷 Math趣味赛
程序员文章站
2024-03-18 23:17:46
...
前言
话说其实写这篇博客是看了之前某这样写,于是我就效仿了一下
不过那位据说公开赛被刷下来了,好像是因为题目过水。。。后来他又奋发图强,出了几个稍微难一点的题,不过还是没有通过,深感同情。。。
之前开的团队公开赛也被刷了,理由好多啊,不过总算管理有认真看了,不过这都无所谓,总之本人自己开了一个邀请赛(因为太弱不敢开公开),希望大家多多支持!
分割线
简介
这是一场很水的比赛。。。
大部分都是水题,由于本人在洛谷发不了讨论所以就发博客了。。。
有些题目在比赛之前可能本人写过博客,现在已经全部影藏了,在赛后我会放出来的!
这篇博客的实际意义主要是下面这两条
在赛时这里是赛时答疑
在赛后这里是赛后题解
这里也会给出各种小,尽情期待吧!(现已停止)
若有疑问请在下方讨论提问,谢谢配合!
链接:https://www.luogu.org/contestnew/show/7773
赛时答疑
(每天给出一个)
所有题目的正解均跟题目名称有关 #2018年6月6日
每个题目的正解总时间不超过1s #2018年6月7日
所有升级版的题目均可以通过改造原题AC #2018年6月8日
有一半以上的题需要预处理 #2018年6月9日
有疑问就在下方评论吧!
赛后题解
T1
等价于求,直接输出就行
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
long long n;
int main()
{
cin>>n;
long long a=log2(n);
cout<<a+1;
return 0;
}
T2
若此数是完全平方数输出其平方根,否则输出那一串字符
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
if (sqrt(n)!=floor(sqrt(n))) {printf("Wu Yongcong is in the pit");return 0;}
printf("%d",(int)sqrt(n));
}
T3
等价求
#include<cstdio>
#include<iostream>
using namespace std;
int gcd(int x,int y)
{
if (x<y) swap(x,y);
return x%y==0? y:gcd(y,x%y);
}
int main()
{
int a,b;scanf("%d %d",&a,&b);
printf("%d",gcd(a,b));
}
T4
改造快排
https://blog.csdn.net/xuxiayang/article/details/80515226
T5&T8
二进制公式推论,由于内存的设置,所以不能使用数组,该代码适用于两题
#include<cstdio>
using namespace std;
char c,d;int n,f;int m,k;
int read()
{
f=0;
while(c=getchar(),c<=47||c>=58);f=(f<<3)+(f<<1)+c-48;
while(c=getchar(),c>=48&&c<=57) f=(f<<3)+(f<<1)+c-48;
return f;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+48);
return;
}
void writeln(int x)
{
write(x);
putchar(10);
return;
}
int main()
{
n=read();m=read();
while(m--)
{
while(d=getchar(),d<65||d>69);k=read();
if(d==65) writeln((n>>k)&1);
if(d==66) writeln(n&((1<<k)-1));
if(d==67) n^=(1<<k),writeln(n);
if(d==68) n|=(1<<k),writeln(n);
if(d==69) n&=~(1<<k),writeln(n);
}
}
T6
详见https://blog.csdn.net/xuxiayang/article/details/80515266
和都能过
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[500001],len;
void write(int x){if(x>9)write(x/10);putchar(x%10+48);return;}
void writes(int x){write(x);putchar(32);return;}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
len=0;
for (int j=1;j*j<=i;j++)
if (i%j==0)
a[++len]=j,writes(j);
for (int j=len;j>0;j--)
if(i/a[j]>a[j])
writes(i/a[j]);
putchar(10);
}
}
#include<cstdio>
#include<vector>
using namespace std;int n;
vector<int>factor[500001];
void write(int x){if(x>9)write(x/10);putchar(x%10+48);return;}
void writes(int x){write(x);putchar(32);return;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n/i;j++)
factor[i*j].push_back(i);
for(int i=1;i<=n;putchar(10),i++)
for(int j=0;j<factor[i].size();j++)
writes(factor[i][j]);
}
T7
因为,然后又因为,所以可以只需要做一次高精度
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[202],m,ans[202],len1;
char s1[202];int gs,s=0;
string s2,s3;
void mod(int *x,int y)
{
gs=0;
for (int i=1;i<=len1;i++)
{
s=(gs<<3)+(gs<<1)+a[i];
ans[i]=s/m;
gs=s%m;
}
return;
}
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
int main()
{
scanf("%s %d",s1,&m);len1=strlen(s1);
for (int i=0;i<len1;i++) a[i+1]=s1[i]-48;
mod(a,m);
if (gs==0) printf("%d",m);else
printf("%d",gcd(m,gs));
}
T9
详见https://blog.csdn.net/xuxiayang/article/details/80409705
50分
筛素数,然后判断
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;int l,r,a[100000001],b[500001],ans,now;
int main()
{
scanf("%d%d",&l,&r);
a[1]=1;fill(a+2,a+2+r,2);
for(int i=2;i<=ceil(sqrt(r));i++)
for(int j=i;j<=r/i;j++)
if(i==j) a[i*j]++;else a[i*j]+=2;
for(int i=2;i<=r;i++)
if(a[i]>now)
{
if(i>=l) b[++ans]=i;
now=a[i];
}
printf("%d\n",ans);
for(int i=1;i<=ans;i++) printf("%d ",b[i]);
}
100分
动态规划+优化
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define N 170000
#define M 100
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int min1[N+1],min2[N+1],ans;
bool vis[M+1];
long long a[300],p[M+1],f[N+1],f1[N+1],m[N+1],t;
long long maxn=9223372036854775807LL,x,l,r;
string name,num,name2;
void make1(int i)//make1和make2是滚动
{
r(j,1<<(i+1),N) f1[j]=maxn;
r(j,1<<i,N)
{
if(f[j]==maxn) continue;
m[j]=min(m[j],f[j]);
double y=log(maxn/f[j])/log(p[i+1]);
y=min(y,min((double)(N/(j+1)-1),(double)min1[j]));
t=1;
r(k,1,y)
{
t*=p[i+1];
if(f[j]*t<f1[j*k+j])
{
f1[j*k+j]=f[j]*t;
min2[j*k+j]=k;
}
}
}
}
void make2(int i)
{
r(j,1<<(i+1),N) f[j]=maxn;
r(j,1<<i,N)
{
if(f1[j]==maxn) continue;
m[j]=min(m[j],f1[j]);
double y=log(maxn/f1[j])/log(p[i+1]);
y=min(y,min((double)(N/(j+1)-1),(double)min2[j]));
t=1;
r(k,1,y)
{
t*=p[i+1];
if(f1[j]*t<f[j*k+j])
{
f[j*k+j]=f1[j]*t;
min1[j*k+j]=k;
}
}
}
}
int main()
{
r(i,2,M)
{
if(!vis[i]) p[++p[0]]=i;
r(j,1,p[0])
{
if(M/p[j]<i) break;
vis[i*p[j]]=true;
if(i%p[j]==0) break;
}
}
f[1]=1;
r(i,2,62) {f[i]=f[i-1]<<1;min1[i]=i-1;}
r(i,63,N) f[i]=maxn;
r(i,2,N) m[i]=maxn;
r(i,1,16)
if(i&1) make1(i);else make2(i);
r(i,1<<17,N) m[i]=min(m[i],f[i]);
x=maxn;
for(int i=N;i>1;i--)
if(m[i]<x)
{
a[++a[0]]=m[i];
x=m[i];
}
cin>>l>>r;//这之前的都是预处理
r(i,1,a[0]) if(a[i]>=l&&a[i]<=r) ans++;
printf("%d\n",ans);
for(int i=a[0];i>0;i--) if(a[i]>=l&&a[i]<=r) cout<<a[i]<<' ';
}
推荐阅读