淘先锋技术网

首页 1 2 3 4 5 6 7

补一补之前没打的cf
比赛链接
A:签到题 排一下序即可

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define ios ios::sync_with_stdio(false)
#define CRL(a) memset(a,0,sizeof a)
#define endl "\n"

using namespace std;
const int maxn = 1e5 + 5;
int a[15];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin >> n;
        char s[50], s1[50];
        for (int i = 1; i <= n;i++)
        {
            cin >> s[i];
            s1[i] = s[i];
        }
        sort(s + 1, s + 1 + n);
        int ans = 0;
        for (int i = 1; i <= n;i++)
        {
            if(s[i]!=s1[i])
                ans++;
        }
        cout << ans << endl;
    }
}

B:
题意:给你n个运动员的五场比赛情况,如果一个运动员中的五场中的三场比另一个人的名次要靠前,证明这个人比他强,问在这些人里能否找到有且仅有一个人比其余的所有都厉害。
题解:我们可以先用擂台赛方法遍历一遍来找在这里面最厉害的,然后再让这个人和除它以外的所有都作比较,如果确实是比其余的所有都厉害,那么就是这个人,否则无解。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define ios ios::sync_with_stdio(false)
#define CRL(a) memset(a,0,sizeof a)
#define endl "\n"
using namespace std;
const int maxn = 5e4 + 5;
int a[maxn][7];
bool cmp(int i,int j)
{
    int cnt = 0;
    for (int k = 1; k <= 5;k++)
    {
        if(a[i][k]<a[j][k])
            cnt++;
    }
    return cnt >= 3;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n;i++)
        {
            for (int j = 1; j <= 5;j++)
            {
                cin >> a[i][j];
            }
        }
        int ans = 1, flag = 1;
        for (int i = 2; i <= n;i++)
        {
            if(!cmp(ans,i))
                ans = i;
        }
        for (int i = 1; i <= n;i++)
        {
            if(i!=ans&&!cmp(ans,i))
                flag = 0;
        }
        cout << (flag ? ans : -1) << endl;
    }
}

C:
题意:给你一个圆,上面有2n个点,已经有m对点两两相连了,问你让剩下的(2n-2k)个点连接,使得所有的这些连接的边相交的点数最多。
题解:假设两个相连的边为(x1,y1),(x2,y2),如果这两条边相交,我们可以得到这样一个关系,x1<x2<y1<y2,或者反过来由这个关系我们可以得到,剩下的点一定是偶数,我们将其排序后,一定是让(i,i+(2n-2k)/2)凑在一块,这样才是最大的情况,你无法找到比这个更大的情况,所以我们再遍历找交点即可。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<int,int>
#define ios ios::sync_with_stdio(false)
#define CRL(a) memset(a,0,sizeof a)
#define endl "\n"

using namespace std;
const int maxn = 1e6 + 5;
int x[205];
pr v[205];
bool check(int a,int b)
{
    if(v[a].first<v[b].first&&v[a].second<v[b].second&&v[b].first<v[a].second||v[a].first>v[b].first&&v[a].second>v[b].second&&v[a].first<v[b].second)
        return true;
    return false;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        memset(x, 0, sizeof x);
        for (int i = 1; i <= m;i++)
        {
            int a, b;
            cin >> a >> b;
            if(a>b)
                swap(a, b);
            x[a] = 1;
            x[b] = 1;
            v[i] = {a, b};
        }
        int a[250], cnt = 0;
        for (int i = 1; i <= 2 * n;i++)
        {
            if(!x[i]) 
            {
                a[++cnt] = i;
            }
        }
        for (int i = 1; i <= cnt/2;i++)
        {
            v[++m] = {a[i], a[i + cnt / 2]};
        }
        int ans = 0;
        for (int i = 1; i <= n;i++)
        {
            for (int j = 1; j < i;j++)
            {
                if(check(i,j))
                    ans++;
            }
        }
        cout << ans << endl;
    }
}

D:
题意:给你一个含n个数的a数组,让你找一个含n个数的b数组,使得ai=bj-bk(1<=j,k<=n),且a中的数都要出现。
题解:假设我们已经有了一个数a,那么我们可以让a1=a-b,a2=b-c…以此类推,但是我们发现我们在得到n-1个数的时候就已经用了n个数了,所以我们要找到a当中的一个元素,使它可以由这个数组当中的几个数相加凑出来,这样我们就可以用n个元素来凑a数组了。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define ios ios::sync_with_stdio(false)
#define CRL(a) memset(a,0,sizeof a)
#define endl "\n"

using namespace std;
const int maxn = 1e5 + 5;
int a[15];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n;i++)
        {
            cin >> a[i];
        }
        set<int> s;
        for (int i = 0; i < 1 << (n);i++)
        {
            int sum = 0;
            for (int j = 0; j < n;j++)
            {
                if((i>>j)&1)
                    sum += a[j+1];
            }
            s.insert(sum);
        }
        if(s.size()<(1<<n))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}