2019.11.2XS模拟赛
loutianchi · · 个人记录
哎呀，昨天忘记写题解了！！！
今天回来补发一下
T1
Problem 1 选拔队员 (seat.pas/c/cpp)
背景
随着 WZOI 的老一辈人员的离开，WZOI 的人数越来越少了。CJH 教练于是想选拔一些人 进入团队
问题描述
这一天，许多的学生齐聚在机房的门口，等待这 CJH 教练的出现 。 。
CJH 教练过了不久就来了，他看见那么多人来参加。虽然十分高兴，但是机房的位置十 分有限，于是他要淘汰一部分人。
CJH 教练说：“各位同学，十分高兴你们能来到这个机房。但是机房内的电脑的数目十分 有限，现在如果你们能答出下面这个问题，那么你们就能成为团队的一份子。注意听，问题 是这样子的：‘机房内总共有 N（这个值 CJH 教练会告诉你）个位置，排列成一条直线，从 左往右编号为 1 到 N。现在你们中的 N 个人要坐到这 N 个位置上去，问总共有多少中安排 的方法。”
所有同学大呼太难了，于是 CJH 教练决定简化问题：从同学中选出若干个男生和若干多 个女生（即男女生的数目随便定）安排到机房内的 N 个位置上去，要求任意两位女生不能 相邻（即任意两个女生之间必须有至少一个男生），问总共有多少种方法，你们姑且可以认 为所有男生是等价的，所有女生是等价的。
CJH 为了再次降低难度，他只要求你将方案种数 mod M 即可。 当然，由于这个问题简化之后太简单了，于是 CJH 会用不同的 N 提问多次，这样他就可
以淘汰许多没能力的人了。
为了能顺利进入 WZOI，许多同学向 WZOI 的朋友求救。显然你就是他们的救星了，现在 将 CJH 教练的问题告诉你，要求你输出正确答案。
输入格式
输入数据第一行包含两个整数 T，M，分别表示测试数据的组数和要将结果 mod M； 接下来 T 行，每行有一个整数 N，表示机房里总共有 N 个位置。
输出格式
输出数据共 T 行，每行一个整数 S，表示总的方案数 mod M 之后的那个数。
样例输入输出
Sample #1
seat.in
seat.out
2 3
1
3
2
2
Sample #2
seat.in
seat.out
2 5
9
5
4
3
数据规模
对于 10%的数据，N≤100，T≤10；
对于 30%的数据，N≤1000，T≤100；
对于 50%的数据，N≤1000000，T≤1000；
对于 100%的数据，N≤1000000000，T≤10000；
对于 100%的数据，M≤10。我的代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#define mp(x,y) make_pair(x,y)
using namespace std;
int fastread()
{
char c;
int fh=1,x=0;
c=getchar();
while (c!='-' && (c<'0' || c>'9'))
c=getchar();
if (c=='-')
{
fh=-1;
c=getchar();
}
while (c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x*fh;
}
map<pair<int,int>,int> f;
int ans[110],tmp_ans;
pair<int,int> ycl(int mo)//预处理
{
int x,y,tmp=1;
x=2%mo,y=3%mo;
ans[1]=x;ans[2]=y;
while (!f[mp(x,y)])
{
cerr<<x<<" "<<y<<endl;
f[mp(x,y)]=tmp;
x=(x+y)%mo;
x^=y;
y=x^y;
x=x^y;
tmp++;
ans[tmp+1]=y;
}
tmp_ans=tmp-1;
return mp(tmp-f[mp(x,y)],f[mp(x,y)]);
}
int main()
{
freopen("seat.in","r",stdin);
freopen("seat.out","w",stdout);
int n,t=fastread(),mo=fastread();
pair<int,int> cs;//预处理出循环节和开始循环的地方(first是循环节,second是开始有循环节的地方)（这里好像开始有循环节的都是1，但是其他时候不一定，所以还是用一般的做法写了）
cs=ycl(mo);
cerr<<cs.first<<" "<<cs.second<<endl;
for (int i=1;i<=tmp_ans;i++)
cerr<<ans[i]<<" ";
cerr<<endl;
for (int i=1;i<=t;i++)
{
n=fastread();
printf("%d\n",ans[(n-cs.second)%cs.first+cs.second]);
}
return 0;
}
T2
Problem 2 观光旅游 (photo.pas/c/cpp)
背景
WZOI 的 CJH 教练经常出去旅游（机房男们那叫一个羡慕啊~~~~~）。当然，CJH 教练的 旅游可不是观赏风景那么简单……
问题描述
CJH 教练预选了 N 个城市，打算去这些城市逛逛，并且要拍出一定质量的照片，第 i 个城 市所能拍出的照片质量为 Ci。可是，由于眼光有限，CJH 教练选出的一些城市并不能拍出 多少精彩的照片，因此，Ci 可能小于零。N 个城市由一些公路连通，每个城市之间有且只 有一条路径使其连通。而 CJH 教练走的路线比较奇特，在他去的几个城市中，连通任意两 个城市的路径上的城市，CJH 教练也都要去过才行（其实就是要求经过的城市连通）。要知 道，拍出的照片可是要在机房中展览的，CJH 教练可不想让机房男嘲笑自己的拍照水准。 鉴于机房男的审美观都不咋的，在好照片中混一些烂照片也不是不可以。CJH 教练有些犯 难，选哪些城市才能让照片总质量最高呢？
CJH 教练非常看好你，就把这个光荣而艰巨的任务交给你了！
输入格式
输入数据第 1 行有 1 个正整数 N，表示城市个数。
第 2 行有 N 个整数，第 i 个表示在第 i 个城市所能拍出的照片质量 Ci。
接下来 N – 1 行，每行有两个整数 u，v（1≤u,v≤N，u≠v），表示城市 u 与城市 v 之间有 一条公路连接。
输出格式
输出数据仅一行，要求输出照片的最高总质量。
样例输入输出Sample #1
Sample #2
photo.in
photo.out
4
-1 3 1 2
4 1
1 3
1 2
5
数据规模
对于 10%的数据，N≤10，|Ci|≤1000； 对于 30%的数据，N≤1000，|Ci|≤2000；
对于 50%的数据，N≤10000，|Ci|≤4000；对于 100%的数据，N≤200000，|Ci|≤8000。
时间限制:1s
input#1:
5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
output#1:
4
input#2:
4
-1 3 1 2
4 1
1 3
1 2
output#2:
5
数据规模
对于 10%的数据，N≤10，|Ci|≤1000； 对于 30%的数据，N≤1000，|Ci|≤2000；
对于 50%的数据，N≤10000，|Ci|≤4000；对于 100%的数据，N≤200000，|Ci|≤8000。我的代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int fastread()
{
char c;
int fh=1,x=0;
c=getchar();
while (c!='-' && (c<'0' || c>'9'))
c=getchar();
if (c=='-')
{
fh=-1;
c=getchar();
}
while (c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x*fh;
}
int va[200010];//记录分数
int head[200010],to[400010],next[400010],tmp=0;//存图
int add(int u,int v)//加边
{
tmp++;
to[tmp]=v;
next[tmp]=head[u];
head[u]=tmp;
return 0;
}
int f[200010];//以第k个节点为根时的最大价值
bool vi[200010];
int dfs(int k)//找第k个节点
{
if (f[k]>=0) return f[k];
vi[k]=true;
int sum=0;
for (int i=head[k];i;i=next[i])
{
if (vi[to[i]]) continue;
sum+=dfs(to[i]);
}
if (sum+va[k]>=0) f[k]=sum+va[k];
else f[k]=0;
vi[k]=false;
return f[k];
}
int main()
{
freopen("photo.in","r",stdin);
freopen("photo.out","w",stdout);
int n=fastread();
for (int i=1;i<=n;i++)
va[i]=fastread();
int x,y;
for (int i=1;i<n;i++)
{
x=fastread();y=fastread();
add(x,y);
add(y,x);
}
memset(f,-1,sizeof(f));
memset(vi,false,sizeof(vi));//false代表没去过
dfs(1);
int ans=0;
for (int i=1;i<=n;i++)
cerr<<f[i]<<" ";
cerr<<endl;
for (int i=1;i<=n;i++)
ans=max(ans,f[i]);
cout<<ans<<endl;
return 0;
}
/*data1
5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
*/T3
Problem 3 骰子游戏 (cube.pas/c/cpp)
背景
机房里面的人最爱玩游戏，这句活说的一点也不错，每天都会有人设计出一种新的小游 戏
问题描述
WZOI 的 LZYP 大牛设计出一款小游戏。这个游戏地图是一个
由 N 行 N 列的棋盘组成的（每一个小格都是 1×1 正方形），如右图 就是一个 5×5 的的地图。LZYP 手中有一枚正方体，这枚正方体的
棱长恰好为 1。也就是说，这枚这正方体恰好可以覆盖一个棋盘格子。 在正方体的每一个面上分别标上了一个非负整数 W，当然正方体的六个面上的数字不一定相同。现在将这枚正方体放在棋盘上（恰好覆 盖一个格子），一个人可以你在棋盘上滚动该立方体（立方体可以向其前、后、左、右四个 方向滚动）。在滚动的过程中，立方体底部与棋盘接触的那个面上的数字被加入总和 S。
LZYP 想要知道该怎样滚动这个正方体，才能使正方体从一个格子滚动到另一个格子得到 的 S 值最小。LZYP 想要知道这个最小值 S，当然他会告诉你起始格子和目标格子的坐标。 注意：立方体在起始格子和目标格子上的地面数字也要被计入总和，起始格子和目标格子是不同的。
为了刁难你，LZYP 决定问你 T 个问题，当然每次你都需要正确告诉他答案是多少；否则 他就会一直烦着你，那么你就无法安心刷水题了。
输入格式
输入数据第一行包含三个整数 N，T（分别用一个空格隔开），分别表示棋盘有 N 行 N 列， 总共会有 T 个问题；
第二行有 6 个整数，表示立方体在开始格子上各个面上的 6 个数字，顺序是：前面、后面、
上面、右面、下面、左面。这 6 个整数用空格隔开。
接下来 T 行，每行四个整数 x1,y1,x2,y2，表示起始格子和目标格子的坐标（注意第一个是 列号，第二个是行号）。输入数据保证会有一条路径从起始格子到达目标格子。
输出格式
输出数据总共 T 行，每行一个整数 S，表示从起始格子到目标格子的最小和。
样例输入输出
Sample #1
cube.in
5 1
0 8 1 2 1 1
5 2 5 3
cube.out
5
Sample #2
cube.in
5 1
1 1 1 1 1 1
1 2 2 3
cube.out
3
样例解释
对于 Sample #1，一条可行的路径就是(5,2)→(4,2)→(4,1)→(5,1)→(5,2)→(5,3)，底面的数字 分别为 1,1,0,1,1,1。
对于 Sample #2，一条可行的路径就是(1,2)→(2,2)→(2,3)，底面的数字分别为 1,1,1。
数据规模
对于 20%的数据，N≤10，0≤W≤10；
对于 50%的数据，N≤50，0≤W≤100；
对于 100%的数据，N≤100，0≤W≤1000。
对于 100%的数据，T≤10.
时间限制
1s
提示
正方体的滚动是指，沿着底面与棋盘格子的一个公共边翻转。每个格子可以走多次，并且 每走一次，需要累加相应的权值。很坑的一道题！
好草啊
我的代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <iomanip>
using namespace std;
int movx[4]={ 0, 1, 0,-1},
movy[4]={-1, 0, 1, 0};
/*
int movx[4]={0,1,0,-1},
movy[4]={1,0,-1,0};
*/
/*
int movx[4]={0,-1,0,1},
movy[4]={-1,0,1,0};
*/
/*
int movx[4]={0,-1,0,1},
movy[4]={1,0,-1,0};
*/
//滚动规则
int fastread()//快读
{
char c;
int fh=1,x=0;
c=getchar();
while (c!='-' && (c<'0' || c>'9'))
c=getchar();
if (c=='-')
{
fh=-1;
c=getchar();
}
while (c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x*fh;
}
struct hhh//记录状态
{
int zft[7];//记录正方体面上的数字
int xu[7];
/* 1:前; 2:后 3:上 4:右 5:下 6:左*/
int x,y;
int zhi;//记录值
bool operator < (const hhh& rhs) const{
return zhi > rhs.zhi;
}
}cs;
int n,t;
int frx,fry,tox,toy;
int f[110][110];
priority_queue<hhh> q;
int vi[110][110][71];//这里注意一下：只知道一个面是无法确定一个正方体的摆放情况的（我一开始就是这样被卡的）
bool fanwei(int x,int y)//判断是不是在棋盘范围内(true means in)
{
return (x>=1 && x<=n && y>=1 && y<=n);
}
hhh gun(int ff,hhh pre)//将正方体转一下（给出转的方向和原始情况）
{
hhh xianzai;
if (ff==0)//向下滚
{
xianzai.zft[1]=pre.zft[3];
xianzai.zft[2]=pre.zft[5];
xianzai.zft[3]=pre.zft[2];
xianzai.zft[4]=pre.zft[4];
xianzai.zft[5]=pre.zft[1];
xianzai.zft[6]=pre.zft[6];
xianzai.xu[1]=pre.xu[3];
xianzai.xu[2]=pre.xu[5];
xianzai.xu[3]=pre.xu[2];
xianzai.xu[4]=pre.xu[4];
xianzai.xu[5]=pre.xu[1];
xianzai.xu[6]=pre.xu[6];
}
if (ff==1)//向右滚
{
xianzai.zft[1]=pre.zft[1];
xianzai.zft[2]=pre.zft[2];
xianzai.zft[3]=pre.zft[6];
xianzai.zft[4]=pre.zft[3];
xianzai.zft[5]=pre.zft[4];
xianzai.zft[6]=pre.zft[5];
xianzai.xu[1]=pre.xu[1];
xianzai.xu[2]=pre.xu[2];
xianzai.xu[3]=pre.xu[6];
xianzai.xu[4]=pre.xu[3];
xianzai.xu[5]=pre.xu[4];
xianzai.xu[6]=pre.xu[5];
}
if (ff==2)//向上滚
{
xianzai.zft[1]=pre.zft[5];
xianzai.zft[2]=pre.zft[3];
xianzai.zft[3]=pre.zft[1];
xianzai.zft[4]=pre.zft[4];
xianzai.zft[5]=pre.zft[2];
xianzai.zft[6]=pre.zft[6];
xianzai.xu[1]=pre.xu[5];
xianzai.xu[2]=pre.xu[3];
xianzai.xu[3]=pre.xu[1];
xianzai.xu[4]=pre.xu[4];
xianzai.xu[5]=pre.xu[2];
xianzai.xu[6]=pre.xu[6];
}
if (ff==3)//向左滚
{
xianzai.zft[1]=pre.zft[1];
xianzai.zft[2]=pre.zft[2];
xianzai.zft[3]=pre.zft[4];
xianzai.zft[4]=pre.zft[5];
xianzai.zft[5]=pre.zft[6];
xianzai.zft[6]=pre.zft[3];
xianzai.xu[1]=pre.xu[1];
xianzai.xu[2]=pre.xu[2];
xianzai.xu[3]=pre.xu[4];
xianzai.xu[4]=pre.xu[5];
xianzai.xu[5]=pre.xu[6];
xianzai.xu[6]=pre.xu[3];
}
return xianzai;
}
int work()//用bfs搜完来找最小值
{
hhh now=cs,zhuan;
memset(f,0x3f,sizeof(f));
memset(vi,0x3f,sizeof(vi));
now.x=frx;now.y=fry;
now.zhi=now.zft[5];
vi[now.x][now.y][now.xu[5]*10+now.xu[4]]=now.zft[5];
f[frx][fry]=now.zhi;
q.push(now);
int dqx,dqy;//要转到的坐标
while (q.size())
{
now=q.top();q.pop();
if (vi[now.x][now.y][now.xu[5]*10+now.xu[4]]>=f[tox][toy]) continue;
for (int i=0;i<4;i++)
{
dqx=now.x+movx[i];
dqy=now.y+movy[i];
if (fanwei(dqx,dqy))
{
zhuan=gun(i,now);
zhuan.x=dqx;
zhuan.y=dqy;
zhuan.zhi=now.zhi+zhuan.zft[5];
if (vi[dqx][dqy][zhuan.xu[5]*10+zhuan.xu[4]]<=zhuan.zhi) continue;
vi[dqx][dqy][zhuan.xu[5]*10+zhuan.xu[4]]=zhuan.zhi;
f[dqx][dqy]=min(f[dqx][dqy],zhuan.zhi);
q.push(zhuan);
}
}
}
cout<<f[tox][toy]<<endl;
return 0;
}
int main()
{
freopen("cube7.in","r",stdin);
freopen("cube.out","w",stdout);
n=fastread(),t=fastread();
for (int i=1;i<=6;i++)
cs.zft[i]=fastread(),cs.xu[i]=i;//初始状态
cs.zhi=cs.zft[5];
for (;t;--t)
{
frx=fastread(),fry=fastread(),tox=fastread(),toy=fastread();//起点和终点
// swap(frx,fry);
// swap(tox,toy);
work();
}
return 0;
}