AtCoder Beginner Contest 139

文章目录

[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

#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() {
        ll n;
        while(cin>>n)
                cout<<(ll)n*(n-1)/2<<endl;
        return 0;
}

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;
}