2019中国大学生程序设计竞赛-女生专场

8题离场,两个人这个水平还可以吧


Ticket

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

北京地铁票每月的打折规则为:本次乘车前总消费不足 100 元本次不打折,满 100 元不足 150 元本次打8 折,满 150 元不足 400 元本次打 5 折,已满 400 元后本次不打折,已知 wls 每次出行的原票价,请问实际的花费是多少? 
Input输入包含两行。第一行一个整数 n 代表 wls 将要出行的次数。第二行 n 个正整数, ai 代表每次出行的票的原价,wls 是按照输入顺序依次出行的。
0 ≤ n ≤ 1, 000
0 < ai ≤ 1, 000 
Output一行一个数,代表实际的花费,保留小数点后两位小数。 

Sample Input

3
100 20 20

Sample Output

132.00

签到

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        double ans=0;
        for(int i=1;i<=n;i++){
            int a;
            scanf("%d",&a);
            if((int)ans<100.0){
                ans+=a*1.0;
            }
            else if(ans<150){
                ans+=a*0.8;
            }
            else if(ans<400){
                ans+=a*0.5;
            }
            else{
                ans+=a*1.0;
            }
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}

 


Gcd

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Descriptionwls

有一个整数 n,他想将 1 − n 这 n 个数字分成两组,每一组至少有一个数,并且使得两组数字的和的最大公约数最大,请输出最大的最大公约数。 
Input输入一行一个整数 n。
2 ≤ n ≤ 1, 000, 000, 000 
Output输出一行一个整数表示答案。 

Sample Input

6

Sample Output

7

签到,找sum的最小质数因子

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    while(scanf("%lld",&n)!=EOF){
        ll ans=(n+1)*n/2;
        ll x;
        if(n&1){
            x=min((n+1)/2,n);
        }
        else{
            x=min(n+1,n/2);
        }
        int fg=0;
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                fg=i;
                break;
            }
        }
        if(fg==0) fg=x;
        printf("%lld\n",ans/fg);
    }
    return 0;
}

 


Function

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

wls 有 n 个二次函数 Fi(x) = aix2 + bix + ci (1 ≤ i ≤ n).
现在他想在∑ni=1xi = m 且 x 为正整数的条件下求∑ni=1Fi(xi)的最小值。
请求出这个最小值。 
Input第一行两个正整数 n, m。
下面 n 行,每行三个整数 a, b, c 分别代表二次函数的二次项, 一次项,常数项系数。
1 ≤ n ≤ m ≤ 100, 000
1 ≤ a ≤ 1, 000
−1, 000 ≤ b, c ≤ 1, 000 
Output一行一个整数表示答案。 

Sample Input

2 3
1 1 1
2 2 2

Sample Output

13

优先队列维护一下答案即可,每次x+1对于fun函数的增量是(2*x+1)*a+b,每次放进去增量最小


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fun{
    ll a,b,c;
};
ll f(ll x,fun y){
    return y.a*x*x+y.b*x+y.c;
}
struct node{
    ll x;
    int id;
    ll cnt;
    bool operator < (const node& y)const{
        return x>y.x;
    }
};

fun ff[100100];
int main(){
    ll n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF){
        int cnt=(m-n);
        priority_queue<node> q;
        ll ans=0;
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&ff[i].a,&ff[i].b,&ff[i].c);
            q.push((node){ff[i].a*3+ff[i].b,i,1ll});
            ans+=f(1,ff[i]);
        }
        while(cnt--){
            node x=q.top();
            q.pop();
            ans+=x.x;
            x.cnt++;
            q.push((node){ff[x.id].a*(2*x.cnt+1)+ff[x.id].b,x.id,x.cnt});
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 


String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

wls 有一个长度为 n 的字符串,每次他可以将一个长度不大于 l 的子串修改成同一种字母,问至少修改多少次可以使字符串最多含有 k 段。
连续的只含同 一种字母的子串被称为一段。比如说, aaabbccaaa 共含有 4 段。 
Input第一行三个整数 n,l,k。
第二行一个字符串。
1 ≤ n ≤ 100, 000
1 ≤ l ≤ 100, 000
1 ≤ k ≤ 10 
Output一行一个数表示答案。 

Sample Input

3 1 1
bab

Sample Output

1

区间DP模版题,dp[i][j][k]维护前i个字符分为j段,最后一个字母是k的最小值,dp[i][j][26]记录最小答案

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
const int INF=0x7fffffff;
int n,l,k,dp[maxn][11][27];
char str[maxn];
void init(){
    memset(dp,0x3f3f3f3f,sizeof(dp));
    rep(j,0,k) rep(c,0,26) dp[0][j][c]=0;
}
void solve(){
    init();
    scanf("%s",str+1);
    rep(i,1,n){
        rep(j,1,k){
            rep(c,0,25){
                if(str[i]==c+'a') dp[i][j][c]=dp[i-1][j][c];
                else dp[i][j][c]=dp[i-1][j-1][c];
                if(i-l<1){
                    dp[i][j][c]=min(dp[i][j][c],dp[1][j][c]+1);
                    dp[i][j][c]=min(dp[i][j][c],dp[1][j-1][26]+1);
                }
                else{
                    dp[i][j][c]=min(dp[i][j][c],dp[i-l][j][c]+1);
                    dp[i][j][c]=min(dp[i][j][c],dp[i-l][j-1][26]+1);
                }
                dp[i][j][26]=min(dp[i][j][26],dp[i][j][c]);
            }
        }
    }
    printf("%d\n",dp[n][k][26]);
}
int main(){
    while(~scanf("%d%d%d",&n,&l,&k)) solve();
}

 


Circle

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

在半径为 1 的圆上有 n 个点,它们也是圆的 n 等分点,将每个相邻的 n 等分点相连,组成了一个正 n边形,现在你可以在圆上再增加一个点,使得新的 n+ 1 边形的面积最大,请输出最大面积。 
Input输入有多组(不超过 100 组)。
每组数据一行一个整数 n 代表点的数量。
3 ≤ n ≤ 100 
Output每组数据输出一行一个数表示加上一个点后的最大面积,结果保留6位小数。 

Sample Input

3

Sample Output

1.732051

简单几何题

#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
int main(){
    double n;
    while(scanf("%lf",&n)!=EOF){
        double ans=n*sin(2*pi/n)/2.0;
        ans+=(sin(2*pi/(n*2))-sin(2*pi/n)/2.0);
        printf("%.6lf\n",ans);
    }
    return 0;
}

 


Clock

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

wls 有一个钟表,当前钟表指向了某一个时间。
又有一些很重要的时刻,wls 想要在钟表上复现这些时间(并不需要依次复现)。我们可以顺时针转动秒针,也可以逆时针转动秒针,分针和时针都会随着秒针按规则转动,wls 想知道秒针至少转动多少角度可以使每个时刻至少都会被访问一次。
注意,时钟上的一种时针分针秒针的组合,可以代表两个不同的时间。 
Input第一行一个整数 n 代表有多少个时刻要访问。
第二行三个整数 h,m,s 分别代表当前时刻的时分秒。
最后n行每一行三个整数 hi,mi,si 代表每个要访问的时刻的时分秒。
1 ≤ n ≤ 86, 400
0 ≤ h, hi < 24
0 ≤ m, mi, s, si < 60 
Output输出一行一个数代表秒钟转的角度,答案保留两位小数。 

Sample Input

1
0 1 0
0 1 1

Sample Output

6.00

乱搞题,最终走完必定有两个点之间的距离是没走过的,枚举每对点,更新最小答案

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const double pi=acos(-1.0);
int cal(int x,int y, int z){return x*60*60+y*60+z;}
const int md=43200;
int v[maxn];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int h,m,s;
        scanf("%d%d%d",&h,&m,&s);
        h%=12;
        int tmp=cal(h,m,s);
        v[0]=tmp;
        for(int i=1;i<=n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            v[i]=cal(x%12,y,z);
        }
        sort(v,v+1+n);
        int ans=999999999;
        for(int i=0;i<=n;i++){
            if(v[i]==v[(i+1)%(n+1)]) continue;    
            if(v[i]==tmp || v[(i+1)%(n+1)]==tmp){
                int ma=999999999;
                if(v[i]==tmp){
                    if(n>1) ma=(tmp+md-v[(i+1)%(n+1)])%md;
                    else ma=min((md+v[(i+1)%(n+1)]-tmp)%md,(tmp+md-v[(i+1)%(n+1)])%md);
                }
                else{
                    if(n>1) ma=(md+v[i]-tmp)%md;
                    else ma=min((md+v[i]-tmp)%md,(tmp+md-v[i])%md);;
                }
                ans=min(ma,ans);
                continue;
            }
            int ls=(tmp+md-v[(i+1)%(n+1)])%md;
            int ln=(v[i]+md-tmp)%md;
            ans=min(ans,ls+ln+min(ls,ln));
        }
        printf("%.2lf\n",(double)ans*6.0);
    }
    return 0;
}

 


Tangram

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

一块七巧板有 7 块,现在 wls 想再在七巧板上加 n 条直线将七巧板切分并且使得切出来的块最多,请问最多能有多少块?

Input输入有多组(不超过 100, 000组)。
每组一行一个正整数 n。
0 ≤ n ≤ 1, 000, 000, 000 
Output每组输出一行一个数代表答案。 

Sample Input

1

Sample Output

13

切一刀这样必定最优,多出6块

再切一刀就是画一条直线越过之前那刀,增加7块,以此类推

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
ll n;
void solve(){
    printf("%lld\n",7ll+n*(11+n)/2);
}
int main(){
    while(~scanf("%lld",&n)) solve();
}

 


Tetris

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

wls 有一个 n ∗ m 的网格,他现在想用俄罗斯方块中的”凸”型密铺它。

一个”凸”型占四个格子,你可以随意把它调成上下左右四个方向中的一个。
密铺的定义是网格中任意一个格子被且只被一个”凸”型铺到,并且这些”凸”型不能铺出网格的边界。
随意输出一组解即可。 
Input一行两个整数 n, m。
1 ≤ n, m ≤ 12 
Output无解输出 no response。
如果有解,输出 n 行,每行 m 个字符。你只能使用 1, 2, 3, 4 这四个字符,由同 一字符组成的四连通块被视为一个”凸”型。
如果有多组解,那么输出任意一种即可。 

Sample Input

4 4

Sample Output

1113
2133
2243
2444

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,m;
int mp[5][5];
void solve(){
    if(n%4||m%4) printf("no response\n");
    else{
        rep(i,1,n){
            rep(j,1,m) printf("%d",mp[(i-1)%4+1][(j-1)%4+1]);
            printf("\n");
        }
    }
}
int main(){
    mp[1][1]=mp[1][2]=mp[1][3]=mp[2][2]=1;
    mp[1][4]=mp[2][3]=mp[2][4]=mp[3][4]=3;
    mp[2][1]=mp[3][1]=mp[3][2]=mp[4][1]=2;
    mp[3][3]=mp[4][2]=mp[4][3]=mp[4][4]=4;
    while(~scanf("%d%d",&n,&m)) solve();
}

 

发表评论,支持MarkDown语法