VP记录:Codeforces Round 867 (Div. 3) A~G2
传送门:CF
A题:TubeTube Feed
简单的模拟题,需要注意的是跳一次视频是需要花一秒钟时间的.并且是从前往后看的.所以我们可以提前预处理出看完第 i i i个视频的最短时间(即视频时长+跳到当前视频的时间,也就是i-1),然后比价一下记录最大值即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn],b[maxn];
int main() {
int T=read();
while(T--) {
int n=read(),t=read();
for(int i=1;i<=n;i++) {
a[i]=read();a[i]+=i-1;
}
for(int i=1;i<=n;i++) {
b[i]=read();
}
int cnt=0;int maxx=-int_INF;int pos=-1;
for(int i=1;i<=n;i++) {
if(t>=a[i]) {
if(b[i]>maxx) {
maxx=max(maxx,b[i]);
pos=i;
}
}
}
cout<<pos<<endl;
}
return 0;
}
B题:Karina and Array
选出最大的两个数的乘积.有多种方法可以解决.注意到最大的乘积可能是由两个负数形成的.所以我们可以直接进行一个排序,然后对最大的两个数的乘积和最小的两个数(可能是负数)的乘积进行一个比较即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define int long long
int T;int a[maxn];
signed main() {
T=read();
while(T--) {
int n=read();
for(int i=1;i<=n;i++) {
a[i]=read();
}
sort(a+1,a+n+1);
cout<<max(a[1]*a[2],a[n]*a[n-1])<<endl;
}
return 0;
}
C题:Bun Lover
观察数据范围发现应该是一道公式题,所以可以对数据进行模拟,发现是每一次n增加答案增加是从属于一个数列分布的(具体证明略),所以直接输出即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define int long long
signed main() {
int T=read();
while(T--) {
int n=read();n-=4;
int sum=10+n*(n+6)+4*(n+4);
cout<<sum<<endl;
}
return 0;
}
D题:Super-Permutation
一道构造题,emmm,关于这道题官方题解对于构造方式也没有什么合理的证明.但是这道题的样例十分的良心,可以根据样例来推出本题的构造方式
发现n=6时,答案是6 5 2 3 4 1,前缀和为6 11 13 16 20 21
发现b数组为1 6 2 5 3 4所以我们可以找到一个比价显然的规律,也就是b组数是呈1 n 2 n-1 3 n-2...来分布的.所以我们只要记录一下当前位置前一个位置的余数即可.因为取模运算是可加性的.我们知道了之前的以及结果,就可以推出加的那一个数字
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
map<int,int>mp;
int main() {
int T=read();
while(T--) {
vector<int>ans;
int n=read();mp.clear();
if(n==1) {
cout<<1<<endl;
continue;
}
int l=2,r=n;int cnt=1;
ans.push_back(n);int flag=0;
for(int i=2;i<=n;i++) {
flag=0;
if(i%2==0) {
if(mp[r-cnt]==0&&r-cnt<=n&&r-cnt>=1) {
ans.push_back(r-cnt);
mp[r-cnt]=1;
flag=1;
}
else {
if(mp[r+n-cnt]==0&&r+n-cnt<=n&&r+n-cnt>=1) {
ans.push_back(r+n-cnt);
mp[r+n-cnt]=1;
flag=1;
}
}
cnt=r;
r--;
}
else {
if(mp[l-cnt]==0&&l-cnt<=n&&l-cnt>=1) {
ans.push_back(l-cnt);
mp[l-cnt]=1;
flag=1;
}
else {
if(mp[l+n-cnt]==0&&l+n-cnt<=n&&l+n-cnt>=1) {
ans.push_back(l+n-cnt);
mp[l+n-cnt]=1;
flag=1;
}
}
cnt=l;
l++;
}
if(flag==0) {
cout<<"-1"<<endl;break;
}
}
if(flag==0) continue;
for(int i=0;i<ans.size();i++) {
cout<<ans[i]<<" ";
}
cout<<endl;
}
return 0;
}
E题:Making Anti-Palindromes
首先可以发现当长度为奇数的时候显然是不符合条件的.因为对于奇数长度来说,最中间位置的那个数字永远都是不满足条件的.所以我们可以直接特判这个.
然后我们统计一下每一个字母在这个字符串中出现的次数.我们发现假设一个字符出现的次数大于了
n
/
2
n/2
n/2,那么显然我们也无法满足条件,证明显然
同样可以发现除了上述情况其他情况都是有解的(可以手画一下,这个比较难讲).
我们可以记录一下左右两段相同的字母对.现在考虑如何进行交换使得最终的交换次数最小.显然我们如果选取两个字母对(比如说是aa,bb),然后我们交换其中的一个字母,就消了两个字母对.反之如果我们没有选取两个字母对,我们就必须选择(aa,cd),然后进行一个交换,此时我们才消了一个字母对,显然没有上面的优秀.所以我们需要尽量的多进行前述的交换方式
到此这道题还没有结束.我们观察一下我们的交换方式,因为此时我们是必然有解的,所以假设我们一直使用上述的交换方式,那么最终会有两种结果:1.我们的所有字母对都用完了,并且恰好使所有的相同的字母对都变得不同. 2.还剩下一种字符的字母对
我们会发现剩下来的那一个字符的字母对只能和不同的字母对进行交换了(形同cd),此时我们每话费一次交换才消掉一个.此时就有一个贪心的想法,也就是让最后剩下来的那一个字符的字母对最少即可.也就是每一次相消都消掉现有最多的两个字母对.
可能讲起来比较抽象,建议结合代码理解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int T;
map<char,int>mp;
map<char,int>mp2;
int main() {
cin.sync_with_stdio(false);
cin>>T;
while(T--) {
int n;string s;mp.clear();mp2.clear();
cin>>n>>s;
if(n&1) {
cout<<"-1"<<endl;
continue;
}
int maxx=-int_INF;
for(int i=0;i<s.length();i++) {
mp[s[i]]++;
maxx=max(maxx,mp[s[i]]);//记录出现最多的那个字符
}
if(maxx*2>n) {
cout<<"-1"<<endl;
continue;
}
priority_queue<int>q;
int l=0,r=n-1;
while(l<r) {
if(s[l]==s[r]) {
mp2[s[l]]++;//记录前后相同的字母对的个数
}
l++;r--;
}
for(auto it : mp2) {
q.push(it.second);
}
int ans=0;
while(q.size()>=2) {
int u1=q.top();q.pop();//每次都取出当前最多的两个字母对,这样能保证最后剩下来的最少
int u2=q.top();q.pop();
u1--;u2--;ans++;
if(u1!=0) q.push(u1);
if(u2!=0) q.push(u2);
}
if(q.size()) ans+=q.top();//最后剩下来的那个颜色每次只能消掉一个了
q.pop();
cout<<ans<<endl;
}
return 0;
}
F题: Gardening Friends
题目中需要求出树上的所有点到一个点的最长距离.此处我们需要使用树的直径.
树的直径是树上的最长链
对于树的直径来说,有一个很强的性质,也就是一棵树上的所有点到其他点的最长距离的位置肯定是直径的两个端点之一,证明使用反证法可以很快证明,此处省略
对于树的直径来说有一个很笼统的求法:也就是先从根节点开始遍历,找到一个距离最远的点,这个点肯定是直径的一个端点(可以使用性质证明),然后再从这个直径的一个端点开始遍历,求出距离最长的点,这个点就是直径的另一端点
此时我们可以直接求出一棵树的直径.那么对于任意的一个点来说,其他点到这个点的最远距离显然就是直径的两个端点到这个点的距离取一个
m
a
x
max
max,因为这个点到直径的两个端点的其中一点最远,就意味着两个端点的一点到这个点最远.
所以此时我们可以预处理所有点到根节点,以及到直径的两个端点的距离
然后枚举每一个点作为我们的最终的根节点,我们移动根节点的花费就是当前点到最初根节点的距离乘上一次移动的花费.最终的利润就是直径的两个端点到这个点的距离取一个
m
a
x
max
max乘上每一条边耳朵花费,
注:求直径时可以使用指针来简化函数代码,博主为了方便并没有使用指针
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
vector<int>tree[maxn];int dep1[maxn];
void dfs(int u,int per_u) {
for(int i=0;i<tree[u].size();i++) {
int v=tree[u][i];
if(v==per_u) continue;
dep1[v]=dep1[u]+1;
dfs(v,u);
}
}
int dep2[maxn];
void dfs2(int u,int per_u) {
for(int i=0;i<tree[u].size();i++) {
int v=tree[u][i];
if(v==per_u) continue;
dep2[v]=dep2[u]+1;
dfs2(v,u);
}
}
int dep3[maxn];
void dfs3(int u,int per_u) {
for(int i=0;i<tree[u].size();i++) {
int v=tree[u][i];
if(v==per_u) continue;
dep3[v]=dep3[u]+1;
dfs3(v,u);
}
}
signed main() {
int T;T=read();
while(T--) {
int n=read(),k=read(),c=read();
for(int i=1;i<=n-1;i++) {
int u=read(),v=read();
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1,0);
int node1;int maxx=-int_INF;
for(int i=1;i<=n;i++) {
if(dep1[i]>maxx) {
maxx=dep1[i];
node1=i;//直径的第一个端点
}
}
dfs2(node1,0);
int node2;maxx=-int_INF;
for(int i=1;i<=n;i++) {
if(dep2[i]>maxx) {
maxx=dep2[i];
node2=i;//直径的第二个端点
}
}
dfs3(node2,0);
int ans=-int_INF;
for(int i=1;i<=n;i++) {
ans=max(ans,max(dep2[i]*k-dep1[i]*c,dep3[i]*k-dep1[i]*c));
}
cout<<ans<<endl;
for(int i=1;i<=n;i++) {
tree[i].clear();
dep1[i]=dep2[i]=dep3[i]=0;
}
}
return 0;
}
G1:Magic Triples (Easy Version)
先预处理出每一个数的个数,然后枚举每一个数作为等比三元组的第一个数
直接枚举等比数列的比值即可.对于一个数
a
[
i
]
a[i]
a[i]来说,因为最大数为
1
e
6
1e6
1e6,所以此时一个数我们需要的复杂度为
q
∗
q
∗
a
[
i
]
<
1
e
6
q*q*a[i]<1e6
q∗q∗a[i]<1e6,特判一下
q
=
1
q=1
q=1的时候情况即可轻松AC本题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000100
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define int long long
int a[maxn];
int mp[maxn];
signed main() {
int T=read();int kkk=1000;
while(T--) {
int n=read();
for(int i=1;i<=n;i++) {
a[i]=read();
mp[a[i]]++;
}
sort(a+1,a+n+1);ll ans=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=kkk;j++) {
if(a[i]*j*j>1e6) break;
if(mp[a[i]*j]&&mp[a[i]*j*j]) {
if(j==1) {
ans+=(mp[a[i]]-1)*(mp[a[i]]-2);
}
else {
ans+=(mp[a[i]*j])*(mp[a[i]*j*j]);
}
}
}
}
for(int i=1;i<=n;i++) {
mp[a[i]]=0;
}
printf("%lld\n",ans);
}
return 0;
}
G2:Magic Triples (Hard Version)
显然我们的G1的方法已经不管用了.此时我们需要进行一点优化.
考虑将每一个数字作为等比三元组的第二项.然后枚举比值q,考虑最大值为
1
e
9
1e9
1e9
我们会发现每一个数需要的复杂度为
1
e
9
/
a
[
i
]
1e9/a[i]
1e9/a[i],当
a
[
i
]
a[i]
a[i]很小的时候复杂度会爆炸,但是
a
[
i
]
a[i]
a[i]较大的时候是可以通过的.所以考虑使用分块.
当
a
[
i
]
>
x
a[i]>x
a[i]>x的时候使用上述算法.当
a
[
i
]
<
x
a[i]<x
a[i]<x的时候再谋出路.
a
[
i
]
<
x
a[i]<x
a[i]<x的时候可以考虑枚举
a
[
i
]
a[i]
a[i]的所有因子.此时可能有人会有疑问了,我们的因子可以到达
a
[
i
]
/
2
a[i]/2
a[i]/2此时复杂度还是爆炸的啊.我们想一下,其实我们的因子只需要枚举到
a
[
i
]
\sqrt{a[i]}
a[i]就可以了.因为另一半大于
a
[
i
]
\sqrt{a[i]}
a[i]的因子显然和小于
a
[
i
]
\sqrt{a[i]}
a[i]的因子是相对应的(也就是两两乘起来应该就等于a[i]).所以此时我们只需要枚举一半即可.我们将复杂度优化到了
a
[
i
]
\sqrt{a[i]}
a[i]
综合考虑两种方式,我们最终取
x
x
x为
1
e
6
1e6
1e6
下面讲一些实现过程中的细节:
1.与G1不同的是,我在G1中是枚举每一个数组中的数的,但是这个显然是可以使用离散化进行优化的.所以在G2中我们进行了离散化优化(这样可以使我们不需要枚举n个数了)
2.对于比值为1的三元组我们应该进行特殊考虑,假设这个数的个数为
k
k
k,那么我们可以在
k
k
k中随意的取出三个位置,此时我们有
C
(
k
,
3
)
C(k,3)
C(k,3)种方案,然后我们进行重排列(因为数字都是相同的,换一下依旧是等比数列),最终有
C
(
k
,
3
)
∗
3
!
C(k,3)*3!
C(k,3)∗3!中方案,也就是
k
∗
(
k
−
1
)
∗
(
k
−
2
)
k*(k-1)*(k-2)
k∗(k−1)∗(k−2)种方案.
3.因为1的原因,我们在后序的遍历中需要注意不重不漏(具体看代码)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000100
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define int long long
int a[maxn];
map<int, int> mp;
signed main() {
int T=read();int kkk=1000;
while(T--) {
int n=read();mp.clear();
for(int i=1;i<=n;i++) {
a[i]=read();
mp[a[i]]++;
}
ll ans=0;
for(auto it : mp) {
int num=it.first;
ans+=(it.second*(it.second-1)*(it.second-2));
if(num<=1e6) {
for(int j=1;j*j<=num;j++) {
if(num%j!=0) continue;
if(j!=1) {
if(mp.count(num/j)&&mp.count(num*j)) {
ans+=(mp[num/j])*(mp[num*j])*(mp[num]);
}
}
int i2=num/j;
if(i2!=j) {
if(mp.count(num/i2)&&mp.count(num*i2)) {
ans+=mp[num/i2]*(mp[num*i2])*(mp[num]);
}
}
}
}
else {
for(int j=2;j<=1e9/num;j++) {
if(num%j!=0) continue;
if(mp.count(num/j)&&mp.count(num*j)) {
ans+=(mp[num/j])*(mp[num*j])*(mp[num]);
}
}
}
}
printf("%lld\n",ans);
}
return 0;
}