Codeforces edu 161 (div2)

volapex-lord / 2024-01-19 / 原文

Problem - A - Codeforces

思维题，判断c字符串的每一位是否都能在相对应的a字符串或者b字符串里面找到；

如果都能找到的话就输出 NO；否则输出YES；

#include <bits/stdc++.h>
using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int k;
    cin >> k;
    
    while(k --)
    {
        int len;
        cin >> len;
        string a , b, c;
        cin >> a >> b >> c;
        
        bool st = false;;
        for(int i = 0 ; i < len ; i ++)
        {
            if(c[i] == a[i])
            {
                
                continue;
            }
            else if(c[i] == b[i])
            {
                continue;
            }
            else 
            {
                st = true;
                break;
            }
        }
        if(st) cout <<"YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
    
}

Problem - B - Codeforces

涉及了组合数的问题；

拼成的三角形只有两种情况：

1.三个一样长度的（也就是说如果某个长度的木棒数量 >= 3 就有Cm3中选择 m个里面选择3个）

2.两个一样长度的 + 比他们小的任何一个长度的

要学会组合数的写法；

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int len[N];
int b[N];
bool st[N];

LL cmb(LL n, LL m)
{
    LL ans = 1;
    for(LL i =1 ; i <= m;i ++)
    {
        ans = ans * (n-m+i)/i;
    }
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int k;
    cin >> k;
    
    while(k --)
    {
        bool st[N];
        int n;
        cin >> n;
        for(int i = 1 ; i <= n ; i ++) st[i] = false;
        
        map<int , int>p;
        map<int , int>num;
        
        for(int i = 1;  i <= n ; i ++) cin >> len[i];
        sort(len + 1 , len + n + 1);
        
        
        for(int i = 1 ; i <= n ; i ++)  p[len[i]] ++; //统计每个长度有多少个
        //for(int i = 1 ; i <= n ; i ++)
        //{
            //if(st[len[i]] == false)
            //{
                //num[len[i]] += p[len[i-1]];
                //st[len[i]] = true;
            //}
        //}
        
        LL res = 0;
        LL m = 0;
        for(auto t : p)
        {
            if(t.second >= 3)
            {
                res += cmb(t.second,3); //对应第一种情况；
            }
            res += m * cmb(t.second,2); //对应第二种情况
            m += t.second;
        }
        
        cout << res << endl;
    }
    return 0;
    
}