我TM怎么这么垃圾，我要是有技术，会是这个吊样？
不过元气骑士要更新了，期待。
第一题
题目: Problem - 1625A - Codeforces
题意:
给n个数字，让我们找到一个转化为二进制后恰好为L位的数字y，使得n个数字与求得的数字y误差之和最小。规定两个数字的误差等于两个数字二进制中不同位的数量。例如：1011和1111的误差为1，因为只有1位不同。
输入格式
输入有多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是两个整数n和L。
每个样例第二行是n个整数，表示给定的n个数字。
输出格式
一个十进制整数y。
样例数 1 <= t <=104 ，其余均小于100。
输出格式
输出一个整数。
数据范围
1 ≤ t ≤ 100
1 ≤ n ≤ 100, 1 ≤ ℓ ≤ 30
0 ≤ xi ≤2ℓ−1
0 ≤ y ≤ 2ℓ−1
输入样例：
7
3 5
18 9 21
3 5
18 18 18
1 1
1
5 30
1 2 3 4 5
6 10
99 35 85 46 78 55
2 1
0 1
8 8
5 16 42 15 83 65 78 42输出样例：
17
18
1
1
39
0
2思路:
- 其实这个题难点在于读懂题意，
原文里鬼扯半天火星、陌生语言、科学家、石板等等，看得我云里雾里的，我到底是来做题的还是来看小说的。 - 题目规定误差就是两个数字二进制下的不同位数，那么显然要用到位操作，题目要求我们找到一个数字y使得y与所有数字的误差最小，那么我们可以从这里入手，建立一个数组表示所有数字在某一位上1的数量，例如a[1]，就表示所有数字二进制表示下，第一位有多少个1。因为具体到某一位要么是1要么是0，那么所谓的误差也就是0和1的数量区别，记录下所有数字的每一位后。遍历数组，如果某个位上1的数量大于n/2，那么我们就加上这一位的权重，求和就是答案。
- 务必看清题目给的数据范围，因为看错n和L的范围导致一直用40的数组在存数，结果痛wrong两次！
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
const int N = 150;
int n,l;
int a[N],w[N];
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n >> l;//n个数，l位
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 1; i <= l; ++i)w[i] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; (1 << j) <= a[i]; ++j)
if (((1 << j) & a[i]))
w[j + 1]++;
}
int res = 0;
for (int i = 1,k=1; i <= l; ++i,k*=2)
if (w[i] > n - w[i])res += k;
cout << res << endl;;
}
return 0;
}
第二题
题目: Problem - 1625B - Codeforces
题意:
在一个数列中找两个长度相同的子数列，这两个子数列必须有相同的成员，相同成员指在两个子数列同一位置有相同的数字。两个子数列的起点必须不同。
输入格式
数据包含多个样例，第一行是一个整数t，表示有t个样例。
每个样例第一行是一个整数n。
每个样例第二行是n个正整数，表示整个数列。
输出格式
一个整数，表示子数列的最大长度。如果找不到则输出-1。
数据范围
1 ≤ t ≤ 100
2 ≤ n ≤ 150000
1 ≤ ai ≤ 150000
输入样例：
4
7
3 1 5 2 1 3 4
6
1 1 1 1 1 1
6
1 4 2 8 5 7
2
15 15输出样例：
4
5
-1
1思路:
- 首先明确一点，题目要求两个子数列必须有相同成员，但是没有要求相同成员的长度，易得相同成员长度为1时得到的两个子数列长度一定是最长的。
- 那么问题就转化为找到两个相同的数字，然后围绕两个相同数字生成两个长度相同，起点不同的数列。什么时候两个子数列长度最大呢？答案是当两个相同字符的距离最近时。
- 为什么？我们先来看如何根据两个数字生成子数列，子数列的长度就等于第一个数字到起点的距离加第二个数字到末尾的距离。因为第二个数字到起点的距离一定小于第一个到起点的距离，而第一个数字到结尾的距离一定小于第二个到结尾的距离。
- 那么就可以得到答案，当两个相同字符，距离最近时，得到的一定是最优解。
代码:
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
using namespace std;
#define ll long long
const int N = 150010;
int n;
int a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; ++i)cin >> a[i];
unordered_map<int, int>p;
int flag = 0,res=0x3f3f3f3f;
for (int i = 1; i <= n; ++i)
{
//cout <<"??" << p[a[i]] << endl;
if (p[a[i]] == 0)p[a[i]] = i;
else
{
res = min(res, i - p[a[i]]);
p[a[i]] = i;
flag = 1;
}
}
//cout << res << endl;
flag == 0 ? cout << -1 << endl : cout << n-res << endl;
}
return 0;
}
第三题-赛后补题
题目: Problem - 1625C - Codeforces
题意:
在一段路程为L的路上有n个路牌，在位置d[i]处有一个路牌，上面记录的数字代表从路牌d[i]走到路牌d[i+1]每公里花费的时间，现在我们最多可以去掉k个路牌，要求给出能够将总时间缩短到多少。注意，第一个路牌不可以去掉。
输出格式
第一行有三个整数n, L, k，分别表示有n个路牌，公路长L公里，最多可以去掉k个路牌。
第二行有n个数，表示路牌的位置。
第三行有n个正整数，表示从当前路牌走到下一个路牌每公里所花费的时间。
输出格式
一个整数，表示缩短后的时间。
数据范围
1 ≤ n ≤ 500, 1 ≤ ℓ ≤ 10^5, 0 ≤ k ≤ n −1
d1=0, di < di+1, 0 ≤ di ≤ ℓ−1
1 ≤ ai ≤ 10^4
输入样例：
4 10 0
0 3 4 8
5 8 3 6输出样例：
47思路:
-
一眼贪心，不出所料wrong answer -
说说为什么不能贪心来做，首先要清晰的明白贪心局部最优，是不能保证整体最优意味着什么。贪心的做法：我们可以将所有路牌按照从大到小排序，然后去掉前j个路牌，如果两个路牌时间相同，那么就比较两者的前一个路牌，去掉前一个路牌数字更小的路牌，虽然确实将时间缩短了，但是无法保证一定是最优解。我们来看这个例子：有3个路牌，路程为10，要求去掉1个路牌。路牌位置：
0,5,9，路牌速度：5,10,11。如果按照贪心来做我们应该去掉数字为11的路牌，结果为5*5+10*5=75，但是显然我们可以通过去掉数字为10的路牌将时间缩短到5*9+11=56。可见贪心是不能保证得到最优解的。 -
考虑动态规划，既然有两个变量，那么一般就要用到二维数组。
-
用
f[i][j]表示走到第i个路牌已经选择了j个路牌所花费的时间的集合，属性是所有时间中的最小值。 -
如何计算状态？从选择了
j个路牌入手，既然当前我们走到第i个路牌已经选择了j个路牌，那么一定是从选择了j-1个路牌处转移过来的，问题在于我们无法确定选择的第j-1块路牌是哪一块，不过没关系，不知道那就暴力跑一边好了，它一定在前i-1个路牌中。 -
那么就得到了状态转移方程：
f[i][j] = min(f[i][j], f[u][j-1] + (a[i] - a[u]) * b[u]);u表示遍历前i-1路牌。 -
务必将极大值写成
0x3f3f3f3f或者1e9，0x3f3f只有可怜的16191，别问我怎么知道的，问就是wrong answer。
代码:
#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;
}
