CodeForces 572A，B，C

ゞ浴缸里的玫瑰 2022-08-18 14:21 20阅读 0赞

[CodeForces 572A][]

题意：给定两个序列，问能否从第一个序列取出k个数，从第二个序列取出m个数，使得第一个序列取出来的所有数都小于第二个序列取出来的数。

思路：水。因为问的是存在，所以只要在第一个序列中取最小的k个和第二个序列中最大的m个，然后比较第一取出来最大是否小于第二取出来最小。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1e5+5;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int v1[N],v2[N];
    int main()
    {
        int n1,n2,k,m;
        scanf("%d%d",&n1,&n2);
        scanf("%d%d",&k,&m);
        ft(i,1,n1) scanf("%d",&v1[i]);
        ft(i,1,n2) scanf("%d",&v2[i]);
        if (v1[k]<v2[n2-m+1]) puts("YES");
        else puts("NO");
    }

[CodeForces 572B][]

题意：给定一些股票的买卖情况，然后买高卖低，然后按价格从大到小输出买卖的股票的序列。

思路：直接开两个数组，一个存取买的，一个存取卖的。输出的时候从100000向下（从0到上）遍历即可。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=100005;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int mp1[N],mp2[N];
    int main()
    {
        int n,m;
        int d,p;
        char s[2];
        scanf("%d %d",&n,&m);
        cls(mp1,0);cls(mp2,0);
        ft(i,1,n){
            scanf("%s %d %d",&s,&p,&d);
            if (s[0]=='S') mp1[p]+=d;
            else mp2[p]+=d;
        }
        int k=0,t=0;
        for(int it=0;it<N&&t<m;it++){
             //if (it%100==0)printf("%d\n",it);
             //if (it>100000) break;
            if (mp1[it]>0)  t++,k=it;
        }
    
        for (int j=k;j>=0;j--) if (mp1[j]>0) printf("S %d %d\n",j,mp1[j]);
        t=0;
        for(int it=N;it>=0&&t<m;it--){
            if (mp2[it]>0) printf("B %d %d\n",it,mp2[it]),t++;
        }
    }

[CodeForces 572C][]

题意：给定一个三角形的三边a，b，c和要延长的长度l，问有多少种方法可以使得延长后的图形为三角形。

思路：先找所有的情况，然后减去不满足的情况。当l为i时，情况为c（i+2，2）（i可以去0-l，一路累加即可）。减去分别以a，b，c作为最长边枚举就算把剩下边加上也无法满足三角形的情况。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    ll sol(ll a,ll b,ll c,ll l){
        ll t=0;
        for(ll i=max(b+c-a,0ll);i<=l;i++)
        {
            ll x=min(l-i,a+i-b-c);
            t+=(x+1)*(x+2)/2;
        }
        return t;
    }
    int main()
    {
        ll a,b,c,l,ans=0;
        cin>>a>>b>>c>>l;
        for(ll i=0;i<=l;i++) ans+=(i+1)*(i+2)/2;
        ans-=sol(a,b,c,l);
        ans-=sol(b,c,a,l);
        ans-=sol(c,a,b,l);
        cout<<ans<<endl;
    }

[CodeForces 572A]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=230607
[CodeForces 572B]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=222307
[CodeForces 572C]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=231125