devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces1600分训练日记_codeforces1600分什么水平

作者：知新_RL | 2024-03-21 10:36:20

赞

踩

codeforces1600分什么水平

2019/5/22

1700 \color{red}1700 1700 模 拟 \color{purple}模拟 模拟

题意主要是要求两种二维坐标的转换；简单的题目，就是暴力转换就可以了
我们需要考虑的就是判断是哪一种形式，通过在字母后出现了字符，在字符后又一次出现了字母的方式。需要注意的是转换BBC这样的形式的时候，通过进制转换%26进行，但是需要考虑=0的时候应该是Z，而Z需要占用一个26，所以/=26之后的结果需要-1

By zylzyl, contest: Codeforces Beta Round #1, problem: (B) Spreadsheet, Accepted, #
 #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

#define ll long long

string str;

int n,x,y;

bool check(){
    int index;
    for(int i=1;i<str.size();i++){
        if(str[i]>='0'&&str[i]<='9'){
            index = i;
            break;
        }
    }
    for(int i=index+1;i<str.size();i++){
        if(str[i]>='A'&&str[i]<='Z')return false;
    }
    return true;
}

int main(){
    cin>>n;
    FOR(i,1,n){
        cin>>str;
        x=0,y=0;
        if(check()){
            int k=0;
            while(!isdigit(str[k])&&k<str.size()){
                y=y*26+(str[k]-'A'+1);
                k++;
            }
            while(k<str.size()){
                x=x*10+(str[k]-'0');
                k++;
            }
            cout<<"R"<<x<<"C"<<y<<endl;
        }
        else{
            int k=1;
            while(str[k]!='C'&&k<str.size()){
                x=x*10+(str[k]-'0');
                k++;
            }
            k++;
            while(k<str.size()){
                y=y*10+(str[k]-'0');
                k++;
            }
            string st="";
            while(y){
                if(y%26!=0)
                st+='A'+y%26-1;
                else st+='Z',y--;
                y/=26;
            }
            for(int i=st.size()-1;i>=0;i--)
                printf("%c",st[i]);
            cout<<x<<endl;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
2100 \color{red}2100 2100 数 学 \color{purple}数学 数学

题意是给出正n边形的三个点，去求最小正n边形的面积。
考虑正n边形的外接圆，三个点都在圆上。三个点可以构成一个三角形。每两个点和正n变形的中心可以构成一个扇形，我们可以了解到，只要求到正n边形的最小扇形即可
我们首先计算三条边的距离：a，b，c；面积用海伦公式计算:
p = a + b + c 2 p=\frac{a+b+c}{2} p=2a+b+c​
S = p ∗ ( p − a ) ∗ ( p − b ) ∗ ( p − c ) S=\sqrt{p*(p-a)*(p-b)*(p-c)} S=p∗(p−a)∗(p−b)∗(p−c) ​
首先对于这些扇形的圆心角，一定是最小圆心角的倍数，可以通过求两个圆心角之间的最小公倍数求出最小圆心角。
*对于扇形对应的三角形，利用余弦定理可以求解出圆心角： cos ⁡ A = b ∗ b + c ∗ c − a ∗ a 2 ∗ a ∗ c \cos A = \frac{b*b+c*c-a*a}{2*a*c} cosA=2∗a∗cb∗b+c∗c−a∗a​
为了保证精确度，求出两个圆心角，直接用 2 π 2\pi 2π减去得到第三个圆心角
面积公式： s = sin ⁡ θ ∗ r ∗ r 2 s=\frac{\sin \theta *r*r}{2} s=2sinθ∗r∗r​
正弦定理： sin ⁡ A a = sin ⁡ B b = sin ⁡ C c = 1 2 ∗ r \frac{\sin A}{a}=\frac{\sin B}{b}=\frac{\sin C}{c}=\frac{1}{2*r} asinA​=bsinB​=csinC​=2∗r1​这里的r为外接圆半径
r = a 2 sin ⁡ A r=\frac{a}{2\sin A} r=2sinAa​
s = 1 2 b c sin ⁡ A s=\frac{1}{2}bc\sin A s=21​bcsinA
推导得到： r = a b c 4 s r=\frac{abc}{4s} r=4sabc​
这样我们可以求出外接圆半径，从而可以用余弦定理求出圆心角，利用fgcd()求出最小圆心角。
求fmod的时候注意eps尽量较大,否则误差会很大

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

#define ll long long
#define eps 1e-4
#define PI acos(-1.0)
string str;

struct Point{
    double x,y;
};

double gcd(double a,double b)
{
	if(b+eps>0&&b-eps<0)
		return a;
	if(a+eps>0&&a-eps<0)
		return b;
	return gcd(b,fmod(a,b));
}

int main(){
    Point a,b,c;
    double A,B,C;
    scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
    double al=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    double bl=sqrt((a.x-c.x)*(a.x-c.x)+(a.y-c.y)*(a.y-c.y));
    double cl=sqrt((b.x-c.x)*(b.x-c.x)+(b.y-c.y)*(b.y-c.y));
    double p=(al+bl+cl)/2;
    double S=sqrt(p*(p-al)*(p-bl)*(p-cl));
    double R=(al*bl*cl)/(4*S);
    A=acos((R*R+R*R-al*al)/(2.0*R*R));
    B=acos((R*R+R*R-bl*bl)/(2.0*R*R));
    C=2*PI-A-B;
    double angle=gcd(A,gcd(B,C));
    //cout<<A<<" "<<B<<" "<<C<<endl;
    double ans;
    //cout<<A<<" "<<B<<" "<<C<<endl;
    ans=sin(angle)*0.5*R*R*(2*PI/angle);
    printf("%.6lf\n",ans);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

2019/5/23

1600 \color{red}1600 1600 模 拟 \color{purple}模拟 模拟

题意是求解最后分数最大的人，如果有相同分数的就选先到达最大分数的人。分数不断累加。
我的想法先用map记录每个人的分数，求出最大，再重新遍历一遍，这时候只考虑最大的人，先到达的先输出

#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int n;
string A[1010];
int B[1010];
map<string,int>M,T;


int main(){
    cin>>n;
    FOR(i,1,n){
        cin>>A[i]>>B[i];
        M[A[i]]+=B[i];
    }
    int ans=-1;
    for(map<string,int>::iterator iter=M.begin();iter!=M.end();iter++){
        ans=max(ans,(*iter).second);
    }
    int res;
    FOR(i,1,n){
        if(M[A[i]]==ans){
            T[A[i]]+=B[i];
            if(T[A[i]]>=ans){
                cout<<A[i]<<endl;
                break;
            }
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
2000 \color{red}2000 2000 D P \color{purple}DP DP

题意：只能往下和往右走，每个走到这个格子乘上这个格子的数，使得最小结果的后缀0尽可能地少
这种无后效性地优先考虑DP，向下和向右真的是完美DP了，但是如果使得这一步到下一步的后缀0最小呢，事实上如果 a = 2 ∗ 2 ∗ 2 ∗ 3 a=2*2*2*3 a=2∗2∗2∗3， b = 5 ∗ 5 ∗ 3 b=5*5*3 b=5∗5∗3一定是两个0，因为2和5可以组成一个0，而且考虑到最后都是2和5组成的0， 4 ∗ 5 = 2 ∗ 2 ∗ 5 4*5=2*2*5 4∗5=2∗2∗5
所以我们预处理出每个数2和5的个数，走两遍dp，最后选最小的
但是要求返回路径，直接用递归，判断能不能符合dp转移即可
还需要考虑的是0的情况，如果含0，那么标记一下，0相当于结果是1，如果ans>1的话可以直接选择0，暴力走到0再走到重点即可

#include<bits/stdc++.h>
#define FOR(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int n;
int A[1010][1010],B[1010][1010][2];
int dp[1010][1010][2];

void Pri(int i,int j,int x){
    int f=3;
    if(i-1>=1&&dp[i-1][j][x]+B[i][j][x]==dp[i][j][x])Pri(i-1,j,x),f=1;
    else if(j-1>=1&&dp[i][j-1][x]+B[i][j][x]==dp[i][j][x])Pri(i,j-1,x),f=2;
    //printf("dp[%d][%d][%d](%d)+B[%d][%d][%d](%d)=dp[%d][%d][%d](%d)\n",i-1,j,x,dp[i-1][j][x],i,j,x,B[i][j][x],i,j,x,dp[i][j][x]);
    //printf("dp[%d][%d][%d](%d)+B[%d][%d][%d](%d)=dp[%d][%d][%d](%d)\n",i,j-1,x,dp[i][j-1][x],i,j,x,B[i][j][x],i,j,x,dp[i][j][x]);
    if(f==3)return ;
    if(f==1)printf("D");
    else printf("R");
}

int main(){
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));
    FOR(i,1,n)FOR(j,1,n)scanf("%d",&A[i][j]);
    int ans,flag=0,_x,_y;
    FOR(i,1,n)FOR(j,1,n){
        int x=A[i][j],y=A[i][j];
        if(!x){
            flag=1;
            _x=i,_y=j;
            B[i][j][0]++,B[i][j][1]++;
            continue;
        }
        while(x&&x%2==0){
            x/=2;
            B[i][j][0]++;
        }
        while(y&&y%5==0){
            y/=5;
            B[i][j][1]++;
        }
    }
    dp[1][1][0]=B[1][1][0];
    dp[1][1][1]=B[1][1][1];
    FOR(i,1,n)FOR(j,(i==1?2:1),n){
        if(i-1>=1)dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]);
        if(j-1>=1)dp[i][j][0]=min(dp[i][j][0],dp[i][j-1][0]);
        dp[i][j][0]+=B[i][j][0];
        if(i-1>=1)dp[i][j][1]=min(dp[i][j][1],dp[i-1][j][1]);
        if(j-1>=1)dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]);
        dp[i][j][1]+=B[i][j][1];
    }
    ans=min(dp[n][n][0],dp[n][n][1]);
    if(ans>1&&flag){
        puts("1");
        int __x=1,__y=1;
        while(__x<_x)__x++,cout<<'D';
        while(__y<_y)__y++,cout<<'R';
        while(__y<n)__y++,cout<<'R';
        while(__x<n)__x++,cout<<'D';
    }
    else{
        cout<<ans<<endl;
        if(dp[n][n][0]<dp[n][n][1]){
            Pri(n,n,0);
        }
        else{
            Pri(n,n,1);
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/280517?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号