526互联

AtCoder Beginner Contest(abc) 310

发布时间 2023-10-28 14:03:43作者: mostimali



B - Strictly Superior

难度: ⭐

题目大意

给定n个商品的价格, 每个商品还有若干个属性, 请问是否存在一个商品是另外一个商品的上位品; 上位品的定义分两种, 一是价格相同, 但是商品A的属性不仅包括了商品B的属性, 还比商品B多了至少一个属性; 二是如果两商品的属性相同, 但是商品A的价格比商品B便宜, 则A也是B的上位品;

解题思路

数据不大, 暴力即可;

神秘代码

#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
typedef pair<int, int> PII;
int n, m;
int p[N], c[N],f[N][N];
int check(int a, int b) {
    for (int i = 1, j=1; i <= c[a]; i++) {
        while (j <= c[b] && f[b][j] < f[a][i]) j++;
        if (f[b][j] > f[a][i] || j > c[b]) return 0;
        else j++;
    }
    if (c[a] == c[b]) return 1;
    else return 2;
}
signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i] >> c[i];
        for (int j = 1; j <= c[i]; j++) {
            cin >> f[i][j];
        }
        sort(f[i] + 1, f[i] + 1 + c[i]);
    }
    bool f = false;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j] < p[i]) {
                int res = check(i, j);
                if (res != 0) {
                    f = true;
                    break;
                }
            }
            else if (p[j] == p[i]) {
                int res = check(i, j);
                if (res == 2) {
                    f = true;
                    break;
                }
            }
        }
        if (f) break;
    }
    if (f) cout << "Yes";
    else cout << "No";
    return 0;
}



C - Reversible

难度: ⭐

题目大意

给定n个字符序列, 问这n个序列中一共有多少个不同的序列; 对于序列的相同定义为如果一个序列与另一个序列或它的反转序列相同, 那么就可以判定为相同: abc=abc=cba;

解题思路

对于每个序列, 我们可以保存它和它反转序列中字典序较大的那个即可;

神秘代码

#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
set<string> st;
signed main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        string str = s;
        reverse(s.begin(), s.end());
        st.insert(max(str,s));
    }
    cout << st.size();
    return 0;
}



D - Peaceful Teams

难度: ⭐⭐⭐

题目大意

给定编号为1~n的n个人, 要求把他们分到t个组中, 但是其中有m对死对头, 死对头不能在一个组中, 请问一共有多少种分组方法, 由于组没有编号, 所以要注意去重;

解题思路

由于n的范围很小, 所以可以考虑用dfs; 该题的难点主要在于去重, 笨方法是遍历所有可能, 最后除以t的全排列, 但是这样大概率会超时; 所以要考虑在dfs的时候去去重; 对于每个人, 我们要限制住他可以选择的组别范围; 因为要去重, 所以我们要按顺序来, 不可以跳; 如果现在已经有x个组, 那么当前这个人可以选择这x个组, 或者去一个没人的组x+1, 但注意按照去重规则他不能去x+2; 按照这样的规则最后出来的就不会有重复;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e3 + 10;
typedef pair<int, int> PII;
int n, t, m, ans = 0;
int a[50], b[50], vis[50]; 
void dfs(int k, int mx) {
    if (k == n + 1) {
        if (mx != t) return;
        for (int i = 1; i <= m; i++) {
            if (vis[a[i]] == vis[b[i]]) return;
        }
        ans++;
        return;
    }
    for (int i = 1; i <= mx + 1; i++) {
        vis[k] = i;
        dfs(k + 1, max(i, mx));
        vis[k] = 0;
    }
}
signed main() {
    cin >> n >> t >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}



E - NAND repeatedly

难度: ⭐⭐⭐

题目大意

现在给定一个长为n的由0/1组成的数列P; 我们定义一种运算A^B: 0^1=1, 1^0=1, 0^0=1, 1^1=0; f(1,n)意思是((((P1P~2~)P3)P~4~)...Pn); 现在要遍历该数列, 把所有f(i,j) (i: 1~n, j: i~n)的值加起来输出; 注意: 当i=j时不会进行^运算, 其结果就是Pi本身;

解题思路

由于n的范围较大, 二重循环肯定会超时, 所以我们要去找规律; 根据定义我们可以看出, 0和任何数运算结果都是1; 也就是说如果Px=0, 那么所有f(i,x)的值都是1; 根据这个规律我们可以用dp进行求解; dp[i]的状态表示为所有右边界是Pi的区间的运算值的和; 根据i和j的范围可以知道所有右边界是第i位的区间(长度大于1)一共有i-1个; 当Pi=0时, 由前面得到规律知道此时dp[i] = i - 1; 当Pi=1时, 可以根据以Pi-1为右边界的区间进行求解; 如果该区间的运算结果为1, 那么再和1运算结果就是0, 反之如果为0的话结果就是1; 而dp[i-1]的值就意味着有多少个以Pi-1为右边界的区间的值是1, 所以我们用(i - 1) - dp[i - 1]就得到了以Pi-1为右边界的区间运算值为0的个数, 这就是以Pi为右边界的区间的运算值总和, 再加上Pi也是1, 所以dp[i] = (i - 1) - dp[i - 1] + 1

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;
int n, m, res;
int f[N], dp[N];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        f[i] = c - '0';
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] == 1) dp[i] = (i - 1) - dp[i - 1] + 1;
        else dp[i] = i - 1;
        res += dp[i];
    }
    cout << res;
    return 0;
}



F - Make 10 Again

题目大意

解题思路

神秘代码