32.代码题

接着上集......

派对：超时了，总该受到惩罚吧？

洛西：至于吗？就0.1秒！

晴/宇：十分应该。

洛西：我.....................

没办法，洛西只能按照要求去抓R了。

1.P1102 A-B 数对

题目描述

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 N,C。

第二行，N 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。

#include<bits/stdc++.h>
#include <map>
using namespace std;
typedef long long LL;
LL b[200001];
map<LL,LL> m;
int main()
{int n;LL c;LL s=0;cin >> n >> c;for(int i=1;i<=n;i++){cin >> b[i];m[b[i]]++;b[i]-=c;    } for(int i=1;i<=n;i++){s+=m[b[i]];} cout << s << endl;return 0;
}

2.P1002 [NOIP 2002 普及组] 过河卒

题目描述

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 B 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int x[] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int y[] = {0, 1, 2, 2, 1, -1, -2, -2, -1};
int bx, by, mx, my;
ll f[40][40];
bool s[40][40]; 
int main()
{scanf("%d%d%d%d", &bx, &by, &mx, &my);bx += 2; by += 2; mx += 2; my += 2;f[2][1] = 1;s[mx][my] = 1;for(int i = 1; i <= 8; i++) s[mx + x[i]][my + y[i]] = 1;for(int i = 2; i <= bx; i++){for(int j = 2; j <= by; j++){if(s[i][j]) continue; f[i][j] = f[i - 1][j] + f[i][j - 1];}}printf("%lld\n", f[bx][by]);return 0;
} 

3.P1030 [NOIP 2001 普及组] 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

#include<iostream>
#include<cstring>
using namespace std;
void s(string i,string a)
{if(i.size()>0){char ch=a[a.size()-1];cout<<ch;int k=i.find(ch);s(i.substr(0,k),a.substr(0,k));s(i.substr(k+1),a.substr(k,i.size()-k-1));}
}
int main()
{string i,a;cin>>i>>a;s(i,a);cout<<endl;return 0;
}

4.P1996 约瑟夫问题

题目描述

n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数，按顺序输出每个出圈人的编号。

#include<cstdio>
using namespace std;
int main()
{int n,m,s=0;scanf("%d%d",&n,&m);bool v[200]={0};for(int k=0;k<n;k++){for(int i=0;i<m;i++){if(++s>n)s=1;if(v[s])i--;}printf("%d ",s);v[s]=true;}return 0;
}

5.结语

洛西：总算完成任务了！