https://acm.ecnu.edu.cn/contest/64/
A.闪卡销售
公司有 n 种类型的闪卡要出售，闪卡类型编号为 1,2,3,…,n，第 i 种类型的闪卡数量为 ai。
现有多个收购商给出的 m 条关于闪卡的报价信息 (p,q)，表示收购第 p 种类型的闪卡的单价为 q。
请计算公司如何销售，才能获得最多收益。
每个收购商可以收购无限量的闪卡。
第一行输入两个整数 n,m (1≤n,m≤1000)，其中 n 为闪卡类型数目，m 为报价信息数目。
第二行输入 n 个整数 a1,a2,a3,…,an，ai (1≤ai≤1000) 表示第 i 种类型闪卡数量。
接下来 m 行，每行输入两个整数 p,q (1≤p≤n,1≤q≤1000)，表示第 p 种类型的闪卡的报价 q。
输出一行，即最多卖出多少价值的闪卡。
题解：保存每个二元对，排序一下，每次取最大。 最大*数量 加起来就是了 ，无难度。（题目一开始没看懂导致代码很垃圾）
#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，按照字典顺序排列输出（升序）。
第一行是一个整数 n。
接下来 n 行，每行一个 DNA。每个 DNA 是由 A, C, G, T 字符组成的，长度不超过 20。
对于 40% 的数据：1≤n≤20；对于 70% 的数据：1≤n≤2000；对于所有的数据：1≤n≤200 000。输出经去重和排序后的 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. 字符串替换输入一个只含有小写字母和数字的字符串，将其中的数字用数字前面的字母序列进行替换，字母序列连续出现次数等于该数字。
输入一个只含数字和小写字母的字符串 s（2≤|s|≤10 000）。
输入保证数字前面必有字母。连续数字个数不超过 3 个，没有前导零，不会都是零。
输出替换后的字符串。
题解： 从头往后扫字符串。扫到非字母而是数字时，算出数字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,y−1)L: (x,y)→(x−1,y)R: (x,y)→(x+1,y)移动命令序列必须从前往后一个一个命令执行。执行完之后从头开始继续一个一个执行。直到移动到目标位置就可停止。
一个命令都不执行也是符合要求的。
第一行输入一个长度不超过 100 个字符的移动命令序列 s，s 只包含字符: U, D, L, R。
第二行一个整数 q，表示询问数。
接下来 q 行，每行输入两个整数 a 和 b，表示目标位置 (a,b)。
部分分约定：
30%: −100≤a,b≤100, 保证只会出现 U, D 或只会出现 L, R, 1≤q≤100;70%: |a|,|b|≤200,1≤q≤105;100%: |a|,|b|≤109,1≤q≤105.对于每次询问，如果从 (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 个字符串都变得相同。
第一行输入一个整数 n。
接下来 n 行，每行输入一个字符串，由小写字母组成，字符串长度不超过 100。
对于 50% 的数据，1≤n≤100；对于 100% 的数据，1≤n≤105。在每一行中输出所需要的最小变换次数。如果不可能达成目标，则输出 −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分钟。
只能说稍微长点自信。
毕竟还是菜。
