B组
T1.factorial 阶乘
upd:改数据了，20分变80分
有这样一个结论，对于m!，设它的一个质因数为pi，则pi的指数为 m/pi+m/pi^2+m/pi^3+...，显然只有pi^k<=m会产生贡献
这样就可以二分答案了！
复杂度大概再1e5+log1e9*ln1e5*log(每个数)
#include#include #include #include using namespace std;const int MAXN=1000005;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}int n;int a[MAXN];int prime[MAXN],tot;bool isx[MAXN];void mkprime(int x){ for(int i=2;i<=x;i++){ if(!isx[i]) prime[++tot]=i; for(int j=1;i*prime[j]<=x&&j<=tot;j++){ isx[i*prime[j]]=1; if(i%prime[j]==0) break; } }}int cnt[MAXN];void div(int x){ for(int i=1;i<=tot;i++){ int v=prime[i]; if(v>x) break; if(x%v) continue; while(x%v==0) cnt[i]++,x/=v; if(x==1) return; }}bool check(int x){ for(int i=1;i<=tot;i++){ long long v=prime[i],tmp=0; while(v<=x){ tmp+=x/v; if(tmp>=1ll*cnt[i])break; v*=prime[i]; } if(tmp<1ll*cnt[i]) return false; } return true;}int main(){ freopen("factorial.in","r",stdin); freopen("factorial.out","w",stdout); n=rd(); mkprime(100000); for(int i=1;i<=n;i++) div(rd()); while(tot){ if(cnt[tot]) break;tot--;} int l=1,r=100000000,mid,ans=1; while(l<=r){ mid=l+r>>1; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } cout<
T2.run 小S练跑步
BFS搜索，注意一个地方。
记录的mn[x][y]为到当前点最少拐弯次数，当新的cost>mn[x][y]剪枝，而不是大于等于，等于的时候可能方向不同，再加一个数组lst[x][y]表示在取到mn时的方向，若cost==mn且当前方向==lst，则跳过。
其实类似一个vis[x][y][4]，记录这个状态是否在队列中，类似SPFA。
#include#include #include #include using namespace std;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}const int MAXN=512;int n,m;int mp[MAXN*MAXN];int lst[MAXN*MAXN];int mn[MAXN*MAXN];struct Node{ int x,y,dir,cost;}node,top;queue Q;int dx[5]={ 0,0,1,0,-1};int dy[5]={ 0,1,0,-1,0};int tran[MAXN];int ans=1<<29;bool succ=0;char s[MAXN];int main(){ freopen("run.in","r",stdin); freopen("run.out","w",stdout); memset(mn,0x3f,sizeof(mn)); n=rd();m=rd(); tran['R']=1; tran['D']=2; tran['L']=3; tran['U']=4; tran['S']=5; for(register int i=1;i<=n;i++){ scanf("%s",s+1); for(register int j=1;j<=m;j++){ mp[(i<<9)+j]=tran[s[j]]; } } node.x=1;node.y=1;node.cost=0;node.dir=0; Q.push(node); while(!Q.empty()){ top=Q.front();Q.pop(); register int x=top.x,y=top.y,cost=top.cost,dir=top.dir; if(x==n&&y==m){ ans=min(ans,cost); succ=1; continue; } if(mp[(x<<9)+y]==5) continue; register int nx,ny; for(register int k=1;k<=4;k++){ if(k==mp[(x<<9)+y]) continue; nx=x+dx[k];ny=y+dy[k]; int v=(nx<<9)+ny; if(!mp[v]) continue; if(mn[v]