题意
给你\(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;
}
题意
给你有\(N\)件产品,每种产品的价格\(P_i\) ,具有\(C_i\)种功能
,\(A_{ij}\)表示第\(i\)种产品具有第\(j\)种功能
找到是否满足以下条件的产品对
- \(P_i\geq P_j\)
- 第\(j\)件产品具有第\(i\)种产品的全部功能
- \(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());
}
}
}
题意
\(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;
}
标签:set,return,int,ABC310,static,new,public
From: https://www.cnblogs.com/SuanBujin/p/17558154.html