大连网站建设服务公司,达州市网站建设,php怎么做网站,搭建个人网站103. 电影 莫斯科正在举办一个大型国际会议#xff0c;有n个来自不同国家的科学家参会。 每个科学家都只懂得一种语言。 为了方便起见#xff0c;我们把世界上的所有语言用1到109之间的整数编号。 在会议结束后#xff0c;所有的科学家决定一起去看场电影放松一下。 他们去的…103. 电影 莫斯科正在举办一个大型国际会议有n个来自不同国家的科学家参会。 每个科学家都只懂得一种语言。 为了方便起见我们把世界上的所有语言用1到109之间的整数编号。 在会议结束后所有的科学家决定一起去看场电影放松一下。 他们去的电影院里一共有m部电影正在上映每部电影的语音和字幕都采用不同的语言。 对于观影的科学家来说如果能听懂电影的语音他就会很开心如果能看懂字幕他就会比较开心如果全都不懂他就会不开心。 现在科学家们决定大家看同一场电影。 请你帮忙选择一部电影可以让观影很开心的人最多。 如果有多部电影满足条件则在这些电影中挑选观影比较开心的人最多的那一部。 输入格式 第一行输入一个整数n代表科学家的数量。 第二行输入n个整数a1,a2…an,其中ai表示第i个科学家懂得的语言的编号。 第三行输入一个整数m代表电影的数量。 第四行输入m个整数b1,b2…bm,其中bi表示第i部电影的语音采用的语言的编号。 第五行输入m个整数c1,c2…cm,其中ci表示第i部电影的字幕采用的语言的编号。 请注意对于同一部电影来说bi≠ci。 同一行内数字用空格隔开。 输出格式 输出一个整数代表最终选择的电影的编号。 如果答案不唯一输出任意一个均可。 数据范围 1≤n,m≤200000, 1≤ai,bi,ci≤109 输入样例 3 2 3 2 2 3 2 2 3 输出样例 2 #include iostream
#include algorithm
#include cstringusing namespace std;const int N 200010;
int n, m, a[N], x[N], y[N], cinema[N*3], tot 0, k, ans[N*3];int find(int f)
{return lower_bound(cinema 1, cinema k 1, f) - cinema; // 返回找到的对应下标
}int main()
{cin n;for(int i 1; i n; i){cin a[i]; //n个整数a1,a2…an,其中ai表示第i个科学家懂得的语言的编号。cinema[tot] a[i];}cin m;for(int i 1; i m; i){cin x[i];cinema[tot] x[i];}for(int i 1;i m; i){cin y[i];cinema[tot] y[i];}//下面步骤为离散化sort(cinema 1, cinema tot 1);k unique(cinema 1, cinema tot 1) - (cinema 1);memset(ans, 0, sizeof(ans)); // 初始化ans 为0for(int i 1; i n; i) ans[find(a[i])]; //第i个科学家懂得的语言的编号int ans0 1, ans1 0, ans2 0;for(int i 1; i m; i) //从1 到 m{int ansx ans[find(x[i])], ansy ans[find(y[i])];if(ansx ans1 || (ansx ans1 ansy ans2)){ans0 i;ans1 ansx;ans2 ansy;}}cout ans0 endl;// cout ans1 endl;// cout ans2 endl;return 0;
} 104. 货仓选址 在一条数轴上有 N 家商店它们的坐标分别为 A1~AN。 现在需要在数轴上建立一家货仓每天清晨从货仓到每家商店都要运送一车商品。 为了提高效率求把货仓建在何处可以使得货仓到每家商店的距离之和最小。 输入格式 第一行输入整数N。 第二行N个整数A1~AN。 输出格式 输出一个整数表示距离之和的最小值。 数据范围 1≤N≤100000 输入样例 4 6 2 9 1 输出样例 12 #include iostream
#include algorithmusing namespace std;const int N 100010;
int n, a[N];int main()
{cin n;for(int i 1; i n; i) cin a[i];sort(a 1, a n 1); //排序int ans 0;int zw a[n/2 1];for(int i 1; i n; i)ans abs(a[i] - zw);cout ans endl;return 0;
} 105. 七夕祭 七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。 于是TYVJ今年举办了一次线下七夕祭。 Vani同学今年成功邀请到了cl同学陪他来共度七夕于是他们决定去TYVJ七夕祭游玩。 TYVJ七夕祭和11区的夏祭的形式很像。 矩形的祭典会场由N排M列共计N×M个摊点组成。 虽然摊点种类繁多不过cl只对其中的一部分摊点感兴趣比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。 Vani预先联系了七夕祭的负责人zhq希望能够通过恰当地布置会场使得各行中cl感兴趣的摊点数一样多并且各列中cl感兴趣的摊点数也一样多。 不过zhq告诉Vani摊点已经随意布置完毕了如果想满足cl的要求唯一的调整方式就是交换两个相邻的摊点。 两个摊点相邻当且仅当他们处在同一行或者同一列的相邻位置上。 由于zhq率领的TYVJ开发小组成功地扭曲了空间每一行或每一列的第一个位置和最后一个位置也算作相邻。 现在Vani想知道他的两个要求最多能满足多少个。 在此前提下至少需要交换多少次摊点。 输入格式 第一行包含三个整数N和M和TT表示cl对多少个摊点感兴趣。 接下来T行每行两个整数x, y表示cl对处在第x行第y列的摊点感兴趣。 输出格式 首先输出一个字符串。 如果能满足Vani的全部两个要求输出both 如果通过调整只能使得各行中cl感兴趣的摊点数一样多输出row 如果只能使各列中cl感兴趣的摊点数一样多输出column 如果均不能满足输出impossible。 如果输出的字符串不是impossible 接下来输出最小交换次数与字符串之间用一个空格隔开。 数据范围 1≤N,M≤100000, 0≤T≤min(N∗M,100000), 1≤x≤N, 1≤y≤M 输入样例 2 3 4 1 3 2 1 2 2 2 3 输出样例 row 1 #include iostream
#include algorithm
#include cstringusing namespace std;const int N 100010;
int n, m, t, x[N], y[N], a[N], s[N];int main()
{cin n m t;for(int i 1; i t; i) cin x[i] y[i];bool row !(t % n), col !(t % m);if(row){if(col) cout both ;else cout row ;}else{if(col) cout column ;else {cout impossible endl;return 0;}}long long ans 0;// 这里必须得long long不然 溢出 T.Tif(row){int num t / n;memset(a, 0, sizeof(a));for(int i 1; i t; i) a[x[i]];for(int i 1; i n; i) a[i] - num; //每个人的纸牌都减去t / ns[0] 0;//求前缀和for(int i 1; i n; i) s[i] s[i - 1] a[i]; //动态规划的思想求前缀和sort(s 1, s n 1);//转换为货仓选址问题for(int i 1; i n; i) ans abs(s[i] - s[(n 1) 1] ); //求中位数 s [(n1) 1] 或者 s[n/2 1]}if(col){int num t / m;memset(a, 0, sizeof(a));for(int i 1; i t; i) a[y[i]];for(int i 1; i m; i) a[i] - num;s[0] 0;for(int i 1; i m; i) s[i] s[i - 1] a[i];sort(s 1, s m 1);for(int i 1; i m; i) ans abs(s[i] - s[(m 1) 1] );// for (int i 1; i m / 2; i) ans s[m-i1] - s[i];}cout ans endl;return 0;} 106. 动态中位数 依次读入一个整数序列每当已经读入的整数个数为奇数时输出已读入的整数构成的序列的中位数。 输入格式 第一行输入一个整数P代表后面数据集的个数接下来若干行输入各个数据集。 每个数据集的第一行首先输入一个代表数据集的编号的整数。 然后输入一个整数M代表数据集中包含数据的个数M一定为奇数数据之间用空格隔开。 数据集的剩余行由数据集的数据构成每行包含10个数据最后一行数据量可能少于10个数据之间用空格隔开。 输出格式 对于每个数据集第一行输出两个整数分别代表数据集的编号以及输出中位数的个数应为数据个数加一的二分之一数据之间用空格隔开。 数据集的剩余行由输出的中位数构成每行包含10个数据最后一行数据量可能少于10个数据之间用空格隔开。 输出中不应该存在空行。 数据范围 1≤P≤1000, 1≤M≤9999 输入样例 3 1 9 1 2 3 4 5 6 7 8 9 2 9 9 8 7 6 5 4 3 2 1 3 23 23 41 13 22 -3 24 -31 -11 -8 -7 3 5 103 211 -311 -45 -67 -73 -81 -99 -33 24 56 输出样例 1 5 1 2 3 4 5 2 5 9 8 7 6 5 3 12 23 23 22 22 13 3 5 5 3 -3 -7 -3 #include iostream
#include algorithm
#include queue
#include vector
#include cstringusing namespace std;const int N 10010;int main()
{int t;cin t;while(t--){int x, m;cin x m;cout x (m1)/2 endl;priority_queueint max_heap; //大根堆priority_queueint,vectorint,greaterint min_heap; //小根堆int cnt 0;for(int i 1; i m; i){int now;cin now;if(min_heap.empty())min_heap.push(now);else{if(now min_heap.top()) min_heap.push(now);else max_heap.push(now);while(min_heap.size() max_heap.size()){min_heap.push(max_heap.top());max_heap.pop();}while(min_heap.size() max_heap.size() 1){max_heap.push(min_heap.top());min_heap.pop();}}if(i 1) //奇数输出{cnt;cout min_heap.top() ;if(cnt % 10 0) puts(); // 输出换行每行包含10个数据}}puts(); //输入完数据换行}return 0;
} 107. 超快速排序 在这个问题中您必须分析特定的排序算法----超快速排序。 该算法通过交换两个相邻的序列元素来处理n个不同整数的序列直到序列按升序排序。 对于输入序列9 1 0 5 4超快速排序生成输出0 1 4 5 9。 您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。 输入格式 输入包括一些测试用例。 每个测试用例的第一行输入整数n代表该用例中输入序列的长度。 接下来n行每行输入一个整数ai,代表用例中输入序列的具体数据第i行的数据代表序列中第i个数。 当输入用例中包含的输入序列长度为0时输入终止该序列无需处理。 输出格式 对于每个需要处理的输入序列输出一个整数op代表对给定输入序列进行排序所需的最小交换操作数每个整数占一行。 数据范围 0≤N500000, 0≤ai≤999999999 输入样例 5 9 1 0 5 4 3 1 2 3 0 输出样例 6 0 #include iostream
#include algorithm
#include cstring#define ll long longusing namespace std;
const int N 500010;
ll n, a[N], b[N];
ll ans;void merge(int l, int mid, int r)
{if(l r) return; //只剩一个数返回merge(l, l mid 1, mid);merge(mid 1, mid 1 r 1, r);int i l, j mid 1; //分成左右两边for(int k l; k r; k){if(j r || (i mid a[i] a[j])) b[k] a[i]; //j r 表示只剩左边或者两边都有比较a[i]和a[j] 较小的入列else{b[k] a[j];ans mid - i 1;}}for(int k l; k r; k) a[k] b[k]; // 把临时存放数组b的放回a数组
}void q_sort()
{for(int i 1; i n; i) cin a[i];ans 0;merge(1, (1 n) 1, n);cout ans endl;
}int main()
{while(cin n n) q_sort();return 0;
} 108. 奇数码问题 你一定玩过八数码游戏它实际上是在一个3×3的网格中进行的,1个空格和1~8这8个数字恰好不重不漏地分布在这3×3的网格中。 例如 5 2 8 1 3 _ 4 6 7 在游戏过程中可以把空格与其上、下、左、右四个方向之一的数字交换如果存在。 例如在上例中空格可与左、上、下面的数字交换分别变成 5 2 8 5 2 5 2 8 1 3 1 3 8 1 3 7 4 6 7 4 6 7 4 6 _ 奇数码游戏是它的一个扩展在一个n×n的网格中进行其中n为奇数1个空格和1~n2−1这n2−1个数恰好不重不漏地分布在n×n的网格中。 空格移动的规则与八数码游戏相同实际上八数码就是一个n3的奇数码游戏。 现在给定两个奇数码游戏的局面请判断是否存在一种移动空格的方式使得其中一个局面可以变化到另一个局面。 输入格式 多组数据对于每组数据 第1行输入一个整数nn为奇数。 接下来n行每行n个整数表示第一个局面。 再接下来n行每行n个整数表示第二个局面。 局面中每个整数都是0~n2−1之一其中用0代表空格其余数值与奇数码游戏中的意义相同保证这些整数的分布不重不漏。 输出格式 对于每组数据若两个局面可达输出TAK否则输出NIE。 数据范围 1≤n500 输入样例 3 1 2 3 0 4 6 7 5 8 1 2 3 4 5 6 7 8 0 1 0 0 输出样例 TAK TAK #include iostream
#include algorithm
#include cstring
#include vectorusing namespace std;int n;
long long ans;
vector int a[2];
const int N 510 * 510 10;
int c[N];void merge(int k, int l, int mid, int r)
{int x l, y mid 1; //分成两部分 x左 y右for(int i l; i r; i){if(y r || (x mid a[k][x] a[k][y]) ) c[i] a[k][x]; //或 后面的部分最好加括号else c[i] a[k][y], ans mid - x 1; //ans 是加一啊}for(int i l; i r; i) a[k][i] c[i];
}void mergesort(int k, int l, int r)
{if(l r) return;int mid (l r) / 2;mergesort(k, l, mid); //递归左半部分mergesort(k, mid 1, r); //递归右半部分merge(k, l, mid, r); //合并
}long long calc(int k)
{ans 0;mergesort(k, 0, n*n - 1);return ans;
}int main()
{while(cin n){a[0].clear();a[1].clear();for(int i 1; i n; i)for(int j 1; j n; j){int x; scanf(%d, x); //要用这种输入方式 才不会Segmentation Fault cin x 错误if (x) a[0].push_back(x); //除了0都push进数组里}for(int i 1; i n; i)for(int j 1; j n; j){int x; scanf(%d, x); //要用这种输入方式 才不会Segmentation Faultif(x) a[1].push_back(x);// while( (cin x) x ! 0) a[1].push_back(x); //错误}puts( a[0].size() (calc(1) - calc(0) 1) ? NIE : TAK); //判断逆序对是不是偶数偶数TAK奇数NIE 奇偶性质 // if( (calc(0) 1) (calc(1) 1) ) puts(TAK); //第一个局面和第二个局面 逆序对个数相同即奇偶性相同// else puts(NIE);}
} 转载于:https://www.cnblogs.com/wmxnlfd/p/10855959.html
