A:门牌制作
题面：
思路：
暴力遍历，1-2020的数字，然后判断每一位，计数。
代码：
/*
* @Date: 2020-10-17 21:49:55
* @LastEditTime: 2020-10-17 21:58:58
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int ans = 0;
for (int i = 1; i <= 2020; i++) {
int j = i;
while (j) {
if (j % 10 == 2){
ans++;
}
j /= 10;
}
}
cout << ans << endl;
return 0;
}
答案：
624
B:既约分数
思路：
遍历1-2020之间的任意点对，判断gcd是否为1，计数。
代码：
/*
* @Date: 2020-10-17 22:02:12
* @LastEditTime: 2020-10-17 22:02:24
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int ans = 0;
for (int i = 1; i <= 2020; i++) {
for (int j = 1; j <= 2020; j++) {
if (__gcd(i, j) == 1){
ans++;
}
}
}
cout << ans << endl;
return 0;
}
答案:
2481215
C:蛇形填数
题面：
思路：
模拟整个过程，判断一下奇偶位置的特殊情况。
代码：
/*
* @Date: 2020-10-17 22:05:26
* @LastEditTime: 2020-10-17 22:06:55
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int mmp[50][50], id;
int main() {
for (int i = 1; i <= 40; i++) {
if (i & 1) {
int idx = i, idy = 1;
for (int j = 0; j < i; j++){
mmp[idx - j][idy + j] = ++id;
}
} else {
int idx = 1, idy = i;
for (int j = 0; j < i; j++){
mmp[idx + j][idy - j] = ++id;
}
}
}
cout << mmp[20][20] << endl;
return 0;
}
答案：
761
D:跑步锻炼
题面：
思路：
直接模拟日期加法，递增到2020年10月1日为止，计数（注意第一天也是2哦），注意判断闰年，处理好年月日。
代码：
/*
* @Date: 2020-10-17 22:09:57
* @LastEditTime: 2020-10-17 22:11:55
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int M[13] = {
0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
int y = 2000, m = 1, d = 1, w = 6, ans = 2;
while (y != 2020 || m != 10 || d != 1) {
if (y % 400 == 0 || (y % 4 == 0 && y % 100)) {
M[2] = 29;
} else {
M[2] = 28;
}
d++;
w = (w + 1) % 7;
if (d > M[m]) {
d = 1;
m++;
if (m > 12) {
m = 1;
y++;
}
}
if (d == 1 || w == 1) {
ans++;
}
ans++;
}
cout << ans << endl;
return 0;
}
答案：
8879
E:七段码
题面：
思路：
暴力枚举 2 7 = 128 2^7=128 27=128次方的所有七段码，然后DFS判断联通块。（不愧是暴力杯 ）
代码：
建图代码:
/*
* @Date: 2020-10-17 21:20:30
* @LastEditTime: 2020-10-17 22:15:57
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int ans = 0;
freopen("in.txt", "w", stdout);
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
for (int c = 0; c <= 1; c++) {
for (int d = 0; d <= 1; d++) {
for (int e = 0; e <= 1; e++) {
for (int f = 0; f <= 1; f++) {
for (int g = 0; g <= 1; g++) {
int mmp[6][4] = {
0};
if (a) {
for (int i = 1; i <= 3; i++) {
mmp[1][i] = 1;
}
}
if (b) {
for (int i = 1; i <= 3; i++) {
mmp[i][3] = 1;
}
}
if (c) {
for (int i = 3; i <= 5; i++) {
mmp[i][3] = 1;
}
}
if (d) {
for (int i = 1; i <= 3; i++) {
mmp[5][i] = 1;
}
}
if (e) {
for (int i = 3; i <= 5; i++) {
mmp[i][1] = 1;
}
}
if (f) {
for (int i = 1; i <= 3; i++) {
mmp[i][1] = 1;
}
}
if (g) {
for (int i = 1; i <= 3; i++) {
mmp[3][i] = 1;
}
}
printf("5 3\n");
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= 3; j++) {
printf("%d", mmp[i][j]);
}
puts("");
}
puts("");
}
}
}
}
}
}
}
return 0;
}
DFS求联通块代码
/*
* @Date: 2020-10-17 21:20:03
* @LastEditTime: 2020-10-17 21:27:00
* @Author's blog: nuoyanli
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
char a[N][N];
int n, m, vis[N][N];
void dfs(int r, int c, int f) {
if (r < 0 || r >= m || c < 0 || c >= n) {
return;
}
if (vis[r][c] > 0 || a[r][c] != '1') {
return;
}
vis[r][c] = f;
for (int i = -1; i <= 1; i++){
for (int j = -1; j <= 1; j++){
if (i != 0 || j != 0){
dfs(r + i, c + j, f);
}
}
}
}
int main() {
int sum = 0;
freopen("in.txt", "r", stdin);
while (~scanf("%d%d", &m, &n)) {
for (int i = 0; i < m; i++){
scanf("%s", a[i]);
}
memset(vis, 0, sizeof(vis));
int cnt = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (vis[i][j] == 0 && a[i][j] == '1'){
dfs(i, j, ++cnt);
}
}
}
if (cnt == 1){
sum += 1;
}
}
printf("%d\n", sum);
return 0;
}
F:成绩统计
题面：
思路：
直接计算，然后注意四舍五入。
代码：
/*
* @Date: 2020-10-17 22:18:36
* @LastEditTime: 2020-10-17 22:21:48
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, jg = 0, yx = 0;
scanf("%d", &n);
while (n--) {
int x;
scanf("%d", &x);
if (x >= 60) {
jg++;
}
if (x >= 85) {
yx++;
}
}
double Jg = jg * 1.0 / n * 1.0;
double Yx = yx * 1.0 / n * 1.0;
int ans_jg = int(Jg * 1000 + 5) / 10;
int ans_yx = int(Yx * 1000 + 5) / 10;
printf("%d%%\n%d%%\n", ans_jg, ans_yx);
return 0;
}
G:回文日期
题面：
思路：
直接按照题意模拟，暴力判断。
代码：
/*
* @Date: 2020-10-18 13:13:44
* @LastEditTime: 2020-11-24 14:41:52
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
int temp[10], m[13] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool hw(int x) {
int tot = 0;
while (x) {
temp[tot++] = x % 10;
x /= 10;
}
for (int i = 0; i < tot; i++) {
if (temp[i] != temp[tot - i - 1]) {
return 0;
}
}
return 1;
}
bool check(int x) {
int year = x / 10000;
int month = temp[3] * 10 + temp[2];
int day = temp[1] * 10 + temp[0];
if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) {
m[2] = 29;
} else {
m[2] = 28;
}
if (month > 12 || month <= 0) {
return 0;
} else {
if (day > m[month]) {
return 0;
}
}
return 1;
}
int main() {
int n;
scanf("%d", &n);
int ans1, ans2;
bool f = 0;
for (int i = n + 1; i <= 1e8; i++) {
if (hw(i)) {
//判断回文
if (check(i)) {
//判断合法
ans1 = i;
if (temp[0] == temp[2] && temp[2] == temp[5] && temp[5] == temp[7] &&
temp[1] == temp[3] && temp[3] == temp[4] && temp[4] == temp[6]) {
ans2 = i;
f = 1;
}
break;
}
}
}
if (!f) {
for (int i = ans1 + 1; i <= 1e8; i++) {
if (hw(i)) {
if (check(i)) {
if (temp[0] == temp[2] && temp[2] == temp[5] && temp[5] == temp[7] &&
temp[1] == temp[3] && temp[3] == temp[4] && temp[4] == temp[6]) {
ans2 = i;
break;
}
}
}
}
}
printf("%d\n%d\n", ans1, ans2);
return 0;
}
H:子串分值和
题面：
思路：
算单字母的贡献，然后记录一下上一个位置。
代码：
/*
* @Date: 2020-10-18 13:13:49
* @LastEditTime: 2020-10-18 15:26:45
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
char s[N];
ll vis[40];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += (i - vis[s[i] - 'a']) * (n - i + 1);
vis[s[i] - 'a'] = i;
}
cout << ans << endl;
return 0;
}
I：平面划分
思路：
这题比赛的时候没做（我考的Java b），赛后听到工作室的他们说感觉很难，最近补题发现，其实不是很难，就是没加入一条直线都要把情况考虑全，每加入一条边，和其余已经存在的边进行比较，如果平行则无需继续向下做，否则，求交点，判重点，可能存在多条边相交于同一个点，这就需要去重了，最后需要加 1，因为最后会形成一个闭合的区间，新生成的，之后累加，即每加入一条边所划分的区域都需加入答案中。
当然需要知道前置知识，直线分平面公式：直线分平面公式是指n条直线最多能把平面分成1+1+2+3+……+n个部分。
代码：
/*
* @Date: 2020-10-18 13:13:54
* @LastEditTime: 2020-11-24 15:00:14
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, inf = 1e9 + 10;
int n, ans, a[N], b[N];
#define Point pair<double, double>
#define x first
#define y second
const Point INF = Point{
inf, inf};
bool check(Point e1, Point e2) {
return (abs(e1.x - e2.x) <= 1e-2 && abs(e1.y - e2.y) <= 1e-2);
}
Point jd(int m, int n) {
//求交点
double x1 = a[m], x2 = a[n], y1 = b[m], y2 = b[n];
//平行则无交点
if (x1 == x2) {
return INF;
}
Point cp = Point{
};
cp.x = (y2 - y1) / (x1 - x2);
cp.y = (x1 * y2 - x2 * y1) / (x1 - x2);
return cp;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i], &b[i]);
}
ans = 2; //初始一条直线可以划分为两个平面
for (int i = 2; i <= n; ++i) {
vector<Point> v;
bool f = 0;
for (int j = 1; j < i; ++j) {
// i 为新加入的点，与之前的点做划分,判断直线 i, j是否存在交点
Point now = jd(i, j);
if (check(now, INF)) {
//直线 i, j不存在交点 continue
continue;
}
//直线i, j存在交点 去重
int len = v.size();
for (int k = 0; k < len; ++k) {
if (check(now, v[k])) {
f = 1;
}
}
if (!f) {
v.push_back(now);
}
}
ans += v.size() + 1;
}
printf("%d\n", ans);
return 0;
}
J：字串排序
题面：
思路：
代码：
串场了下面两个题目是第一场的最后两题2333333
I：整数拼接(第一场)
题面：
思路：
首先暴力跑一下， O ( n 2 ) O(n^2) O(n2)骗 30 30% 30分：
代码如下：
/*
* @Date: 2020-10-18 13:13:54
* @LastEditTime: 2020-11-18 18:10:48
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k;
vector<ll> num;
bool check(ll a, ll b) {
if (a % k == 0 && b % k == 0) {
//本身算的话也要加 但是只能加一次
return 1;
}
ll temp = b;
while (temp) {
temp /= 10;
a *= 10;
}
return (a + b) % k == 0;
}
int main() {
scanf("%lld%lld", &n, &k);
while (n--) {
ll x;
scanf("%lld", &x);
num.push_back(x);
}
n = num.size();
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && check(num[i], num[j])) {
ans++;
}
}
}
printf("%lld\n", ans);
return 0;
}
那么怎么优化呢？
我们能不能优化掉一个循环呢？
显然最外层肯定是去不掉的，因为至少要枚举到每个数，那么考虑如何优化掉内层循环，也就是考虑如何快速求出与 a [ i ] a[i] a[i]拼接起来为 k k k的倍数的数字的个数。
不难发现， a [ i ] a[i] a[i]和 a [ j ] a[j] a[j]拼起来等价于： a [ i ] ∗ 1 0 a [ j ] 的 长 度 + a [ j ] a[i]*10^{a[j]的长度}+a[j] a[i]∗10a[j]的长度+a[j]，学过数学的都知道， a [ j ] 的 长 度 = ⌊ l o g 10 a [ j ] ⌋ + 1 a[j]的长度=⌊log_{10}a[j]⌋+1 a[j]的长度=⌊log10a[j]⌋+1，那么与 a [ i ] a[i] a[i]拼接起来为 k k k的倍数的数字也就是： a [ i ] ∗ 1 0 ⌊ l o g 10 a [ j ] ⌋ + 1 + a [ j ] a[i]*10^{⌊log_{10}a[j]⌋+1}+a[j] a[i]∗10⌊log10a[j]⌋+1+a[j] 是 k 的倍数，展开就是： a [ i ] ∗ 1 0 ⌊ l o g 10 a [ j ] ⌋ + 1 % k + a [ j ] % k a[i]*10^{⌊log_{10}a[j]⌋+1}\%k+a[j]\%k a[i]∗10⌊log10a[j]⌋+1%k+a[j]%k 是 k 的倍数。由于 k ≤ 1 e 5 k\leq1e5 k≤1e5那么这些余数是可以用数组存下的，我们用 s u m [ i ] [ j ] sum[i][j] sum[i][j]表示：乘 1 0 i 10^i 10i后模 k k k 的结果为 j j j 的数的个数。
然后对于所有的 a [ i ] a[i] a[i]， a n s + = s u m [ ⌊ l o g 10 a [ i ] ⌋ + 1 ] [ ( k − a [ i ] % k ) % k ] ans+=sum[⌊log_{10}a[i]⌋+1][(k-a[i]\%k)\%k] ans+=sum[⌊log10a[i]⌋+1][(k−a[i]%k)%k] 即可。
要注意的是这样求出来的是所有 i < j i<j i<j也就是 a [ i ] a[i] a[i]放在 a [ j ] a[j] a[j]前面的情况，对于 a [ i ] a[i] a[i]放在 a [ j ] a[j] a[j]后面的情况，我们只需要把数组 a a a反转，然后再求一遍答案累加就好了！
代码：
/*
* @Date: 2020-10-18 13:13:54
* @LastEditTime: 2020-11-18 18:50:43
* @Author's blog: blog.nuoyanli.com
* @Description: Plum blossom from the bchter cold!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, k, ans, sum[11][N];
vector<ll> a;
ll log_10(ll x) {
ll len = 0;
while (x) {
x /= 10;
len++;
}
return len;
}
void solve() {
for (ll i = 0; i < n; i++) {
ans += sum[log_10(a[i])][(k - a[i] % k) % k];
for (ll j = 0, temp = 1; j < 11; j++) {
sum[j][temp * a[i] % k]++;
temp = temp * 10 % k;
}
}
}
int main() {
scanf("%lld%lld", &n, &k);
for (ll i = 0; i < n; i++) {
ll x;
scanf("%lld", &x);
a.push_back(x);
}
solve();
memset(sum, 0, sizeof(sum));
reverse(a.begin(), a.end());
solve();
printf("%lld\n", ans);
return 0;
}
J:网络分析(第一场)
题面：
转载：https://blog.csdn.net/nuoyanli/article/details/109138714
查看评论