文档章节

Codejam Qualification Round 2019

o
 osc_gu9d45li
发布于 2019/04/07 14:00
字数 1637
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

本渣清明节 闲里偷忙 做了一下codejam 水平不出意外的在投稿之后一落千丈 后两题的hidden test竟然都挂了

A. Foregone Solution 水题,稍微判断一下特殊情况(比如1000, 5000这种)就好了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
// #include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;


char num[105];
char a[105];
char b[105];
int main() {
    int _;
    scanf("%d", &_);
    for(int cas = 1; cas <= _; ++cas) {
        scanf("%s", num);

        bool flag = true;
        for(int i = 0, len = strlen(num); i < len; ++i) {
            if(num[i] == '4') {
                a[i] = '2';
                b[i] = '2';
                flag = false;
            } else {
                a[i] = num[i];
                b[i] = '0';
            }
        }

        if(flag == true) {
            int pos = -1;
            
            for(int i = strlen(num) - 1; i >= 0; --i) {
                if(num[i] != '0') {
                    pos = i;
                    // if(num[i] == '1') {
                    //     hasOne = true;
                    // }
                    break;
                }
            }
            int hasOne = false; 
            for(int i = 0, len = strlen(num); i < len; ++i) {
                if(i < pos) {
                    a[i] = num[i];
                    b[i] = '0';
                } else if(i == pos) {
                    if(num[i] == '5') {
                        a[i] = '3';
                        b[i] = '2';
                    } else if(num[i] == '1' && i != strlen(num) - 1) {
                        a[i] = '0';
                        b[i] = '0';
                        hasOne = true;
                    } else {
                        a[i] = num[i] - 1;
                        b[i] = '1';
                    }
                } else {
                    if(hasOne) {
                        a[i] = '9';
                        b[i] = (i == strlen(num) - 1) ? '1' :'0';
                    } else {
                        a[i] = num[i];
                        b[i] = '0';
                    }
                }
            }
        }

        printf("Case #%d: ", cas);
        for(int i = 0, len = strlen(num), flag = true; i < len; ++i) {
            if(a[i] == '0' && flag) {
            } else {
                flag = false;
                printf("%c", a[i]);
            }
        }
        printf(" ");
        for(int i = 0, len = strlen(num), flag = true; i < len; ++i) {
            if(b[i] == '0' && flag) {
            } else {
                flag = false;
                printf("%c", b[i]);
            }
        }
        printf("\n");
    
    }
    return 0;
}

B. You Can Go Your Own Way 水题,直接和她反着来就好了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
// #include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

char seq[100005];
char result[100005];
int main() {
    int _;
    scanf("%d", &_);
    for(int cas = 1; cas <= _; ++cas) {
        int n;
        scanf("%d %s", &n, seq);
        for(int i = 0, len = strlen(seq); i < len; ++i) {
            if(seq[i] == 'S')
                result[i] = 'E';
            else 
                result[i] = 'S';
        }
  

        printf("Case #%d: ", cas);
        for(int i = 0, len = strlen(seq); i < len; ++i) {
            printf("%c", result[i]);
        }
        printf("\n");

    
    }
    return 0;
}

C. Cryptopangrams 大家都知道求下相邻的数的gcd,然后去重,排序 有个小坑就是,序列当中可能相邻的数是相同的,也就意味着有原始密码有a,b,a这种。需要找到一个相邻的数不相同的,然后反推其他的所有 其次就是大数,c++模版不好找,不如写java, python

import java.io.*;
import java.util.*;
import java.math.*;


public class Solution {
    Scanner in = new Scanner(new BufferedInputStream(System.in));
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BigInteger seq[] = new BigInteger[105];
    BigInteger prime[] = new BigInteger[105];
    //    BigInteger num[] = new BigInteger[105];
    int lower_bound(BigInteger[] nums, int begin, int end, BigInteger value) {
        while (begin < end) {
            int mid = begin + (end - begin) / 2;
            if (nums[mid].compareTo(value) == -1) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        return begin;
    }
    void solve() {
        int casNum;
        casNum = in.nextInt();
        for(int cas = 1; cas <= casNum; ++cas) {
            BigInteger n;
            int l;
            n = in.nextBigInteger(); l = in.nextInt();
            for(int i = 0; i < l; ++i) {
                seq[i] = in.nextBigInteger();
            }

            int pos = -1;
            for(int i = 1; i < l; ++i) {
                if(seq[i].equals(seq[i-1]) == false) {
                    prime[i] = seq[i].gcd(seq[i-1]);
                    pos = i;
                    break;
                }
            }

            for(int i = pos - 1; i >= 0; --i) {
                prime[i] = seq[i].divide(prime[i + 1]);
            }
            for(int i = pos + 1; i <= l; ++i) {
                prime[i] = seq[i-1].divide(prime[i-1]);
            }

            List<BigInteger> num=new ArrayList<>();
            for(int i = 0; i <= l; ++i) {
                num.add(prime[i]);
            }
            Set<BigInteger> uniqueGas = new HashSet<BigInteger>(num);
//            out.println(uniqueGas.size());
//            for(BigInteger i : uniqueGas) {
//                out.println(i);
//            }
            BigInteger[] result = uniqueGas.toArray(new BigInteger[0]);
            Arrays.sort(result, 0, uniqueGas.size());
            assert(uniqueGas.size() == 26);
            // printf("%d\n", (int)num.size());
            // for(int i = 0, len = num.size(); i < len; ++i) printf("%lld ", num[i]); printf("\n");
            out.printf("Case #%d: ", cas);

            for(int i = 0; i <= l; ++i) {
                int tt = lower_bound(result,0, uniqueGas.size(), prime[i]);
                out.printf("%c", tt + 'A');
            }
            out.printf("\n");
        }
        out.flush();
    }
    public static void main(String args[]) {
        new Solution ().solve();

    }
}

D. Dat Bae 如果B没有小于等于15的限制的话,本渣觉得需要10次查询,这也是本渣的解法 不断二分01查询,比如0011, 0101这样查,就能最后判断出来每个位置在不在

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

vector<pair<int, int> > prepare;
vector<pair<int, int> > solve; 
vector<int> preClip;
vector<int> solveClip;
int result[2005];
char answer[2005];
int main() {
    int _;
    scanf("%d", &_);
    for(int cas = 1; cas <= _; ++cas) {
        int n, b, f;
        scanf("%d %d %d", &n, &b, &f);
        prepare.clear();
        preClip.clear();
        prepare.push_back(make_pair(1, n));
        preClip.push_back(n - b);

        while(1) {
            solveClip.clear();
            solve.clear();
            int flag = false;
            int maxx = -1;
            for(int i = 0, len = prepare.size(); i < len; ++i) {
                int start = prepare[i].first; int end = prepare[i].second;
                // if(end == start) {
                //     solve.push_back(make_pair(start, end));
                // } else {
                    int mid = (start + end) / 2;
                    solve.push_back(make_pair(start, mid));
                    solve.push_back(make_pair(mid + 1, end));
                // }
                maxx = max(maxx, end - start);
            }
            if(maxx == 1) flag = true;

            for(int i = 0, len = solve.size(); i < len; ++i) {
                int start = solve[i].first; int end = solve[i].second;
                for(int j = start; j <= end; ++j) {
                    printf("%d", (i % 2 == 0) ? 0 : 1);
                }
            }
            printf("\n");
            fflush(stdout);
            scanf("%s", answer);
            for(int i = 0, len = preClip.size(), pre = 0; i < len; ++i) {
                int pos = pre + preClip[i];
                for(int j = pre, endJ = pre + preClip[i]; j < endJ; ++j) {
                    if(answer[j] == '1') {
                        pos = j;
                        break;
                    }
                }
                solveClip.push_back(pos - pre);
                solveClip.push_back(preClip[i] - pos + pre);
                pre += preClip[i];
            }

            if(flag == true) break;

            // assert(solve.size() == solveClip.size());
            // for(int i = 0, len = solve.size(); i < len; ++i) {
            //     int start = solve[i].first; int end = solve[i].second; int val = solveClip[i];
            //     printf("%d %d %d: ", start, end, val);
            // } printf("\n");

            prepare.swap(solve);
            preClip.swap(solveClip);
        }

        assert(solve.size() == solveClip.size());

        for(int i = 0, len = solve.size(); i < len; ++i) {
            int start = solve[i].first; int end = solve[i].second; int val = solveClip[i];
            if(start == end) {
                if(val == 1) {
                    result[start] = 1;
                } else {
                    result[start] = 0;
                }
            }
        }
        for(int i = 1, fir = true; i <= n; ++i) {
            if(result[i] == 0) {
                if(fir) fir = false;
                else printf(" ");
                printf("%d", i - 1);
            } 
        }
        printf("\n");
        fflush(stdout);

        int basa;
        scanf("%d", &basa);
    }
    return 0;
}

/*
1000
5 2 10
answer(0 3)
2 1 10
answer(0)



*/

但是如果只是5次查询,这样不行。反过来通过1,2,4,8为界的查询方式,判断一个16个数的组的borken情况。 如下所示 0101010101010101 0011001100110011 0000111100001111 0000000011111111 可以每16个数一个组,因为我们知道最多15个broken,每组必会有数保留,那么我们就可以判断出每个数是在哪个组当中的。贴下别人的代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <assert.h>
#include <iomanip>
using namespace std;
const int N = 7005;
const int M = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
typedef long long ll;

void solve(){
	int F = 4;
	int n, b, fake_f;
	cin >> n >> b >> fake_f;
	// assert(fake_f >= F);
	for(int f = 0; f < F; f++){
		string g;
		for(int i = 0; i < n; i++){
			g += (char)('0' + ((i >> f) & 1));
		}
		cout << g << '\n' << flush;
	}
	vector<int> answers(n-b);
	for(int f = 0; f < F; f++){
		string res;
		cin >> res;
		for(int i = 0; i < n-b; i++){
			answers[i] ^= (res[i] - '0') << f;
		}
        // for(int i = 0; i < n - b; ++i) {
        //     printf("%d ", answers[i]);
        // } printf("\n");
	}
	vector<int> broken;
	int z = 0;
	for(int i = 0; i < n-b; i++){
		while((z & 15) != answers[i]){
			cout << z << ' ';
			z++;
		}
		z++;
	}
	while(z < n){
		cout << z << ' ';
		z++;
	}
	cout << '\n';
	cout << flush;
	int res;
	cin >> res;
}


int main(){
	int T;
	cin >> T;
	for(int t = 1; t <= T; t++){
		solve();
	}
}

/*
1000
5 2 10

01010
00110
00001
00000
00000
100
010
001
000
000
answer(0 3)
000
010
001
000
000
answer(0 3)

2 1 10
answer(0)



*/
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Code jam Qualification Round 2020

#A Vestigium (7pts)https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020993c?show=progress 题解: t组数据。每组数据给出一个n x n的矩阵,元素的取值......

osc_unnbi4yg
04/04
3
0
Let Me Count The Ways(Kickstart Round H 2018)

题目链接:https://code.google.com/codejam/contest/3324486/dashboard#s=p2 题目: 思路:    代码实现如下: 1 #include <set> 2 #include <map> 3 #include <deque> 4 #include <queue......

osc_9z0e3l8u
2018/11/18
1
0
google compute test Problem C. Moist

google compute test Problem C. Moist URL:https://code.google.com/codejam/contest/2933486/dashboard#s=p2 #include "stdafx.h" include<iostream> include<fstream> include<vector> i......

liangxiao
2013/09/15
40
0
HTML5 Code Jam&金山移动开发大赛

“金山移动大赛”是由html5梦工厂和金山网络联合主办,北京GDG社区协办的开发者大赛。由金山网络赞助支持,推广和宣传的一次开发者codejam活动。活动面向所有的开发者,不管你是HTML5,Andro...

红薯
2013/07/04
442
2
MyEclipse生成的Hibernate一对一配置问题

myeclipse的hibernate反转工具生成的一对一映射配置无法使用,在项目启动时就报错, 错误信息如下:

思想永无止境
2016/11/04
37
0

没有更多内容

加载失败,请刷新页面

加载更多

038. RocketMQ 高性能最佳实践

1. 最佳实践之 Producer 1. 一个应用尽可能用一个 Topic,消息子类型用 tags 来标识,tags 可以由应用自由设置。 只有发送消息设置了 tags,消费方在订阅消息时,才可以利用 tags 在 broker...

华夏紫穹
58分钟前
32
0
QQ音乐Android客户端Web页面通用性能优化实践

QQ音乐 Android 客户端的 Web 页面日均 PV 达到千万量级,然而页面的打开耗时与 Native 页面相距甚远,需要系统性优化。本文将介绍 QQ 音乐 Android 客户端在进行 Web 页面通用性能优化过程中...

腾讯云开发者社区
今天
32
0
rabbitmq+sleuth+zinkip 分布式链路追踪

我们都知道,微服务之间通过feign传递,在复杂的微服务架构系统中,几乎每一个前端请求都会形成一个复杂的分布式服务调用链路,在每条链路中任何一个依赖服务出现延迟超时或者错误都有可能引...

良许Linux
今天
16
0
5分钟搭建属于你的视频会议系统

前言 在疫情的推动下视频会议和线上办公大力发展,如果你也想了解视频会议,看看这篇文章吧 准备工作 一台Ubuntu18.04拥有公网IP的服务器 一个域名提前解析到这台服务器上 安全组设置规则tcp...

死磕音视频
今天
17
0
从文本JavaScript中删除HTML - Strip HTML from Text JavaScript

问题: 有没有一种简单的方法可以在JavaScript中获取html字符串并去除html? 解决方案: 参考一: https://stackoom.com/question/3RxM/从文本JavaScript中删除HTML 参考二: https://oldbug...

fyin1314
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部