526互联

ABC310

发布时间 2023-07-16 17:18:47作者: liuguanyi

A

题意

给你\(n,p,q\)
给你一个\(n\)长度的数组\(D\) ，返回\(\min(D_i+q,p)\)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef priority_queue<int> pq;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


int n, p, q;

int main() {

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> p >> q;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        p = min(p, x + q);
    }
    cout << p << endl;
    return 0;
}

B

题意

给你有\(N\)件产品，每种产品的价格\(P_i\) ,具有\(C_i\)种功能
，\(A_{ij}\)表示第\(i\)种产品具有第\(j\)种功能
找到是否满足以下条件的产品对

  1. \(P_i\geq P_j\)
  2. 第\(j\)件产品具有第\(i\)种产品的全部功能
  3. \(P_i>P_j ||C_i<C_j\)

AC代码

import java.io.*;

import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {


    static class in extends PrintWriter {
        BufferedReader r;
        StringTokenizer st;

        // 标准 IO
        in() {
            this(System.in, System.out);
        }

        in(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }

        // 文件 IO
        in(String input, String output) throws IOException {
            super(output);
            r = new BufferedReader(new FileReader(input));
        }

        // 在没有其他输入时返回 null
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return null;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int[] getArrInt(int n) {
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] getArrLong(int n) {
            long[] a = new long[n + 1];
            for (int i = 1; i <= n; i++)
                a[i] = nextLong();
            return a;
        }
    }


    static in in = new in();


    public static class Mymath {
        public static int power(int a, int b) {
            if (b == 0) return 1;
            return b == 1 ? a : a * (power(a, b - 1));
        }

        public static long power(long a, long b) {
            if (b == 0) return 0L;
            return b == 1 ? a : a * (power(a, b - 1));
        }

        public static long mul(long a, long b) {
            long ans = 1;
            while (b > 0) {
                if ((b & 1) == 1) {
                    ans *= a;
                }
                b >>= 1;
                a *= a;
            }
            return ans;
        }

        public static long mul(long a, long b, int mod) {
            long ans = 1;
            while (b > 0) {
                if ((b & 1) == 1) {
                    ans *= a;
                    ans %= mod;
                }
                b >>= 1;
                a = a * a;
                a %= mod;
            }
            return ans;
        }
    }

    public static void main(String[] arg) throws Exception {
        int t = 1;
//        t = in.nextInt();
        while (t-- > 0) {
            new Solve();
        }
        in.close();
    }

    public static class Solve {
        private static final String yes = "Yes";
        private static final String no = "No";
        private static final int MOD = (int) (1e9 + 7);

        class Info {
            int v;
            HashSet<Integer> set;

            public Info(int v, HashSet<Integer> set) {
                this.v = v;
                this.set = set;
            }
        }

        public Solve() {
            int n = in.nextInt();
            int m = in.nextInt();
            Info[] a = new Info[n];
            for (int i = 0; i < n; i++) {
                int v = in.nextInt();
                int c = in.nextInt();
                HashSet<Integer> set = new HashSet<>();
                while (c-- > 0) {
                    set.add(in.nextInt());
                }
                a[i] = new Info(v, set);
            }
            Arrays.sort(a, (x, y) -> x.v - y.v);
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (cheak1(a[i].set, a[j].set) && (a[i].v < a[j].v || cheak2(a[i].set, a[j].set))) {
                        in.println("Yes");
                        return;
                    }
                }
            }
            in.println("No");
        }

        private boolean cheak2(HashSet<Integer> set1, HashSet<Integer> set2) {
            return set1.size() > set2.size();
        }

        private boolean cheak1(HashSet<Integer> set1, HashSet<Integer> set2) {
            for (int x : set2) {
                if (!set1.contains(x)) return false;
            }
            return true;
        }

    }
}

[C][https://atcoder.jp/contests/abc309/tasks/abc309_c]

题意

给你\(N\)个字符串，\(S_i\) 表示第\(i\)个字符串,如果一个字符串反转。或者本身，与另外一个字符串反转或者本身相同，就认为是一种字符串，\(S\)中有多少个这样的字符串

一眼并查集

import java.io.*;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {


    static class in extends PrintWriter {
        BufferedReader r;
        StringTokenizer st;

        // 标准 IO
        in() {
            this(System.in, System.out);
        }

        in(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }

        // 文件 IO
        in(String input, String output) throws IOException {
            super(output);
            r = new BufferedReader(new FileReader(input));
        }

        // 在没有其他输入时返回 null
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return null;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int[] getArrInt(int n) {
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] getArrLong(int n) {
            long[] a = new long[n + 1];
            for (int i = 1; i <= n; i++)
                a[i] = nextLong();
            return a;
        }
    }


    static in in = new in();


    public static class Mymath {
        public static int power(int a, int b) {
            if (b == 0) return 1;
            return b == 1 ? a : a * (power(a, b - 1));
        }

        public static long power(long a, long b) {
            if (b == 0) return 0L;
            return b == 1 ? a : a * (power(a, b - 1));
        }

        public static long mul(long a, long b) {
            long ans = 1;
            while (b > 0) {
                if ((b & 1) == 1) {
                    ans *= a;
                }
                b >>= 1;
                a *= a;
            }
            return ans;
        }

        public static long mul(long a, long b, int mod) {
            long ans = 1;
            while (b > 0) {
                if ((b & 1) == 1) {
                    ans *= a;
                    ans %= mod;
                }
                b >>= 1;
                a = a * a;
                a %= mod;
            }
            return ans;
        }
    }

    public static void main(String[] arg) throws Exception {
        int t = 1;
//        t = in.nextInt();
        while (t-- > 0) {
            new Solve();
        }
        in.close();
    }

    public static class Solve {
        private static final String yes = "Yes";
        private static final String no = "No";
        private static final int MOD = (int) (1e9 + 7);

        class Union {
            public Union(int n) {
                p = new int[n];
                size = new int[n];
                for (int i = 0; i < n; i++) {
                    p[i] = i;
                }
                Arrays.fill(size, 1);
            }

            int[] p;
            int[] size;

            public int find(int x) {
                if (x != p[x]) p[x] = find(p[x]);
                return p[x];
            }

            public int getSize(int x) {
                return size[find(x)];
            }

            public void merge(int from, int to) {
                from = find(from);
                to = find(to);
                if (from != to) {
                    p[from] = to;
                    size[to] += size[from];
                }
            }
        }

        public Solve() {
            int n = in.nextInt();
            Union union = new Union(n);
            HashMap<String, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                String s = in.next();
                if (map.containsKey(s)) {
                    union.merge(map.get(s), i);
                }
                map.put(s, i);
                StringBuffer s1 = new StringBuffer(s);
                map.put(s1.reverse().toString(), i);
            }
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < n; i++) {
                set.add(union.find(i));
            }
            in.println(set.size());
        }

    }
}

D

题意

\(N\)个人，\(M\)对关系表示\(A_i,B_i\) 关系不行，将\(N\)个人分配到\(T\)个盒子中，每个盒子必须有一个一个人，关系不好的人不能分配到同一个盒子里面

思路

暴力，枚举，假设现在开设的盒子为\(u\) 个，此时要么新开一个盒子，要么在\(1-u\)中选一个盒子放
最后判断所有盒子是否满足条件

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef priority_queue<int> pq;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


const int N = 15;
int g[N][N];

vector<int> a[N];
int n, T, m, x, y;
ll ans = 0;

void dfs(int index, int d) {
    if (d > T)return;
    if (index > n) {
        if (d == T) {
            bool ok = 1;
            //枚举盒子是否满足条件
            for (int i = 1; i <= T; i++) {
                for (auto u: a[i]) {
                    for (auto o: a[i]) {
                        ok &= !g[u][o];
                    }
                }
            }
            if (ok)ans++;
        }
        return;
    }
    //要么新开一个盒子，要么放入原先的盒子中
    for (int i = 1; i <= d + 1; i++) {
        a[i].push_back(index);
        dfs(index + 1, max(i, d));
        a[i].pop_back();
    }
}

void solve() {
    cin >> n >> T >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        g[x][y] = g[y][x] = 1;
    }
    dfs(1, 0);
    cout << ans << endl;
}

int main() {

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}