AtCoder Beginner Contest 139

「爱情、让人受尽委屈。」 2024-04-18 09:05 66阅读 0赞

### 文章目录 ###

*  \[A - Tenki\](https://atcoder.jp/contests/abc139/tasks/abc139\_a)
 *  \[B - Power Socket\](https://atcoder.jp/contests/abc139/tasks/abc139\_b)
 *  \[C - Lower\](https://atcoder.jp/contests/abc139/tasks/abc139\_c)
 *  \[D - ModSum\](https://atcoder.jp/contests/abc139/tasks/abc139\_d)
 *  \[E - League\](https://atcoder.jp/contests/abc139/tasks/abc139\_e)
 *  \[F - Engines\](https://atcoder.jp/contests/abc139/tasks/abc139\_f)

# [A - Tenki][] #

比较一下

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e3+7;
    
    int main() {
        
            string s,t;
            while(cin>>s>>t) {
        
                    int ans = 0;
                    for(int i=0;i<3;++i)
                            if(s[i]==t[i])
                                    ans ++;
                    cout<<ans<<endl;
            }
            return 0;
    }

# [B - Power Socket][] #

模拟一下

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e3+7;
    
    int main() {
        
            int a,b;
            while(cin>>a>>b) {
        
                    int ans = 0,num = 0;
                    // num = (b-1)/(a-1);
                    while(ans<b) {
        
                            num++;
                            if(ans+a<b)     ans += a-1;
                            else            ans += a;
                    }
                    if(b==1)        num = 0;
                    cout<<num<<endl;
            }
            return 0;
    }

# [C - Lower][] #

找连续不递增子段的最大长度

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e5+7;
    int dp[MAXN];
    int a[MAXN];
    int main() {
        
            int n;
            while(cin>>n) {
        
                    for(int i=0;i<n;++i)
                            cin>>a[i];
                    int ans = 0;
                    int num = 0;
                    for(int i=1;i<n;++i) {
        
                            if(a[i]<=a[i-1])        num++;
                            else                    num = 0;
                            ans = max(ans,num);
                    }
                    cout<<ans<<endl;
            }
            return 0;
    }

# [D - ModSum][] #

# [E - League][] #

这个题的意思是，给你一个的矩阵  
矩阵一共有  n n n 行，每行有 n − 1 n-1 n−1个数  
第i行表示第  i i i 个玩家，他进行网球比赛的次序就是这一行的数字，需要严格的与从左到右这些人比赛。  
每个人每天最多只能参加一场比赛  
问这些人比赛完的最小天数

如果不存在输出-1

用队列模拟，  
要求最后所有队列都清空

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e3+7;
    
    int a[MAXN][MAXN];
    int b[MAXN];
    bool vis[MAXN];
    queue<int> Q[MAXN];
    int main(){
        
            int n;
            cin>>n;
            for(int i=0;i<n;++i){
        
                    b[i] = 0;
                    for(int j=0;j<n-1;++j) {
        
                            cin>>a[i][j];
                            a[i][j]--;
                            Q[i].push(a[i][j]);
                    }
            }
            int ans = 0;
            while(true) {
        
                    bool flag = 0;
                    for(int i=0;i<n;++i) {
        
                            if(Q[i].empty())        continue;
                            if(Q[Q[i].front()].front()==i) {
        
                                    b[i] = b[Q[i].front()] = max(b[i],b[Q[i].front()]) + 1;
                                    Q[Q[i].front()].pop();
                                    Q[i].pop();
                                    flag = 1;
                            }
                    }
                    if(!flag) {
        
                            cout<<-1<<endl;
                            return 0;
                    }
                    int num = 0;
                    for(int i=0;i<n;++i)
                            num += Q[i].size();
                    if(num==0)      break;
            }
            for(int i=0;i<n;++i)
                    ans = max(ans, b[i]);
            cout<<ans<<endl;
            return 0;
    }

# [F - Engines][] #

将这n个二元组看做n个向量。  
移动方式遵循平行四边形定则。  
所以两个向量夹角越小，相加形成的和向量模长就越大。  
所以将这些向量按照极角排序。  
选择的向量肯定是一个区间。  
枚举左右端点，求最大值即可。

/*
    将这n个二元组看做n个向量。
    移动方式遵循平行四边形定则。
    所以两个向量夹角越小，相加形成的和向量模长就越大。
    所以将这些向量按照极角排序。
    选择的向量肯定是一个区间。
    枚举左右端点，求最大值即可。
    */
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e2+5;
    
    struct Point{
        
            int x,y;
    }p[MAXN];
    
    bool cmp(Point a,Point b) {
        
            return atan2(a.y,a.x) < atan2(b.y, b.x);
    }
    
    int nx[MAXN];//让它循环
    int main() {
        
            int n;
            cin>>n;
            for(int i=1;i<=n;++i)   cin>>p[i].x>>p[i].y;
            for(int i=1;i<=n;++i)    nx[i] = i+1; nx[n] = 1;
            sort(p+1,p+n+1,cmp);
            ll  ans=0;
            for(int i=1;i<=n;++i) {
        
                    ll x = p[i].x, y = p[i].y;
                    ans = max(ans, x * x + y * y);
                    for(int j=nx[i];j!=i;j = nx[j]) {
        
                            x += p[j].x;
                            y += p[j].y;
                            ans = max(ans, x * x + y * y);
                    }
            }
            printf("%.10lf\n",sqrt(ans));
            return 0;
    }

[A - Tenki]: https://atcoder.jp/contests/abc139/tasks/abc139_a
[B - Power Socket]: https://atcoder.jp/contests/abc139/tasks/abc139_b
[C - Lower]: https://atcoder.jp/contests/abc139/tasks/abc139_c
[D - ModSum]: https://atcoder.jp/contests/abc139/tasks/abc139_d
[E - League]: https://atcoder.jp/contests/abc139/tasks/abc139_e
[F - Engines]: https://atcoder.jp/contests/abc139/tasks/abc139_f