@Dmaxiya
2020-08-24T23:48:42.000000Z
字数 4822
阅读 896
Hello_World
判断元音字母与奇数个数的和。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100;
char str[maxn];
char ch[10] = {'a', 'e', 'i', 'o', 'u', '1', '3', '5', '7', '9'};
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%s", str) != EOF) {
int ans = 0;
for(int i = 0; str[i]; ++i) {
for(int j = 0; j < 10; ++j) {
if(str[i] == ch[j]) {
++ans;
}
}
}
printf("%d\n", ans);
}
return 0;
}
对所有线段排序后,取相邻的三条线段,判断能否构成一个非退化三角形,用加法注意爆 int。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n;
int num[maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
for(int i = 0; i < n; ++i) {
scanf("%d", &num[i]);
}
sort(num, num + n);
bool flag = false;
for(int i = 2; i < n; ++i) {
if(num[i] - num[i - 1] < num[i - 2]) {
flag = true;
break;
}
}
if(flag) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
并查集,将并查集内节点数量记到根上。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 30000 + 100;
int n, m, num;
int x, y;
int fa[maxn];
int sum[maxn];
int Find(int x) {
return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
if(xx != yy) {
fa[xx] = yy;
sum[yy] += sum[xx];
}
}
void Init(int n) {
for(int i = 0; i < n; ++i) {
fa[i] = i;
sum[i] = 1;
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m), n != 0 || m != 0) {
Init(n);
for(int i = 0; i < m; ++i) {
scanf("%d", &num);
scanf("%d", &x);
for(int j = 1; j < num; ++j) {
scanf("%d", &y);
unit(x, y);
x = y;
}
}
printf("%d\n", sum[Find(0)]);
}
return 0;
}
将第一个序列的数字离散化为(映射到)对应的数字,对于没有出现的数字,映射到 ,然后对第二个序列的每个数字按照映射后的序列找最长递增子序列。对于已经 的同学,请再测试以下数据:
输入:
2
3 6 7
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
3 1 4
1 9
1 2 7 8 9
输出:
Case 1: 4
Case 2: 2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 300;
int T, n, p, q, cnt;
int *it;
int f[maxn * maxn];
int first[maxn * maxn], second[maxn * maxn];
int num[maxn * maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
scanf("%d", &T);
for(int cas = 1; cas <= T; ++cas) {
memset(f, 0, sizeof(f));
scanf("%d%d%d", &n, &p, &q);
for(int i = 1; i <= p + 1; ++i) {
scanf("%d", &first[i]);
f[first[i]] = i;
}
for(int i = 1; i <= q + 1; ++i) {
scanf("%d", &second[i]);
second[i] = f[second[i]];
}
cnt = 0;
for(int i = 1; i <= q + 1; ++i) {
if(second[i] != 0) {
it = upper_bound(num, num + cnt, second[i]);
if(it - num == cnt) {
num[cnt++] = second[i];
} else {
*it = second[i];
}
}
}
printf("Case %d: %d\n", cas, cnt);
}
return 0;
}
按照花费从大到小排序,花费大的先选择大于等于原起飞时间最小的时间,从 中删掉该时间,依次往下取。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 300000 + 100;
int n, k;
struct Node {
int cost;
int pos;
Node() {}
Node(int c, int p) {
cost = c;
pos = p;
}
};
bool operator<(const Node &a, const Node &b) {
return a.cost > b.cost;
}
vector<Node> vct;
set<int> st;
set<int>::iterator it;
int cost[maxn];
int ans[maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%d", &cost[i]);
vct.push_back(Node(cost[i], i));
}
sort(vct.begin(), vct.end());
for(int i = 1; i <= n; ++i) {
st.insert(i + k);
}
for(int i = 0; i < n; ++i) {
it = st.upper_bound(vct[i].pos);
int abs1 = INT_MAX;
if(it != st.end()) {
abs1 = abs(*it - vct[i].pos);
}
int abs2 = INT_MAX;
if(it != st.begin()) {
--it;
abs2 = abs(*it - vct[i].pos);
++it;
}
if(abs1 < abs2) {
ans[vct[i].pos] = *it;
st.erase(it);
} else {
--it;
ans[vct[i].pos] = *it;
st.erase(it);
}
}
LL sum = 0;
for(int i = 1; i <= n; ++i) {
sum += (LL)(abs(ans[i] - i)) * cost[i];
}
printf("%I64d\n", sum);
for(int i = 1; i <= n; ++i) {
if(i != 1) {
printf(" ");
}
printf("%d", ans[i]);
}
return 0;
}