一些练习题&题解

#A A+B Problem

好！很有精神！

#include<iostream>
using namespace std;
int main() {
    int a,b;
    cin>>a>>b;
    cout<<a+b<<endl;
    return 0;
}

#B Financial Management

#include<iostream>
#include<iomanip>
using namespace std;

int main(){
    float sum=0;
    for(int i=1;i<=12;i++){
        float x;
        cin>>x;
        sum+=x;
    }
    sum/=12.0;
    cout<<fixed<<setprecision(2)<<'$'<<sum<<endl;

}

#C Hangover

打了个表

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=307;
float n;
float card[maxn];

void init(){
    memset(card,0,sizeof(card));
    for(int i=1;i<=maxn;i++){
        card[i]=card[i-1]+1.0/(float)(i+1);
    }
}
int main(){
    init();
    cin>>n;
    while(n!=0) {
        int res=upper_bound(card,card+maxn-1,n)-card;
        cout<<res<<" card(s)"<<endl;
        cin>>n;
    }
}

#D DNA Sorting

DNA动了

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=57;
const int maxm=107;

int n,m;//n length m 行
struct dna_length{
    string s;
    int length;
    bool operator <(const dna_length &a) const{
        return length<a.length;
    }
};
vector<dna_length> dna;

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        dna_length x;
        x.length=0;
        cin>>x.s;
        dna.push_back(x);
    }
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            for(int k=j+1;k<n;++k){
                if(dna[i].s[j]>dna[i].s[k]) dna[i].length++;
            }
        }
    }
    sort(dna.begin(),dna.end());
    for(int i=0;i<m;++i){
        cout<<dna[i].s<<endl;
    }
}

#E Vertical Histogram

打柱状图的题，标记最长的一行的长度为maxtime，每输出一行，maxtime–；

若字母的频率大于等于(实际上不可能大于)maxtime就输出一个*，否则输出空格

#include<iostream>
#include<string>
using namespace std;

int times[26]={0};
int main(){
    string x;
    for(int i=0;i<4;++i){
        getline(cin,x);
        for(int j=0;j<x.length();++j){
            if(x[j]<'A'||x[j]>'Z') continue;
            else{
                times[x[j]-'A']++;
            }
        }
    }
    int maxtime=0;
    for(int i=0;i<26;++i){
        maxtime=max(maxtime,times[i]);
    }
    while(maxtime!=0){
        if(times[0]>=maxtime) cout<<'*';
        else cout<<' ';
        for(int i=1;i<26;++i){
            cout<<' ';
            if(times[i]>=maxtime){
                cout<<'*';
            }
            else cout<<' ';
        }
        cout<<endl;
        maxtime--;
    }
    cout<<'A';
    for(char c='B';c<='Z';++c){
        cout<<' '<<c;
    }
}

#F Herd Sums

计算一个整数能被拆成多少种 连续的整数的和的形式

can add up to 15. They are: 15, 7+8, 4+5+6, and 1+2+3+4+5.

设这个数为n，一个数的和（n/1）一定成立；

两个数的和n/2，若除以2余0.5，则能够成立；

三个数的和n/3，若无余数，则能够成立；4+5+6这种

类推，奇数个数的和，没有余数能够成立；偶数个数的和，余0.5能够成立

#include<iostream>
using namespace std;
int n;
int res=1;
int main(){
    cin>>n;
    for(int i=2;;++i){
        if(n/i-i/2<=0) break;//不能有负数情况
        else if(i%2==1&&n%i==0) res++;
        else if(i%2==0&&((float)n/i)-int(n/i)==0.5) res++;
    }
    cout<<res<<endl;
}

#G Adding Reversed Numbers

呜呜，我打字符串实在太菜了

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int stringtoi(string x){
    int res=0;//就是你让我wa了三次是吧？？？
    for(int i=x.size()-1,j=1;i>=0;--i,j*=10) {
        res+=(x[i]-'0')*j;
    }
    return res;
};
string itostring(int x){
    string res;
    for(;x>0;x/=10) res+=x%10+'0';
    return res;
}
void omitzero(string &z){
    for(string::iterator iter=z.begin();iter!=z.end();){
        if(*iter=='0') z.erase(iter);
        else break;
    }
}
int main(){
    int n;
    cin>>n;
    while(n--) {
        string x, y;
        cin >> x >> y;
        omitzero(x);
        omitzero(y);
        reverse(x.begin(),x.end());
        reverse(y.begin(),y.end());
        int a=stringtoi(x);
        int b=stringtoi(y);
        int c=a+b;
        if(!c) {
            cout<<c<<endl;
            continue;
        }
        string z=itostring(c);
        omitzero(z);
        cout<<z<<endl;

    }
}

#H Manhattan 2025

计算一个立方体的矩阵，略麻烦

先算中间一层平面，然后两边给他操作一下

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20;
const int inf=0x3f3f3f3f;
int cube[2*maxn+1][2*maxn+1];
int temp[2*maxn+1][2*maxn+1];
int n;
void cubecal(int x){
    memset(cube,inf,sizeof(cube));
    for(int i=0;i<=x;++i){
        for(int j=0;j<=x;++j){
            if(i+j>x) break;
            cube[x-i][x-j]=i+j;
            cube[x-i][x+j]=i+j;
            cube[x+i][x-j]=i+j;
            cube[x+i][x+j]=i+j;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        cubecal(x);//得到中间一层(n+1层)的矩阵
        cout<<"Scenario #"<<i<<":"<<endl;
        for(int j=1;j<=2*x+1;++j){//j 第j层矩阵 j=x+1的时候就是cube
            cout<<"slice #"<<j<<":"<<endl;
            for(int m=0;m<2*x+1;++m){//j层矩阵的第m行
                for(int n=0;n<2*x+1;++n){//j层矩阵的第n列
                    temp[m][n]=cube[m][n]+abs(x+1-j);
                    if(temp[m][n]>x) cout<<".";
                    else cout<<temp[m][n];
                }
                cout<<endl;
            }
        }
        cout<<endl;
    }
}

#I Exponentiation

高精浮点数指数幂

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
string A;
int a[305],b[305],n,ans[50005],t[3005],temp[50005],lena,lenb,lent,lenans;
void clean_it()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(ans,0,sizeof(ans));
    memset(t,0,sizeof(t));
    lena=lenb=lent=lenans=0;
}
void work()
{
    clean_it(); bool flag=0;
    for(int i=0;i<A.length();i++)
    {
        if(A[i]=='.') break;
        if(A[i]!='0') flag=1;
        if(flag) a[lena++]=A[i]-'0';
    }  flag=0;
    for(int i=A.length()-1;i>=0;i--)
    {
        if(A[i]=='.') break;
        if(A[i]!='0') flag=1;
        if(flag) b[lenb++]=A[i]-'0';
    }
    for(int i=0;i<lenb;i++) t[lent++]=ans[lenans++]=b[i];
    for(int i=0;i<lena;i++) t[lent++]=ans[lenans++]=a[lena-i-1];
    for(int k=2;k<=n;k++)
    {
        memset(temp,0,sizeof(temp));
        for(int i=0;i<lenans;i++)
            for(int j=0;j<lent;j++)
            {
                temp[i+j]+=ans[i]*t[j];
                temp[i+j+1]+=temp[i+j]/10;
                temp[i+j]%=10;
            }
        lenans+=lent-1;
        if(temp[lenans]>0) lenans++;
        for(int i=0;i<lenans;i++) ans[i]=temp[i];
    }  lenb*=n;
    if(lenb>lenans)
    {
        cout<<".";
        for(int i=1;i<=lenb-lenans;i++) cout<<0;
    }
    for(int i=lenans-1;i>=0;i--)
    {
        if(lenans-1-i+lenb==lenans) cout<<".";
        cout<<ans[i];
    } cout<<endl;
}
int main()
{
    while(cin>>A>>n) work();
    return 0;
}

#J Ride to School

#K Big Square

#L Hotline

#M Yeehaa!

再往后除了Y好像都是计算几何

所有常数记得都来个.0

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cout<<"Scenario #"<<i<<":"<<endl;
        double r;
        int c;
        cin>>r>>c;
        double temp=sqrt(1.0-cos((360.0/c)*3.141592653589/180.0));
        double res=(r*temp)/(sqrt(2.0)+temp);
        cout<<fixed<<setprecision(3)<<res<<endl<<endl;
    }
}

#N Factorial

计算一个数的阶乘后边有几个零

就是计算有多少个因数5

但是一开始完全不是这样想的qwq

#include<iostream>
using namespace std;
typedef unsigned long long ll;

int main(){
    int n;
    cin>>n;
    while(n--){
        ll x,cnt=0;
        cin>>x;
        for(ll i=5;i<=x;i*=5){
            cnt+=x/i;
        }
        cout<<cnt<<endl;
    }
}

#O The Circumference of the Circle

知三点求圆周长，求半径然后乘2pai

#include<iostream>
#include<cmath>
#include<iomanip>
#define pi 3.141592653589793
using namespace std;
struct point{
    double x,y;
};
double dis(point p1,point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int main(){
    point p1,p2,p3;
    while(cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y){
        double a=dis(p1,p2);
        double b=dis(p2,p3);
        double c=dis(p1,p3);
        double p=(a+b+c)/2;
        double r=a*b*c/(4* sqrt(p*(p-a)*(p-b)*(p-c)));
        cout<<fixed<<setprecision(2)<<r*pi*2<<endl;
    }
}

#P Goldbach’s Conjecture

哥德巴赫猜想

用求素数的板子做的

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e6+7;
bool notprime[maxn];
int n;
void init(){
    memset(notprime,false,sizeof(notprime));
    notprime[0]=notprime[1]=true;
    for(int i=2;i<maxn;++i){
        if(!notprime[i]){
            if(i>maxn/i) continue;
            for(int j=i*i;j<maxn;j+=i)
                notprime[j]=true;
        }
    }
}
int main(){
    init();
    cin>>n;
    while(n!=0){
        for(int i=2;i<n;++i){
            if(notprime[i]) continue;
            else{
                if(notprime[n-i]== false){
                    cout<<n<<" = "<<i<<" + "<<n-i<<endl;
                    break;
                }
            }
        }
        cin>>n;
    }
}

#Q Area

挖藕！这个123456789是数字小键盘！

计算多边形面积，可能有凹多边形，叉乘之后的结果不取绝对值；如果结果为负转换为正输出

#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
struct point{
    int x,y;
};
point polygon[maxn];
point p;
void init(){
    for(int i=0;i<maxn;++i){
        polygon[i].x=0;
        polygon[i].y=0;
    }
}
ll perarea(point a,point b){
    return a.x*b.y-a.y*b.x;
}
ll area(int size){
    ll ans=0;
    for(int i=0;i<size;++i){
        ans+=perarea(polygon[i],polygon[i+1]);
    }
    return ans;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        char c;
        int size=0;
        p.x=0;p.y=0;
        init();
        while(scanf("%c",&c)){
            if(c=='6'){
                p.x++;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='9'){
                p.x++;
                p.y++;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='8'){
                p.y++;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='7'){
                p.x--;
                p.y++;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='4'){
                p.x--;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='1'){
                p.x--;
                p.y--;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='2'){
                p.y--;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='3'){
                p.x++;
                p.y--;
                polygon[size].x=p.x;
                polygon[size].y=p.y;
                size++;
            }
            else if(c=='5')
                break;
            else
                continue;
        }
        if(size==0){
            cout<<0<<endl;
            continue;
        }
        ll ans=area(size);
        if(ans<0) ans=-ans;
        if(ans%2==0) printf("%lld\n",ans/2);
        else printf("%lld.5\n",ans/2);

    }
}

#R BST

表面二叉树，实际上是数学问题

#include<iostream>
using namespace std;
typedef long long ll;
ll pow(ll x,int a){
    ll ans=1;
    for(int i=0;i<a;++i){
        ans*=x;
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        ll x,sum=0;
        cin>>x;
        ll temp=x;
        while(temp%2!=1){
            sum++;
            temp/=2;
        }
        cout<<x-pow(2,sum)+1<<' '<<x+pow(2,sum)-1<<endl;
    }
}

#S Chocolate Chip Cookies

做出这道题就去吃巧克力曲奇！

要注意只有一个点的情况！！！！！！我在这卡了俩小时

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const double eps=1e-6;
struct point{
    double x,y;
};
vector<point> choco;
inline double dis(point a,point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool judge_circle(point a,point b){
    double ab_edge=dis(a,b)/2.0;//如果大于2.5（半径）就可以不玩了
    if(ab_edge>2.5+eps) return false;
    else return true;
}
point center(point a,point b){
    point mid;
    mid.x=(a.x+b.x)/2.0;
    mid.y=(a.y+b.y)/2.0;
    point ab;//向量ab
    ab.x=a.x-b.x;
    ab.y=a.y-b.y;
    point s;//圆心和mid所在的方向向量
    double temp=sqrt(ab.x*ab.x+ab.y*ab.y);
    s.x=-ab.y/temp;
    s.y=ab.x/temp;
    double ab_edge=dis(a,b)/2.0;
    double mid_edge=sqrt(6.25-ab_edge*ab_edge);//勾股定理
    point c;//圆心
    c.x=mid.x+s.x*mid_edge;
    c.y=mid.y+s.y*mid_edge;

    return c;
}
bool judge(point c,point a){
    if((a.x-c.x)*(a.x-c.x)+(a.y-c.y)*(a.y-c.y)<=6.25+eps){
        return true;
    }
    else return false;
}
int main(){
    point p;
    int ans=0;
    while(cin>>p.x>>p.y){
        choco.push_back(p);
    }
    int size=choco.size();
    for(int i=0;i<size;++i){
        for(int j=0;j<size;++j){
            if(i==j){
                ans=max(ans,1);
                continue;
            }
            if(!judge_circle(choco[i],choco[j])){
                continue;
            }
            else {
                point c1 = center(choco[i], choco[j]);
                int sum = 0;
                for (int k = 0; k < size; ++k) {
                    if (judge(c1, choco[k]))
                        sum++;
                }
                ans = max(ans, sum);
            }
        }
    }
    cout<<ans<<endl;
}

#T Game of Connections

#U Inversion

#V Find The Multiple

#W Queens in peaceful positions

#X Utopia Divided

#Y Basketball One-on-One

怎么跟我们上羽毛球课一样啊

#include<iostream>
#include<string>
using namespace std;
int a=0,b=0;
string s;

int main(){
    cin>>s;

    for(int i=0;i<s.size();i+=2){
        if(s[i]=='A'){
            a+=s[i+1]-'0';
        }
        else if(s[i]=='B'){
            b+=s[i+1]-'0';
        }
        if(a>=11&&b<10){
            cout<<'A'<<endl;
            break;
        }
        else if(b>=11&&a<10){
            cout<<'B'<<endl;
            break;
        }
        else if(a==10&&b==10){
            i+=2;
            for(;i<s.size();i+=2) {
                if (s[i] == 'A') {
                    a += s[i + 1] - '0';
                }
                else if (s[i] == 'B') {
                    b += s[i + 1] - '0';
                }
                if (a - b >= 2) {
                    cout<<'A'<<endl;
                    break;
                }
                else if(b-a>=2){
                    cout<<'B'<<endl;
                    break;
                }
            }
            break;
        }
    }
}