因为今天省选组也做a组，以为今天a组会很难，就做了做b组。t1和t3强行暴力，好在有t2保底。t1和正解就差一点，然而考试时死活想不起来......

 

今天改题可以少改一道了！ovo

 

救救孩子吧！t1T到上天......然后打完后电脑蓝屏了。不想动弹

 

好吧，重打了一遍，终于调对了。

t1：

Description

有n个正整数a[i]，设它们乘积为p，你可以给p乘上一个正整数q，使p*q刚好为正整数m的阶乘，求m的最小值。

 

Input

共两行。

第一行一个正整数n。

第二行n个正整数a[i]。

Output

共一行

一个正整数m。

质因数分解，然后二分m，找因子个数判断。注意质因数分解的方式......

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int prime[100010],ps[100010],dv[100010],cntt,n,tot;int a[100010],b[100010];long long cnt[100010];int check(long long mid){    for(int i=1;i<=tot;i++)    {        long long con=0;        for(long long j=b[i];j<=mid;j*=b[i])        {            con=(con+mid/(j));        }        if(con
         
          >n;    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    for(int i=1;i<=100000;i++)        prime[i]=1;    dv[1]=1;    for(int i=2;i<=100000;i++)    {        if(prime[i])            ps[++cntt]=i,dv[i]=i;        for(int j=1;j<=cntt;j++)        {            if(ps[j]*i>100000)                break;            prime[ps[j]*i]=0;            dv[i*ps[j]]=ps[j];            if(i%ps[j]==0) break;        }            }    for(int i=1;i<=n;i++)    {        while(dv[a[i]]!=a[i])        {            if(!cnt[dv[a[i]]])                b[++tot]=dv[a[i]];            cnt[dv[a[i]]]++;            a[i]/=dv[a[i]];        }        if(a[i]!=1)        {            if(!cnt[a[i]])                b[++tot]=a[i];            cnt[a[i]]++;        }    }    long long l=1,r=100000000;    while(l
          
           >1; if(check(mid)) r=mid; else l=mid+1; } cout<
          
         
        
       
      
     

 

先整上t2吧：

 

这道题正解是搜索，但我考试时觉得它和day3的t2有点像，就写了一个差不多的套路。向不用拐弯可以到达的点连边，然后一个spfa就出答案了。当时有点虚，但反正愉悦ac了，快乐。

Description

       小S是一个爱锻炼的孩子，他在放假期间坚持在A公园练习跑步。

      但不久后，他就开始为在重复的地点练习感到厌烦了，他就打算去B公园跑步。

      但是小S由于没有去过B公园，他不知道B公园是否适合练习跑步，又不知道在B公园怎样跑是最优的。所以小S就去B公园进行了一番勘测。

      小S在进行了一番勘测后，画出了一张地图，地图每一个位置上都辨识了小S到达该位置后不能往哪一个方位移动。其中有5种表示的符号：“U”代表不能向上移动，“D”代表不能向下移动，“L”代表不能向左移动，“R”代表不能向右移动，如果该位置有障碍物，小S到达那里后无法继续训练，就用“S”来代表。整个公园共有n行m列，小S会从第1行第1列出发，到第n行第m列结束他的练习。

      现在小S想要知道，从起点（即第1行第1列）到终点（第n行第m列），途中最少要改变几次方向（即上一次移动的方向和这一次移动的方向不一样）？

      注意：小S如在训练途中离开公园（即地图范围），则算是结束训练。

 

Input

      第1行两个整数n和m，它们的定义请看【题目描述】。

      第2~n+1行，每行有m个字符，表示小S的移动方向。

Output

      如果小S从第1行第1列出发无论如何都到达不了第n行第m列，输出“No Solution”，否则输出小S途中最少要改变方向的次数。

#include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int n,m,cnt,head[250010],dis[250010],vis[250010];char mp[510][510];struct Edge{    int v,nxt,val;}e[25000010];void spfa(){    int nn=n*m;    for(int i=1;i<=n*m;i++)        dis[i]=0x3f3f3f3f;    queue
             
              q; dis[1]=0; vis[1]=1; q.push(1); while(!q.empty()) { int u=q.front(); vis[u]=0; q.pop(); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(dis[v]>dis[u]+1) { dis[v]=dis[u]+1; if(!vis[v]) { vis[v]=1; q.push(v); } } } }}void add(int u,int v,int val){ e[++cnt].nxt=head[u]; e[cnt].v=v; e[cnt].val=val; head[u]=cnt;}int num(int x,int y){ return (x-1)*m+y;}void addup(int x,int y){ int nums=num(x,y); int xx=x-1; while(xx>0) { add(nums,num(xx,y),1); if(mp[xx][y]=='U'||mp[xx][y]=='S') return; xx--; }}void adddown(int x,int y){ int nums=num(x,y); int xx=x+1; while(xx<=n) { add(nums,num(xx,y),1); if(mp[xx][y]=='D'||mp[xx][y]=='S') return; xx++; }}void addleft(int x,int y){ int nums=num(x,y); int yy=y-1; while(yy>0) { add(nums,num(x,yy),1); if(mp[x][yy]=='L'||mp[x][yy]=='S') return; yy--; }}void addright(int x,int y){ int nums=num(x,y); int yy=y+1; while(yy<=m) { add(nums,num(x,yy),1); if(mp[x][yy]=='R'||mp[x][yy]=='S') return; yy++; }}int main(){ freopen("run.in","r",stdin); freopen("run.out","w",stdout); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(mp[i][j]=='S') continue; if(mp[i][j]!='U') addup(i,j); if(mp[i][j]!='D') adddown(i,j); if(mp[i][j]!='L') addleft(i,j); if(mp[i][j]!='R') addright(i,j); } spfa(); if(dis[num(n,m)]==0x3f3f3f3f) cout<<"No Solution"; else cout<
             
            
           
          
         
        

 

待补充！