最近在去听某个做软件开发的团队介绍平时的工作流程的时候，有讲到一个做思维导图的软件，是叫做xmind。我打算最近学习使用这个软件。看起来，感觉做的很漂亮，这个软件。
信息学奥赛一本通1638：五指山
url: https://ybt.ssoier.cn/problem_show.php?pid=1638
tag:
裴蜀定理，拓展欧几里得算法，数论
思路：
根据题意可以得出，y - x = b d mod n ⇒ b d - a n = y - x。所以可以先求出n与d的最大公约数，如果y - x 不能整除，说明不能到达，如果可以整除再求最小的b。用拓展欧几里得算法可以求出 x n + y d = (n,d) 的一组解，然后令该式两边同乘 （y - x）/ （n，d）可以将该式变为b d - a * n = y - x。最后求最小的d就是让其取模n / gcd的正余数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
int T;
cin >> T;
while (T --)
{
LL n, d, x, y, a, b;
scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
LL gcd = exgcd(n, d, a, b);
if ((y - x) % gcd) cout << "Impossible\n";
else
{
b *= (y - x) / gcd;
n /= gcd;
printf("%lld\n", (b % n + n) % n);
}
}
return 0;
}蓝桥杯2018初赛 明码
url: http://oj.ecustacm.cn/problem.php?id=1369
tag:
模拟
思路：
求字节的二进制表示，其实就是求每个数的补码。对于正数来说，补码就是原码。对于负数来说，先是对原码求反码然后再加1.对于-128来说比较特殊，补码是10000000，通过正常的求法求不出，所以需要特殊判断。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int num[10];
void resoult(int a)
{
int j = 8;
while(a)
{
num[j --] = a % 2;
a /= 2;
}
}
void inverse()
{
for (int i = 2; i <= 8; i ++)
{
if (num[i] == 0) num[i] = 1;
else num[i] = 0;
}
num[8] += 1;
for (int i = 8; i >= 3; i --)
{
num[i - 1] += num[i] / 2;
num[i] %= 2;
}
}
void binary(int a)
{
if (a == -128)
{
cout << "1 " << endl;
return;
}
memset(num, 0, sizeof num);
if (a >= 0)
{
num[1] = 0;
resoult(a);
}
else
{
num[1] = 1;
resoult(abs(a));
inverse();
}
}
void print()
{
for (int i = 1; i <= 8; i ++)
{
if (num[i]) cout << 1;
else cout << ' ';
}
}
int main()
{
for (int i = 0; i < 10; i ++)
{
for (int j = 0; j < 16; j ++)
{
int a, b;
cin >> a >> b;
binary(a);
print();
binary(b);
print();
cout << endl;
}
cout << endl;
}
return 0;
}简洁版：
#include <iostream>
#include<cstring>
using namespace std;
int num[10];
void print()
{
for(int i=1;i<=8;i++) printf("%c",num[i]==1?"1":" ");
}
int main()
{
int a,b;
for(int i=1;i<=10;i++)
{
for(int j=1;j<=16;j++)
{
cin>>a>>b;
memset(num,0,sizeof(num ));
for(int k =8;k>=1;i--) num[k]&=a,a>>=1;
print();
memset(num,0,sizeof(num ));
for(int k =8;k>=1;k--) num[k]&=b,b>>=1;
print();
cout<<endl;
}
cout<<endl;
}
return 0;
}结果：
1
1
1 1
111111111111
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1 1
1 1 1
1 1111
11
1 1
1 1
1 1 1 1
1111111 111111
1 1 1 1
1 11 1
1 1 1
1 1 1 1
111111 11 1
1 1 1 1
1 1 1
1 1 1
1 1 1
111111 1
1 1 1 1
1
1
1
1
1 1
111111111111
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1 1
1 1 1
1 1111
11
1
1 1
1
11 1
11
1 1 1
1111111
1 1
1 1 1
1 1
1 1
111 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 111
1 1 1
1
11
1
1
111111111111111
1
1 1
11111111
1 1
1 1
1 1
1 1
1 1
1 1
1 1 1
1 1
1 1
1 1 1 1
11111 111111
1 1 1 1
1 1 1
1
11111111111
1
111111111111111
1
1 1
11111111111
1 1
1 1
1 1
1
1
11111111111
1
1
1
1 1
111111111111111
1
1
1
1
1
1
1
1 1
1
1
1
1111111
1 1
11 1
1 1 11
1 1 1
1 1
1
11 1
11
111 1111111
1 1
11 1
1 1 1
1 111
1
111
111
1
1
1
1 1 1
1 1 1
1 1 11
1 1 1
1 1 1
1 1 1
1 1
1 1
1
1
1
11
111
1111111
11 11
11 11
111 11
111
111
11
1
11
1
1111
11
1
答案：
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
printf("%.0f", pow(9, 9));
return 0;
}洛谷 P4095 HEOI2013 Eden 的新背包问题
url: https://www.luogu.com.cn/problem/P4095
tag:
动态规划，背包DP，进制，枚举
思路：
多重背包问题为基础，做两次01背包，前一次后一次，之后对于每次询问的id就跳过那个id求可能的最大值。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
struct node{
int id;LL s;
}w[N], v[N];
LL f1[N][1010], f2[N][1010];
int idx, m, n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int cw, cv, c;
cin >> cw >> cv >> c;
int now = 1;
while (now <= c)
{
w[++idx].s = cw * now, v[idx].s = cv * now;
w[idx].id = i, v[idx].id = i;
c -= now, now *= 2;
}
if(c) {
w[++idx].s = cw * c, v[idx].s = cv * c;
w[idx].id = i, v[idx].id = i;
}
}
cin >> m;
n = idx;
for (int i = 1; i <= n; i ++)
{
for (int j = 0; j <= 1000; j ++) f1[i][j] = f1[i - 1][j];
for (int j = 1000; j >= w[i].s; j --)
{
f1[i][j] = max(f1[i][j], f1[i - 1][j - w[i].s] + v[i].s);
}
}
for (int i = n; i >= 1; i --)
{
for (int j = 0; j <= 1000; j ++) f2[i][j] = f2[i + 1][j];
for (int j = 1000; j >= w[i].s; j --)
{
f2[i][j] = max(f2[i][j], f2[i + 1][j - w[i].s] + v[i].s);
}
}
for (int k = 1; k <= m; k ++)
{
int cn, V;
cin >> cn >> V;
cn ++;
LL ans = 0;
int l = 0, r = 0;
while (w[l + 1].id < cn && l < n) ++ l;
r = l;
while (w[r + 1].id <= cn && r < n) ++ r;
for (int j = 0; j <= V; j++)
{
ans = max(ans, f1[l][j] + f2[r + 1][V - j]);
}
cout << ans << endl;
}
return 0;
}蓝桥杯2018初赛 乘积尾零
url: http://oj.ecustacm.cn/problem.php?id=1361
tag:
数学
思路：
计算末尾零可以求每个因子中有多少对因子5和因子2，因为2 * 5 = 10，又因为2出现的次数会比5多，因为只要是偶数的情况就会出现因子2.所以只要计算这100个数中，每个数中因子5的个数，然后累加最后输出即可。
对于求阶乘来说，如果是某个数的阶乘，求这个数除以5，25，125……5k之后累加。例如100除以5之后等于20，那么对于1到20来说每个数乘以5后都会变成一个贡献5因子的数，除以25之后等于4说明1到4中每个数乘25都可以变成一个贡献25因子的数，而25 = 5 5，则是在原来贡献了5因子基础上多贡献一个5，为了避免重复，以及避免漏算，只需要将4 加上 20，即为答案。说明对于100！（1 2 3 …… * 100）来说，一共可以贡献出24个因子5，就是有24个末尾0.这种求阶乘末尾0的方式实际上和本题有出路。
代码：
// 乘积尾零
#include <iostream>
using namespace std;
int main()
{
int n = 10;
int cnt = 0;
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < n; j ++)
{
int a;
cin >> a;
while (a && a % 5 == 0)
{
if (a % 5 == 0)
{
a /= 5;
cnt ++;
}
}
}
}
cout << cnt << endl;
return 0;
}答案：
#include <iostream>
using namespace std;
int main()
{
cout << 31 << endl;
return 0;
}