第一题
题目: Takahashi’s Failure
题意:
给定n个数组成的数列，有k个询问，每个询问是一个序号，如果某一次询问的序号在原数列中是最大的数，输出 Yes 否则输出 No 。
输入格式
输入有三行，第一行有两个整数n和k。
第二行是n个整数。
第三行是k个整数。
输出格式
Yes 或 No
数据范围
1 ≤ K ≤ N ≤ 100
1 ≤ Ai ≤ 100
1 ≤ Bi ≤ N
输入样例：
5 3
6 8 10 7 10
2 3 4输出样例：
Yes思路:
- 输入时维护一个最大值，询问时看对应的数是否等于最大值就可以。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<cmath>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 150;
int m, n;
int a[N];
int main()
{
cin >> n >> m;
int mm=0;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
mm = max(mm, a[i]);
}
int flag = 0;
for (int i = 1; i <= m; ++i)
{
int x;
cin >> x;
if (a[x] == mm)flag = 1;
}
flag ? cout << "Yes" : cout << "No";
return 0;
}第二题-赛后补题
题目: Slot Strategy
题意:
给我们一个由n列字符组成的老虎机，每列字符数量固定为10且列内字符互不相同，保证字符只会在 ‘0’~‘9’ 中出现。n列从第0秒开始一起转动，从第0秒开始可以令某一列停止，问当老虎机停下时，第一行全部为同一个字符最少需要经过多少秒。
输入格式
第一行是一个整数n。
第2行到第n+1行均为10个字符组成的字符串。
输出格式
一个整数。
数据范围
2 ≤ N ≤ 100
输入样例：
5
0123456789
0123456789
0123456789
0123456789
0123456789输出样例：
40思路:
- 因为数据范围很小且只有10中字符，所以我们可以从
'0'到'9'依次遍历，找到代价最小的情况。 - 我们先看字符
'0'，因为我们每秒只能停下一列，同时老虎机每秒走一个字符，容易想到的是，当两个字符'0'在同一行时，为了让这两列停止时两个字符依然在同一行，那么至少需要等10秒。这样令字符'0'在老虎机停止时全部对齐的最小的花费，其实就是找到字符'0'在哪一行的数量最多，然后加上这一行到起始位置的距离就可以。 - 思路很简单，但是比赛时写的代码却怎么也不对，很奇怪也很懊恼。果然不够优雅的代码终将被淘汰。
AC代码
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 150;
int m, n;
int a[15][15];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
string s;
cin >> s;
for (int j = 0; j < 10; ++j)a[s[j]-'0'][j]++;
}
int ans = 0x3f3f3f3f;
for (int i = 0; i < 10; ++i)
{
int res = 0;
for (int j = 0; j < 10; ++j) res = max(res, (a[i][j] - 1) * 10 + j);
ans = min(ans, res);
}
cout << ans;
return 0;
}26.0/32.0的WA代码
不知道错在哪了，虽然确实有点丑，但是实在找不到错误了，32个样例对了26个，唉
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 150;
int m, n;
string s[N];
int a[15];//a[i]表示全不对齐的情况下，让某个数字对齐的花费
int c[15][15], d[15];//d[i]表示的是在同一位置出现次数最多的数字出现的位置
int mm;
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> s[i];
for (int u = 0; u < 10; ++u)
{
int b[15] = { 0 };
mm = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 10; ++j)
if (s[i][j] == u + '0')
if (b[j])
{
c[u][j]++;
if (c[u][j] > mm)
{
mm = c[u][j];
d[u] = j;
}
}
else
{
a[u] = max(a[u], j);
b[j] = 1;
}
}
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j)c[i][10] = max(c[i][10], c[i][j]);
int res = 0x3f3f3f3f;
for (int i = 0; i < 10; ++i) res = min(res, max(a[i] ,d[i] + c[i][10] * 10));
cout << res;
return 0;
}第三题-赛后补题
题目: Distinct Trio
题意:
给我们n个数组成的数列，然后问我们从中挑出三个数，且三个数各不相同的组合有多少种。
输出格式
第一行有1个整数n。
第二行有n个整数。
输出格式
一个整数。
数据范围
3 ≤ N ≤ 2×105
1 ≤ Ai ≤ 2×105
1 ≤ ai ≤ 104
输入样例：
15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9输出样例：
355思路:
- 首先我们可以先不看条件的限制，单看从n个数中取出3个数有多少种取法，很容易得到方案数为：C3n ，然后从中去掉有重复元素的组数就可以了。
- 因为这是个三元组，所以重复元素个数只能为2或3，分别减去对应的数量就可以了。
- 需要注意的是当重复元素个数是2时的算法，例如
aab这种组合，b的可选方案是n-cnt[a]，不要忘记乘。
代码:
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
using namespace std;
#define PII pair<int,int>
#define ll long long
const int N = 510;
int n, m, k;
int a[N], b[N], f[N][N];//a坐标，b每公里路程所花时间
//f[i][j]是从起点走到第i个路牌时，恰好选了j个路牌（可以包含第i个路牌）的方式所花时间的集合，属性取所有时间中的最小值
int main()
{
cin >> n >> m >> k;//n个路牌，m段路程，删除k个
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 1; i <= n; ++i)cin >> b[i];
a[n + 1] = m;//
memset(f,0x3f3f,sizeof f);
f[1][1] = 0;//走到第一个路牌并且选了一个路牌所花费时间为0
for (int i = 2; i <= n + 1; ++i)
{
for (int j = 1; j <= i; ++j)
for (int u = 1; u < i; ++u)
f[i][j] = min(f[i][j], f[u][j-1] + (a[i] - a[u]) * b[u]);
}
int res = 0x3f3f3f3f;
//我们将终点处视为一个路牌
for (int i = 0; i <= k; ++i)res = min(res, f[n + 1][n + 1 - i]);
cout << res << endl;
return 0;
}
