GCJ 2016 QR解题报告

本文主要是介绍GCJ 2016 QR解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.  

题目大意是，给你一个初始的整数，然后用他*1, * 2,*3 ....，并把所有出现过的数字记录下来， 问什么时候0～9所有数字都出现了一遍。

刚开始还怀疑有没有可能死循环， 后来没想直接跑了一个1～100000的看了下，都有结果，就直接暴力上了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <string>
#define INF 1000000007
using namespace std;
long long gao(int x) {int v[10];memset(v, 0, sizeof(v));int cnt = 1;while(true) {long long now = (long long)cnt * (long long)x;while(now) {v[now % 10] = 1;now /= 10;}int flag = 1;for(int i = 0; i < 10; i++) {if(v[i] == 0) {flag = 0;break;}}if(flag) return (long long)cnt * (long long)x;cnt++;}
}
int main() {int T, cas = 0, n;scanf("%d", &T);while(T--) {scanf("%d", &n); if(n == 0) {printf("Case #%d: INSOMNIA\n", ++cas);continue;}long long ans = gao(n);printf("Case #%d: %lld\n", ++cas, ans);}return 0;
}

B. 

给出一个栈序列，是由若干'+'和'-' 组成的。每次允许的操作是从栈顶取出若干元素，整体倒过来放进栈中，倒过来后'+'将变成'-'，反之亦然。

问用最少的操作使得整个序列都是'+'

这次完全没想别的直接上dp了，而正解好像只需要统计有多少段就行了。

dp[i][2]有两个状态，分别表示从0到i，整个变成'-'需要的操作数和变成'+'的操作

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char s[111];
int dp[111][2];
int main() {int T, cas = 0;scanf("%d", &T);while(T--) {scanf("%s", s); dp[0][0] = dp[0][1] = 0;int len = strlen(s);for(int i = 0; i < len; i++) {if(s[i] == '-') {dp[i + 1][0] = min(dp[i][0], dp[i][1] + 1);dp[i + 1][1] = dp[i + 1][0] + 1;} else {dp[i + 1][1] = min(dp[i][1], dp[i][0] + 1);dp[i + 1][0] = dp[i + 1][1] + 1;}}printf("Case #%d: %d\n", ++cas, dp[len][1]);}return 0;
}

C. 构造题。

给一个长度n,一个数量J 

问你是否能够找到J个长度为n的二进制数，使得他在二进制，三进制....九进制，十进制时都不是素数，并输出相应的一个因子

我的做法是直接构造，指定每个进制的因子分别为3,2,5,2,7,2,9,2,11 这样。或者3,2,3,2,7,2,3,2,3这样

然后开始构造二进制串，每个串中最多四重循环枚举位置，计算余数。 就可以了。

代码非常丑陋。就不贴了。

但是这个题显然有更直接的做法。来自昂神。

构造一个诸如1????11????1 这样的串，其中?随意填写0或者1

那么因子就是1????1  并且对任意进制都符合。 这解法又直接又简洁。

D. 这题题意大意就是给了一个分形。

原始串中包含L或者G，长度为K， 迭代时，串中L会变成原始串，G会变成K个G。

迭代C次，长度就是K^C 

现在给你经过若干次迭代后的串， 问你是否能最多查看S处元素的情况下判别出原始串是否有G。

那么对于小数据， 比较简单了。因为S＝ K。

我们首先对原始串的任意一个位置，  假设该处为G ，那么在最终串中必然会生成一个长度为K^(C-1)的区间，里面都是G。

对于每个区间任选一个位置检查即可， 总共检查K次。

那么对于S < K怎么办

还是一样的方法，对于原始串的某个位置i，假设该处为G，那么在最终串中最坏情况下，也会生成若干个G，这些G分布在若干个长度不一的区间内。

例如K＝5， C＝3时

我们看每个位置生成G的情况。 由于串太长了。 我们先看最终串前25个

i=1,GGGGGGGGGGGGGGGGGGGGGGGGG

i=2,?G???GGGGG?G????G????G???

i=3,??G????G??GGGGG??G????G??

i=4,???G????G????G?GGGGG???G?

i=5,????G????G????G????GGGGGG

观察这些我们发现，最多连续三个串，会在某一个位置都是G

例如i = 1,2,3时，第8个位置都是G，那么我们检查这个位置就同时检查了3个位置。

而最多多少个串可以被同时检查，可以发现取决于C，也就是同时C个串必然可以同时被检查。

那么最终最少的检查次数就是 ceil(K * 1.0 / C)了

每个位置画一画就发现， 需要检查的位置也很容易算出来了。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {int T, S, K, C,cas = 0;scanf("%d", &T);while(T--) {scanf("%d%d%d", &K, &C, &S);long long base = 1;for(int i = 0; i < C - 1; i++) {base = base * (long long)K;}int num = (int)(ceil(K * 1.0 / C));printf("Case #%d:", ++cas);if(num > S) {printf("  IMPOSSIBLE\n");continue;} for(int i = 1; i <= num; i++) {int now = (i - 1) * C + 1;long long st = (long long)(now - 1) * base; long long tmp = base;for(int j = 1; j < C; j++) {if(j + now > K) break;tmp /= K;st += tmp * (long long)(j + now - 1);}//long long mid = ed - base + 1 + 1;printf(" %lld", st + 1);}printf("\n");}return 0;
}

这篇关于GCJ 2016 QR解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---