ABC306 CDE Solution - By LaDeX - 帖子

直接按题意用结构体排序即可，注意会卡精度，用 long double。

const LL N = 1e6 + 10;
LL n;
struct RealMan{
	LL a, b, k;
} man[N];
 
bool cmp(RealMan a, RealMan b){
	long double x = (long double)a.a / (a.a + a.b);
	long double y = (long double)b.a / (b.a + b.b);
	if (x != y)
		return x > y;
	return a.k < b.k;
}
 
int main(){
	Fcin;
	cin >> n;
	for (LL i = 1; i <= n; i ++){
		cin >> man[i].a >> man[i].b;
		man[i].k = i;
	}
	sort(man + 1, man + 1 + n, cmp);
	for (LL i = 1; i <= n; i ++)
		cout << man[i].k << " ";
	return 0;
}

爆搜，BFS。

const LL N = 510;
LL H, W;
char G[N][N];
 
bool vis[N][N];
 
LL dx[4] = {1, 0, -1, 0};
LL dy[4] = {0, 1, 0, -1};
map<char, char> nxt;
int main(){
	Fcin;
	nxt['s'] = 'n';
	nxt['n'] = 'u';
	nxt['u'] = 'k';
	nxt['k'] = 'e';
	nxt['e'] = 's';
	cin >> H >> W;
	for (LL i = 1; i <= H; i ++){
		for (LL j = 1; j <= W; j ++){
			cin >> G[i][j];
		}
	}
	if (G[1][1] != 's'){
		cout << "No";
		return 0;
	}
	queue<pair<LL, LL> > q;
	vis[1][1] = 1;
	q.push(mkp(1, 1));
	while (!q.empty()){
		LL x = q.front().first, y = q.front().second; q.pop();
		if (x == H && y == W){
			cout << "Yes";
			return 0;
		}
		for (LL k = 0; k < 4; k ++){
			LL nxtx = x + dx[k], nxty = y + dy[k];
			if (nxtx >= 1 && nxtx <= H && nxty >= 1 && nxty <= W && G[nxtx][nxty] == nxt[G[x][y]] && !vis[nxtx][nxty]){
				q.push(mkp(nxtx, nxty));
				vis[nxtx][nxty] = 1;
			}
		}
	}
	cout << "No";
	return 0;
}

可发现总共的状态只有种，先处理出三个数的状态对应的，再进行计数。

对字符串从前往后枚举。

用数组进行计数，表示长度为状态数为的个数，同理。

对于 str[i]：

若它为 M：说明它是第一个数字，加一。
若它为 E：说明它是第二个数字，枚举一个数字时的三种状态，再对进行统计。
若它为 X：枚举两个数字时的状态，直接统计进答案。

LL n, A[N], cnt1[N], cnt2[N];
string str;
map<LL, LL> sta;
LL Ans = 0;
int main(){
	Fcin;
	for (LL i = 0; i < 3; i ++){
		for (LL j = 0; j < 3; j ++){
			for (LL k = 0; k < 3; k ++){
				for (LL p = 0; p <= 4; p ++){
					if (i != p && j != p && k != p){
						sta[i * 100 + j * 10 + k] = p;
						break;
					}
				}
			}
		}
	}
 
 
	cin >> n;
 
	for (LL i = 1; i <= n; i ++)
		cin >> A[i];
	cin >> str;
	for (LL i = 0; i < (LL)str.size(); i ++){
		if (str[i] == 'M'){
			cnt1[A[i + 1]] ++;
		}
		else if (str[i] == 'E'){
			for (LL p = 0; p < 3; p ++){
				LL tmp = p * 10 + A[i + 1];
				cnt2[tmp] += cnt1[p];
			}
		}
		else{
			for (LL p = 0; p <= 30; p ++){
				LL tmp = p * 10 + A[i + 1];
				Ans += sta[tmp] * cnt2[p];
			}
		}
	}
	cout << Ans;
	return 0;
}