基于分治法的大整数乘法
/*
* @Author : Gehrychiang
* @LastEditTime : 2021-06-15 14:31:31
* @Website : www.yilantingfeng.site
* @E-mail : gehrychiang@aliyun.com
* @ProbTitle : 大整数乘法
*/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dMax = 1000;
struct calNode
{
char s[dMax + 5];
int length = 0; //s的有效数位长度
int powNum = 0; //10^powNum
calNode()
{
memset(s, 0, sizeof(s));
length = 0;
powNum = 0;
}
calNode(string in)
{
calNode();
for (int i = 0; i < in.length(); i++)
{
s[length++] = in[i];
}
standardize();
}
calNode(ll in)
{
calNode();
while (in)
{
s[length++] = char((in % 10) + '0');
in /= 10;
}
for (int i = 0; i < length / 2; i++)
{
swap(s[i], s[length - i - 1]);
}
standardize();
}
calNode operator+(const calNode &b) const
{
calNode ret = calNode();
ret.powNum = min(powNum, b.powNum);
int flag = 0;
for (int i = min(powNum, b.powNum); i < max(powNum + length, b.powNum + b.length) + 1; i++)
{
int left = ((i - powNum) >= 0 && i < length + powNum) ? s[length - 1 - i + powNum] - '0' : 0;
int right = ((i - b.powNum) >= 0 && i < b.length + b.powNum) ? b.s[b.length - 1 - i + b.powNum] - '0' : 0;
if (i == max(powNum + length, b.powNum + b.length) && flag == 0)
{
break;
}
ret.s[ret.length++] = char((left + right + flag) % 10 + '0');
flag = (left + right + flag) / 10;
}
for (int i = 0; i < ret.length / 2; i++)
{
swap(ret.s[i], ret.s[ret.length - i - 1]);
}
ret.standardize();
return ret;
}
void standardize()
{
while (length > 1 && s[length - 1] == '0')
{
length--;
powNum++;
}
}
bool read()
{
scanf("%s", s);
length = strlen(s);
bool preZero = false;
for (int i = 0; i < length; i++)
{
if (s[i] == '0' && !preZero) //前导0
{
return false;
}
if (s[i] < '0' || s[i] > '9') //不合法数字
{
return false;
}
if (s[i] != '0' && !preZero) //允许前导0
{
preZero = true;
}
}
standardize();
return true;
}
void write()
{
printf("%s", s);
if (powNum != 0)
{
for (int i = 0; i < powNum; i++)
{
printf("0");
}
}
printf("\n");
}
bool smallerThanInt()
{
if (length <= 9)
{
return true;
}
else
{
return false;
}
}
int toInt()
{
int ret = 0;
int tmp = 1;
for (int i = length - 1; i >= 0; i--)
{
ret += (s[i] - '0') * tmp;
tmp *= 10;
}
return ret;
}
pair<calNode, calNode> divide()
{
calNode highNum = calNode();
calNode lowNum = calNode();
for (int i = 0; i < length; i++)
{
if (i < length / 2)
{
highNum.s[highNum.length++] = s[i];
}
else
{
lowNum.s[lowNum.length++] = s[i];
}
highNum.powNum = powNum + ((length + 1) / 2);
lowNum.powNum = powNum;
}
return make_pair(highNum, lowNum);
}
};
calNode multiply(calNode calA, calNode calB)
{
if (calA.smallerThanInt() && calB.smallerThanInt())
{
calNode ret = calNode((ll)calA.toInt() * calB.toInt());
ret.powNum = calA.powNum + calB.powNum;
return ret;
}
else if (calB.smallerThanInt())
{
calNode calAHigh = calNode();
calNode calALow = calNode();
pair<calNode, calNode> res = calA.divide();
calAHigh = res.first;
calALow = res.second;
return multiply(calAHigh, calB) + multiply(calALow, calB);
}
else
{
calNode calBHigh = calNode();
calNode calBLow = calNode();
pair<calNode, calNode> res = calB.divide();
calBHigh = res.first;
calBLow = res.second;
return multiply(calA, calBHigh) + multiply(calA, calBLow);
}
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
calNode a = calNode();
a.read();
calNode b = calNode();
b.read();
multiply(a, b).write();
return 0;
}
基于动态规划的导弹拦截问题
/*
* @Author : Gehrychiang
* @LastEditTime : 2021-06-15 14:04:35
* @Website : www.yilantingfeng.site
* @E-mail : gehrychiang@aliyun.com
* @ProbTitle : 导弹拦截
*/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int ss[100005];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = 0;
while (cin >> a[n])
{
n++;
}
//打一个lis
ss[0] = a[n - 1];
int len = 1;
for (int i = n - 2; i >= 0; i--)
{
if (a[i] >= ss[len - 1])
{
ss[len++] = a[i];
}
else
{
ss[upper_bound(ss, ss + len, a[i]) - ss] = a[i];
}
}
cout << len << endl;
memset(ss, 0, sizeof(ss));
ss[0] = a[0];
len = 1;
for (int i = 1; i < n; i++)
{
if (a[i] > ss[len - 1])
{
ss[len++] = a[i];
}
else
{
ss[lower_bound(ss, ss + len, a[i]) - ss] = a[i];
}
}
cout << len << endl;
return 0;
}
利用贪心算法的唱片规划问题
/*
* @Author : Gehrychiang
* @LastEditTime : 2021-06-15 14:14:36
* @Website : www.yilantingfeng.site
* @E-mail : gehrychiang@aliyun.com
* @ProbTitle : 歌曲磁带问题
*/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000;
int a[N + 5];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
//考虑a[i]与a[i+1]的顺序关系
//之前与之后的所有曲子的加载时间不会因为a[i]与a[i+1]的顺序关系产生改变，故只需考察a[i]与a[i+1]的顺序何者更优
//如a[i]在前a[i+1]在后 则a[i]的加载时间为T,a[i+1]的加载时间为T+a[i]
//如a[i+1]在前a[i]在后 则a[i]的加载时间为T+a[i+1],a[i+1]的加载时间为T
//显然要是总和最小，即使歌曲按时长从小大到大排序即可
sort(a, a + n);
for (int i = 0; i < n; i++)
{
printf("%d", a[i]);
}
return 0;
}
基于回溯剪枝策略的图着色问题
/*
* @Author : Gehrychiang
* @LastEditTime : 2021-06-15 14:27:15
* @Website : www.yilantingfeng.site
* @E-mail : gehrychiang@aliyun.com
* @ProbTitle : 图的m着色问题
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 4;
int gra[N + 5][N + 5];
int ans[N + 5];
int n, m, flag;
bool chk(int curLevel, int curColor)
{
for (int i = 1; i < curLevel; i++)
{
//check i and curLev conflict
if (gra[curLevel][i] == 1 && ans[i] == curColor)
{
return false;
}
}
return true;
}
void dfs(int curLevel)
{
if (curLevel == n + 1)
{
if (flag == 0)
{
cout << "Vertices: ";
for (int i = 1; i <= n; i++)
{
cout << i << " ";
}
flag++;
}
cout << "Color: ";
for (int i = 1; i <= n; i++)
{
cout << ans[i] << " ";
}
cout << endl;
return;
}
for (int i = 1; i <= m; i++)
{
if (chk(curLevel, i))
{
ans[curLevel] = i;
dfs(curLevel + 1);
ans[curLevel] = 0;
}
}
}
int main()
{
cin >> n;
int k;
cin >> k;
for (int i = 0; i < k; i++)
{
int a, b;
cin >> a >> b;
gra[a][b] = 1;
gra[b][a] = 1;
}
cin >> m;
dfs(1);
if (flag == 0)
{
cout << "No solution";
}
else
{
cout << "Total count is " + flag;
}
return 0;
}
/*
5
9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
4
*/
