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;
}