【比赛报告】2018.8.7集训 NOIP练习赛卷十
A.函数
题目链接
问题描述
对于一个整数，定义 f(x)为他的每个数位的阶乘的乘积。例如 f(135)=1! * 3! * 5! =
720。给出一个数 a（可以包含前缀零）， a 满足他的至少一个数位大于 1。我们要求出最
大 的整数 x，其中 x 不含 0 或 1，并且满足 f(a) = f(x)。
输入
第一行一个整数 n，表示 a 的长度。 接下来一个整数 a。
输出
一行一个整数 x 表示答案。
【输入样例 1】
4
1234
【输出样例 1】
33222
【样例 1 说明】
1! * 2! * 3! * 4! = 3! * 3! * 2! * 2! * 2!
【输入样例 2】
2
03
【输出样例】
3
【样例 2 说明】
0! * 3! = 3！
【数据范围】
对 30%的输入数据 ： n≤2
对 100%的输入数据 ： n≤15
考场上居然把这题打挂了气死了……教练都说这题随便乱搞都能过的……
可以知道2~9的阶乘可以写成2,3,5,7的阶乘的组合……于是我也来乱搞了
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
char a[20];
int num[20];
int zs[4]={2,3,5,7};
vector<int>vx[10];
priority_queue<int>ans;
void Init()
{
vx[2].push_back(2);
vx[3].push_back(3);
vx[4].push_back(3);vx[4].push_back(2);vx[4].push_back(2);
vx[5].push_back(5);
vx[6].push_back(5);vx[6].push_back(3);
vx[7].push_back(7);
vx[8].push_back(7);vx[8].push_back(2);vx[8].push_back(2);vx[8].push_back(2);
vx[9].push_back(7);vx[9].push_back(3);vx[9].push_back(3);vx[9].push_back(2);
}
int main()
{
int n;
Init();
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
num[i]=a[i]-'0';
if(num[i]==0||num[i]==1)continue;
for(int j=0;j<vx[num[i]].size();j++)ans.push(vx[num[i]][j]);
}
while(!ans.empty())
{
int tmp=ans.top();ans.pop();
cout<<tmp;
}
puts("");
return 0;
}
B.箱子
用 dist[position][box1][box2][box3]记录人在 position，箱子 1 在 box1，箱子 2 在box2，箱子 3 在 box3 位置时最少需要花费的步数。 Bfs 一遍即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6e6+10;
bool vis[10][10];//标记是否可行
char s[10];//读入每一行
int nm[110][3];//新建图
int R,C;//r行c列
int sx,sy;//人的位置
int cnt1,cnt2,cnt3;
//cnt1用来编号，cnt2cnt3为箱子和按钮的编号
int nextx[4]={1,-1,0,0};
int nexty[4]={0,0,1,-1};//枚举四个方向
int pos[10][10];//每个位置的编号
int num[10][10];//地图的数字
int box[5],button[5];//盒子与按钮的编号
int f[50][50][50][50];//f[i][j][k][l]表示人在i，三个盒子在j,k,l时的最小步数
int c[N][5];//c模拟队列
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&R,&C);///R行C列
memset(nm,0,sizeof(nm));
memset(f,255,sizeof(f));
memset(num,0,sizeof(num));
memset(box,0,sizeof(box));
memset(button,0,sizeof(button));
memset(vis,true,sizeof(vis));
cnt1=cnt2=cnt3=0;
for(int i=1;i<=R;i++)
{
scanf("%s",s);
for(int j=1;j<=C;j++)
{
pos[i][j]=++cnt1;//给每个点标号
nm[cnt1][1]=i;nm[cnt1][2]=j;
num[i][j]=s[j-1]-'0';//转成数字
if(num[i][j]==2)box[++cnt2]=pos[i][j];
if(num[i][j]==3)button[++cnt3]=pos[i][j];
if(num[i][j]==4)sx=i,sy=j,num[i][j]=0;
}
}
f[pos[sx][sy]][box[1]][box[2]][box[3]]=0;//初始状态
c[1][0]=pos[sx][sy];//人的编号
c[1][1]=box[1];
c[1][2]=box[2];
c[1][3]=box[3]; //三个箱子
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++)
if(num[i][j]==1)vis[i][j]=false;
for(int l=1,k=1;l<=k;l++)
{
int man=c[l][0],box1=c[l][1],box2=c[l][2],box3=c[l][3];
int xman=nm[man][1],yman=nm[man][2];
int xbox1=nm[box1][1],ybox1=nm[box1][2];
int xbox2=nm[box2][1],ybox2=nm[box2][2];
int xbox3=nm[box3][1],ybox3=nm[box3][2];
vis[xbox1][ybox1]=vis[xbox2][ybox2]=vis[xbox3][ybox3]=false;
if(box1==button[1]&&box2==button[2]&&box3==button[3])
{
printf("%d\n",f[man][box1][box2][box3]);
return 0;
}
int step=f[man][box1][box2][box3];
for(int i=0;i<4;i++)
{
int nxman=xman+nextx[i];
int nyman=yman+nexty[i];//拓展一步
if(nxman>=1&&nxman<=R&&nyman>=1&&nyman<=C){
if(vis[nxman][nyman]&&f[pos[nxman][nyman]][box1][box2][box3]==-1)//这种状态没有走过
{
f[pos[nxman][nyman]][box1][box2][box3]=step+1;
c[++k][0]=pos[nxman][nyman];
c[k][1]=box1;
c[k][2]=box2;
c[k][3]=box3;
}
int q[4];
q[1]=box1;q[2]=box2;q[3]=box3;
if(pos[nxman][nyman]==q[2])swap(q[1],q[2]);
if(pos[nxman][nyman]==q[3])swap(q[1],q[3]);//避免状态重复
if(pos[nxman][nyman]==q[1])
{
int nnxman=xman+2*nextx[i];
int nnyman=yman+2*nexty[i];//沿当前方向再向前一步
if(nnxman>=1&&nnxman<=R&&nnyman>=1&&nnyman<=C&&vis[nnxman][nnyman])
{
q[1]=pos[nnxman][nnyman];
for(int a=1;a<=3;a++)
for(int b=a+1;b<=3;b++)
if(q[b]!=0&&q[a]>q[b])swap(q[a],q[b]);
if(f[pos[nxman][nyman]][q[1]][q[2]][q[3]]==-1)
{
f[pos[nxman][nyman]][q[1]][q[2]][q[3]]=step+1;
c[++k][0]=pos[nxman][nyman];
c[k][1]=q[1];
c[k][2]=q[2];
c[k][3]=q[3];
}
}
}
}
vis[xbox1][ybox1]=vis[xbox2][ybox2]=vis[xbox3][ybox3]=true;
}
}
}
总结
bfs问题，最关键的是建模
C.tree
题目描述
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。
输入
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行
每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)
输出
一行表示所求生成树的边权和。
样例输入
2 2 1
0 1 1 1
0 1 2 0
样例输出
2
数据规模和约定
10%:V<=10
30%:V<=15
100%:V<=50000,E<=100000
所有数据边权为[1,100]中的正整数。
题解
考虑如何才能让白边显得更（不）重要，即在每条白边上（加上）减去一个值。
我们可以二分这个值，然后用寻常方法做最小生成树。 统计在此最小生成树里有多少白边。
然后我们就可以找到一个合适的值，带这个权做一次最小生成树。
在计算答案的时候把这些值补偿回去就做完了。
#include<cstdio>
#include<vector>
#include<algorithm>
#define PB(v) push_back(v)
using namespace std;
const int N=5e4+10;
const int M=1e5+10;
int n,m,k;
struct Edge{
int u,v,prew,noww,color;//端点,最初边权，修改后的边权，边的颜色
bool operator <(const Edge rhs)const{
return noww<rhs.noww||(noww==rhs.noww&&color<rhs.color);}
};
vector<Edge>w;//白边
vector<Edge>b;//黑边
int set[N];
int sum,cnt;
int findset(int x)
{
return set[x]==x?x:set[x]=findset(set[x]);
}
bool check(int x)
{
for(int i=0;i<w.size();i++)
w[i].noww=w[i].prew+x;//修改白边边权
Edge edge[M];
merge(w.begin(),w.end(),b.begin(),b.end(),edge);//修改后白边和黑边按顺序加入容器中
for(int i=0;i<n;i++)
set[i]=i;
sum=cnt=0;
for(int i=0;i<m;i++)//跑最小生成树
{
int fu=findset(edge[i].u);
int fv=findset(edge[i].v);
if(fu==fv)continue;
set[fu]=fv;
sum+=edge[i].noww;
if(!edge[i].color)cnt++;
}
return cnt>=k;//白边数目与需要数目
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
{
Edge e;
scanf("%d%d%d%d",&e.u,&e.v,&e.prew,&e.color);
e.noww=e.prew;
if(e.color==0)w.PB(e);
else b.PB(e);
}
sort(b.begin(),b.end());
sort(w.begin(),w.end());
int l=-101,r=101;
while(l<r-1)//二分修改的边权
{
int mid=l+r>>1;
if(check(mid))l=mid;//白边多了说明加的数过小
else r=mid;//白边少了说明加的数过大
}
check(l);
printf("%d\n",sum-l*k);
return 0;
}
比赛总结
这套题最关键的就是bfs建模和二分边权的生成树