9.15NOIP模拟题
GRYZ 模拟考试套题 9.15
gryz信息组专场
题目名称 |
最初的最初 |
太 |
妃 |
糖 |
可执行文件名 |
eat |
hwc |
dance |
sugar |
输入文件 |
eat.in |
hwc.in |
dance.in |
sugar.in |
输出文件 |
eat.out |
hwc.out |
dance.out |
sugra.out |
时间限制 |
1s |
0.2s |
1s |
0.5s |
是否有部分分 |
无 |
无 |
无 |
无 |
满分 |
1000 |
100 |
100 |
100 |
空间限制 |
128M |
128M |
128M |
128M |
测试点数量 |
20 |
20 |
20 |
20 |
测试点分值 |
50 |
5 |
5 |
5 |
数据是否分层 |
否 |
是 |
是 |
否 |
不要相信出题人
注意事项:
1. 文件名(输入和输出文件名) 必须是英文小写。
2. 若无说明,对比方式均为忽略行末空格及文末回车的全文比较。
3. C/C++中函数 main()的返回值必须是 int,程序正常结束的返回
值必须是 0。
4. 评测环境为 cena 注意:windows 下 long long 输入输出请使用%I64d。
5. 编译时不打开任何优化选项。
6.本套题目不保证没有任何彩蛋。
另:题目难度与题目顺序无关!
最初的最初
题目描述:
思绪,漂浮,荒乱,不知去向。
那些记忆,凌乱的,盘旋于脑海,迟迟不肯离去。
以为,时间会带走一切,我拼命的拒绝着你虚假演绎的片段。
想忘记,忘记。
当一切又回到最初的最初,杂乱而又不知所措。hkd望着远处苍茫迷蒙的混沌,陷入了久久的沉思。忽而,一把巨斧划过天际,盘古破开了混沌,hkd也在之混沌破灭之际被巨斧斩断,身体一分为二,化为了两件先天至宝,随盘古一起落入了洪荒之中。
后来,鸿钧成圣,捡到了两件先天至宝------hkd的身体,他想要知道混沌魔神hkd身体大大小,但是众所周知,古代人的算数水平都比较差,聪明的你能帮助他解决问题吗?
输入描述:
一行。两个数x和y,分别表示hkd两段身体的大小。
输出描述:
一行,hkd身体的大小。
样例输入:
4 7
样例输出:
11
提示:
x<=100000000;
y<=100000000;
题解:A+B
代码略 分值1000
太
题目描述:
残存的碎片却愈加清晰。
好久一段时间,记忆突然停顿了,脑子一片空白。
忘记此刻是何年何月,甚至忘记自己是谁,等待太久,一切都回不到最初的原点。
九年。
相遇,分离,重逢,再…… 从初始到末端。
如傻瓜般虔诚的追随在你左右
2333年,在银河系的某星球上,X军团和Y军团正在激烈地作战。在战斗的某一阶段,Y军团一共派遣了N个巨型机器人进攻X军团的阵地,其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时,这个巨型机器人就被摧毁了。X军团有M个激光武器,其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭,他们急需下达更多的指令。
输入描述:
一行 给你一个数n 表示下达的指令。
输出描述:
一行 请输出第n个回文数
样例输入:
输入样例#1:
2333
输出样例#1:
1334331
样例输出:
输入样例#2:
12345678987654321
输出样例#2:
23456789876543222234567898765432
提示:
对于 10%的数据 n<=100
对于 20%的数据 n<=100000000
对于 100%的数据 n<=1000000000000000000
/*
打表找规律
例如 23333
第一位减一,最后一位加一 13334
再对称 133343331
如果第一位是1就往前移动一位若当前第一位还是0就变为9
如果第一位为1并且第二位不是零就直接对称,否则对称的时候最后一位就不要
不要问我为什么....这是规律?理论依据呢......
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std;
char s[];
int num[],ans,flag; int main()
{
scanf("%s",s);
int len=strlen(s);
for(int i=len-; i>=; i--)
{
num[i+]=s[i]-''+num[i+]/;
num[i+]%=;
if(i==) num[i+]-=;
if(i==len-) num[i+]+=;
}
for(int i=; i<=len; i++)
{
if(num[i]==&&i==)
{
ans=;
continue;
}
else if(num[i]==&&i==&&ans) flag=,cout<<"";
else cout<<num[i];
}
if(ans==&&flag!=) len=len;
else len-=;
for(int i=len; i>=; i--)
{
if(num[i]==&&i==) continue;
else if(num[i]==&&i==&&ans) cout<<"";
else cout<<num[i];
}
}
妃
题目描述:
回忆的章节错乱不堪,想要收拾那些画面用来重温,却显得七零八乱。
整个人是麻木的,记忆也跟着苍白。
曾留下太多太深的足迹在心里。
刻意隐瞒,隐藏,隐忍着……
用近乎笨拙的方式隐身荒芜的背后,一直在原地徘徊。
决绝的用极端的方式否定了一切的伤痕和不舍, 清楚的听见自己心碎的声音。
一次次对灵魂华丽的自残,壮观而且荒谬。
我想我还是做错了,一味强求,不想离开你。
众所周知,三校区有一项优雅的大课间活动——广场舞。广场舞在以前是十分好跳的,同学们只要随着音乐翩翩起舞即可。但是三区校长为了增加广场舞的趣味性和可观性,勒令同学们摞成一摞跳操。同学们碍于各班班长的淫威只得同意了,同学们在跳操时是这样纸的,30个人摞成一摞(因为学校人数太少了,(*^__^*) ),摞成了n摞:
校长会偷偷的窝在小黑屋里,放各种颜色的烟花来指挥跳舞。校长最多可以燃放30个烟花,烟花有四种颜色,分别可以指挥所有的同学向东,西,南,北各移动一个格。但是这样跳操太累了,同学们都想偷懒,当一摞同学最下面的同学移动到教学楼时,这摞同学最上面的学生会跳到教学楼顶层,如下图
同学们想要尽可能多的偷懒,于是找到了你,总校后勤烟花爆竹管制处处长。
因为校长的烟花都是由你提供的,而校长只会按照你提供的烟花的顺序去燃放烟花,请你给出最多可以有几名同学偷懒,和此时燃放烟花的顺序。顺序用E,W,S,N表示指挥东西南北各种不同颜色的烟花。若有多个相同的,输出字典序最小的。
输入描述:
第1行3个整数n,m,k,描述同学摞成了几摞,教学楼的个数,校长可燃放的烟花的个数。
第2到1+n行每行两个整数x,y,描述n摞同学开始时的坐标。
第n+2到n+m+1行每行两个整数x,y,描述m个教学楼的坐标。
输出描述:
两行。
第一行 :最多能偷懒的学生的个数。
第二行 :此时燃放烟花的方案。
样例输入:
3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7
样例输出:
6
EEE
提示:
10%的数据,n<=1000,m<=1000,k<=5
40%的数据,n<=1000,m<=1000,k<=10
70%的数据,n<=1000;m<=1000;k<=20
100%的数据,n<=1000,m<=1000,k<=30,0<=x<=10000,0<=y<=10000
洛谷 P2905
/*
一到比较好的动态规划
dp[k][i][j]表示吹k次哨 纵向移动了i-31步,横向移动了j-31步,所能拯救的最多的牛的数量。
当j-31<0时,说明是向西移动,反之向东移动。i-31也是同理的。
转移显然 预处理和输出麻烦
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib> #define N 1507
#define inf 0x3f3f3f3f using namespace std;
int n,m,K,ans;
int dx[]={,,,-};
int dy[]={,,-,};
char step[][][];
char C[]={'W','S','N','E'};
int cnt[][],dp[][][];
int cawx[N],cawy[N],grax[N],gray[N]; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int max(int a,int b,int c,int d)
{
return max(max(a,b),max(c,d));
} void init()
{
n=read();m=read();K=read();
for(int i=;i<=n;i++) cawx[i]=read(),cawy[i]=read();
for(int i=;i<=m;i++) grax[i]=read(),gray[i]=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int cx=cawx[i]-grax[j];
int cy=cawy[i]-gray[j];
if(abs(cx)<= && abs(cy)<=) //因为k<=30,所以当有一个方向的距离大于30,就不用考虑了,因为一定不可能走到
cnt[cx+][cy+]++;//否则cnt记录走纵向i步横向走j步所能拯救的牛的数量.
}
} void work()
{
for(int k=;k<=K;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
dp[k][i][j]=-inf,step[k][i][j]='Z';
dp[][][]=;
//因为他可以向上下左右走,为了防止负坐标的出现,我们把一开始时的原点坐标当做(31,31).
for(int k=;k<=K;k++)
for(int i=;i<=;i++)//可能向左向右30步,所以循环61次
for(int j=;j<=;j++)
dp[k][i][j]=cnt[i][j]+max(dp[k-][i+][j],dp[k-][i-][j],dp[k-][i][j+],dp[k-][i][j-]); for(int i=;i<=;i++)
for(int j=;j<=;j++)
ans=max(ans,dp[K][i][j]);
} void solve()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(ans==dp[K][i][j]) step[K][i][j]='A'; //如果为纵向走i步横向走j步是一种可行的走法,记录以方便求字典序最小. for(int k=K-;k>=;k--)//倒序找出所有可能的走法.
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int l=;l<;l++)
{
if(dp[k][i][j]+cnt[i+dx[l]][j+dy[l]]==dp[k+][i+dx[l]][j+dy[l]]
&& step[k+][i+dx[l]][j+dy[l]]<'Z')
step[k][i][j]=C[l];
}
printf("%d\n",ans); int i=,j=;
for(int k=;k<K;k++)
{
cout<<step[k][i][j];
if(step[k][i][j]=='E') i--;//坐标原点在右下角!
else if(step[k][i][j]=='W') i++;
else if(step[k][i][j]=='S') j++;
else if(step[k][i][j]=='N') j--;
}return;
} int main()
{
init();
work();
solve();
return ;
}
糖
题目描述:
还是忘不了。
关于你的好与不好。
分分合合,早已成为习惯。
偏执的如同我的性格般执拗。
什么事都不做,安静的蜷缩在被窝里,细数自己的心碎与莫落。
最初的最初。
最后的最后。
Xxy每天都奋斗在跳楼梯的第一线,所以回宿舍后感到又累又饿,很快陷入了梦乡。在梦中,xxy进入了一个巨大的城堡。
这个题从叶子节点去算的话显然很困难,所以我们可以从xx所在的两个点开始倒着搞。 min和man记录每个节点最多和最少有多少个糖果才能让xx恰好吃到k只。然后,分别以这两个点为根节点,深搜一下求出所有的min和man。
接着,二分答案,求一下对于每个节点,g群糖果中符合条件的糖果的群数。最后,群数*k即为所求。
Xxy惊讶的发现,这座城堡有n个房间和m条走廊,走廊非常窄,只能单向通行。Xxy惊讶的发现在每个房间里都有一个魔法阵,魔法阵可以召唤魔法糖果,每个房间有且只有一个魔法糖果。每个魔法糖果都有一个饱腹值,xxy吃下糖果,就会增加饱腹值,不那么饿。与吃糖果相反的是,xxy需要穿越走廊才能吃到糖果,而每个走廊又有一定的疲惫值。Xxy想在吃完糖果后返回出发点。
Xxy现在非常的饥饿,所以她想吃到尽量多的糖果。但是,xxy也非常的累,所以她不想去浪费时间走更多的路。所以xxy希望在平均单位时间里,获得的饱腹值尽可能的大。请问xxy能得到的最大平均饱腹值是几?(因为xxy太饿了,所以他至少要吃掉2颗糖果)
输入描述:
第一行:输入n,m,分别表示城堡中房间的数量,和走廊的数量。
第二行:输入n个数f,表示从1到n号房间内,每个房间里糖果能提供的饱腹值。
接下来m行,每行输入三个数x,y,z,表示房间x与y之间有走廊相连通。走完这条走廊的疲惫之为z。
输出描述:
一行,一个数ans表示xxy能得到的最大平均饱腹值,结果保留两位小数。
样例输入:
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
样例输出:
6.00
提示:
对于100%数据:2≤n≤1000,2≤m≤5000,1≤x,y≤n,1≤f,z≤1000。
洛谷P2868
/*
这道题...算分数规划?
设一段路程的收益是F,花费是dis,则比率为 ΣF/Σdis=r
要找出最大的r
二分出r设为x ,将每条边的边权修改为 “目的地的收益f - 边长度dis*x”
然后SPFA检查图上是否有负环,有负环则x可以更优,答案可以增大。
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 100010 using namespace std;
const double eps=1e-; struct edge
{
int v,nxt,w;
double c;
} e[N<<];
int head[N],f[N];
bool vis[N];
double dis[N];
int n,m,mct,u,v,w; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} void add(int u,int v,int w)
{
e[++mct].v=v;e[mct].nxt=head[u];e[mct].w=w;head[u]=mct;
} bool SPFA(int u)
{
vis[u]=;
for(int i=head[u]; i; i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].c)
{
dis[v]=dis[u]+e[i].c;
if(vis[v] || SPFA(v))
{
vis[v]=;
return ;
}
}
}vis[u]=;return ;
} void judge(double r)
{
for(int i=; i<=mct; i++)
e[i].c=(double)e[i].w*r-f[e[i].v];
return;
}
bool check()
{
for(int i=; i<=n; i++)
if(SPFA(i))return ;
return ;
}
int main()
{
n=read();m=read();
for(int i=; i<=n; i++) f[i]=read();
for(int i=; i<=m; i++)
{
u=read();v=read();w=read();
add(u,v,w);
}
double l=,r=,ans;
while(r-l>eps)
{
double mid=(l+r)/;
judge(mid);
if(check())
{
ans=mid;l=mid;
}
else r=mid;
}
printf("%.2f\n",ans);
return ;
}
最新文章
- [LeetCode] Unique Substrings in Wraparound String 封装字符串中的独特子字符串
- nuget 服务器
- Python开发入门与实战14-基于Extjs的界面
- MVC之过滤器
- web初学之request,session与application
- WPF之MVVM(Step2)&mdash;&mdash;自己实现DelegateCommand:ICommand
- 以DDD为开发模式的设计开发步骤可以是
- python子类分配
- easyUi中的一段漂亮代码之将list转换成tree.
- JAVA类型信息——Class对象
- 2006: [NOI2010]超级钢琴 - BZOJ
- POJ 2029 Get Many Persimmon Trees(DP||二维树状数组)
- Linux下Nginx的安装、升级及动态添加模块
- 纯IPv6环境App适配的坑
- Android开发(20)--RadioGroup的使用
- 网页 HTML表格
- php 实现购物车功能,以大苹果购物网为例,上图上代码。。。。
- Liunx find的运用
- POJ1163-The Triangle-动态规划
- GET 和 POST 请求的优缺点和误区