携程算法方向（专业笔试一）编程题 100% 100% 87%

#include<vector>
#include<iostream>
#include<string>
using namespace std;

int main()
{
	string str;
	cin >> str;
	vector<int> res;
	vector<int> v(26, 0);
	for (int i = 0;i < str.length();i++)
	{
		int t = str[i] - 'a';
		v[t] = i;
	}
	for (int i = 0;i < str.length();i++)
	{
		int t = v[str[i]-'a'];
		int tmp = 0;
		for (int j = i + 1;j <= t;j++)
		{
			if (v[str[j] - 'a'] >= t) t = v[str[j] - 'a'];
		}
		res.push_back(t - i + 1);
		i = t;
	}
	for (int i = 0;i < res.size();i++)
	{
		cout << res[i];
		if (i != res.size() - 1) cout << ",";
	}
	cout << endl;
	return 0;
}

#include<vector>
#include<iostream>
#include<map>
#include<functional>
#include<iomanip>
using namespace std;

int main()
{
	int n;
	cin >> n;
	map<float, int> mp;
	int tp = 0, fp = 0, fn = 0, tn = 0;
	for (int i = 0;i < n;i++)
	{
		int a;
		float b;
		cin >> a >> b;
		mp.insert(make_pair(b, a));
		if (a == 1) fn++;
		else tn++;
	}
	float tpr = 0, fpr = 0, res = 0;
	for (map<float,int>::iterator it=mp.end();it!=mp.begin();)
	{
		it--;
		float t1 = tpr, t2 = fpr;
		if (it->second == 1)
		{
			tp++;
			fn--;
		}
		else {
			fp++;
			tn--;
		}
		tpr = (float)tp / (tp + fn);
		fpr = (float)fp / (fp + tn);
		res += (tpr + t1)*(fpr - t2) / 2;
	}
	res += (1 + tpr)*(1 - fpr) / 2;
	cout << setiosflags(ios::fixed) << setprecision(2) << res<< endl;
	return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int res = -1;
bool find(vector<int>& cur, int j)
{
	for (int i = 0;i < cur.size();i++)
		if (cur[i] == j) return true;
	return false;
}
void helper(vector<int>& cur, vector<vector<int>>& dp, int i,int n,int sum)
{
	if ((int)cur.size() == n&&i == n - 1)
	{
		if (res < 0 || sum < res) res=sum;
	}
	else if (i == n - 1) return;
	else
	{
		for (int j = 0;j < n;j++)
		{
			if (dp[i][j] != -1 && !find(cur,j))
			{
				cur.push_back(j);
				helper(cur, dp, j, n, sum + dp[i][j]);
				cur.pop_back();
			}
		}
	}
}
int main()
{
	int n;
	cin >> n;
	int m;
	cin >> m;
	vector<vector<int>> dp(n+1, vector<int>(n+1,-1));
	for (int i = 0;i < m;i++)
	{
		int a, b, t;
		cin >> a >> b >> t;
		dp[a][b] = dp[b][a] = t;
	}
	for (int i = 0;i <= n;i++)
	{
		dp[n][i] = dp[i][n] = dp[0][i];
	}
	vector<int> cur{ 0 };
	helper(cur,dp,0,n+1,0);
	cout << res << endl;
	return 0;
}