传送门:CF

前提提要:无

A题:A. Twin Permutations

简单思维题.不难发现只要将所有数对$ai+bi$控制等于$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
int a[maxn];
int main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) {cout<<n-a[i]+1<<" ";}cout<<endl;}return 0;
}

B题:B. Array merging

简单思维题.因为我们可以掌控出数的时刻.不难发现,我们只要找到两个数列中每一个数字的连续的个数即可.我们最终的答案就是两个数列中最大的每一个数字的连续个数和.
举一个栗子,对于合并,假设我们最终的答案是$1$,我们肯定是需要找到a数列中最长的连续的1的位置(记为pos1)以及b数列中最长的连续的1的位置(记为pos2),我们先将pos2,pos1之前的所有数字都加入c中,然后我们再加入所有的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();map<int,int>num1,num2;for(int i=1;i<=n;i++) {a[i]=read();}for(int i=1;i<=n;i++) {b[i]=read();}int cnt=1;num1[a[1]]=1;for(int i=2;i<=n;i++) {if(a[i]==a[i-1]) {cnt++;	}else {num1[a[i-1]]=max(num1[a[i-1]],cnt);cnt=1;}if(i==n) {num1[a[i]]=max(num1[a[i]],cnt);}}cnt=1;num2[b[1]]=1;for(int i=2;i<=n;i++) {if(b[i]==b[i-1]) {cnt++;}else {num2[b[i-1]]=max(num2[b[i-1]],cnt);cnt=1;}if(i==n) {num2[b[i]]=max(num2[b[i]],cnt);}}int maxx=-int_INF;for(int i=1;i<=2*n;i++) {maxx=max(maxx,num1[i]+num2[i]);}cout<<maxx<<endl;}return 0;
}

C题:C. Copil Copac Draws Trees

一道图论题.推一推样例之后很容易知道应该怎么做.
考虑对所有给定的边进行建树,并且记录每一条边的优先级.
然后我们就可以开始从根节点开始跑dfs,对于每一条边,假设我们的下一条边的优先级小于我们的当前边,我们就可以在一次循环中将其遍历,反之我们需要将花费+1.
但是需要注意的是,我们在一次循环中可能遇到很多条需要加花费的边,这些边的花费是可以在一次循环中解决的,也就是花费只需要一,所以我们不能反复累加.
解决方案是,可以记录遍历到每一个节点需要的花费,最后在每一个叶子结点取一个$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 maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
map<int,map<int,int> >mp;
vector<int>tree[maxn];
int vis[maxn];int ans=0;
void dfs(int u,int per_u,int last,int dep) {for(int i=0;i<tree[u].size();i++) {int v=tree[u][i];if(v==per_u) continue;if(mp[u][v]>last) {dfs(v,u,mp[u][v],dep);}else {dfs(v,u,mp[u][v],dep+1);}}ans=max(ans,dep);
}
int main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) {tree[i].clear();vis[i]=0;}mp.clear();for(int i=1;i<=n-1;i++) {int u=read(),v=read();tree[u].push_back(v);tree[v].push_back(u);mp[u][v]=mp[v][u]=i;}ans=1;dfs(1,0,0,1);cout<<ans<<endl;}return 0;
}

D题:D. The BOSS Can Count Pairs

本题的突破口也是比较经典的了.对于这种看起来很像$n^2$的题目,一般都有一些性质.比如本题,在数的值域方面就是一个突破口.很显然对于n^2的暴力算法,我们的值域可以达到1e9,但是为什么这里的值域才n呢,想到这里,对于这道题应该就有思路了.

对于$ai+aj=bi+bj$,又因为$bi+bj<=2\ast n$,所以有$ai\ast aj<=2\ast n$,因为最终是求点对的数量,和先后顺序无关,所以我们不妨将a数组从小到大排一个序.此时我们保证$ai<=aj$.
然后我们枚举$aj$,注意此时我们不能枚举$ai$,这样我们的复杂度还是炸裂的(此时为$ai$~$2\ast n/a[i]$),至于为什么枚举$aj$竟然就可以缩小复杂度呢,这就是算法的巧妙所在了.真是太妙啦.

考虑枚举$aj$,然后我们此时可以枚举$ai$的值域,显然我们的$ai<=\sqrt{2\ast n/aj}$,因为此时$ai<=aj$.此时我们就可以将复杂度降为$n\sqrt{n}$了.因为此时枚举了$aj$,所以我们也知道了$bj$,所以我们就知道了与$ai$相配的$bi$的大小,也就是$ai\ast aj-bj$.所以此时我们的问题就变成了有多少个$<ai,bi>$满足这个关系.这个也不难解决,使用一个桶记录一下即可.

注意本题比较卡内存和时限,map会被卡,数组大小需要计算一下,还需要开longlong

#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
int mp[635][200010];
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Node{int a,b;bool operator < (const Node &rhs) const {return a<rhs.a;}
}node[200010];
int mp1[200010],mp2[200010];
signed main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) {node[i].a=read();mp1[node[i].a]++;}for(int i=1;i<=n;i++) {node[i].b=read();mp2[node[i].b]++;}sort(node+1,node+n+1);int ans=0;int limit=__builtin_sqrt(2*n);for(int i=1;i<=n;i++) {for(int j=1;j<=limit&&j*node[i].a<=2*n;j++) {if(mp1[j]) {if(node[i].a*j-node[i].b>n||node[i].a*j-node[i].b<0) continue;ans+=(ll)mp[j][node[i].a*j-node[i].b];}}if(node[i].a<=limit)mp[node[i].a][node[i].b]++;}for(int i=1;i<=n;i++) {if(node[i].a<=limit)mp[node[i].a][node[i].b]=0;mp1[node[i].a]=0;mp2[node[i].b]=0;}cout<<ans<<endl;}return 0;
}