#867 div3
A:
题目:
现在存在一些视频,每个视频都有一个有趣值,每次从第一个视频开始看,可以花费1秒跳过当前视频。但是你有一个定量的时间,
问你在时间内,你可以看完最有趣的视频是哪一个。
思路:
从前往后枚举,如果跳过前面的视频,看当前视频的有趣值是多少即可
代码
void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
int ans = 0;
int idx = -1;
for(int i = 1; i <= n; i++)
{
int sum = i - 1;
if(sum + a[i] <= m)
{
if(b[i] > ans) ans = b[i], idx = i;
}
}
cout << idx << endl;
}
B:
题目:
现在给出一个数组,我们定义数字的最大美值是,数组内存在一对相邻的最大乘积。
它可以删除任意个元素,但是保证剩下两个。问你数组最大的美值是多少。
思路:
毫无疑问 要么是最大正数 * 正数,要么最小负数*负数
排个序即可
代码
void solved()
{
cin >> n ;
for(int i = 0; i < n; i++) cin >> a[i];
int mx = -1e18;
sort(a, a + n);
mx = a[n - 1] * a[n - 2];
mx = max(mx, a[0] * a[1]);
cout << mx << endl;
}
C:
题目:
现在存在一个面包卷,问你面包卷上的黑色条的长度是多少。
每个面包卷都是由前一个面包卷再包裹构成。
思路:
我们找一下规律,可以发现,由 26 开始每次 是上一个的长度 + 2 * i + 1
递推得公式(5 + n) * (n - 4) + (n - 4) + 26
代码
void solved()
{
cin >> n;
if(n == 4)
{
cout << 26 << endl;
return;
}
cout << (5 + n) * (n - 4) + (n - 4) + 26 << endl;
}
D:
题目:
现在存在一个排列 a,定义数组 bi 为 (a1 + ~a[i]) % n, 如果数组 a是超级排列,那么 bi + 1 ,b数组也是排列。
问你长度为 n 的超级排列是否存在,存在输出 b 数组
思路:
观察首先发现,n 为奇数的情况下都是不存在的,除了 n 为 1。
考虑 n 为偶数的情况,观察几个样例发现,存在合法的数据,相邻的和都是 n - 1, 并且开头都是 0,
所以把 a 数组构造出来后,直接得到 b 数组
代码
void solved()
{
cin >> n;
if(n == 1)
{
cout << 1 << endl;
return;
}
if(n % 2 != 0)
{
cout << -1 << endl;
return;
}
a[1] = 0;
for(int i = 2; i <= n; i++)
{
if(i % 2 == 0) a[i] = abs(n - 1 - a[i - 1]);
else a[i] = abs(n - a[i - 1]);
}
b[1] = n;
for(int i = 2; i <= n; i++)
{
b[i] = (a[i] - a[i - 1] + n) % n;
}
for(int i = 1; i <= n; i++) cout << b[i] << " ";
cout << endl;
}
E:
题目:
现在存在一个字符串,如果这个字符串,在回文意义下都不相等,那么他就是反回文。
现在你可以一次操作下,交换任意位置的两个字符。
如果可以问你最小次数
思路:
如果一个字符占据了整个字符串超过一半的次数,那么肯定存在相同情况,直接pass掉。
否则一定存在答案。
不难发现对于一组不合法的 a[i] == a[n - i + 1], 我们找到另一组与字符不相同的交换一下。
这样一下子可以解决两个不合法的位置。如果最后剩下一个单独的,那么随便交换肯定有答案。
所以用堆来维护,每个字符出现不合法的次数,然后两两交换。为了满足最优,每次对不合法次数,最大和
最小的两种字符交换。
代码
void solved()
{
has.clear();
cin >> n;
string s; cin >> s;
s = "?" + s;
if(n % 2 != 0)
{
cout << -1 << endl;
return;
}
int mx = 0;
for(int i = 1; i <= n; i++)
{
char c = s[i];
has[c]++;
mx = max(mx, has[c]);
}
if(mx > n / 2)
{
cout << -1 <<endl;
return;
}
vector<int> id[26];
int mid = n / 2;
for(int i = 1; i <= mid; i++)
{
if(s[i] == s[n - i + 1]) id[s[i] - 'a'].push_back(i);
}
priority_queue<int>q;
for(int i = 0; i < 26; i++)
{
if(id[i].size())
q.push(id[i].size());
}
int ans = 0;
while(q.size())
{
int tp = q.top();
q.pop();
if(q.size() == 0)
{
ans += tp;
break;
}
int tp2 = q.top();
q.pop();
if(tp != 1) q.push(tp - 1);
if(tp2 != 1) q.push(tp2 - 1);
ans++;
}
cout << ans << endl;
}
G1
题目:
现在存在一个数组,让你找有多少个三元组满足 两个等式
思路:
不难发现假如枚举出 aj 和 b,那么其他两个统计出现次数就可以解决。
因为 ai * b = j, 所以 b 是 aj的因子,那么枚举 b 只要枚举当前 aj 的合法因子即可。
需要注意的当 b 为1,要特殊处理,对次数>=3 的计算一下答案即可。
那么复杂度就是 n logn
代码
void solved()
{
map<int, int>st;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i], st[a[i]]++;
int ans = 0;
for(auto x : st)
{
if(x.second >= 3)
{
ans += x.second * (x.second - 1) * (x.second - 2);
}
}
for(int i = 0; i < n; i++)
{
int x = a[i];
for(int j = 2; j <= x / j; j++)
{
if(x % j == 0)
{
if(x % (j * j) == 0 && st[x / j] && st[x / (j * j)])
{
ans += st[x / j] * st[x / (j * j)];
}
}
}
}
cout << ans << endl;
}