Monthly Archives: April 2017

hihoCoder 1505-小Hi和小Ho的礼物

Leave a reply

hihoCoder 1505-小Hi和小Ho的礼物

#1505 : 小Hi和小Ho的礼物

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

某人有N袋金币，其中第i袋内金币的数量是Ai。现在他决定选出2袋金币送给小Hi，再选2袋金币送给小Ho，同时使得小Hi和小Ho得到的金币总数相等。他想知道一共有多少种不同的选择方法。 具体来说，有多少种下标四元组(i, j, p, q)满足i, j, p, q两两不同，并且i < j, p < q, Ai + Aj = Ap + Aq。 例如对于数组A=[1, 1, 2, 2, 2]，一共有12种选法： 
i j p q
1 3 2 4
1 3 2 5
1 4 2 3
1 4 2 5
1 5 2 3
1 5 2 4
2 3 1 4
2 3 1 5
2 4 1 3
2 4 1 5
2 5 1 3
2 5 1 4

输入

第一行包含一个整数N。 第二行包含N个整数，A1, A2, A3 … AN。 对于70%的数据，1 <= N <= 100 对于100%的数据，1 <= N <= 1000, 1 <= Ai <= 1000000

输出

不同选择的数目。
样例输入
5
1 1 2 2 2
样例输出
12
简化一下题意就是：给定一个数组，从中取出四个数a,b,c,d，使得a+b=c+d，问一共有多少种取法。 首先尝试了一下$$O(n^4)$$的暴力方法，过了70%的数据。后面想想先把所有数存hash表，然后固定a,b,c三个数，如果a+b-c也在hash表中，则找到一种合法的取法，想来复杂度能降到$$O(n^3)$$，提交之后居然WA，没理解。 后来参考大神的解法。首先把数及其频率hash到hash1中，然后把任意两数之和的频率hash到hash2中。最后遍历a和b，则hash2[a+b]是所有和为a+b的两数取法数，hash2[a+b]-hash1[a]*hash1[b]则是所有不是a和b但两数之和也是a+b的取法数，如果a,b本身有多次重复的话，还需要加上(hash1[a]-1)*(hash1[b]-1)。 比如有三个1和两个2，a=1,b=2，则还剩两个1和一个2，此时，如果从1,2中选两个数等于3，则有2*1=2种取法，即(hash1[a]-1)*(hash1[b]-1)。但是还有可能有0+3=3的情况，这就是hash2[a+b]-hash1[a]*hash1[b]。 当然还需要分a和b是否相等两种情况，因为a==b的情况有点特殊。 代码如下： [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<string> #include<map> #include<unordered_map> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d", &n); vector<long long> nums(n, 0); unordered_map<long long, int> hash1, hash2; for (int i = 0; i < n; ++i) { scanf("%lld", &nums[i]); ++hash1[nums[i]]; } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { ++hash2[nums[i] + nums[j]]; } } long long ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] != nums[j])ans += hash2[nums[i] + nums[j]] – hash1[nums[i]] * hash1[nums[j]] + (hash1[nums[i]] – 1)*(hash1[nums[j]] – 1); else { int cnt = hash1[nums[i]]; int left = cnt – 2; ans += hash2[nums[i] + nums[j]] – cnt*(cnt – 1) / 2 + left*(left – 1) / 2; } } } printf("%lld\n", ans); return 0; } [/cpp] 本代码提交AC，用时444MS。]]>

hihoCoder 1502-最大子矩阵

1 Reply

hihoCoder 1502-最大子矩阵

#1502 : 最大子矩阵

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个NxM的矩阵A和一个整数K，小Hi希望你能求出其中最大（元素数目最多）的子矩阵，并且该子矩阵中所有元素的和不超过K。

输入

第一行包含三个整数N、M和K。 以下N行每行包含M个整数，表示A。 对于40%的数据，1 <= N, M <= 10 对于100%的数据，1 <= N, M <= 250 1 <= K <= 2147483647 1 <= Aij <= 10000

输出

满足条件最大的子矩阵所包含的元素数目。如果没有子矩阵满足条件，输出-1。
样例输入
3 3 9
1 2 3
2 3 4
3 4 5
样例输出
4
给定一个N*M的矩阵，要从中找出一个元素最多的子矩阵，使得该子矩阵的和不超过K。 如果确定了子矩阵的左上角点和右下角点，则唯一确定了该子矩阵。所以我们可以用一种完全暴力的方法来试一下这个题。两层循环确定左上角点(i,j)，两层循环确定右下角点(u,v)，再两层循环累加从(i,j)到(u,v)的元素和，如果和不超过K，则更新最大元素个数，否则继续循环。复杂度为$$O(n^6)$$，TLE，但是能过40%的数据。 类似这样求子矩阵的和，子数组的和等问题，一般都需要求从0到i的累加和。网上有一题也是求最大子矩阵的问题，但是那道题定义子矩阵的大小是用子矩阵的和来定义的，而本题是用子矩阵中元素个数来定义的。但是原理差不多，可以参考。 定义一个二维数组sum[i][j]表示固定子矩阵的左上角坐标为(1,1)（假设矩阵的下标从1开始），当右下角坐标为(i,j)时，这个子矩阵的和是多少。则有： sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+matrix[i][j] 这个很好理解，相当于求面积，sum[i][j-1]+sum[i-1][j]加了两遍sum[i-1][j-1]，所以要减掉一个，最后再加上sum[i][j]独有的matrix[i][j]。 有了sum[i][j]之后，怎样求任意一个子矩阵的和呢？假设我们要求第i,j两行、u,v两列交成的子矩阵的和，应该怎样计算呢。这个也很好算，也是面积的加加减减，如下图所示，把(j,v)的面积减去(j,u)左边以及(i,v)上边的面积，但是(i,u)左上的面积减了两次，所以还要加上。总结成公式就是： cursum=sum[j][v]-sum[j][u-1]-sum[i-1][v]+sum[i-1][u-1] 
      |               |
-----(i,u)----------(i,v)----
      |               |
      |               |
-----(j,u)----------(j,v)----
      |               |
通过cursum公式，我们很容易就能求出任意一个子矩阵的和了。但是要求和不超过K，且元素个数最多的子矩阵，还是免不了枚举起点和终点。所以最后求解的时候，我还是枚举了起点(i,j)和终点(u,v)，然后通过上述公式求到子矩阵的和cursum，如果cursum不超过K，则更新最大子矩阵元素个数。 但是，这种方法还是TLE了！在我几近绝望的时候，我试着把v的遍历顺序由u→m改成了由m→u。什么意思呢，因为要求元素个数最多，如果从u列到最大的m列的子矩阵和都不超过K，则此时的元素个数肯定是在这个循环里最大的，所以直接跳过了v从u→m-1的那些列。但是如果v的遍历顺序是u→m，则开始的好多v的子矩阵和都不超过K，这样的话，v就需要遍历很久才能找到一个超过K的子矩阵和，最坏的情况是，遍历到最大值m时的子矩阵和也不超过K，所以还不如从最大值往小的遍历。这么简单的一改，居然AC了！不知道会不会是数据太弱了，毕竟复杂度都是一样的$$O(n^4)$$。 代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<unordered_map> #include<string> #include<climits> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n, m, k; scanf("%d %d %d", &n, &m, &k); vector<vector<int>> matrix(n + 1, vector<int>(m + 1, 0)); int minvalue = INT_MAX; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &matrix[i][j]); minvalue = min(minvalue, matrix[i][j]); } } if (minvalue > k)printf("-1\n"); else if (minvalue == k)printf("1\n"); else { int ans = INT_MIN; vector<vector<int>> sum(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { sum[i][j] = sum[i – 1][j] + sum[i][j – 1] – sum[i – 1][j – 1] + matrix[i][j]; } } for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { //for (int u = 1; u <= m; ++u) { // for (int v = u; v <= m; ++v) { // TLE // int cursum = sum[j][v] – sum[j][u – 1] – sum[i – 1][v] + sum[i – 1][u – 1]; // if (cursum <= k)ans = max(ans, (j – i + 1)*(v – u + 1)); // else break; // } //} for (int u = 1; u <= m; ++u) { for (int v = m; v >= u; –v) { int cursum = sum[j][v] – sum[j][u – 1] – sum[i – 1][v] + sum[i – 1][u – 1]; if (cursum <= k) { ans = max(ans, (j – i + 1)*(v – u + 1)); break; } } } } } printf("%d\n", ans); } return 0; } [/cpp] 本代码提交AC，用时169MS。]]>

hihoCoder 1501-风格不统一如何写程序

Leave a reply

hihoCoder 1501-风格不统一如何写程序

#1501 : 风格不统一如何写程序

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi写程序时习惯用蛇形命名法(snake case)为变量起名字，即用下划线将单词连接起来，例如：file_name、 line_number。 小Ho写程序时习惯用驼峰命名法(camel case)为变量起名字，即第一个单词首字母小写，后面单词首字母大写，例如：fileName、lineNumber。 为了风格统一，他们决定邀请公正的第三方来编写一个转换程序，可以把一种命名法的变量名转换为另一种命名法的变量名。 你能帮助他们解决这一难题吗？

输入

第一行包含一个整数N，表示测试数据的组数。(1 <= N <= 10) 以下N行每行包含一个以某种命名法命名的变量名，长度不超过100。 输入保证组成变量名的单词只包含小写字母。

输出

对于每组数据，输出使用另一种命名法时对应的变量名。
样例输入
2
file_name
lineNumber
样例输出
fileName
line_number
本题要求把蛇形命名法和驼峰命名法相互转换。简单题，首先判断字符串中是否有下划线来区分原命名法，然后遍历字符串，找下划线或者大写字母，然后直接转换即可。 代码如下，注意在getline之前把换行符读了。 [cpp] #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<unordered_map> #include<string> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n; char c; scanf("%d", &n); scanf("%c", &c); // 读取换行符\n string line; while (n–) { getline(cin, line); if (line.find(‘_’) != string::npos) { string ans = ""; int len = line.size(), i = 0, j = 0; for (j = 0; j < len; ++j) { if (line[j] == ‘_’&&j + 1 < len) { line[j + 1] = toupper(line[j + 1]); ans += line.substr(i, j – i); i = j + 1; } } ans += line.substr(i, j – i); cout << ans << endl; } else { string ans = ""; int len = line.size(), i = 0, j = 0; for (j = 0; j < len; ++j) { if (isupper(line[j])) { line[j] = tolower(line[j]); if(ans=="") ans += line.substr(i, j – i); else ans += "_" + line.substr(i, j – i); i = j; } } ans += "_" + line.substr(i, j – i); cout << ans << endl; } } return 0; } [/cpp] 本代码提交AC，用时0MS。]]>

LeetCode Contiguous Array

Leave a reply

525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

给定一个二进制数组（即数组中只包含0和1），要求找到最长的子数组，使得该子数组中0和1的个数相等。 感觉应该用DP和累加和，但是没想出具体的解法，参考网上的题解。 把数组中的0换成-1，然后计算累加和，把[0,i]的累加和及对应的下标存入到一个hash中，即hash[sum[0,i]]=i，在后续的累加计算中，如果遇到累加和出现在hash中，则说明这两个区间之间的0和1个数相等。比如下面的例子：

  • 序列：    1,-1,-1,-1,1,-1,-1,-1,1
  • 累加和：1,0,-1,-2,-1,-2,-3,-4,-3

累加和第一次遇到-2时，记录hash[-2]=3，表示sum[0,3]=-2，当再次遇到累加和为-2时，是sum[0,5]=-2，则说明[4,5]之间的1和-1个数是相等的。因为序列中没有0元素，两次的累加和又一样，说明中间经过的数累加和是0，导致累加和没变化，累加和是0，又说明1和-1的个数相等，即1和0的个数相等。
代码如下，初始时，没有元素，累加和也是0，但是要记录下标是-1，实际跑一下第一个样例就知道了。

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        unordered_map<int, int> hash;
        hash[0] = -1; // init
        int sum = 0, n = nums.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i] == 1 ? 1 : -1;
            if (hash.find(sum) != hash.end()) {
                ans = max(ans, i – hash[sum]);
            }
            else {
                hash[sum] = i;
            }
        }
        return ans;
    }
};

本代码提交AC，用时138MS。
果然遇到子数组的问题，要善于利用累加和/积的方法。

LeetCode Complex Number Multiplication

Leave a reply

LeetCode Complex Number Multiplication Given two strings representing two complex numbers. You need to return a string representing their multiplication. Note i2 = -1 according to the definition. Example 1: 

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2: 
Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note:
  1. The input strings will not have extra blank.
  2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.
给定两个复数字符串，要求计算它们的乘积。 简单题，展开之后是：(a1+a2i)(b1+b2i)=(a1*b1-a2*b2)+(a1*b2+a2*b1)i。所以只需要提取出a1,a2,b1,b2，然后代入公式计算到c1和c2，最后用to_string转换为字符串即可。 代码如下： [cpp] class Solution { void str2cpx(const string& s, int& c1, int&c2) { int i = 0, j = 0; while (s[j] != ‘+’)++j; c1 = atoi(s.substr(i, j – i).c_str()); i = ++j; while (s[j] != ‘i’)++j; c2 = atoi(s.substr(i, j – i).c_str()); } public: string complexNumberMultiply(string a, string b) { int a1 = 0, a2 = 0, b1 = 0, b2 = 0, c1 = 0, c2 = 0; str2cpx(a, a1, a2); str2cpx(b, b1, b2); c1 = a1*b1 – a2*b2; c2 = a1*b2 + a2*b1; return to_string(c1) + "+" + to_string(c2) + "i"; } }; [/cpp] 本代码提交AC，用时3MS。]]>

LeetCode Minimum Height Trees

Leave a reply

LeetCode Minimum Height Trees For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels. Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels). You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges. Example 1: Given n = 4, edges = [[1, 0], [1, 2], [1, 3]] 

        0
        |
        1
       / \
      2   3
return [1] Example 2: Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 
     0  1  2
      \ | /
        3
        |
        4
        |
        5
return [3, 4] Show Hint
    Note: (1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.” (2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
    给定一个无向无环图，问以哪个顶点为根形成的有根树的树高是最小的，如果有多个这样的最小高度的有根树，则输出所有这样的根节点。 很有意思的一题，需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个，我想了想，应该最多只有两个吧。可以用反证法，假设有3个，则这3个根肯定会形成环，具体原因大家可以在纸上画个图举个例子就知道了。 然后我由题目的样例想到的是，把图转换为有根的最小高度的树，根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数，然后选两个度数最高的节点，对这两个点DFS求以他们为根时的树高，如果树高相同，说明这两个点都是答案，否则取树高更高的节点作为根节点。 但是很可惜，代码提交之后WA，错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。 
    8     3
  \    \
    2----0----5----6----7----9
  /    /
4    1
    在上图中，度数最多的前两个点是0和2，但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。 参考网上的题解，好巧妙呀。这种解法类似于剥洋葱，一层一层把叶子节点剥离掉，最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的，没剥掉一层，相当于树高减一，一直减，到最后还剩下的节点肯定就是根节点了。比如上图中，第一层剥掉8,3,9,4,1，变成下图 
    2----0----5----6----8
    第二层剥掉之后变成下图 
    0----5----6
    第三层剥掉之后就只剩下5号节点了，所以以5号节点为根，树的高度最低，只有3，而我的解法算出来的根节点0的树高是4，不是最小的。 
    5
    剥洋葱的解法用BFS来实现就非常方便了，BFS天然就是一层循环就是剥掉一层。 代码中，初始时，我们把图转换为类似邻接表的结果，但是每个vector里存的是unordered_set，而不是list，因为剥洋葱的时候，比如第一层时剥掉8号节点时，我们同时需要把2号节点的邻接表中的8号节点删掉，所以用unordered_set.erase就非常方便。后面循环时，没剥一层，我们就检查一下，把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时，剩余的节点就是有根树的根节点。如果剩余两个节点，说明这两个节点的高度是一样的，都是正确答案。 代码如下： [cpp] class Solution { public: vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) { if (n == 1)return{ 0 }; int m = edges.size(); vector<unordered_set<int>> graph(n, unordered_set<int>()); for (int i = 0; i < m; ++i) { graph[edges[i].first].insert(edges[i].second); graph[edges[i].second].insert(edges[i].first); } queue<int> q; for (int i = 0; i < n; ++i) { if (graph[i].size() == 1) q.push(i); } while (n > 2) { int t = q.size(); n -= t; while (t–) { int leaf = q.front(); q.pop(); for (auto par : graph[leaf]) { // only one par graph[par].erase(leaf); if (graph[par].size() == 1)q.push(par); } } } vector<int> ans; while (!q.empty()) { ans.push_back(q.front()); q.pop(); } return ans; } }; [/cpp] 本代码提交AC，用时79MS。]]>

    hihoCoder 1495-矩形分割

    Leave a reply

    hihoCoder 1495-矩形分割

    #1495 : 矩形分割

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

    描述

    小Hi有一块由NxM个单位正方形组成的矩形。现在小Ho在某些单位正方形上画了一道分割线，这条分割线或者是单位正方形的主对角线（用’\’表示），或者是副对角线（用’/’表示）。 现在小Hi想知道这些分割线把NxM的矩形分割成了多少块区域。 例如 
    /\
\/
    就把2×2的矩形分成了5个区域。 
    /\/\
\  /
 \/\
    把3×4的矩形分成了7个区域。

    输入

    第一包含两个整数N和M。(1 <= N, M <= 100) 以下N行每行包含M个字符。每个字符只可能是/\或者空格。

    输出

    分割成的区域数目。
    样例输入
    3 4
/\/\
\  /
 \/\
    样例输出
    7
    本题又是一个考察并查集的题，再一次栽在了并查集！ 给定一个由n*m个小正方形组成的大矩形，现在在某些小正方形上画一道分隔线，该分隔线可能是小正方形的主对角线\，也可能是副对角线/。问经过分隔之后，把大矩形分隔成了多少块区域。 判断平面区域个数问题，一般都可以转化为并查集的问题，但是这题相对上一次的并查集又进了一步，这题应该算是三维的并查集了。 对于小正方形的每个点，我们用三维信息来表示(x,y,z)，其中x,y表示顶点所在小正方形的行号和列号，z表示该顶点在该小正方形中的位置，坐标从左上角开始顺时针递增，如下图。 
    0-----1
|     |
|     |
3-----2
    初始时，每个顶点自成一体，所以par[i]=i。 但是因为画的分隔线只能是对角线，所以相邻两个正方形中的共享边肯定属于同一个区域，应该把相邻正方形共享边的两个顶点union起来。比如下图中，第一列的两个正方形，蓝色的两条边应该union，即左上角正方形的2号节点应该和左下角正方形的0号节点union；同理，第一行的两个正方形，红色的两条边也应该union，即左上角的1号节点和右上角的3号节点union。 其实，红色的边也可以union 0和2，但此时蓝色的边就应该union 1和3了，只要两者不一致并在整个程序中统一就行。 
    0-----1  0-----1
|     |  |     |
|     |  |     |
3-----2  3-----2
0-----1
|     |
|     |
3-----2
    注意，不是把红色边的0和1 union，2和3 union，因为0和1可能属于不同的区域，比如下图中，红色的0和1就属于不同的区域了。 
    0-----1  0-----1
|   / |  | \   |
| /   |  |   \ |
3-----2  3-----2
0-----1
|     |
|     |
3-----2
    初始化完成之后，就需要进行并查集操作了。如果遇到空格，好说，把这个正方形的四个顶点都union起来。 如果遇到左斜杠/，类似于上图左上角的分隔线，则把这个正方形中的四个顶点分成了两个不同的区域。此时，我们需要统一一个划分顶点的规则：被分隔的对角点和其顺时针的下一个顶点属于一个集合。比如3顺时针的下一个顶点是0，所以3和0 union；1顺时针的下一个顶点是2，所以1和2 union。 类似的，如果遇到右斜杠\，类似上图右上角的分隔线。根据统一的规则，0和1 union，2和3 union。 所有操作完成之后，统计一下并查集中不同区域的个数就是最终结果。 代码如下，注意%c会读取换行符，所以在每行开头先%c读取上一行的换行符。 [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> #include<vector> using namespace std; const int MAXN = 105; int n, m; vector<int> par(MAXN * MAXN * 4); int find_par(int u) { if (par[u] != u) par[u] = find_par(par[u]); return par[u]; } void union_par(int u, int v) { par[find_par(u)] = find_par(v); } int id(int x, int y, int z) { return x * m * 4 + y * 4 + z; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); int total = n * m * 4; for (int i = 0; i < total; ++i)par[i] = i; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (i > 0)union_par(id(i, j, 0), id(i – 1, j, 2)); if (j > 0)union_par(id(i, j, 3), id(i, j – 1, 1)); //if (i < n – 1)union_par(id(i, j, 2), id(i + 1, j, 0)); // 多余 //if (j < m – 1)union_par(id(i, j, 1), id(i, j + 1, 3)); // 多余 } } char c; for (int i = 0; i < n; ++i) { scanf("%c", &c); // 读取上一行的\n for (int j = 0; j < m; ++j) { scanf("%c", &c); if (c == ‘ ‘) { union_par(id(i, j, 0), id(i, j, 1)); union_par(id(i, j, 1), id(i, j, 2)); union_par(id(i, j, 2), id(i, j, 3)); //union_par(id(i, j, 3), id(i, j, 0)); // 多余 } else if (c == ‘/’) { union_par(id(i, j, 3), id(i, j, 0)); union_par(id(i, j, 1), id(i, j, 2)); } else if (c == ‘\\’) { union_par(id(i, j, 0), id(i, j, 1)); union_par(id(i, j, 2), id(i, j, 3)); } } } int ans = 0; for (int i = 0; i < total; ++i) { if (find_par(i) == i)++ans; } printf("%d\n", ans); return 0; } [/cpp] 本代码提交AC，用时4MS。]]>

    hihoCoder 1496-寻找最大值

    Leave a reply

    hihoCoder 1496-寻找最大值

    #1496 : 寻找最大值

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

    描述

    给定N个数A1, A2, A3, … AN，小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大。其中AND是按位与操作。 小Ho当然知道怎么做。现在他想把这个问题交给你。

    输入

    第一行一个数T，表示数据组数。(1 <= T <= 10) 对于每一组数据： 第一行一个整数N（1<=N<=100,000） 第二行N个整数A1, A2, A3, … AN (0 <= Ai <220)

    输出

    一个数表示答案
    样例输入
    2
3
1 2 3
4
1 2 4 5
    样例输出
    12
80
    给定一个数组，要求从中选出两个数a和b（它们的下标不能相同），使得乘积a*b*(a&b)最大。 这题的AC之路还挺有意思的，首先我尝试了$$O(n^2)$$的暴力方法，不出所料的TLE了，不过也得了40分。所以$$O(n^2)$$的方法肯定是不行的，我就想各种O(n)的方法。 首先分析一下a*b*(a&b)，有两个部分，a*b和a&b。最优的方案当然是求a*b*(a&b)整体的最大值，但是这需要$$O(n^2)$$。次优的方案是求a*b或者a&b的最大值，然后看看整体a*b*(a&b)会不会也是最大呢。 我先考虑了a&b，因为要使a&b越大，则a和b的高位要有很多一致的’1’，这样，a和b本身也就比较大，进而a*b也就比较大。但还是需要$$O(n^2)$$的时间，只不过循环过程中省略了a*b*(a&b)的计算。提交之后WA了，而且是0分，推断这种解法不可行。 后来尝试了求a*b的最大值，想法也和求a&b的最大值类似。如果a*b越大，则a,b本身也比加大，导致a&b也会比较大吧？求a*b的最大值，就好办多了，当然不能暴力两层循环，要不然又TLE。我们只需一次遍历，找到最大和次大的两个数，则他们的乘积肯定是最大的。这次提交之后，虽然也是WA，但是居然得了80分。 所以我就想，可能真的是a,b越大，则a*b*(a&b)也越大。后来一想可能会遇到a很大，二进制是10000；但是b也很大，而且是只比a小1，二进制是01111，这样虽然a*b很大，但是a&b就是0了。导致整体a*b*(a&b)是0。于是我进一步扩大了范围，记录前3大的元素first,second和third，他们之间有3个组合(first,second)、(first,third)、(second,third)，只需在这3个对里面求最大就好了。我当时的想法是，虽然first和second会遇到10000和01111的情况，但是second和third可能会不会了。提交之后，居然真的AC了！ 代码如下： [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> #include<vector> #include<climits> #include<cfloat> using namespace std; typedef long long LL; vector<LL> nums(100005, 0); int main() { //freopen("input.txt", "r", stdin); int t, n; scanf("%d", &t); while (t–) { scanf("%d", &n); LL first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN; for (int i = 0; i < n; ++i) { scanf("%d", &nums[i]); if (nums[i] > first) { third = second; second = first; first = nums[i]; } else if (nums[i] > second) { third = second; second = nums[i]; } else if (nums[i] > third) { third = nums[i]; } } LL ans = max(first*second*(first&second), first*third*(first&third)); ans = max(ans, second*third*(second&third)); printf("%lld\n", ans); } return 0; } [/cpp] 本代码提交AC，用时85MS。 后来看前几名AC的代码，好多是先对数组排序，然后从大到小求a*b*(a&b)的最大值，这样最坏复杂度还是$$O(n^2)$$，但是好像也能AC。]]>

    hihoCoder 1494-一面砖墙

    1 Reply

    hihoCoder 1494-一面砖墙

    #1494 : 一面砖墙

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

    描述

    小Hi的学校的教学楼前有一面砖墙。这面墙由N层砖砌成，其中从上到下第i层包含Ci块高度相同但宽度不同的砖。 例如下图所示的这面墙，由3层砖砌成。其中第1层包含3块砖，从左到右宽度依次是6、4和3；第2层包含4块砖，从左到右依次宽度依次是4、4、2和3；第3层包含3块砖，从左到右宽度依次是5、6和2。 
    +------------+
|  6  | 4 |3 |
+------------+
| 4 | 4 |2|3 |
+------------+
| 5  | 6   |2|
+------------+
          ^
    现在小Hi想在墙上画一道竖线，并且希望竖线穿过的砖块数目越少越好（如果竖线刚好在左右两块砖的交界处，则不会穿过砖块）。例如上例在墙^标示的位置画线，只会穿过一块砖。 注意小Hi不能在墙的左右边沿画线。

    输入

    第一行一个整数N，表示层数。 (1 < N <= 100000) 以下N行每行包含若干个整数。其中第一个整数Ci代表该层砖块的数目，之后Ci个整数表示从左到右每块砖的宽度。 整面墙总砖块数目不超过100000，总宽度不超过100000000。

    输出

    最少穿过的砖块数目。
    样例输入
    3
3 6 4 3
4 4 4 2 3
3 5 6 2
    样例输出
    1
    一面墙，由若干层砖砌成，每层有不同块不同宽度的砖。现在墙上画一道线，问最少能穿过多少块砖。重点是，如果线是画在某两块砖的交界处，则不算穿过这两块砖。 根据重点，画的线必须穿过越多层砖的交界处越好，如果这条线在这一层处于交界处，则在这一层没有和砖相交。所以我们只需统计一下所有层每两块砖之间的交界处坐标，我们在出现最多次数的交界处画一条线，则穿过最少的砖，穿过的砖块数是总的层数减去该交界坐标的频数。 代码如下： [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> using namespace std; int main() { //freopen("input.txt", "r", stdin); unordered_map<int, int> hash; int n, ci, width, total; scanf("%d", &n); total = n; while (n–) { scanf("%d", &ci); int sum = 0; while (ci–) { scanf("%d", &width); sum += width; if (ci != 0)++hash[sum]; } } int maxlevel = 0; for (auto it = hash.begin(); it != hash.end(); ++it) { maxlevel = max(maxlevel, it->second); } printf("%d\n", total – maxlevel); return 0; } [/cpp] 本代码提交AC，用时60MS。]]>

    hihoCoder 1493-歌德巴赫猜想

    Leave a reply

    hihoCoder 1493-歌德巴赫猜想

    #1493 : 歌德巴赫猜想

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

    描述

    哥德巴赫猜想认为“每一个大于2的偶数，都能表示成两个质数之和”。 给定一个大于2的偶数N，你能找到两个质数P和Q满足P<=Q并且P+Q=N吗？

    输入

    一个偶数N(4 <= N <= 1000000)

    输出

    输出P和Q。如果有多组解，输出P最小的一组。
    样例输入
    10
    样例输出
    3 7
    给定一个大于2的偶数N，找出两个质数P和Q，满足P<=Q且P+Q=N。 我还以为这题有什么数论技巧，没想到直接从小到大暴力枚举P就行了。。。 代码如下： [cpp] #include<cstdio> #include<cmath> #include<iostream> using namespace std; bool isPrim(int x) { if (x < 2)return false; for (int i = 2; i <= sqrt(x); ++i) { if (x%i == 0)return false; } return true; } int main() { int N; scanf("%d", &N); for (int i = 2; i <= N / 2; ++i) { if (isPrim(i) && isPrim(N – i)) { printf("%d %d\n", i, N – i); return 0; } } return 0; } [/cpp] 本代码提交AC，用时0MS。]]>