哇！刚刚突然发现我的那篇扩展欧几里得达到了500+的阅读量，开森森~ 看起来努力就是有回报的嘛！用心写的文章和不用心写的文章相信广大程序员萌都一眼看得出来撒~
快乐！你们的关注和点赞是我最大的动力嗷！┗|｀O′|┛
好了，闲话不多说~ 正片开始！
A.跑步训练
这个题个人不建议写程序，直接手算就好了，但是要注意的是，每一轮-600然后+300，就相当于-300，但是！一定要记得这-300的时间是120s，而不是60s，手算党千万要小心！检查检查再检查，这个分丢得相当不值得。
结果：3880
B.纪念日
日期题目年年有，一点都不稀奇~关键在于快速A，听说C++算日期很麻烦，谁要咱也不是Java选手呢，害，鱼和熊掌⑧可兼得嘛，祭上大杀器——计算器！
结果：52038720
C.合并检测
这个题，数学功底相当强 懒得写程序的我，直接手算！
结果：10
D.REPEAT程序
先说好啊，这玩意不是按照样例算的，实战的时候人家是给了数据的，是一个txt文件，那玩意长的，保证你放弃硬写出这些个循环的想法。
我重新梳理了一遍带佬的思路，然后附上了详细注释
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int a[N], b[N];//a用来存放当前行层的缩进格数，b用来存放当前层的循环次数
int main(int argc, char const *argv[])
{
int pos = 0, p = 0, w = 1, ans = 0;//pos存第几层循环，p存每行前面的空格数，w是总的循环数，ans存结果
a[0] = -1, b[0] = 1;
freopen("prog.txt","r",stdin);//就是将标准输入流重定向到这个txt文件中，
//从文件中获取输入
gets(str);//首行的“A=0”不需要
while(gets(str)){
int len = strlen(str);
p = 0;//每次p都要归零啊
while(str[p] == ' ') p++;
while(p <= a[pos]) w /= b[pos--];//说明退出了最近的那一层
if(str[len - 1] == ':'){
//是REPEAT语句
int k = str[len - 2] - '0';//当前循环重复的次数
w *= k;
pos ++;//来到新的一层
a[pos] = p, b[pos] = k;
}else {
//不是循环语句
int k = str[len - 1] - '0';//要加上的数
ans += w * k;
}
}
cout<<ans<<endl;
return 0;
}
结果：241830
E.矩阵
这题很容易让人想起我们之前做过的那一道DP+打表的题目，有人说DP本质就是打表，我觉得可以这么说，起码以目前我不太高深的实力，可以这么理解。
首先我们自己列出小数据表格，然后根据列出的表格找规律并且写代码。
这样的填表莫名让我想起了小学课本上的那个找国王要米的人，在棋盘上堆米直到堆成山。。
其实自己在草稿纸上画一画很容易发现规律——也就是我们要的递推式。
代码就很好写了~~
#include <bits/stdc++.h>
using namespace std;
const int N = 2025;
int dp[N][N];
int main(int argc, char const *argv[])
{
dp[1][1] = 1;//1必然在首格
for (int i = 2; i <= 2020; ++i)
{
for (int j = 1; j <= i; ++j)//在第一行放j个
{
dp[i][j] += dp[i - 1][j - 1];
if(2 * j >= i) dp[i][j] += dp[i - 1][j];//如果第一行的数目>=第二行，那么就还可以加上上方那个
dp[i][j] %= 2020;//可能数很大
}
}
printf("%d\n", dp[2020][1010]);//注意是第1010列
return 0;
}
F.整除序列
苦等了这么久终于来了一道签到题！/(ㄒoㄒ)/~~
蓝桥是不是变🚹了呜呜呜
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main(int argc, char const *argv[])
{
scanf("%ld", &n);
while(n >= 1){
printf("%ld", n);
if(n != 1) printf(" ");
else printf("\n");
n = (int) n >> 1;
}
return 0;
}
G.解码
签到×2！果然不会让咱们太难看哈~
我呵呵呵我又不审题！我把字母l看成了1，哭晕。。我难看了，对八七！我反省！我以后一定好好审题！
// #include <bits/stdc++.h>
// using namespace std;
// const int MAXN = 110;
// char str[MAXN];
// int main(int argc, char const *argv[])
// {
// scanf("%s",str);
// int len = strlen(str);
// for (int i = 0; i < len; )
// {
// char ch;
// int num = 0, digit = 0;
// if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')){
// ch = str[i];
// }
// while(str[++i] >= '0' && str[i] <= '9'){
// digit += str[i] - '0';
// num += digit;
// digit *= 10;
// }
// for (int j = 0; j < num; ++j) putchar(ch);
// }
// printf("\n");
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
char s[MAXN];
int main() {
scanf("%s", s);
for (int i = 0; s[i]; i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
putchar(s[i]);
} else if (s[i] >= 'A' && s[i] <= 'Z') {
putchar(s[i]);
} else {
int k = s[i] - '0' - 1;
while (k--) putchar(s[i - 1]);
}
}
puts("");
return 0;
}
H.走方格
虽然兴奋，切记还是不能大意~
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int dp[N][N];
int main(int argc, char const *argv[])
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if(i == 1 && j == 1){
//只需要一个1
dp[i][j] = 1;
continue;
}
if(i & 1 || j & 1) //只要有一个不是2的倍数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
printf("%d\n", dp[n][m]);
return 0;
}
I.整数拼接
这题，确实没思路，要是暴力肯定炸，于是瞪着带佬没有注释的代码看了一个小时，终于。。懂了，现在给亲爱的读者朋友们奉上注释~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int cnt[10][N];
int a[N];
int ans;
int get_length(int x){
//得到一个整数的长度（利用传形参不变实际值）
int length = 0;
while(x){
x /= 10;
length++;
}
return length;
}
int main(int argc, char const *argv[])
{
int n, m;
scanf("%d%d", &n, &m);
int ans = 0;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
{
int len = get_length(a[i]);
int left = (m - a[i] % m) % m; //这个left和a[i]%m是关于m互余的
ans += cnt[len][left];//看看前面有没有契合的拼接对象
int p = 10;//十位起步
for (int j = 1; j <= 9; ++j)
{
cnt[j][1ll * p * a[i] % m] ++;//这个数的另一半是j位，这个数就是(j+1)位，不然无法拼接
p *= 10;
}
}
memset(cnt, 0, sizeof(cnt));//记得清空
for (int i = n; i >= 1; --i)//反着跑一遍
{
int len = get_length(a[i]);
int left = (m - a[i] % m) % m;
ans += cnt[len][left];//看看后面有没有契合的拼接对象
int p = 10;//十位起步
for (int j = 1; j <= 9; ++j)
{
cnt[j][1ll * p * a[i] % m] ++;//这个数的另一半是j位，这个数就是(j+1)位，不然无法拼接
p *= 10;
}
}
printf("%d\n", ans);
return 0;
}
为什么(m-x%m)和x%m是契合的呢？
我们来研究一个案例就清楚了——
45为什么可以整除3？
因为40%3=1（这一部分余三多一），而3-5%3也=1（这一部分余三少一），刚刚好，一拍即合！加起来就可以整除3。这也就是ans += cnt[len][(m-x%m)%m]的理由。
J.网络分析
最后一题拖了三天了QWQ，效率太低了（废物哇的一声哭出来）
这题，不是裸的并查集，注意标黄部分。
每次新的结点加入之后，之前集合中的点加上的值是不能算在新人头上的，洗澡的时候想到了，每次新人加入的时候，就问问自己的父亲现在手上有多少值，然后自己的结点就要减去前人积累（也就是加入的时候父亲的值）的值，最后在输出的时候检查是否是根结点，如果不是就要加上父亲的值，等于新人加入之后的值之和。
本来想的是每个点都标记前人的值，后来借鉴了带佬的思路，每次在merge的时候减去根结点的值，然后再在最后加回来，就是加入之后的值，还是觉得这样比较简单。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;
int father[N];
ll ans[N];
void init(int x){
for (int i = 1; i <= x; ++i)
father[i] = i;
}
int find(int x){
int a = x;
while(x != father[x]) x = father[x];//x抵达根节点
while(a != father[a]){
//路径压缩
father[a] = x;
a = father[a];
}
return x;
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x != y) {
father[x] = y; //x的粑粑是y
ans[x] -= ans[y]; //之前的别人的就要减掉，只算加入之后的【关键一步】
}
}
int main(int argc, char const *argv[])
{
int n, m, flag;
scanf("%d%d", &n, &m);
init(n);
while(m--){
scanf("%d", &flag);
if(flag == 1){
int a, b; scanf("%d%d",&a, &b);
merge(a, b);
}else {
int p, t; scanf("%d%d",&p, &t);
int fa = find(p);
ans[fa] += t;
}
}
for (int i = 1; i <= n; ++i)
{
ll res = ans[i];
int fa = find(i);
if(i != fa) res += ans[fa];
printf("%lld%c", res, " \n"[i == n]);//最后输出换行的方法，学习！
}
return 0;
}
特别说明
本blog代码不是标程，欢迎大家提出不同的思路还有纠错呀~
最后，卑微安安在线求点赞、收藏、关注三连~
转载：https://blog.csdn.net/weixin_43905108/article/details/107608355