【写在前面】 就不写题意了，紫书上面有中文翻译，下面水题我直接给出代码了，一些需要推导的详细写一下！
【3-1】水题，顺序扫描一遍就行了。复杂度O(len)
char s[82];
bool vis[82];
int main()
{
int T;
scanf("%d",&T);
REP(i, T){
memset(vis, false, sizeof(vis));
scanf("%s", s);
int ans = 0;
int len = strlen(s);
REP(i, len){
if(vis[i] || s[i] == 'X') continue;
int cnt = 0;
while(s[i] == 'O'){
vis[i] = true;
cnt++, i++;
}
ans += cnt * (cnt + 1) / 2;
}
printf("%d\n", ans);
}
return 0;
}【3-2】同水题，模拟一下即可。复杂度O(len)
map<char, double> mp;
char s[20];
int main()
{
mp['C'] = 12.01, mp['H'] = 1.008, mp['O'] = 16.00, mp['N'] = 14.01;
int T;
scanf("%d", &T);
REP(j, T)
{
scanf("%s", s);
int len = strlen(s);
double ans = 0;
REP(i, len){
if(isdigit(s[i])) continue;
if(isdigit(s[i+1])){
double cnt = s[i+1] - '0';
int j = i + 2;
while(isdigit(s[j])){
cnt = cnt * 10 + s[j] - '0';
j++;
}
ans += cnt * mp[s[i]];
}
else{
ans += mp[s[i]];
}
}
printf("%.3f\n", ans );
}
return 0;
}【3-3】把所有的数字放到数组里面，或者边循环边基数都可以。
int a[100010];
int b[10];
int main()
{
int T, n;
scanf("%d", &T);
REP(k, T){
int cnt = 0;
scanf("%d", &n);
memset(b, 0, sizeof(b));
for(int i = 1; i <= n; i++){
int j = i;
while(j){
a[cnt++] = j % 10;
j /= 10;
}
}
for(int i = 0; i < cnt; i++){
b[a[i]]++;
}
for(int i = 0; i < 9; i++){
printf("%d ", b[i]);
}
printf("%d\n", b[9]);
}
return 0;
}【3-4】模拟长度并判断，复杂度O(n^2)
char s[82];
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%s", s);
int len = strlen(s);
int ans;
for(int i = 1; i <= len; i++){
bool ok = 1;
string temp = "";
for(int j = 0; j < i; j++) temp += s[j];
for(int j = i; j < len; j += i){
string xx = "";
for(int k = j; k < i + j; k++){
xx += s[k];
}
if(xx != temp){
ok = 0;
break;
}
}
if(ok){
ans = i;
break;
}
}
if(T >= 1)
printf("%d\n\n", ans);
else{
printf("%d\n",ans);
}
}
return 0;
}【3-5】纯模拟，没啥说的！
char maze[5][5];
char ope[1010];
bool judge(int x, int y)
{
if(x >= 0 && x < 5 && y >= 0 && y < 5) return true;
else return false;
}
int main()
{
int ks = 0;
while(gets(maze[0])){
if(maze[0][0] == 'Z') break;
gets(maze[1]);
gets(maze[2]);
gets(maze[3]);
gets(maze[4]);
for(int i = 0; i < 5; i++){
if(maze[i][4] == '\0'){
maze[i][4] = ' ';
}
}
int cnt = 0;
while(~scanf("%c", &ope[cnt])){
if(ope[cnt] != '0') cnt++;
else break;
}
ope[cnt++] = '0'; getchar();
int sx, sy;
for(int i = 0; i < 5; i++){
for(int j = 0; j < 5; j++){
if(maze[i][j] == ' '){
sx = i, sy = j;
}
}
}
bool ok = 1;
int len = strlen(ope);
REP(i, len){
if(ope[i] == '0') break;
if(ope[i] == 'L'){
if(judge(sx, sy - 1)){
maze[sx][sy] = maze[sx][sy-1];
maze[sx][sy-1] = ' ';
sy--;
}
else{
ok = 0;
break;
}
}
if(ope[i] == 'R'){
if(judge(sx, sy + 1)){
maze[sx][sy] = maze[sx][sy+1];
maze[sx][sy+1]=' ';
sy++;
}
else{
ok = 0;
break;
}
}
if(ope[i] == 'A'){
if(judge(sx-1, sy)){
maze[sx][sy] = maze[sx-1][sy];
maze[sx-1][sy] = ' ';
sx--;
}
else{
ok = 0;
break;
}
}
if(ope[i] == 'B'){
if(judge(sx+1, sy)){
maze[sx][sy] = maze[sx+1][sy];
maze[sx+1][sy] = ' ';
sx++;
}
else{
ok = 0;
break;
}
}
}
if(ks++) printf("\n");
printf("Puzzle #%d:\n", ks);
if(ok == 0){
printf("This puzzle has no final configuration.\n");
}
else{
for(int i = 0; i < 5; i++){
for(int j = 0; j < 4; j++){
printf("%c ",maze[i][j]);
}
printf("%c\n",maze[i][4]);
}
}
}
return 0;
}【3-6】纯模拟，不过输出要按照序号排序之后再输出。格式有点坑，pe了很多发。
int n, m;
char maze[12][12];
int id[12][12];
bool check(int x, int y)
{
if(x >= 0 && x < n && y >= 0 && y < m){
return true;
}
else{
return false;
}
}
struct node{
int pos;
string s;
bool operator<(const node &rhs) const{
return pos < rhs.pos;
}
void init(){
pos = 0;
s = "";
}
}ans[110];
int main()
{
int ks = 1;
while(scanf("%d", &n), n)
{
scanf("%d", &m);
for(int i = 0; i < n; i++){
scanf("%s", maze[i]);
}
for(int i = 0; i < 110; i++){
ans[i].init();
}
int cntt = 0;
memset(id, 0, sizeof(id));
int cnt = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(maze[i][j] == '*') continue;
if((check(i-1, j) == false || maze[i-1][j] == '*') || (check(i, j-1) == false || maze[i][j-1] == '*')){
id[i][j] = ++cnt;
}
}
}
if(ks>1) printf("\n");
printf("puzzle #%d:\n", ks++);
printf("Across\n");
int k;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j += k){
if(id[i][j] != 0){
//printf(" %d.", id[i][j]);
ans[cntt].pos = id[i][j];
k = 0;
while( maze[i][j+k] != '*' && (j + k) < m){
//printf("%c", maze[i][j+k]);
ans[cntt].s += maze[i][j+k];
k++;
}
//printf("\n");
cntt++;
}
else{
k = 1;
}
}
}
sort(ans, ans+cntt);
for(int i = 0; i < cntt; i++){
printf("%3d.",ans[i].pos);
cout<<ans[i].s<<endl;
}
cntt = 0;
for(int i = 0; i < 110; i++){
ans[i].init();
}
printf("Down\n");
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j += k){
if(id[j][i] != 0){
//printf(" %d.", id[j][i]);
ans[cntt].pos = id[j][i];
k = 0;
while(maze[j+k][i] != '*' && (j + k) < n){
//printf("%c", maze[j+k][i]);
ans[cntt].s += maze[j+k][i];
k++;
}
cntt++;
//printf("\n");
}
else{
k = 1;
}
}
}
sort(ans, ans+cntt);
for(int i = 0; i < cntt; i++){
printf("%3d.",ans[i].pos);
cout<<ans[i].s<<endl;
}
}
return 0;
}【3-7】贪心，找每一列出现最多的那个字母！复杂度O(n*m)
char s[1002];
struct node{
int a, c, g, t;
void init(){
a = 0, c = 0, g = 0, t = 0;
}
}thing[1005];
int main()
{
int T, n, m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i = 0; i < m; i++){
thing[i].init();
}
for(int i = 0; i < n; i++){
scanf("%s", s);
for(int j = 0; j < m; j++){
if(s[j] == 'A') thing[j].a++;
else if(s[j] == 'C') thing[j].c++;
else if(s[j] == 'G') thing[j].g++;
else thing[j].t++;
}
}
char ans[1005] = {'0'};
int maxx, anss = 0;
for(int i = 0; i < m; i++){
ans[i] = 'A';
maxx = thing[i].a;
if(thing[i].c > maxx){
ans[i] = 'C';
maxx = thing[i].c;
}
if(thing[i].g > maxx){
ans[i] = 'G';
maxx = thing[i].g;
}
if(thing[i].t > maxx)
{
ans[i] = 'T';
maxx = thing[i].t;
}
anss += n - maxx;
}
ans[m] = '\0';
printf("%s\n", ans);
printf("%d\n", anss);
}
return 0;
}【3-8】计算循环节。n除以m的余数只能是0~m-1，根据抽屉原则，当计算m+1次时至少存在一个余数相同， 即为循环节；存储余数和除数，输出即可。复杂度O(m)
int a[3003], b[3003], c[3003];
int main()
{
int n, m, t;
while(scanf("%d%d", &n, &m) != EOF)
{
t = n;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
int cnt = 0;
a[cnt++] = n/m;
n = n % m;
while(!b[n] && n){
b[n] = cnt; //记录第一次出现的位置
c[cnt] = n;
a[cnt++] = 10*n/m;
n = 10*n%m;
}
printf("%d/%d = %d.", t, m, a[0]);
for(int i = 1; i < cnt && i <= 50; i++){
if(n && c[i] == n) printf("(");
printf("%d", a[i]);
}
if(n == 0) printf("(0");
if(cnt > 50) printf("...");
printf(")\n");
printf(" %d = number of digits in repeating cycle\n\n", n == 0 ? 1 : cnt - b[n]);
}
return 0;
}【3-9】满足单调性，O(n扫描一下文本串即可！
char s1[100010], s2[100010];
int main()
{
while(scanf("%s%s", s1,s2) != EOF)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
int p = 0;
if(len1 > len2){
printf("No\n");
continue;
}
for(int i = 0; i < len2; i++){
if(s2[i] == s1[p]){
p++;
}
}
if(p == len1){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}【3-10】根据长方体的特点去判断即可！
struct Plane{
int x, y;
bool operator<(const Plane &rhs) const{
if(x == rhs.x) return y > rhs.y;
return x > rhs.x;
}
}p[6];
bool judge(){
if(memcmp(p, p + 1, sizeof(Plane)) || memcmp(p + 2, p + 3, sizeof(Plane)) || memcmp(p + 4, p + 5, sizeof(Plane))) return false;
if(p[0].x != p[2].x || p[0].y != p[4].x || p[2].y != p[4].y) return false;
return true;
}
int main()
{
while(scanf("%d%d",&p[0].x,&p[0].y) != EOF)
{
if(p[0].x < p[0].y) swap(p[0].x, p[0].y);
for(int i = 1; i < 6; i++){
scanf("%d%d",&p[i].x,&p[i].y);
if(p[i].x < p[i].y){
swap(p[i].x, p[i].y);
}
}
sort(p, p + 6);
if(judge()){
printf("POSSIBLE\n");
}
else{
printf("IMPOSSIBLE\n");
}
}
return 0;
}【3-11】固定一个不变，移动宁一个，判断合法性，取最小值 复杂度O(max(len1, len2))
char s1[200], s2[200];
int len1, len2;
int solve(char *s1, char *s2, int n)
{
int sumlen = len1 + len2;
int minn = min(len1, len2);
int len = sumlen;
REP(i, n){
int ok = 1, lcm = min(n - i, minn);
REP(j, lcm){
if(s1[i + j] == '2' && s2[j] == '2'){
ok = 0;
break;
}
}
if(ok && len > sumlen - lcm){
len = sumlen - lcm;
}
}
return len;
}
int main()
{
while(scanf("%s%s",s1,s2)!=EOF)
{
len1 = strlen(s1);
len2 = strlen(s2);
int ans = min(solve(s1, s2, len1), solve(s2, s1, len2));
printf("%d\n", ans);
}
return 0;
}【3-12】
如果每组数都要计算比较找到对应的m和e运算量太大,所以先打表，涉及浮点数表示的一些数学知识。
假设当前一层M和E的值为m和e，它们的位数分别为i和j。
首先计算m的值，用二进制表示的话，m的值为0.11…，也就是m = 2^(-1) + 2^(-2) + … + 2^(-1 - i)（i比实际1的个数少1个），也就是m = 1 - 2^(-1 - i)。
接下来就是计算e的值，不难得出，e = 2^j - 1。
那么也就有m * 2^e = A * 10^B，似乎可以直接计算了。然而，直接这样算的话是不行的，因为当e太大的话（e最大可以是1073741823，注意这还只是2的指数），等号左边的数就会超出上限，所以要想继续算下去，就得自己去想办法再写出满足要求的类来，这显然太麻烦了。所以，这个时候我们对等式两边同时取对数，这个时候就有 log10(m) + e × log10(2) = log10(A) + B。因为此时m和e的值都是确定的，所以不妨令等式左边为t，也就有t = log10(A) + B。
这个时候就有问题了，A和B怎么算。
科学记数法对于A，有1 ≤ A < 10。那么0 < log10(A) < 1。所以t的小数部分就是log10(A)，整数部分就是B，即B = ⌊t⌋，A = 10^(t - B)。那么接下来，我们只需要开出两个二维数组来，分别记录对应i和j下A和B的大小，之后从输入里提取出A和B的大小，去二维数组里面查找对应的i和j即可。
编程知识：
1.如果浮点数赋值给整数，小数部分会被截取。
2.类似这样5.699141892149156e76的数据串，想把e两端的数据分别赋给两个变量，可以先用string接收整个数据串，将string中的'e'替换为‘ ’,
再将string拷贝到istringstream的一个对象，再从该对象读取到两个变量即可。double A[20][40];
long B[20][40];
string s;
void init(){
REP(m, 9){
REPZ(e, 30){
double x = 1 - pow(2, -1 - m), y = pow(2, e) - 1;
double t = log10(x) + y*log10(2);
B[m][e] = t;
A[m][e] = pow(10, t - B[m][e]);
}
}
}
int main()
{
init();
while(cin>>s){
if(s == "0e0") break;
for(auto it = s.begin(); it != s.end(); it++){
if(*it == 'e'){
*it = ' ';
break;
}
}
istringstream is(s);
double a;
long b;
bool ok = 0;
is>>a>>b;
REP(m, 9){
REPZ(e, 30){
if(b == B[m][e] && (fabs(a - A[m][e]) < 1e-5)){
cout<<m<<" "<<e<<endl;
ok = 1;
break;
}
}
if(ok) break;
}
}
return 0;
}
京公网安备 11010502036488号