1608A - Find Array
直接从2-n+1即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,T;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=2;i<=n+1;i++) printf("%d ",i);
printf("\n");
}
return 0;
}
1608B - Build the Permutation
首先考虑怎样才能有解,设有a个峰b个谷,那么a+b+1<n,并且a和b最多差一个,画一画就能发现,因为两个峰之间必有一个谷
然后考虑构造,直接取最大的a+b+2个,大的作峰,小的作谷,然后剩余的按从小到大放在最前面即可,具体的看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int p[maxn];
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T,n,a,b;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&a,&b);
if(abs(a-b)>1 || a+b+2>n){printf("-1\n"); continue;}
int flag=0;
if(a<b) swap(a,b),flag=1;
int pos=n;
if(a==b)
{
for(int i=0;i<=a;i++) p[n-i*2]=pos--;
for(int i=0;i<=b;i++) p[n-i*2-1]=pos--;
for(int i=1;i<=pos;i++) p[i]=i;
}
else
{
for(int i=0;i<a;i++) p[n-i*2-1]=pos--;
for(int i=0;i<=a;i++) p[n-i*2]=pos--;
for(int i=1;i<=pos;i++) p[i]=i;
}
for(int i=1;i<=n;i++)
{
if(!flag) printf("%d ",p[i]);
else printf("%d ",n-p[i]+1);
}
printf("\n");
}
return 0;
}
1608C - Game Masterh
个人觉得这道题非常的棒
首先我们要倒着考虑这个问题,如果x最后胜者,那么x一定在最后一轮赢了一个人y,倒数第二轮应该是x或y赢了z,这样依次拓展下去,如果能拓展到所有的人,就意味着x可以最终获胜
显然这个过程可以和图联系起来,考虑每一个人向他能打败的人连一个边,那么要是可以从x出发走到所有的点,就意味着x最终可以取胜,至此我们得到了一个的算法
继续考虑优化,由于这张图已经有级别的边了,所以一定要从这里入手优化,我们分别按照两张地图上的能力作为关键字排序,而后每次仅连接 i 和 i+1 即可,这样就仅仅连 2n-2 条边,又发现能到所有点相当于走到a最大或者b最大的点(因为他们可以战胜任何人),所以我们从amax和bmax两个位置出发遍历整张图即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int T,n;
struct capability
{
int val,id;
}a[maxn],b[maxn];
vector <int> G[maxn];
bool cmp(capability x,capability y)
{
return x.val<y.val;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;
for(int i=1;i<=n;i++) scanf("%d",&b[i].val),b[i].id=i;
sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);
vector <int> ans(n+5,0);
for(int i=1;i<=n;i++)
G[i].clear();
for(int i=1;i<n;i++) G[a[i].id].push_back(a[i+1].id);
for(int i=1;i<n;i++) G[b[i].id].push_back(b[i+1].id);
ans[a[n].id]=ans[b[n].id]=1;
queue <int> q;
q.push(a[n].id),q.push(b[n].id);
while(!q.empty())
{
int u=q.front(); q.pop();
for(auto to:G[u])
{
if(ans[to]) continue;
ans[to]=1;
q.push(to);
}
}
for(int i=1;i<=n;i++) printf("%1d",ans[i]);
printf("\n");
}
return 0;
}