|
[编程题]平分物品
现在有n个物品，每一个物品都有一个价值，现在想将这些物品分给两个人，要求这两个人每一个人分到的物品的价值总和相同（个数可以不同，总价值相同即可），剩下的物品就需要扔掉，现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。
思路：dfs遍历所有的情况，注意剪枝，如果丢弃的物品超过了已知的最好情况则剪枝。
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<memory.h>
#include<cstring>
#include<stdlib.h>
#include<sys/types.h>
#include<set>
#include<stack>
#include<map>
#include<unordered_map>
using namespace std;
bool complare(int a, int b)
{
return a > b;
}
int a = 0;
int b = 0;
int min_throw = 0x7FFFFFFF;
void push_value(vector<int> v,int num,int throw_value)
{
if (throw_value > min_throw)
{
return;
}
if (num == v.size())
{
if (throw_value < min_throw && a==b)
{
min_throw = throw_value;
return;
}
}
if (num < v.size())
{
b += v[num];
push_value(v, num + 1, throw_value);
b -= v[num];
push_value(v, num + 1, throw_value+ v[num]);
a += v[num];
push_value(v, num + 1, throw_value);
a -= v[num];
}
}
int main()
{
int t, n;
cin >> t;
vector<int> v;
while(t--)
{
a = 0;
b = 0;
min_throw = 0x7FFFFFFF;
v.clear();
cin >> n;
int tmp = 0;
while (n--)
{
cin >> tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end(), complare);
push_value(v, 0,0);
cout << min_throw << '\n';
}
return 0;
}
[编程题]买票问题
现在有n个人排队买票，已知是早上8点开始卖票，这n个人买票有两种方式：
第一种是每一个人都可以单独去买自己的票，第 i 个人花费 a[i] 秒。
第二种是每一个人都可以选择和自己后面的人一起买票，第 i 个人和第 i+1 个人一共花费 b[i] 秒。
最后一个人只能和前面的人一起买票或单独买票。
由于卖票的地方想早些关门，所以他想知道他最早几点可以关门，请输出一个时间格式形如：08:00:40 am/pm
时间的数字要保持 2 位，若是上午结束，是 am ，下午结束是 pm。
思路：动态规划，dp[i]表示前i个人的最快时间，转移方程dp[i]=min(dp[i-1]+a[i-1],dp[i-2]+b[i-2])，此题的一个小坑是输出时间的格式。
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<memory.h>
#include<cstring>
#include<stdlib.h>
#include<sys/types.h>
#include<set>
#include<stack>
#include<map>
#include<unordered_map>
using namespace std;
bool complare(int a, int b)
{
return a > b;
}
int main()
{
int t, n;
cin >> t;
while (t--)
{
vector<int> a;
vector<int> b;
bool find;
int use_second = 0;
cin >> n;
vector<int> dp(n + 1, 0);
int tmp = n;
int tmp_num;
while (tmp--)
{
cin >> tmp_num;
a.push_back(tmp_num);
}
tmp = n - 1;
while (tmp--)
{
cin >> tmp_num;
b.push_back(tmp_num);
}
tmp = n;
int abs_t;
int min_abs = 0;
find = false;
int this_i = -1;
int ans_second;
if (n == 1)
{
use_second = a[0];
}
else
{
dp[1] = a[0];
for (int i = 2; i <= n; i++)
{
dp[i] = min(dp[i - 1] + a[i - 1], dp[i - 2] + b[i - 2]);
}
use_second = dp[n];
}
ans_second = use_second % 60;
use_second = (use_second - use_second % 60) / 60;
int ans_minute = use_second % 60;
int ans_clock = 8 + (use_second - use_second % 60) / 60;
if (ans_clock%12 < 10&& ans_clock<12)
{
cout << '0' << ans_clock << ':';
}
else
{
cout << ans_clock << ':';
}
if (ans_minute < 10)
{
cout << '0' << ans_minute << ':';
}
else
{
cout << ans_minute << ':';
}
if (ans_second < 10)
{
cout << '0' << ans_second;
}
else
{
cout << ans_second;
}
if (ans_clock <= 12 )
{
cout << " am" << '\n';
}
else
{
cout << " pm" << '\n';
}
}
return 0;
}
[编程题]小易爱回文
小易得到了一个仅包含大小写英文字符的字符串，该字符串可能不是回文串。（“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串，“asds”就不是回文串。）
小易可以在字符串尾部加入任意数量的任意字符，使其字符串变成回文串。
现在请你编写一个程序，程序要能计算出小易可以得到的最短回文串。
思路：依次判断string.substr(i,string.size())是否是回文字段，在末尾加上相对应的字符，其中用reverse在逆序数组可以快速判断是否为回文。//我没用。。
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<memory.h>
#include<cstring>
#include<stdlib.h>
#include<sys/types.h>
#include<set>
#include<stack>
#include<map>
#include<unordered_map>
using namespace std;
bool ishui(string s)
{
int mid;
mid = s.size() / 2;
bool ishui = false;
if (s.size() % 2 == 1)
{
for (int i = 1; i <= mid; i++)
{
if (s[mid - i] != s[mid + i])
{
return false;
}
}
return true;
}
else
{
for (int i = 1; i <= mid; i++)
{
if (s[mid - i] != s[mid + i - 1])
{
return false;
}
}
return true;
}
return ishui;
}
int main()
{
string s;
cin >> s;
int i;
int mid = s.size() / 2;
bool ishuim = false;
for (i = 0; i < s.size(); i++)
{
if (ishui(s.substr(i, s.size() - i)))
{
break;
}
}
while (i - 1 >= 0)
{
s += s[i - 1];
--i;
}
cout << s << '\n';
return 0;
}
[编程题]学术认可
在一次聚会中，教授们被要求写下自己认可哪位教授的学术成果（也可以写自己，且可能出现重复）。已知，如果教授 A 认可教授 B ，且教授 B 认可教授 C，那么即可视为教授 A 也认可教授 C。现在我们想知道有多少对教授是两两互相认可的？
思路：采用tarjan算法来进行连通图的计算，每个连通图计算n*(n-1)/2。
#include <vector>
#include <iostream>
using namespace std;
void tarjan(vector<vector<int>>& G, vector<int>& low, vector<int>& dfn, vector<bool>& visited, vector<int>& st, int v, int& times, int& ans)
{
st.push_back(v);
visited[v] = true;
dfn[v] = times;
low[v] = times;
++times;
for (auto i : G[v])
{
if (dfn[i] == -1)
{
tarjan(G, low, dfn, visited, st, i, times, ans);
low[v] = min(low[i], low[v]);
}
else if (visited[i])
{
low[v] = min(low[i], low[v]);
}
}
if (dfn[v] == low[v])
{
int cnt = 0;
int tmp;
do {
tmp = st.back();
st.pop_back();
visited[tmp] = false;
++cnt;
} while (tmp != v);
ans += cnt * (cnt - 1) / 2;
}
}
int main()
{
int ans = 0;
int n, m;
cin >> n >> m;
vector<int> low(n + 1);
vector<int> dfn(n + 1, -1);
vector<int> st;
vector<vector<int>> G(n + 1);
vector<bool> visited(n + 1, false);
int from, to;
while (m--)
{
cin >> from >> to;
G[from].push_back(to);
}
int times = 0;
for (int i = 1; i <= n; i++)
{
if (dfn[i] == -1)
{
tarjan(G, low, dfn, visited, st, i, times, ans);
}
}
cout << ans << endl;
return 0;
}
|