HPU19级算法训练赛第七场【题解】

A - 程序设计：合并数字

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+10;

int N,cnt;
int sk[maxn],top;
int main(){
    cin>>N;
    while(N--){
        int t;scanf("%d",&t);
        while(true){
            if(top && sk[top] - 1 == t){
                cnt++;
                top--;
                continue;
            }else if(top && sk[top] + 1 == t){
                cnt++;
            }else{
                sk[++top] = t;
            }
            break;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

B - 程序设计：找质数

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,N;
int ans[maxn];
bool vis[maxn];
int P[maxn/10],tail;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

void initP(int N){
    for(int i = 2;i<=N;i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0;P[j]<=N/i;j++){
            vis[P[j]*i] = true;
            if(i % P[j] ==0 ) break;
        }
    }
}

int main(){
    initP(1000000);
    cin>>T;
    while(T--){
        N = read();
        for(int i = 0;i<tail && P[i]+P[i]<=N;i++){
            if(!vis[N-P[i]]){
                printf("%d %d\n",P[i],N-P[i]);
                break;
            }
        }
    }

    return 0;
}

C - Red and Black

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int N,M,startx,starty,cnt;
int dir[4][2] = {-1,0,1,0,0,1,0,-1};
char str[25][25];
bool vis[25][25];
void dfs(int x,int y){
    cnt++;
    vis[x][y] = true;
    for(int i = 0;i<4;i++){
        int nx = x+dir[i][0],ny = y+dir[i][1];
        if(nx<1 || nx>N || ny<1 || ny>M || vis[nx][ny] || str[nx][ny] == '#') continue;
        dfs(nx,ny);
    }
}

int main(){
    while(scanf("%d %d",&M,&N)){
        if(N == 0 && M == 0) break;
        cnt = 0;
        memset(vis,0,sizeof vis);
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=M;j++){
                scanf(" %c",&str[i][j]);
                if(str[i][j] == '@'){
                    startx = i,starty = j;
                }
            }
        }
        dfs(startx,starty);
        printf("%d\n",cnt);
    }

    return 0;
}

D - Game 23

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int N,M;
int main(){
    cin>>N>>M;
    if(M%N !=0 ) puts("-1");
    else{
        int r = M/N;
        int cnt = 0;
        for(int i:{2,3}){
            while(r%i == 0){
                cnt++;
                r/=i;
            }
        }
        if(r > 1) puts("-1");
        else printf("%d\n",cnt);
    }
    return 0;
}

E - 棋盘问题

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int N,K,res;
pii arr[maxn];int tail;
bool row[10],col[10];

void dfs(int now,int cnt){
    if(cnt == K) {
        res++;
        return ;
    }
    if(now>tail) return ;
    pii p = arr[now];
    if(!row[p.first] && !col[p.second]){
        row[p.first] = true;
        col[p.second] = true;
        dfs(now+1,cnt+1);
        row[p.first] = false;
        col[p.second] = false;
    }
    dfs(now+1,cnt);
}
int main(){
    while(scanf("%d %d",&N,&K)){
        if(N == -1 && K == -1) break;
        res = 0;tail = 0;
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=N;j++){
                char c;scanf(" %c",&c);
                if(c == '#') arr[++tail] = {i,j};
            }
        }
        dfs(1,0);
        printf("%d\n",res);
    }

    return 0;
}

F - Super Jumping! Jumping! Jumping!

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int N;
ll dp[1010];
int arr[1010];
int main(){
    while(scanf("%d",&N)){
        if(N == 0) break;
        memset(dp,0,sizeof dp);
        for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
        for(int i = 1;i<=N;i++){
            dp[i] = arr[i];
            for(int j = 1;j<i;j++){
                if(arr[j] < arr[i])
                    dp[i] = max(dp[i],dp[j] + arr[i]);
            }
        }
        ll mx = 0;
        for(int i = 1;i<=N;i++) mx = max(mx,dp[i]);
        printf("%lld\n",mx);

    }

    return 0;
}

G - Primes

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int N;
bool div(int N){
    for(int i = 2;i*i<=N;i++){
        if(N%i == 0) return false;
    }
    return true;
}
int main(){
    int kase = 0;
    while(scanf("%d",&N)){
        if(N == 1 || N == 2) {
            printf("%d: no\n",++kase);
            continue;
        }
        if(N <=0) break;
        if(div(N)) printf("%d: yes\n",++kase);
        else printf("%d: no\n",++kase);
    }
    return 0;
}

H - WeirdSort

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,N,M;
int arr[maxn],p[maxn];

bool is_sort(){
    while(true){
        int change = 0;
        for(int i = 1;i<=M;i++){
            int idx = p[i];
            if(arr[idx] > arr[idx+1]) {
                swap(arr[idx],arr[idx+1]);
                change = 1;
            }
        }
        if(!change) break;
    }
    for(int i = 1;i<N;i++) if(arr[i] > arr[i+1]) return false;
    return true;
}
int main(){
    cin>>T;
    while(T--){
        scanf("%d %d",&N,&M);
        for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
        for(int i = 1;i<=M;i++) scanf("%d",&p[i]);
        if(is_sort()) puts("YES");
        else puts("NO");
    }


    return 0;
}

I - Integer Divisibility

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,N,M;

ll fun(){
    ll r = 0,tim = 0;
    while(true){
        r = (r*10 + M) % N;
        tim++;
        if(r == 0) break;
    }
    return tim;
}
int main(){
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%d %d",&N,&M);
        ll res = fun();
        printf("Case %d: %lld\n",++kase,res);
    }

    return 0;
}

J - Pie

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,N,F;
double area[maxn];

bool judge(double x){
    int cnt = 0;
    for(int i = 1;i<=N;i++){
        cnt += int(area[i]/x);
    }
    return cnt>=F;
}

int main(){
    cin>>T;
    while(T--){
        double l = 0,r = 0,mid;
        scanf("%d %d",&N,&F);F++;
        for(int i = 1;i<=N;i++){
            int R;scanf("%d",&R);
            area[i] = R * R * PI;
            r = max(r,area[i]);
        }
        l = r/F;
        while(r-l > 1e-5){
            mid = (l+r)/2;
            if(judge(mid)) l = mid;
            else r = mid;
        }
        printf("%.4lf\n",l);
    }

    return 0;
}

K - 水果

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,M,tag;
struct node{
    string name,place;
    bool operator < (const node & o) const{
        if(place != o.place) return place < o.place;
        return name < o.name;
    }
};
map<node,int> mp;
int main(){
    cin>>T;
    while(T--){
        mp.clear();
        if(tag) puts("");tag = 1;
        cin>>M;
        while(M--){
            string s1,s2;int v;
            cin>>s1>>s2>>v;
            mp[{s1,s2}] += v;
        }
        string lastplace = "-1";
        for(auto p:mp){
            node info  = p.first;
            if(info.place != lastplace){
                cout<<info.place<<endl;
                lastplace = info.place;
            }
            printf("   |----%s(%d)\n",info.name.c_str(),p.second);
        }
    }

    return 0;
}

L - Dead Pixel

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,A,B,X,Y;
int main(){
    cin>>T;
    while(T--){
        scanf("%d %d %d %d",&A,&B,&X,&Y);
        int t1 = X*B;
        int t2 = (A-X-1)*B;
        int t3 = A*Y;
        int t4 = A*(B-Y-1);
        int res = max(max(t1,t2),max(t3,t4));
        printf("%d\n",res);
    }

    return 0;
}

M - Complete the Sequence

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,S,C;
int dif[111][111];

void dfs(int now,int tail){
    if(tail == 1){
        for(int i = 2;i<=100;i++) dif[now][i] = dif[now][1];
        return ;
    }
    for(int i = 2;i<=tail;i++){
        dif[now+1][i-1] = dif[now][i] - dif[now][i-1];
    }
    dfs(now+1,tail-1);
    int cur = dif[now][1];
    for(int i = 1;i<=99;i++){
        cur += dif[now+1][i];
        dif[now][i+1] = cur;
    }
}

int main(){
    cin>>T;
    while(T--){
        memset(dif,0,sizeof dif);
        scanf("%d %d",&S,&C);
        for(int i = 1;i<=S;i++) scanf("%d",&dif[1][i]);
        dfs(1,S);
        for(int i = 1;i<=C;i++) {
            printf("%d",dif[1][S+i]);
            if(i < C) putchar(' ');
        }
        puts("");
    }

    return 0;
}

N - Harmonic Number

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;

int T,N;
double ans[maxn];
void init(){
    double cur = 0;
    for(int i = 1;i<=100000000;i++){
        cur += 1/double(i);
        if(i%100 == 0) ans[i/100] = cur;
    }
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        printf("Case %d: ",++kase);
        scanf("%d",&N);
        double res = ans[N/100];
        for(int i = N/100*100 + 1;i<=N;i++){
            res += 1/double(i);
        }
        printf("%.9lf\n",res);
    }

    return 0;
}
全部评论

相关推荐

11-12 12:35
中国地质大学 电力电子工程师
点赞 评论 收藏
分享
头像
11-12 20:50
深圳技术大学 前端工程师
点赞 评论 收藏
分享
10-24 11:10
山西大学 Java
大家避雷一下吧兄弟们 我直接上图了
你要是直接说不想要招满了就行，这样做我真的觉得恶心😅😅😅
若梦难了：哥们，面试挂是很正常的。我大中厂终面挂，加起来快10次了，继续努力吧。
点赞 评论 收藏
分享
11-07 10:30
门头沟学院 前端工程师
终于轮到我了
lastday&nbsp;知无不言
无敌虾孝子：喜欢爸爸还是喜欢妈妈
点赞 评论 收藏
分享
头像
11-12 17:37
南京技师学院 全栈开发
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 晒一晒我的offer #
9587437次浏览 104157人参与
# 简历被挂麻了，求建议 #
2440845次浏览 32775人参与
# 百度开奖 #
56621次浏览 357人参与
# 签约/解约注意事项 #
316103次浏览 1964人参与
# 00后45度躺现状 #
12371次浏览 187人参与
# 在国企工作的人，躺平了吗？ #
280165次浏览 3661人参与
# 北方华创开奖 #
6103次浏览 82人参与
# 那些拿到大厂offer的简历长啥样 #
115189次浏览 2130人参与
# 求职你最看重什么？ #
14969次浏览 111人参与
# 百度工作体验 #
104131次浏览 852人参与
# 实习，投递多份简历没人回复怎么办 #
2353115次浏览 33787人参与
# 你的工资什么时候发？ #
11117次浏览 104人参与
# 产运销实习日记 #
26633次浏览 303人参与
# 第一份工作应该选择高薪还是大平台 #
83464次浏览 556人参与
# AI了，我在打一种很新的工 #
20099次浏览 436人参与
# 秋招想进国企该如何准备 #
28118次浏览 252人参与
# 面试被问第一学历差时该怎么回答 #
72205次浏览 489人参与
# 来聊聊你目前的求职进展 #
509509次浏览 6111人参与
# 金融银行求职进展汇总 #
57585次浏览 394人参与
# 如何拒绝/反向PUA #
49526次浏览 331人参与
# 数据人的面试交流地 #
428227次浏览 7737人参与
# 秋招签约后的心态变化 #
59420次浏览 741人参与
牛客网
牛客企业服务