10.11NOIP模拟赛

2023-10-20 10:50
文章标签 模拟 noip 10.11

本文主要是介绍10.11NOIP模拟赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题 A: 图腾计数

时间限制: 1 Sec
内存限制: 128 MB
提交: 95
解决: 54
提交 状态

题目描述

whitecloth 最近参观了楼兰图腾。图腾的所在地有一排N 个柱子，N个柱子的高度恰好为一个1 到N 的排列，而楼兰图腾就隐藏在这些柱子中。由于whitecloth 弱爆了，他只知道图腾由3 个柱子组成，这三个柱子组成了下凸或上凸的图形（>.<），所谓下凸，设三个柱子的高度从左到右依次为h1，h2，h3，那么h1>h2，h3>h2，上凸则满足h1<h2，h3<h2。现在whitecloth 也找不到图腾具体是哪三个柱子，他只想知道满足这两个形状的柱子有几组。

输入

第一行一个数N
接下来一行N 个数，依次表示每个柱子的高度

输出

一行两个数，表示下凸形状的数量和上凸形状的数量，用空格隔开

样例输入

51 5 3 2 4

样例输出

3 4

提示

对于30%的数据，N<=100

对于100%的数据，N<=200000



问题 B: 分糖果

时间限制: 1 Sec
内存限制: 128 MB
提交: 88
解决: 33
提交 状态

题目描述

whitecloth 有N 个糖果，小猫rainbow 和freda 来找whitecloth 要糖吃……对于每个糖果，rainbow 和freda 各有一个喜欢度ri 和fi，whitecloth不能不给他们糖果（他们会闹的），但又不想全给，于是whitecloth决定给他们恰好M 块糖果。为了让两只小猫不要闹矛盾，whitecloth 希望所给糖果的ri 的和与fi的和的差值的绝对值尽量小，在此基础上，whitecloth 还希望所有ri和fi 的总和最大，于是他请你来帮他出主意。

输入

第一行两个数N，M
接下来N 行，每行两个数ri，fi

输出

第一行一个数，表示最小的差值的绝对值
第二行一个数，表示最大的ri 和fi 的总和。

样例输入

4 21 22 34 16 2

样例输出

210

提示

对于30%的数据，N<=20,M<=10


对于100%的数据，N<=200,M<=20,1<=ri,fi<=20,M<=N







注意数组下标为负如何处理

问题 C: 智力游戏

时间限制: 1 Sec
内存限制: 128 MB
提交: 71
解决: 29
提交 状态

题目描述

whitecloth 最近迷上了一个你小时候已经玩厌了的游戏：移火柴棒。他现在吵着要你陪他玩，你没有办法，只好写一个程序来完成这个工作了。

你被给出了一个火柴拼成的等式，比如说下面这个：（ 5 + 7 = 7 ）

它显然是不成立的，但是我们可以通过移动一个其中的火柴使得它成立。变成如下的一个等式：( 6 + 1 = 7 )

现在给出一个类似的等式，请问最少移动多少根火柴可以使得它变成一个成立的等式。

输入

三个整数，表示原等式中的两个加数以及和

输出

一个数，表示最小移动几根火柴能使等式成立，不允许改变位数以及符号，不要制造0 开头的数。

样例输入

5 7 7

样例输出

1

提示

对于100%的数据，每个数在0 到999 之间

问题 D: 最远距离

时间限制: 1 Sec
内存限制: 128 MB
提交: 87
解决: 33
提交 状态

题目描述

whitecloth 有一块矩形土地，被分为N*M 块1*1 的小格子。有的格子含有障碍物。如果从格子A 可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A 不可以走到格子B，就没有距离。如果格子X 和格子Y 有公共边，并且X 和Y 均不含有障碍物，就可以从X 走到Y。如果whitecloth 可以移走T 块障碍物，求所有格子间的最大距离。保证移走T 块障碍物以后，至少有一个格子不含有障碍物。

输入

第一行包含三个整数，N M T。
接下来有N 行，每行一个长度为M 的字符串，'0'表示空格子，'1'表示该格子含有障碍物。

输出

一个数表示答案，保留6 位小数

样例输入

3 3 0001001110

样例输出

1.414214

提示

对于20%的数据，满足1 <= N,M <= 30 ，0 <= T <= 0

对于40%的数据，满足1 <= N,M <= 30 ，0 <= T <= 2

对于100%的数据，满足1 <= N,M <= 30 ，0 <= T <= 30

//下凸 h1>h2<h3
//上凸 h1<h2>h3
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;
typedef long long LL;
const int MAXN=200010;int n;
LL shangtu,xiatu;
int qianda[MAXN],houda[MAXN];
int qianxiao[MAXN],houxiao[MAXN];
int a[MAXN],t[MAXN],b[MAXN],c[MAXN],d[MAXN];void add(int x,int d) {while(x<=n) {t[x]+=d;x+=(x&(-x));}
}int sum(int x) {int res=0;while(x) {res+=t[x];x-=(x&(-x));}return res;
}void work2() {int i,j;for(i=1;i<=n;++i) scanf("%d",&a[i]);for(i=1;i<=n;++i) {add(a[i]+1,1);c[i]=sum(a[i]);}memset(t,0,sizeof(t));for(i=n;i>=1;i--) {add(a[i]+1,1);d[i]=sum(a[i]);}for(i=1;i<=n;++i) {shangtu+=(LL)c[i]*d[i];xiatu+=(LL)(i-1-c[i])*(n-i-d[i]); }printf("%lld %lld",xiatu,shangtu);
}void init() {int i;scanf("%d",&n);work2();
}int main() {init();
}


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int MAXN=205;int f[MAXN][1510],Max,n,m;
int l[MAXN],r[MAXN];
bool p[MAXN][1510];void init() {int i,j,k;scanf("%d%d",&n,&m);for(i=1; i<=n; ++i) scanf("%d%d",&l[i],&r[i]);f[0][1000]=0;p[0][1000]=1;for(k=1; k<=n; ++k)for(i=m; i; --i)for(j=500; j<=1500; j++)if(p[i-1][j-l[k]+r[k]]&&f[i][j]<f[i-1][j-l[k]+r[k]]+l[k]+r[k]) {f[i][j]=f[i-1][j-l[k]+r[k]]+l[k]+r[k];p[i][j]=1;}int ans1=0x3f3f3f3f,ans2=-1;for(i=0;i<=500;++i) {if(p[m][i+1000]||p[m][1000-i]) {ans1=i;break;}}if(p[m][ans1+1000]&&ans2<f[m][ans1+1000]) ans2=f[m][ans1+1000];if(p[m][1000-ans1]&&ans2<f[m][1000-ans1]) ans2=f[m][1000-ans1];printf("%d\n%d",ans1,ans2);
}int main() {init();
}


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int MAXN=1010;int a,b,c,tot,ans=0x3fffffff;
int huo[10]={6,2,5,5,4,5,6,3,7,6};
bool at[10][7];int sum(int x) {int res=0;if(x<10) return huo[x];else  {while(x){int temp=x%10;res+=huo[temp];x/=10;}}return res;
}void change(int x,int *arr) {if(!x) {arr[++arr[0]]=0;return;}while(x) {arr[++arr[0]]=x%10;x/=10;}
}int Min(int a,int b) {return a<b?a:b;
}int make(int a,int b,int c,int A,int B,int C) {//A->a B->b C->cint x[5]={0},y[5]={0},z[5]={0},X[5]={0},Y[5]={0},Z[5]={0},res=0,i,j;change(a,x),change(b,y),change(c,z),change(A,X),change(B,Y),change(C,Z);if(x[0]!=X[0]||y[0]!=Y[0]||z[0]!=Z[0]) return 0x3fffffff;for(i=1;i<=x[0];++i) {int aa=x[i],AA=X[i];for(j=0;j<7;++j)if((at[aa][j]==1&&at[AA][j]==0))res++;}for(i=1;i<=y[0];++i) {int bb=y[i],BB=Y[i];for(j=0;j<7;++j)if((at[bb][j]==1&&at[BB][j]==0))res++;}for(i=1;i<=z[0];++i) {int cc=z[i],CC=Z[i];for(j=0;j<7;++j)if((at[cc][j]==1&&at[CC][j]==0))res++;}return res;
}void work() {int i,j;for(i=0;i<=1000;++i)for(j=0;j<=1000;++j) {if(i+j<=1000&&sum(i)+sum(j)+sum(i+j)==tot) {int temp=make(a,b,c,i,j,i+j);ans=Min(ans,temp);}}printf("%d",ans);
}void init(){at[0][0]=1;at[0][1]=1;at[0][2]=1;at[0][3]=1;at[0][4]=1;at[0][6]=1;at[1][2]=1;at[1][4]=1;at[2][0]=1;at[2][2]=1;at[2][3]=1;at[2][5]=1;at[2][6]=1;at[3][0]=1;at[3][2]=1;at[3][4]=1;at[3][5]=1;at[3][6]=1;at[4][1]=1;at[4][2]=1;at[4][4]=1;at[4][5]=1;at[5][0]=1;at[5][1]=1;at[5][4]=1;at[5][5]=1;at[5][6]=1;at[6][0]=1;at[6][1]=1;at[6][3]=1;at[6][4]=1;at[6][5]=1;at[6][6]=1;at[7][0]=1;at[7][2]=1;at[7][4]=1;at[8][0]=1;at[8][1]=1;at[8][2]=1;at[8][3]=1;at[8][4]=1;at[8][5]=1;at[8][6]=1;at[9][0]=1;at[9][1]=1;at[9][2]=1;at[9][4]=1;at[9][5]=1;at[9][6]=1;scanf("%d%d%d",&a,&b,&c);if(a+b==c){printf("0");return ;}tot=sum(a)+sum(b)+sum(c);
//	printf("tot=%d\n",tot);work();
}int main(){init();while(1);
}

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cstring>
# include <deque>
# include <cmath># define Max(a,b) ((a)>(b)?(a):(b))using namespace std;const int MAXN=40;int n,m,T;
int gx[4]={1,0,-1,0};
int gy[4]={0,1,0,-1};
double ans;
bool map[MAXN][MAXN];void bfs(int x,int y) {double qx,qy;deque < pair<int,int> > q;bool vis[MAXN][MAXN];int dis[MAXN][MAXN];memset(vis,0,sizeof(vis));dis[x][y]=map[x][y];vis[x][y]=1;q.push_back(make_pair(x,y));while(!q.empty()) {pair<int,int> t=q.front();q.pop_front();int cost=dis[t.first][t.second];int xx,yy;if(cost>T) break;qx=(double)t.first-x;qy=(double)t.second-y;ans=Max(qx*qx+qy*qy,ans);for(int d=0; d<4; ++d) {xx=t.first+gx[d];yy=t.second+gy[d];if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy]) {if(map[xx][yy]) {q.push_back(make_pair(xx,yy));dis[xx][yy]=cost+1;} else {q.push_front(make_pair(xx,yy));dis[xx][yy]=cost;}vis[xx][yy]=1;}}}return ;
}void init() {int i,j;char x;cin>>n>>m>>T;for(i=0; i<n; ++i)for(j=0; j<m; ++j) {cin>>x;map[i][j]=x=='1';}for(i=0; i<n; ++i)for(j=0; j<m; ++j)bfs(i,j);ans=sqrt(ans);printf("%.6lf",ans);return ;
}int main() {freopen("distance.in","r",stdin);freopen("distance.out","w",stdout);init();return 0;
}


这篇关于10.11NOIP模拟赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/246609。

相关文章

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》：本文主要介绍了如何使用CSS模拟HTML的title属性，通过鼠标悬浮显示提示文字效果，通过设置`.tipBox`和`.tipBox.tipContent`的样式，实现了提示内容的隐藏和显示，详细内容请阅读本文，希望能对你有所帮助... 效
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...
hdu4431麻将模拟

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况： 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想： 对于某张牌>=3个，先减去3个相同，再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
【算法专场】模拟（下）

【算法专场】模拟（下）

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法，这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+
阅读更多...
模拟实现vector中的常见接口

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
1 模拟——67. 二进制求和

1 模拟——67. 二进制求和

1 模拟 67. 二进制求和 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 示例 1：输入:a = "11", b = "1"输出："100"示例 2：输入：a = "1010", b = "1011"输出："10101" 算法设计 可以从低位到高位（从后向前）计算，用一个变量carry记录进位，如果有字符没处理完或者有进位，则循环处理。两个字符串对
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2