ARC161
A
排序后直接奇偶分类地填即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int a[MAXN];
int b[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
int Pi=1;
for(int i=1;i<=n;i+=2)
{
b[i]=a[Pi++];
}
for(int i=2;i<=n;i+=2)
{
b[i]=a[Pi++];
}
bool f=1;
for(int i=1;i<=n;i++)
{
if(i%2==0)
{
if(b[i]>b[i-1]&&b[i]>b[i+1])
{
}
else
{
//printf("%d???\n",i);
f=0;
}
}
}
if(f)
{
printf("Yes\n");
}
else
{
printf("No");
}
}
B
直接看\(n\)的二进制里有多少个\(1\),如果有\(3\)个以上就直接取最高的三位即可,否则我们就看\(n\)最近的二进制位,让他降位即可
#include<bits/stdc++.h>
using namespace std;
int T;
long long n;
int b[1005];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
int Cnt=0;
long long Now=n;
while(Now)
{
b[Cnt++]=(Now&1ll);
Now>>=1ll;
}
int Lp=0;
for(int i=0;i<Cnt;i++)
{
if(b[i])
{
Lp++;
}
}
cerr<<Lp<<endl;
if(Lp>=3)
{
long long Ne=n;
for(int i=0;i<Cnt;i++)
{
if(b[i]&&Lp>3)
{
Ne-=(1ll<<(i));
Lp--;
}
}
printf("%lld\n",Ne);
}
else
{
long long Ne=0;
if(Cnt>=4)
{
if(Lp==1)
{
for(int i=Cnt-2;i>=Cnt-4;i--)
{
Ne+=(1ll<<(i));
}
printf("%lld\n",Ne);
}
else
{
if((b[0])||(b[1]))
{
for(int i=Cnt-2;i>=Cnt-4;i--)
{
Ne+=(1ll<<(i));
}
printf("%lld\n",Ne);
}
else
{
Ne=n;
for(int i=2;i<Cnt;i++)
{
if(b[i])
{
Ne-=(1ll<<(i-2));
break;
}
}
printf("%lld\n",Ne);
}
}
}
else
{
printf("-1\n");
}
}
}
}
C
先选度数\(\ge3\)的作为根
考虑自低向上递推,我们记录当前\(x\)是否被确定为\(B,W\)，以及满足条件时\(fa\)的要求即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int T;
int n;
int x,y;
vector<int>g[MAXN];
char s[MAXN];
int dp[MAXN];
int Rd[MAXN];
int Ned[MAXN];
bool found=1;
int Rt;
void dfs(int x,int f)
{
int Cnt1=0,Cnt2=0;
int Cnt0=0;
int Ned1=0;
int Ned2=0;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dfs(v,x);
if(Ned[v]==1)
{
Ned1++;
}
else if(Ned[v]==2)
{
Ned2++;
}
if(dp[v]==1)
{
Cnt1++;
}
else if(dp[v]==2)
{
Cnt2++;
}
else
{
Cnt0++;
}
}
if((Ned1)&&(Ned2))
{
found=0;
}
else if(Ned1)
{
dp[x]=1;
}
else if(Ned2)
{
dp[x]=2;
}
//printf("%d %d %d %d::\n",x,Cnt0,Cnt1,Cnt2);
if(s[x]=='B')
{
if((Cnt1+Cnt0>Cnt2+1)||(x==Rt&&(Cnt1+Cnt0>Cnt2)))
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
// printf("%d???\n",v);
if(dp[v]==0)
{
dp[v]=1;
// printf("%d???\n",v);
}
}
Ned[x]=0;
}
else if((Cnt1+Cnt0+1>Cnt2)&&(x!=Rt))
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(dp[v]==0)
{
dp[v]=1;
}
}
Ned[x]=1;
}
else
{
found=0;
}
}
else
{
if((Cnt2+Cnt0>Cnt1+1)||(x==Rt&&(Cnt2+Cnt0>Cnt1)))
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(dp[v]==0)
{
dp[v]=2;
}
}
Ned[x]=0;
}
else if((Cnt2+Cnt0+1>Cnt1)&&(x!=Rt))
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(dp[v]==0)
{
dp[v]=2;
}
}
Ned[x]=2;
}
else
{
//cerr<<"fuck"<<endl;
found=0;
}
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
g[i].clear();
Rd[i]=0;
Ned[i]=0;
dp[i]=0;
}
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
Rd[x]++;
Rd[y]++;
}
scanf("%s",s+1);
if(n==2)
{
printf("%c%c\n",s[2],s[1]);
continue;
}
found=1;
for(int i=1;i<=n;i++)
{
if(Rd[i]!=1)
{
Rt=i;
break;
}
}
dfs(Rt,0);
if(found)
{
for(int i=1;i<=n;i++)
{
if(dp[i]==1)
{
printf("B");
}
else
{
printf("W");
}
}
printf("\n");
}
else
{
printf("-1\n");
}
}
}
D
考虑直接构造一个图每个点的度数均为\(d\)
我是直接先取个环,然后再隔\(i\)个连边
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,d;
int D[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&d);
d=(d*2);
if(d<=n-1)
{
printf("Yes\n");
for(int i=1;i<=n;i++)
{
D[i]=d;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=i+(d/2);j++)
{
printf("%d %d\n",i,(j%n)?(j%n):n);
}
}
}
else
{
printf("No");
}
}