因为今天省选组也做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]。
第一行一个正整数n。
第二行n个正整数a[i]。
Output
共一行
一个正整数m。
一个正整数m。
质因数分解，然后二分m，找因子个数判断。注意质因数分解的方式......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int prime[],ps[],dv[],cntt,n,tot;
int a[],b[];
long long cnt[];
int check(long long mid)
{
for(int i=;i<=tot;i++)
{
long long con=;
for(long long j=b[i];j<=mid;j*=b[i])
{
con=(con+mid/(j));
}
if(con<cnt[b[i]])
return ;
}
return ;
}
int main()
{
freopen("factorial.in","r",stdin);
freopen("factorial.out","w",stdout);
cin>>n;
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=;i++)
prime[i]=;
dv[]=;
for(int i=;i<=;i++)
{
if(prime[i])
ps[++cntt]=i,dv[i]=i;
for(int j=;j<=cntt;j++)
{
if(ps[j]*i>)
break;
prime[ps[j]*i]=;
dv[i*ps[j]]=ps[j];
if(i%ps[j]==) break;
} }
for(int i=;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]!=)
{
if(!cnt[a[i]])
b[++tot]=a[i];
cnt[a[i]]++;
}
}
long long l=,r=;
while(l<r)
{
long long mid=(l+r)>>;
if(check(mid))
r=mid;
else
l=mid+;
}
cout<<l;
fclose(stdin);
fclose(stdout);
return ;
}
先整上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如在训练途中离开公园（即地图范围），则算是结束训练。
但不久后，他就开始为在重复的地点练习感到厌烦了，他就打算去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的移动方向。
第2~n+1行，每行有m个字符，表示小S的移动方向。
Output
如果小S从第1行第1列出发无论如何都到达不了第n行第m列，输出“No Solution”，否则输出小S途中最少要改变方向的次数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,cnt,head[],dis[],vis[];
char mp[][];
struct Edge
{
int v,nxt,val;
}e[];
void spfa()
{
int nn=n*m;
for(int i=;i<=n*m;i++)
dis[i]=0x3f3f3f3f;
queue<int>q;
dis[]=;
vis[]=;
q.push();
while(!q.empty())
{
int u=q.front();
vis[u]=;
q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>dis[u]+)
{
dis[v]=dis[u]+;
if(!vis[v])
{
vis[v]=;
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-)*m+y;
}
void addup(int x,int y)
{
int nums=num(x,y);
int xx=x-;
while(xx>)
{
add(nums,num(xx,y),);
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+;
while(xx<=n)
{
add(nums,num(xx,y),);
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-;
while(yy>)
{
add(nums,num(x,yy),);
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+;
while(yy<=m)
{
add(nums,num(x,yy),);
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=;i<=n;i++)
for(int j=;j<=m;j++)
cin>>mp[i][j];
for(int i=;i<=n;i++)
for(int j=;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<<dis[num(n,m)]-;
fclose(stdin);
fclose(stdout);
return ;
}
待补充！