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;
}
全部评论

相关推荐

头像
今天 09:40
莆田学院 产品经理
点赞 评论 收藏
分享
11-21 15:10
华南农业大学 运营
点赞 评论 收藏
分享
10-18 21:51
西安电子科技大学 C++
看看逆天公司😅😅😅
ArisRobert：统一解释一下，第4点的意思是，公司按需通知员工，没被通知到的员工是没法去上班的，所以只要没被通知到，就自动离职。就是一种比较抽象的裁员。
点赞 评论 收藏
分享
10-14 23:12
重庆理工大学 Java
双非自知于中大厂无缘，有什么中偏小厂推吗？😊😔
躺尸修仙中：因为很多92的也去卷中小厂，反正投递简历不要钱，面试不要钱，时间冲突就推，不冲突就面试积累经验
点赞 评论 收藏
分享
11-19 12:33
已编辑
产品运营
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
305880次浏览 2733人参与
# 如果不工作真的会快乐吗 #
59673次浏览 521人参与
# 阿里云管培生offer #
18340次浏览 300人参与
# 地方国企笔面经互助 #
3970次浏览 11人参与
# 美团求职进展汇总 #
1328908次浏览 12455人参与
# 选完offer后，你后悔学本专业吗 #
20303次浏览 145人参与
# 百度开奖 #
164754次浏览 986人参与
# 正在实习的你，几点下班 #
52300次浏览 393人参与
# 国央企薪资爆料 #
8944次浏览 69人参与
# 如何一边实习一边秋招 #
992900次浏览 12641人参与
# 提前批简历挂麻了怎么办 #
146688次浏览 1949人参与
# 学历or实习经历，哪个更重要 #
51526次浏览 403人参与
# 海康威视求职进展汇总 #
399282次浏览 3406人参与
# 米哈游求职进展汇总 #
176304次浏览 1460人参与
# 求职遇到的搞笑事件 #
70986次浏览 577人参与
# 投递实习岗位前的准备 #
1180081次浏览 18399人参与
# 面试体验感最好的是哪家？ #
85227次浏览 846人参与
# 实习生应该准时下班吗 #
167559次浏览 1159人参与
# 得物求职进展汇总 #
66500次浏览 682人参与
# 网申一定要掌握的小技巧 #
5378次浏览 54人参与
# 招聘要求与实际实习内容不符怎么办 #
10347次浏览 273人参与
# 0offer是寒冬太冷还是我太菜 #
899615次浏览 8017人参与
牛客网
牛客企业服务