1.
平分物品
现在有n个物品,每一个物品都有一个价值,现在想将这些物品分给两个人,要求这两个人每一个人分到的物品的价值总和相同(个数可以不同,总价值相同即可),剩下的物品就需要扔掉,现在想知道最少需要扔多少价值的物品才能满足要求分给两个人。
要求:时间复杂度O(),空间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
int ans;
void dfs(vector<int> vec,int step,int a,int b,int sum){
if(sum>ans)return ;
if(step==vec.size()){
if(a==b&&sum<ans)ans=sum;
return ;
}
int t=vec[step];
dfs(vec,step+1,a+t,b,sum);
dfs(vec,step+1,a,b+t,sum);
dfs(vec,step+1,a,b,sum+t);
}
int main() {
int T;
cin>>T;
for(int _=0;_<T;++_){
int n;
cin>>n;
vector<int> vec;
int sum=0;
for(int i=0;i<n;++i){
int t;
cin>>t;
vec.emplace_back(t);
sum+=t;
}
ans=0x3f3f3f3f;
dfs(vec,0,0,0,0);
cout<<ans<<endl;
}
return 0;
}
2.
买票问题
现在有n个人排队买票,已知是早上8点开始卖票,这n个人买票有两种方式:
第一种是每一个人都可以单独去买自己的票,第 i 个人花费 a[i] 秒。
第二种是每一个人都可以选择和自己后面的人一起买票,第 i 个人和第 i+1 个人一共花费 b[i] 秒。
最后一个人只能和前面的人一起买票或单独买票。
由于卖票的地方想早些关门,所以他想知道他最早几点可以关门,请输出一个时间格式形如:08:00:40 am/pm
时间的数字要保持 2 位,若是上午结束,是 am ,下午结束是 pm
进阶:时间复杂度O(n) ,空间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
int dp[2005];
int main() {
int T;
cin>>T;
for(int _=0; _<T; ++_) {
int n;
cin>>n;
vector<int> a,b;
for(int i=0; i<n; ++i) {
int t;
cin>>t;
a.emplace_back(t);
}
for(int i=0; i<n-1; ++i) {
int t;
cin>>t;
b.emplace_back(t);
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
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]);
}
int h,m,s;
h=dp[n]/3600;
dp[n]%=3600;
m=dp[n]/60;
dp[n]%=60;
s=dp[n];
if(h>=2)cout<<8+h<<":";
else cout<<0<<8+h<<":";
if(m<10)cout<<0<<m<<":";
else cout<<m<<":";
if(s<10)cout<<0<<s<<" am"<<endl;
else cout<<s<<" am"<<endl;
}
return 0;
}
3.
小易爱回文
小易得到了一个仅包含大小写英文字符的字符串,该字符串可能不是回文串。(“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串,“asds”就不是回文串。)
小易可以在字符串尾部加入任意数量的任意字符,使其字符串变成回文串。
现在请你编写一个程序,程序要能计算出小易可以得到的最短回文串。
#include <bits/stdc++.h>
using namespace std;
bool csc(string s) {
for (int i = 0; i < s.length() / 2; ++i) {
if (s[i] != s[s.length() - i - 1])return false;
}
return true;
}
int main() {
string s;
cin >> s;
for (int i = 0; i < s.length(); ++i) {
if (csc(s.substr(i, s.length()))) {
string t = s.substr(0, i);
reverse(t.begin(), t.end());
cout << s << t << endl;
break;
}
}
return 0;
}
4.
学术认可
在一次聚会中,教授们被要求写下自己认可哪位教授的学术成果(也可以写自己,且可能出现重复)。已知,如果教授 A 认可教授 B ,且教授 B 认可教授 C,那么即可视为教授 A 也认可教授 C。现在我们想知道有多少对教授是两两互相认可的?
#include <bits/stdc++.h>
using namespace std;
int cnt;
int vec[400005],head[400005],jump[400005];
void add_path(int a,int b){
vec[++cnt]=b;jump[cnt]=head[a];head[a]=cnt;
}
int DFN[500005],LOW[500005];
int book[500005];
stack<int> sta;
int step;
long long ans;
void tarjan(int x){
DFN[x]=LOW[x]=++step;
sta.push(x);
book[x]=1;
for(int idx=head[x];idx;idx=jump[idx]){
int y=vec[idx];
if(!DFN[y]){
tarjan(y);
LOW[x]=min(LOW[x],LOW[y]);
}
else if(book[y])LOW[x]=min(LOW[x],DFN[y]);
}
if(DFN[x]==LOW[x]){
long long k=0;
while(!sta.empty()){
++k;
int t=sta.top();
sta.pop();
book[t]=0;
if(t==x)break;
}
ans+=k*(k-1)/2;
}
}
int main() {
int n,m;cin>>n>>m;
for(int i=0;i<m;++i){
int a,b;
cin>>a>>b;
add_path(a,b);
}
for(int i=1;i<=n;++i){
if(!DFN[i])tarjan(i);
}
cout<<ans<<endl;
return 0;
}