A.配对：
贪心，倒序配对。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const double eps=1e-6;
priority_queue<int,vector<int>,greater<int> >que;
int a[N],b[N];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int cnt=0,ans=0;
for(int i=n;i>=n-k+1;i--)
{
int t=a[i]+b[2*n-k+1-i];
que.push(t);
}
ans=que.top();
printf("%d\n",ans);
return 0;
}
B.图：
思路：
先用拓扑排序，把所有不在环中的点选择出来标记。然后处理环，遍历每一个环，求出环内的点数，然后把环内的所有的点的 num 数组都赋相同的值。然后，从非环内的点进行记忆化搜索，求出每个点对应 num 数组数值,取最大即可。
一开始用了 stl 的 map 和 set ， t 了好几发，时间差别竟然这么大。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const double eps=1e-6;
const ll mod=1e9+7;
//map<int,map<int,int> >mp;
int pic[N],num[N],degree[N];
bool vis[N],book[N];
void read(int &x)
{
x=0;
int f=1;
char c;
c=getchar();
while(!isdigit(c))
{
if(c=='-')
f=-1;
c=getchar();
}
while(isdigit(c))
{
x=x*10+c-'0';
c=getchar();
}
x*=f;
}
int ans;
void bfs(int n)
{
queue<int>que;
for(int i=1;i<=n;i++)
{
if(degree[i]==0)
que.push(i);
}
while(!que.empty())
{
int now=que.front();
que.pop();
vis[now]=1;
int t=pic[now];
degree[t]--;
if(degree[t]==0)
que.push(t);
}
}
void solve(int x)
{
int tx=x;
int t=pic[x];
int cnt=1;
book[x]=1;
int f=0;
while(!book[t]||t==tx&&f==0)
{
book[t]=1;
if(t!=tx)
cnt++;
else
f=1;
//mp[x][t]=1;
x=t;
t=pic[x];
}
num[tx]=cnt;
t=pic[tx];
while(t!=tx)
{
num[t]=cnt;
t=pic[t];
}
}
int dfs(int v)
{
if(num[v])
return num[v];
int t=pic[v];
return num[v]=dfs(t)+1;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
read(pic[i]);
degree[pic[i]]++;
}
bfs(n);
ans=0;
for(int i=1;i<=n;i++)//环
{
if(!vis[i]&&num[i]==0)
solve(i);
}
for(int i=1;i<=n;i++)
{
if(vis[i]&&num[i]==0)
num[i]=dfs(i);
}
for(int i=1;i<=n;i++)
{
if(ans<num[i])
ans=num[i];
}
printf("%d\n",ans);
return 0;
}
/* 6 3 1 2 2 3 5 */
附上题解代码：
作者：珩月
链接：https://ac.nowcoder.com/discuss/367149?type=101&order=0&pos=1&page=1
来源：牛客网
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1000050;
int to[N], siz[N], n, vis[N], ins[N], sta[N];
int dfs(int x){
if(siz[x]) return siz[x];
return siz[x] = 1 + dfs(to[x]);
}
int main()
{
int i, j, k, h;
scanf("%d", &n);
for(i = 1; i <= n; i ++)
scanf("%d", &to[i]);
for(i = 1; i <= n; i ++){
if(vis[i] == 0){
j = i;
while(vis[j] == 0){
sta[++ sta[0]] = j;
vis[j] = ins[j] = 1;
j = to[j];
}
if(ins[j]){
k = j, h = 0;
do{
k = to[k];
h ++;
}while(k != j);
do{
k = to[k];
siz[k] = h;
}while(k != j);
}
while(sta[0]){
ins[sta[sta[0]]] = 0;
sta[0] --;
}
}
}
for(i = 1, h = 0; i <= n; i ++)
h = max(h, dfs(i));
printf("%d", h);
return 0;
}
基环树：
基环树有且仅有一个环，所以也被成为环套树。从一个点出发，沿着出边一路走下去，一定会走到一个环。
<mark>C.汉诺塔</mark>：
思路：
根据贪心的思想，放在一组的相邻两块木板，他们的 x 和 y 值之差越小越好。可以先根据各块木板的 x 值，从小到大排好序。然后把所分的每一组当作一个栈，维护每个栈的栈顶元素（个人觉得这个思想很好），即该组内的最大 y 值。遍历每个木板，根据 y 值，对已有的各个组进行二分，找到比它的 y 值小的最大 y 值所在的组，放入，可以保证最优。
题解的另一种思路：
将木板按照 Xi 从小到大排序，将这时的 Yi 数列记为 Zi 数列，则问题变成将Zi划分为尽可能少的若干组上升子序列。
根据 Dilworth定理，最小组数等于 Zi 的最长下降子序列长度。
Dilworth定理
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
struct node
{
int pos,x,y;
bool operator <(const node b)const
{
return x<b.x;
}
}h[N];
int g[N],s[N];
int main()
{
int n,x,y;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&h[i].x,&h[i].y);
h[i].pos=i;
}
int maxn=0;
sort(h+1,h+1+n);
for(int i=1;i<=n;i++)
{//二分手写或者调用函数：
int left=upper_bound(s+1,s+1+maxn,h[i].y,greater<int>())-s;
/*int left=1,right=maxn; while(left<=right) { int mid=(left+right)>>1; if(s[mid]<h[i].y) right=mid-1; else left=mid+1; }*/
if(left>maxn)//新组
maxn=left;
s[left]=h[i].y;//更新该组最大的y值
g[h[i].pos]=left;//标号
}
printf("%d\n",maxn);//忘了输出
for(int i=1;i<=n;i++)
printf("%d%c",g[i],i==n?'\n':' ');
return 0;
}
D.重排列：
思路：
首先， A,B 数组中各个数的位置对最终结果没有影响，因为只要满足对应位置的关系即可。为了方便处理，先各自按升序排好序。然后，对 B 数组开始讨论，计算其每个位置可以放几个 A 数组中的数。我们从左向右来填，当到达B数组某一位 i 时，如果此时对应 A 数组中最多到 j 位比此i 位的数小或等。那么，由于 i 位前，已经用了 j 位数中的 i−1 个，所以 i 位上还可以填 j−i+1 个数。最后相乘即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=1e9+7;
int a[N],b[N];
int main()
{
int n;
ll ans=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int j=1;
for(int i=1;i<=n;i++)
{
while(j<=n&&a[j]<=b[i])
j++;
j--;
ll t=max(0,j-i+1);
ans=ans*t%mod;
if(t==0)
break;
}
printf("%lld\n",ans%mod);
return 0;
}
<mark>E.立方数</mark>：
思路：
技巧暴力，先用欧拉筛预处理出 (1e18) 的 1/4 次方范围内的素数及其立方（此处取 N=4e4+5）。然后用这些数对 n 进行质因子分解（Pollard Rho因数分解，复杂度 O(n1/4)）。对于剩下的数，要么是一个大于 N 的素数的立方，要么就是一个大于 N 的素数。接下来在 (N,1e6]之间进行二分，判断剩下的数是否为某数立方的数。
如果直接用 1e6 内的素数去筛，会超时。
如果范围更小一点就会错。因为，如果范围小的话，可能剩余的数为某个大于上界的素数的四次方，会使答案变小；而如果选择 1e18 的 1/4 次方，这样就不会这种情况。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e4+5;
vector<int>prime;
bool vis[N];
ll num[N];
int cnt=0;
void init()
{
memset(vis,0,sizeof*(vis));
cnt=0;
for(int i=2;i<=N-5;i++)
{
if(!vis[i])
{
prime.push_back(i);
num[cnt++]=1LL*i*i*i;
}
for(int j=0;j<prime.size()&&i*prime[j]<=N-5;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
ll divide(ll n)//Pollard Rho因数分解:O(n^(1/4))
{
int cnt=0;
ll ans=1;
for(int i=0;i<prime.size()&&prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
while(n%num[i]==0)
{
ans*=prime[i];
n/=num[i];
}
while(n%prime[i]==0)
n/=prime[i];
}
}
int left=40005,right=1000000;
while(left<=right)
{
int mid=(left+right)/2;
if(1LL*mid*mid*mid<n)
left=mid+1;
else
right=mid-1;
}
if(1LL*left*left*left==n)
ans*=left;
return ans;
}
int main()
{
int t;
init();
ll n;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
printf("%lld\n",divide(n));
}
return 0;
}
H.云【简单扫描线】：
<mark>I.导航系统</mark>【最小生成树】：
思路：
给出的距离表是基于树的，那么可以根据表得到一个完全图。如果我们对这个完全图求最小生成树，假如距离表是正确的，那么生成树上任意两点间的最短距离就是表中的距离。如果不一致，则为错误。因此，可以用最小生成树求解验证。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=130000;
struct edge
{
int val,u,v;
bool operator <(const edge b)const
{
return val<b.val;
}
}eg[N];
int pic[510][510],pre[510],ans[510][510];
vector<int>g,p[510];
int Find(int x)
{
if(x!=pre[x])
return pre[x]=Find(pre[x]);
else
return x;
}
void dfs(int f,int v,int pp)
{
for(int i=0;i<p[v].size();i++)
{
int t=p[v][i];
if(t!=pp)
{
ans[f][t]=ans[f][v]+pic[v][t];
dfs(f,t,v);
}
}
}
int main()
{
int n,w,cnt=0;
bool f=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
pre[i]=i;
for(int j=1;j<=n;j++)
{
scanf("%d",&w);
pic[i][j]=w;
if(i>j&&pic[i][j]!=pic[j][i])//判断1
f=0;
}
}
if(!f)
{
printf("No\n");
return 0;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
eg[++cnt]=edge{pic[i][j],i,j};
}
sort(eg+1,eg+1+cnt);
int cot=0;
for(int i=1;i<=cnt;i++)
{
int x=Find(eg[i].u);
int y=Find(eg[i].v);
if(x!=y)
{
pre[y]=x;
p[eg[i].u].push_back(eg[i].v);
p[eg[i].v].push_back(eg[i].u);//建立树的邻接表
cot++;
g.push_back(i);
}
if(cot==n-1)
break;
}
for(int i=1;i<=n;i++)//求任意两地之间的最短距离O(n*n)
dfs(i,i,i);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(pic[i][j]!=ans[i][j])//判断2
{
f=0;
break;
}
}
}
if(!f)
printf("No\n");
else
{
printf("Yes\n");
for(int i=0;i<g.size();i++)
{
int t=g[i];
printf("%d\n",eg[t].val);
}
}
return 0;
}
京公网安备 11010502036488号