直接按题意用结构体排序即可,注意会卡精度,用 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;
}