问题描述 给定n个正整数，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。 输入格式 输入的第一行只有一个正整数n(1 ≤ n ≤ 1000)，表示数字的个数。 输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。 输出格式 输出这n个次数中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。 样例输入 6 10 1 10 20 30 20 样例输出 10
随便怎么乱搞都行，直接数组记数也行，和我一样写取尺法也行
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <Stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<LL> vec;
typedef vector<vec> mat;
const int MX = 1e3 + 5;
int A[MX];
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
sort(A + 1, A + 1 + n);
int Max = 0, ans, l, r;
for(l = 1; l <= n; l = r + 1) {
for(r = l; r < n && A[l] == A[r + 1]; r++);
int cnt = r - l + 1;
if(cnt > Max || (cnt == Max && A[l] < ans)) {
Max = cnt; ans = A[l];
}
}
printf("%d\n", ans);
return 0;
}
问题描述 每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。 识别码的计算方法如下： 首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。 编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出是正确的ISBN号码。 输入格式 输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 输出格式 输出一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。 样例输入1 0-670-82162-4 样例输出1 Right 样例输入2 0-670-82162-0 样例输出2 0-670-82162-4xjb乱搞
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <Stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<LL> vec;
typedef vector<vec> mat;
const int MX = 1e3 + 5;
char S[MX];
int main() {
scanf("%s", S);
int sz = 0, n = strlen(S), s = 0;
for(int i = 0; i < n - 1; i++) {
if(S[i] != '-') {
s += (S[i] - '0') * (++sz);
s %= 11;
}
}
bool sign;
if(s == 10) {
sign = (S[n - 1] == 'X');
} else {
sign = (S[n - 1] - '0' == s);
}
if(sign) printf("Right\n");
else {
char x = s == 10 ? 'X' : '0' + s;
S[n - 1] = x;
printf("%s\n", S);
}
return 0;
}
问题描述 在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。 请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。 输入格式 第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。 第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。 输出格式 输出一行，包含一个整数，即给定直方图内的最大矩形的面积。 样例输入 6 3 1 6 5 2 3 样例输出 10数据范围这么小，连单调栈都不需要维护，两个for循环就搞完了
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <Stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<LL> vec;
typedef vector<vec> mat;
const int MX = 1e3 + 5;
int A[MX];
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &A[i]);
}
int ans = 0;
for(int i = 1; i <= n; i++) {
int Min = A[i];
for(int j = i; j <= n; j++) {
Min = min(Min, A[j]);
ans = max(ans, Min * (j - i + 1));
}
}
printf("%d\n", ans);
return 0;
}
问题描述 我们把一个数称为有趣的，当且仅当： 1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。 2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。 3. 最高位数字不为0。 因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。 请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。 输入格式 输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。 输出格式 输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。 样例输入 4 样例输出 3设dp[i][s]表示长度为i，数字的状态为s时的种类数。
s直接状态压缩了一下，s>>i&1表示数字i是否以及出现过
接下来xjb数位dp就行了
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <Stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<LL> vec;
typedef vector<vec> mat;
const int MX = 1e3 + 5;
const int mod = 1e9 + 7;
LL dp[MX][20];
int main() {
int n;
scanf("%d", &n);
dp[1][2] = dp[1][4] = dp[1][8] = 1;
for(int i = 2; i <= n; i++) {
for(int s = 0; s < 16; s++) {
for(int j = 0; j <= 3; j++) {
if(j == 0 && (s >> 1 & 1)) continue;
if(j == 2 && (s >> 3 & 1)) continue;
int news = s | (1 << j);
dp[i][news] += dp[i - 1][s];
dp[i][news] %= mod;
}
}
}
printf("%lld\n", dp[n][15]);
return 0;
}
问题描述 给定一个R行C列的地图，地图的每一个方格可能是'#', '+', '-', '|', '.', 'S', 'T'七个字符中的一个，分别表示如下意思： '#': 任何时候玩家都不能移动到此方格； '+': 当玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格； '-': 当玩家到达这一方格后，下一步可以向左右两个方向相邻的一个非'#'方格移动一格； '|': 当玩家到达这一方格后，下一步可以向上下两个方向相邻的一个非'#'方格移动一格； '.': 当玩家到达这一方格后，下一步只能向下移动一格。如果下面相邻的方格为'#'，则玩家不能再移动； 'S': 玩家的初始位置，地图中只会有一个初始位置。玩家到达这一方格后，下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格； 'T': 玩家的目标位置，地图中只会有一个目标位置。玩家到达这一方格后，可以选择完成任务，也可以选择不完成任务继续移动。如果继续移动下一步可以向上下左右四个方向相邻的任意一个非'#'方格移动一格。 此外，玩家不能移动出地图。 请找出满足下面两个性质的方格个数： 1. 玩家可以从初始位置移动到此方格； 2. 玩家不可以从此方格移动到目标位置。 输入格式 输入的第一行包括两个整数R 和C，分别表示地图的行和列数。(1 ≤ R, C ≤ 50)。 接下来的R行每行都包含C个字符。它们表示地图的格子。地图上恰好有一个'S'和一个'T'。 输出格式 如果玩家在初始位置就已经不能到达终点了，就输出“I'm stuck!”（不含双引号）。否则的话，输出满足性质的方格的个数。 样例输入 5 5 --+-+ ..|#. ..|## S-+-T ####. 样例输出 2 样例说明 如果把满足性质的方格在地图上用'X'标记出来的话，地图如下所示： --+-+ ..|#X ..|## S-+-T ####X就这题恶心。
很明显两次加上方向的vis的BFS。但是要注意从起点和终点出发，里面的判断是有些不一样的
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <Stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<LL> vec;
typedef vector<vec> mat;
const int MX = 50 + 5;
int n, m;
bool vis[MX][MX][4];
bool sign[MX][MX][3];
char S[MX][MX];
struct Data {
int x, y, d;
Data() {}
Data(int _x, int _y, int _d) {
x = _x; y = _y; d = _d;
}
} Begin, End;
int dist[][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};//右左下上
void BFS_IN(Data bg) {
queue<Data>Q;
for(int i = 0; i < 4; i++) {
Q.push(Data(bg.x, bg.y, i));
}
while(!Q.empty()) {
Data fp = Q.front(); Q.pop();
vis[fp.x][fp.y][fp.d] = 1;
sign[fp.x][fp.y][0] = 1;
for(int k = 0; k < 4; k++) {
int nx = fp.x + dist[k][0];
int ny = fp.y + dist[k][1];
if(S[fp.x][fp.y] == '-' && k >= 2) continue;
if(S[fp.x][fp.y] == '|' && k <= 1) continue;
if(S[fp.x][fp.y] == '.' && k != 2) continue;
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(vis[nx][ny][k] || S[nx][ny] == '#') continue;
vis[nx][ny][k] = 1;
Q.push(Data(nx, ny, k));
}
}
}
void BFS_OUT(Data bg) {
queue<Data>Q;
for(int i = 0; i < 4; i++) {
Q.push(Data(bg.x, bg.y, i));
}
while(!Q.empty()) {
Data fp = Q.front(); Q.pop();
vis[fp.x][fp.y][fp.d] = 1;
sign[fp.x][fp.y][1] = 1;
for(int k = 0; k < 4; k++) {
int nx = fp.x + dist[k][0];
int ny = fp.y + dist[k][1];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(vis[nx][ny][k] || S[nx][ny] == '#') continue;
if(S[nx][ny] == '-' && k >= 2) continue;
if(S[nx][ny] == '|' && k <= 1) continue;
if(S[nx][ny] == '.' && k != 3) continue;
vis[nx][ny][k] = 1;
Q.push(Data(nx, ny, k));
}
}
}
int main() {
//FIN;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%s", S[i] + 1);
for(int j = 1; j <= m; j++) {
if(S[i][j] == 'S') Begin = Data(i, j, 0);
if(S[i][j] == 'T') End = Data(i, j, 0);
}
}
BFS_IN(Begin);
memset(vis, 0, sizeof(vis));
BFS_OUT(End);
if(!sign[End.x][End.y][0]) printf("I'm stuck!\n");
else {
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(sign[i][j][0] && !sign[i][j][1]) ans++;
}
}
printf("%d\n", ans);
}
/*for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
fuck((int)sign[i][j][1]);
}
printf("\n");
}*/
return 0;
}
总结：模拟题只是找自信的，考试还是要挂