新鲜事 原文

Archer_5
46秒前
//寻找多数元素,即在给定长度为n的数组中,寻找出现次数大于n/2的元素。 //从第一个数开始count=1,遇到相同的就加1,遇到不同的就减1,减到0就重新换个数开始计数,总能找到最多的那个 #include <cstdio> #include <iostream> using namespace std; const int N=100; int q[N]; int n; int majorityElement(int q[]) { int num = q[0]; int count = 1; for(int i = 1; i < n; i ++) { if(count > 0) { if(num == q[i]) count ++; else count --; } else { num = q[i]; count = 1; } } return num; } int main() { cin >> n; for(int i=0;i<n;i++) scanf("%d",&q[i]); int t=majorityElement(q); cout << t << endl; return 0; }




import java.io.*;

public class Main {
    static int n, idx;
    static int[] happy;
    static int[] h, e, ne;
    static int[][] f;
    static boolean[] has_father;//判断每个点是否有父节点
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine());
        happy = new int[n + 1];
        h = new int[n + 1];
        e = new int[n - 1];
        ne = new int[n - 1];
        f = new int[n + 1][2];
        has_father = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            happy[i] = Integer.parseInt(reader.readLine());
            h[i] = -1;
        }
        while (n-- > 1) {
            String[] str1 = reader.readLine().split(" ");
            int a = Integer.parseInt(str1[0]);
            int b = Integer.parseInt(str1[1]);
            has_father[a] = true;//表示a有父节点,是b
            add(b, a);
        }

        int root = 1;
        while (has_father[root]) {
            root++;//求出根节点
        }

        dfs(root);

        writer.write(Math.max(f[root][0], f[root][1]) + "");
        writer.flush();
        writer.close();
        reader.close();
    }

    public static void dfs(int u) {
        f[u][1] = happy[u];
        for (int i = h[u]; i != -1; i = ne[i]) {//遍历其每个孩子节点
            int j = e[i];
            dfs(j);
            f[u][0] += Math.max(f[j][0], f[j][1]);
            f[u][1] += f[j][0];
        }
    }

    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];//ne和h存的都是元素下标
        h[a] = idx++;
    }
}



P__sR
31分钟前
#include <algorithm>

using namespace std;

const int N = 5010;

int s[N][N];

int main()
{
    int n, r;
    scanf("%d%d", &n, &r);
    r = min(r, 5001);

    for (int i = 0; i < n; i++)
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x++, y++;
        s[x][y] += w;
    }

    for (int i = 1; i <= 5001; i++)
        for (int j = 1; j <= 5001; j++)
        {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }

    int res = 0;
    for (int i = r; i <= 5001; i++)
        for (int j = r; j <= 5001; j++)
        {
            res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }

    printf("%d\n", res);

    return 0;
}



思路:

  1. 先将所有区间按左边界大小排序;
  2. 遍历每个区间,两两比较,若前一个区间的右边界小于后一区间的左边界,则这两个区间无法合并,直接把前一区间放入结果数组中;
  3. 若前一个区间的右边界大于等于后一区间的左边界,表示这俩区间能够合并。此时保持前一区间的左边界不变,右边界变为俩区间最大的右边界;
  4. 上一条的右边界之所以如此界定,是为了解决前一区间包含后一区间的情况,比如[[1,4],[2,3]],很明显,合并后区间右边界应该是4而不是3
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        vector<int> tmp;

        sort(intervals.begin(), intervals.end());       // 1.

        tmp = intervals[0];
        for (int i = 1; i < intervals.size(); ++ i)
        {
            if (tmp[1] < intervals[i][0])               // 2.
            {
                res.push_back(tmp);
                tmp = intervals[i];                     //把tmp更新为后一区间
            }
            else
            {
                tmp[1] = max(tmp[1], intervals[i][1]);  // 3.
            }
        }

        res.push_back(tmp);
        return res;
    }
};



木水易雨
41分钟前

同样的数据范围
更改第二个条件为
选择至少两个数,且所选择的数的最大公约数等于 1
该怎么解决这道题呢




a19627197
44分钟前
#include <iostream>
using namespace std;
int main( )
{
    printf("size of char = %d\n",sizeof(char)); //size of char = 1
    printf("size of short int = %d\n",sizeof(short int)); //size of short int = 2
    printf("size of int = %d\n",sizeof(int)); //size of int = 4
    printf("size of long int = %d\n",sizeof(long int)); //size of long int = 8
    printf("size of long long = %d\n",sizeof(long long)); //size of long long = 8
   return 0;
}



晓龙coding
1小时前
  1. 欧拉回路的充要条件:
    无向连通图中,每个点的度数为2。
    有向连通图中,每个点的入度和出度都相等。
#include<iostream>
#include<cmath>
using namespace std;

int main() {
    double x1, x2, y1, y2, len = 0;
    cin >> x1 >> y1;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        double dx = x1 - x2, dy = y1 - y2;
        len += sqrt(dx * dx + dy * dy) * 2;
    }
    int minute = round(len / 1000 / 20 * 60), hour = minute / 60;
    minute %= 60;
    printf("%d:%02d\n", hour, minute);
    return 0;
}



/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> printFromTopToBottom(TreeNode root) {
        //定义返回集合
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        //采用宽度遍历,装元素的队列q
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        //true:从左往右
        //false:从右往左
        boolean flag = true;

        while(!q.isEmpty()){
            //队列中的元素个数
            int size = q.size();
            List<Integer> list = new LinkedList<>();
            for(int i=0;i<size;i++){
                //出队操作
                TreeNode node = q.poll();

                if(flag){
                    list.add(node.val);
                }else{
                    //指定位置插入
                    list.add(0,node.val);
                }

                if(node.left!=null){
                    q.add(node.left);
                }
                if(node.right!=null){
                    q.add(node.right);
                }
            }
            flag = !flag;
            res.add(list);
        }
        return res;
    }
}



解法1:
#include<iostream>
#include<cstring>

using namespace std;

const int N = 305;

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
char g[N][N];
int _0[N][N];
int T, n;

void dfs(int x, int y){
    _0[x][y] = -1;
    for(int i = 0; i < 8; i ++ ){
        int a = dx[i] + x, b = dy[i] + y;
        if(a >= 0 && b >= 0 && a < n && b < n && _0[a][b] != -1){
            if(!_0[a][b])   _0[a][b] = -1, dfs(a, b);
            _0[a][b] = -1;
        }
    }
}

int main(){
    cin>>T;
    for(int q = 1; q <= T; q ++ ){
        int res = 0;
        cin>>n;
        for(int i = 0; i < n; i ++ )    cin>>g[i];
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < n; j ++ ){
                if(g[i][j] == '*')  _0[i][j] = -1;
                else{
                        _0[i][j] = 0;
                        for(int k = 0; k < 8; k ++ ){
                            int a = dx[k] + i, b = dy[k] + j;
                            if(a >= 0 && b >= 0 && a < n && b < n && g[a][b] == '*')
                                _0[i][j] ++;
                        }
                }
            }
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < n; j ++ ){
                if(!_0[i][j]){
                    res ++;
                    dfs(i, j);
                }
            }
        }
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < n; j ++ )
                if(_0[i][j] != -1)
                    res ++;
        printf("Case #%d: %d\n", q, res);
    }
    return 0;
}
解法2
#include<iostream>
#include<cstring>

using namespace std;

const int N = 305;

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
char g[N][N];
int _0[N][N];
bool st[N][N];
int T, n;

void dfs(int x, int y){
    st[x][y] = true;
    for(int i = 0; i < 8; i ++ ){
        int a = dx[i] + x, b = dy[i] + y;
        if(a >= 0 && b >= 0 && a < n && b < n && !st[a][b] && g[a][b] != '*'){
            st[a][b] = true;
            if(!_0[a][b])   dfs(a, b);
        }
    }
}

int main(){
    cin>>T;
    for(int q = 1; q <= T; q ++ ){
        int res = 0;
        memset(st, false, sizeof st);
        cin>>n;
        for(int i = 0; i < n; i ++ )    cin>>g[i];
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < n; j ++ ){
                if(g[i][j] == '*')  _0[i][j] = -1;
                else{
                        int cou = 0;
                        for(int k = 0; k < 8; k ++ ){
                            int a = dx[k] + i, b = dy[k] + j;
                            if(a >= 0 && b >= 0 && a < n && b < n && g[a][b] == '*')  cou ++;
                        }
                        _0[i][j] = cou;
                }
            }
        }
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < n; j ++ ){
                if(!st[i][j] && !_0[i][j]){
                    res ++;
                    dfs(i, j);
                }
            }
        }
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < n; j ++ )
                if(!st[i][j] && g[i][j] == '.')
                    res ++;
        printf("Case #%d: %d\n", q, res);
    }
    return 0;
}



xianhai
1小时前

利用位运算输出二进制串

#include <cstdio>
#include <cstring>
char a[10];

int main() {
    scanf("%s", a);
    int n = strlen(a);
    int sum = 0, d;
    // 输出第一行,并计算出对应的十进制数
    for (int i = 0; i < n; i++) {
        if (a[i] >= '0' && a[i] <= '9') {
            d = a[i] - '0';
        } else if (a[i] >= 'a' && a[i] <= 'b') {
            d = a[i] - 'a' + 10;
        }
        sum = sum * 12 + d;
        printf("%d ", d);
    }
    printf("\n");
    // 输出第二行
    printf("%d\n", sum);
    // 输出第三行
    for (int i = 31; i >= 0; i--) {
        if (i != 31 && (i + 1) % 8 == 0) {
            printf(" ");
        }
        if ((sum & (1 << i)) == 0) {
            printf("0");
        } else {
            printf("1");
        }
    }
    return 0;
}