20190821中山晨考DAY2 from 重庆 题解

T1.数字

description

定义s(i)表示将1到n视为字符串后依次相连形成的串，例如s(12)为123456789101112.

给定正整数n，求出最小的i使得将n视为字符串后是s(i)的子串。

有多组数据。

Input

第一行一个正整数t表示数据组数，每组数据一行一个正整数n.

Output

每组数据输出一行一个整数表示答案

Sample 

Input

2

2

10

Output

2

10

DAta Constraint

Subtask 1(10pts):n<=1000。

Subtask 2(25pts):n<=200000。

Subtask 3(65pts):无特殊限制。

对于全部数据，t<=10000,n<=10^17。

（对于第一次手打题目的我要死了QAQ）。

这道题可以看到第一个子任务是可以轻松离线做的，所以用极其暴力的做法暴力模拟就可以了

10分代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {int x = 0, f = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') {f = -1;}c = getchar();}while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();}return x * f;
}
int m[1088896], a[1088896], numa[1088896];inline bool judge(int place, int num, int ws) {int x = num;for(int i = 1; i <= ws; i++) {if(m[place + ws - i ] != x % 10) {return false;}x = x / 10;}return true;
}inline int nums(int numm, int ws) {for(int i = 1; i <= 1088895; i++) {if(judge(i, numm, ws)) {return numa[i + ws - 1];}}
}inline int ws(int num) {int x = num, ans = 0;while(x != 0) {x /= 10;ans++;}return ans;
}signed main() {freopen("number.in", "r", stdin);freopen("number.out", "w", stdout);int cnt = 0;for(int i = 1; i <= 200000; i++) {int x = i;int p = 0;if(x / 10 == 0) {p = 1;} else if(x / 100 == 0) {p = 10;} else if(x / 1000 == 0) {p = 100;} else if(x / 10000 == 0) {p = 1000;} else if(x / 100000 == 0) {p = 10000;} else if(x / 1000000 == 0) {p = 100000;}while(p != 0) {m[++cnt] = x / p;numa[cnt] = i;x %= p;p /= 10;}}for(int i = 1; i <= 1000; i++) {a[i] = nums(i, ws(i));}a[0] = 10;int T = read();while(T--) {int n = read();if(n <= 1000) {cout << a[n] << endl;} else {printf("%lld\n", nums(n, ws(n)));}}return 0;
}/*考场上我试着做了30分的代码，可是爆炸了，所以QAQ。只有10分*/

接下来直接就是满分做法了。

题解中是这样说明的。

意思就是说你想到的就是题解（QAQ，真的，都想到了，所以，这道题便开始了狂暴的测试当中）

满分代码（暂缺）

T2.Maja

Description

蜜蜂 Maja 到了一片草地，草地可以被描述成 N 行 M 列的网格图，在第 i 行第 j 列的位置上有 C_{i,j} 朵未授粉的花。
Maja 会从第 A 行第 B 列出发，每次只能移动到与当前位置四相邻的格子上，且不能移动到草地以外。每到达一个格子，她会把此处所有未授粉的花都授粉。
然而，当 Maja 离开一个格子，此处又会长出 C_{i,j} 朵未授粉的花。
Maja 想知道，如果她从第 A 行第 B 列出发，选择一条长度恰好为 K 的路径，最后又回到第 A 行第 B 列，最多能为多少朵花授粉。

Input

第一行 5 个正整数 N,M,A,B,K，如题面所述（K 一定是偶数）。
接下来 N 行每行 M 个非负整数，第 i 行第 j 个表示题面所述的 C_{i,j}。
数据保证 C_{A,B}=0。

Output

一个整数，表示授粉数的最大值。

Sample Input

Sample 1:

2 2 1 1 2
0 1
2 10

Sample 2:

2 2 1 1 4
0 5
5 10

Sample 3:

3 3 2 2 6
5 1 0
1 0 3
1 3 3

Sample Output

Sample 1:

2

Sample 2:

20

Sample 3:

15

Data Constraint

对于40%的数据：

k<=10000

对于100%的数据：

2<=n,m<=100 1<=A<=n  1<=B<=m  2<=k<=10^9  0<=cij<=10^9

这道题目，

40%滚动数组DP，100%滚动数组DP（……）只不过哦统计答案的方式有一些不一样罢了

40%直接出答案，100%还要讨论一下摇摆的情况，就是走到一个点，在那里走过来走过去，然后再回去

所以，40分的

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {int x = 0, f = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') {f = -1;}c = getchar();}while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();}return x * f;
}
int mapa[101][101];
int zdx = 0x7ffffff, zdy = 0x7ffffff;
int xx[4] = {0, 0, 1, -1};
int yy[4] = { -1, 1, 0, 0};
int f[101][101][101];
signed main() {freopen("maja.in", "r", stdin);freopen("maja.out", "w", stdout);int n = read(), m = read(), A = read(), B = read(), k = read();for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {mapa[i][j] = read();}}for(int o = 0; o < 4; o++) {f[1][A + xx[o]][B + yy[o]] = mapa[A + xx[o]][B + yy[o]];}for(int i = 2; i <= k; i++) {for(int x = 1; x <= n; x++) {for(int y = 1; y <= m; y++) {for(int o = 0; o < 4; o++) {f[i % 100][x][y] = max(f[i % 100][x][y], f[(i - 1) % 100][x + xx[o]][y + yy[o]]);}if(f[i % 100][x][y] != 0) {f[i % 100][x][y] += mapa[x][y];}}}}int ans = f[k % 100][A][B];printf("%lld\n", ans);return 0;
}

100分的

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {int x = 0, f = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') {f = -1;}c = getchar();}while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();}return x * f;
}
int mapa[101][101];
int zdx = 0x7ffffff, zdy = 0x7ffffff;
int maxv[101][101];
int xx[4] = {0, 0, 1, -1};
int yy[4] = { -1, 1, 0, 0};
int f[101][101][101];
signed main() {freopen("maja.in", "r", stdin);freopen("maja.out", "w", stdout);int n = read(), m = read(), A = read(), B = read(), k = read();for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {mapa[i][j] = read();}}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {for(int o = 0; o < 4; o++) {maxv[i][j] = max(maxv[i][j], mapa[i + xx[o]][j + yy[o]]);}}}for(int o = 0; o < 4; o++) {f[1][A + xx[o]][B + yy[o]] = mapa[A + xx[o]][B + yy[o]];}int ans = 0;for(int i = 2; i <= min(k / 2, n * m); i++) {for(int x = 1; x <= n; x++) {for(int y = 1; y <= m; y++) {for(int o = 0; o < 4; o++) {f[i % 100][x][y] = max(f[i % 100][x][y], f[(i - 1) % 100][x + xx[o]][y + yy[o]]);}if(f[i % 100][x][y] != 0) {f[i % 100][x][y] += mapa[x][y];ans = max(ans, f[i % 100][x][y] * 2 + (maxv[x][y] + mapa[x][y]) * (k - i * 2) / 2 - mapa[x][y]);}}}}printf("%lld\n", ans);return 0;
}

（说实话我觉得100分代码跟40分的差不多QAQ）

T3.djq的朋友圈