ECNU 2018 程序能力实训第一次机考(下午场)

xiaoxiao2021-02-28  2

https://acm.ecnu.edu.cn/contest/64/

A.闪卡销售

公司有 n 种类型的闪卡要出售,闪卡类型编号为 1,2,3,,n,第 i 种类型的闪卡数量为 ai

现有多个收购商给出的 m 条关于闪卡的报价信息 (p,q),表示收购第 p 种类型的闪卡的单价为 q

请计算公司如何销售,才能获得最多收益。

每个收购商可以收购无限量的闪卡。

Input

第一行输入两个整数 n,m (1n,m1000),其中 n 为闪卡类型数目,m 为报价信息数目。

第二行输入 n 个整数 a1,a2,a3,,anai (1ai1000) 表示第 i 种类型闪卡数量。

接下来 m 行,每行输入两个整数 p,q (1pn,1q1000),表示第 p 种类型的闪卡的报价 q

Output

输出一行,即最多卖出多少价值的闪卡。

题解:保存每个二元对,排序一下,每次取最大。 最大*数量 加起来就是了 ,无难度。(题目一开始没看懂导致代码很垃圾)

#include <bits/stdc++.h> using namespace std; const int maxn = 1200; struct info{ int x; int price; info(int a = 0 , int b = 0):x(a),price(b){}; bool operator < (const info& rhs){ return rhs.price < price; } }; int num[maxn]; vector<info> vec; int main() { int n = 0 , m = 0; cin >> n >> m; int x = 0, y = 0; for (int i = 1 ; i <= n ;++i) cin >> num[i]; for (int i = 0 ; i < m ; ++i) { cin >> x >> y; vec.push_back(info(x,y)); } sort(vec.begin(),vec.end()); int ans = 0; int sz = vec.size(); for (int i = 0 ; i < sz ; ++i) { x = vec[i].x; y = vec[i].price; if(num[x]) { ans += y*num[x]; num[x] = 0; } } cout << ans << endl; return 0; }

B. DNA 排序题

有若干个 DNA,每个 DNA 可能出现一次或者多次。

统计每个 DNA 出现的次数,然后再按照 DNA 出现次数的升序来输出这些 DNA。对于出现次数相同的 DNA,按照字典顺序排列输出(升序)。

Input

第一行是一个整数 n

接下来 n 行,每行一个 DNA。每个 DNA 是由 A, C, G, T 字符组成的,长度不超过 20

对于 40% 的数据:1n20;对于 70% 的数据:1n2000;对于所有的数据:1n200 000

Output

输出经去重和排序后的 DNA,每个 DNA 一行。

题解:保存每个字符串,记录每个字符串的出现次数,然后先排次数后排字符串输出即可。难点可能在于怎么判断每个字符串是否出现过。暴力算法的话大概要O(n^2*L),全数据的话肯定挂。我考虑了两种方法:哈希+map<ull,int> 或 map<string,int> 把字符串映射成出去即可。然后直接sort就可以了。当然有兴趣写个计数排序+sort 可能会更快些。我自然用的是最懒的方法。。。

#include <bits/stdc++.h> using namespace std; const int maxn = 200000; struct Dna{ string info; int occur; bool operator < (const Dna& rhs){ if(occur == rhs.occur) return info < rhs.info; return occur < rhs.occur; } }; Dna seq[maxn]; int cnt = 1; int main() { int n = 0; cin >> n; string str; map<string,int> mps; for (int i = 0 ; i < n ; ++i){ cin >> str; int t = mps[str]; if(t != 0) seq[t].occur++; else { mps[str] = cnt; seq[cnt].info = str; seq[cnt++].occur = 1; } } sort(seq+1,seq+cnt); for (int i = 1 ; i < cnt ; ++i) cout << seq[i].info << endl; return 0; }

C. 字符串替换

输入一个只含有小写字母和数字的字符串,将其中的数字用数字前面的字母序列进行替换,字母序列连续出现次数等于该数字。

Input

输入一个只含数字和小写字母的字符串 s2|s|10 000)。

输入保证数字前面必有字母。连续数字个数不超过 3 个,没有前导零,不会都是零。

Output

输出替换后的字符串。

题解: 从头往后扫字符串。扫到非字母而是数字时,算出数字k的值,然后把之前最近第一个不是数字的字符开始输出k次。 然后扫完以后查一查还有没有没有输出的字符,因为如果字母后面没有数字就默认是0次,所以如果发现还有没输出的字符串输出即可。这道题多的人居然比上一题多。 (我偷懒用的string) #include <bits/stdc++.h> using namespace std; const int maxn = 12000; char str[maxn]; int len; int getNextNumber(int &start){ int num = 0; for (int i = start ; str[i] && isdigit(str[i]) ; ++i) num = num * 10 + str[i] - '0'; return num == 0?1:num; } void solve(){ string outs; for (int i = 0 ; i < len ; ++i){ if(isalpha(str[i])) outs += str[i]; else { int num = getNextNumber(i); for (int t = 0 ; t < num ; ++t) cout << outs; outs = ""; } } if(outs!="") cout << outs; cout << endl; } int main() { cin >> str; len = strlen(str); solve(); return 0; }

D. 移动游戏

给定初始位置 (0,0) 和目标位置 (a,b),从一个位置可进行上下左右四个方向的移动。现给定一个移动命令序列,请判断是否能通过执行该序列,从初始位置达到目标位置。

移动命令格式如下:

U: (x,y)(x,y+1)D: (x,y)(x,y1)L: (x,y)(x1,y)R: (x,y)(x+1,y)

移动命令序列必须从前往后一个一个命令执行。执行完之后从头开始继续一个一个执行。直到移动到目标位置就可停止。

一个命令都不执行也是符合要求的。

Input

第一行输入一个长度不超过 100 个字符的移动命令序列 ss 只包含字符: U, D, L, R。

第二行一个整数 q,表示询问数。

接下来 q 行,每行输入两个整数 ab,表示目标位置 (a,b)

部分分约定:

30%: 100a,b100, 保证只会出现 U, D 或只会出现 L, R, 1q100;70%: |a|,|b|200,1q105;100%: |a|,|b|109,1q105.

Output

对于每次询问,如果从 (0,0) 能移动到目标位置则输出 Yes 否则输出 No。

题解:       一、第一组数据:模拟。不断执行序列。成功即输出。不成功则判断是否发现一个序列走完离目标越来越远,是则输出失败。       二、第二组数据:广度优先搜索。把能够遍历到的点给遍历一遍。然后对于每个询问,判断是否在a,b中即可。处理负数的话,对数组加个偏移量就行了。(想想CSAPP课上 double数据是怎么干的)       三、第三组数据:想到了其实很简单。 因为你一定是走了一整个序列的正整数倍, 并且走到了序列的某个指令上。              令走一遍序列后所得到的位置偏移向量为 ~a , 当前走到的指令的偏移向量为 ~b , 询问所求的偏移向量为 ~c             那么一定有 x * (~a) + ~b = ~c 其中x为整数            也就是说如下的一元一次方程组有整数解:            x*Ax + Bx = Cx            x*Ay + By = Cy            解这个方程我想大家都会。但要注意特别判断有零的情况。 然后比较(Cx - Bx)/Ax 和 (Cy - By)/Ay 也就是说方程的两个解是否相同即可。

                    

#include <bits/stdc++.h> const int maxn = 200; using namespace std; int sz = 0; typedef long long long_int; struct Vector{ long_int x , y; Vector(long_int _x = 0 , long_int _y = 0):x(_x),y(_y){} /* Vector operator * (const int& k){ return Vector(x*k,y*k); } */ Vector operator + (const Vector & rhs){ return Vector(x+rhs.x,y+rhs.y); } Vector operator - (const Vector & rhs){ return Vector(x-rhs.x,y-rhs.y); } Vector operator = (const Vector& rhs){ x = rhs.x; y = rhs.y; } bool operator == (const Vector& rhs) const{ return (x == rhs.x) && (y == rhs.y); } bool buildby (const Vector& rhs)const { if(x == 0 && y == 0) return true; if(rhs.x == 0 && rhs.y == 0) return false; if(x * rhs.x < 0) return false; if(y * rhs.y < 0) return false; if(rhs.x == 0 && x != 0) return false; if(x == 0 && rhs.x != 0) return false; if(rhs.y == 0 && y != 0) return false; if(y == 0 && rhs.y != 0) return false; if(x == 0) return (y % rhs.y == 0); else if (y == 0) return (x % rhs.x == 0); else { if(y % rhs.y != 0 || x % rhs.x != 0) return false; int k1 = y / rhs.y; int k2 = x / rhs.x; return k1 == k2; } } void putLocation(){ cout << x <<' ' << y << endl; } }; Vector arr[maxn]; const Vector Up(0,1); const Vector Down(0,-1); const Vector Left(-1,0); const Vector Right(1,0); Vector EndSequence; string str; int querys; bool solve_Equation(Vector target){ for (int i = 0 ; i <= sz ; ++i){ Vector new_Vec = target - arr[i]; if(new_Vec.buildby(EndSequence)) return true; } return false; } int main() { arr[0] = Vector(0,0); cin >> str; cin >> querys; sz = str.size(); for (int i = 1 ; i <= sz ; ++i) { switch(str[i-1]) { case 'U' : arr[i] = arr[i-1] + Up; break; case 'D' : arr[i] = arr[i-1] + Down;break; case 'L' : arr[i] = arr[i-1] + Left;break; case 'R' : arr[i] = arr[i-1] + Right;break; } } EndSequence = arr[sz]; Vector target; long_int cx = 0, cy = 0; for (int i = 0 ; i < querys ; ++i) { cin >> cx >> cy; target = Vector(cx,cy); if(solve_Equation(target)){ cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }

E. 字串变换

假设对一个字符串可进行以下两种类型的变换:

对字串中的任意一个字符进行复制。例如:xyz 复制其中一个字符 y 变为 xyyz。对字串中的相邻的两个相同字符删除其中一个。例如:xxyz 删除其中一个字符 x 变为 xyz。

现在给出 n 个字符串,计算最少需要几次以上变换才能使得这 n 个字符串都变得相同。

Input

第一行输入一个整数 n

接下来 n 行,每行输入一个字符串,由小写字母组成,字符串长度不超过 100

对于 50% 的数据,1n100;对于 100% 的数据,1n105

Output

在每一行中输出所需要的最小变换次数。如果不可能达成目标,则输出 1

题解:        首先可以判断的是,每个字符串出现字母的规律必须是一样的。 比如(aabc: a-b-c) (abbbbc:a-b-c) (bac:b-a-c)        所以aabc,abbbbc,bac的结果一定是 -1            然后这个问题就自然而然转换成了如下问题:        给你你一串数字a1,a2..an,把他们都变成一样的数字t,如何让他们 差的绝对值 abs(t-ai) 的和最小。                        然后坑的地方就来了。这道题数据数量的范围是10^5。每个数据不超过100.        算这个差的绝对值最小的方法一开始我想平均值行不行?不行! 比如 1,1,1,100000。一定不是这么做的。这里面也没有什么动态规划的感觉。一看,字符串做多100位,干脆就1-100交个暴力上去算了。        90!最后一个点被卡常了。这个真是太恶心了,后来又考虑维护一个最大值最小值,考虑减少循环次数。还是TLE        这可把人惹急了???这种考试100的常数都接受不了吗,真的忍心吗。        实在没办法写了个二分l = 1 , r = 100 , mid = (l+r) / 2; 每次判断把mid,mid+1当成修改值测试.        如果mid小,则r = mid-1        如果mid+1小 则l = mid + 1        把100 压到 2*log(2,100) ,终于算是过了。

#include <bits/stdc++.h> using namespace std; typedef long long long_int; const long_int maxss = 20000100; const int maxn = 100050; char s[120]; int n = 0; struct data{ int length; vector<char> alpha; vector<int> occur; }; data seq[maxn]; int sum[maxn]; int max_num[maxn]; int total_len = 0; long_int try_aver(int index , int aver){ long_int res = 0; for (int i = 0 ; i < n ; ++i) res += abs(seq[i].occur[index] - aver); return res; } int solve(){ int ans = 0; total_len = seq[0].length; long_int tmp = 0; for (int i = 0 ; i < total_len ; ++i) { tmp = maxss; long_int tmp1 = 0 , tmp2 = 0; int l = 1 , r = 100; while(l <= r) { int mid = (l+r) >> 1; tmp1 = try_aver(i,mid); tmp2 = try_aver(i,mid+1); if(tmp1 < tmp2) { r = mid - 1; tmp = min(tmp,tmp1); } else { l = mid + 1; tmp = min(tmp,tmp2); } } ans += tmp; } return ans; } int main() { cin >> n; for (int i = 0 ; i < n ; ++i){ scanf("%s",s); // puts(s); int cnt = 0; char t = 0; int len = strlen(s); for (int j = 0 ; j < len ; ++j) { if(t != s[j]) { if(t != 0) { seq[i].alpha.push_back(t); seq[i].occur.push_back(cnt); sum[seq[i].length] += cnt; seq[i].length++; } t = s[j]; cnt = 1; } else cnt++; } if(t != 0) { seq[i].alpha.push_back(t); seq[i].occur.push_back(cnt); sum[seq[i].length] += cnt; max_num[seq[i].length] = max(cnt,max_num[seq[i].length]); seq[i].length++; if(seq[i].length != seq[0].length){ cout << -1 << endl; return 0; } for (int j = 0 ; j < seq[j].length ; ++j) { if(seq[i].alpha[j] != seq[0].alpha[j]) { cout << -1 << endl; return 0; } } } } // above are inputs; cout << solve() << endl; return 0; }

耗时:1小时58分钟。

只能说稍微长点自信。

毕竟还是菜。

转载请注明原文地址: https://www.6miu.com/read-2000133.html

最新回复(0)