Preface
ARC战俘闪总出列
这场一上来就感觉状态不太对，先是A顺序敲反WA了一发，然后C题看到秒出一个贪心然后也WA了
看一眼榜发现D过的比C多，然后跑去把D写了，中间还偷偷挂了两发
最后50min回去沉淀C题，结果换了两种写法都还是一样的挂，后面发现想法还是有纰漏
总结：彩笔
A - Make M
考虑在\(2,4,\cdots,n-1\)的位置上放上最大的\(\frac{n-1}{2}\)个数，然后在\(1,3,\cdots,n\)的位置上放最小的\(\frac{n+1}{2}\)个数，然后检验即可
注意放的时候要注意顺序，让所有数中最大的数去和\(\frac{n+1}{2}\)小的数中最大的去对
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a[N],ans[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (sort(a+1,a+n+1),j=n,i=n-1;i>=0;i-=2) ans[i]=a[j--];
for (j=i=1;i<=n;i+=2) ans[i]=a[j++];
for (i=2;i<=n;i+=2) if (ans[i]<=ans[i-1]||ans[i]<=ans[i+1]) return puts("No"),0;
return puts("Yes"),0;
}
B - Exactly Three Bits
稍作分析不难发现当\(f(X)\ge 3\)时，答案就是保留\(X\)二进制下的前三个\(1\)出现的位置，然后后面全部置为\(0\)
如果初始时给出的\(f(X)\le 2\)呢，那我们直接暴力模拟减\(1\)的过程，知道出现\(f(X)\ge 3\)的状态
手玩一下很容易发现较大的数做很少次操作后就一定会变成\(f(X)\ge 3\)，因此复杂度没有问题
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,d[100],len; long long n;
inline int calc(CI len)
{
int ret=0; for (RI i=1;i<=len;++i) ret+=d[i]; return ret;
}
inline void output(CI len)
{
long long ret=0; for (RI i=len;i>=1;--i) ret=ret*2LL+d[i]; printf("%lld\n",ret);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%lld",&n),len=0;n;d[++len]=n&1,n>>=1);
while (len&&calc(len)<3)
{
int pos=1; while (!d[pos]) ++pos;
for (i=1;i<pos;++i) d[i]=1; d[pos]=0;
if (pos==len) --len;
}
if (!len) { puts("-1"); continue; }
if (calc(len)==3) { output(len); continue; }
int cur=0; for (i=len;i>=1;--i)
if ((cur+=d[i])>3) d[i]=0; output(len);
}
return 0;
}
C - Dyed by Majority (Odd Tree)
首先比赛的时候很naive地写了个按照度数从小到大枚举点的贪心
因为显然从叶子节点可以确定它们父亲的状态，然后就很想当然地再去检验度数为\(3\)，为\(5\)的点，但这样是不够严密的
考虑合理的做法，我们把树看作有根树，然后先确定\(x\)子树内其它点的状态，再确定\(x\)的状态
但是这样会有一个问题，就是有些点为了达到目标状态，只通过子树内的其它点是不够的（比如叶子节点），这时候就需要让它们向父亲节点传递一个信号，表示需要父亲节点的取值来帮助该点到达状态
而如果某个点仅仅通过子树内的点就足以达到目标状态，那么贪心地来看，让它的状态等于它父亲需要的状态即可
其实这题想清楚就很简单的说，但比赛的时候就是猪脑过载，属实有点可惜
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x,y,ans[N],a[N],rst[N][2]; char s[N]; vector <int> v[N]; bool flag;
inline void DFS(CI now=1,CI fa=0)
{
int c[2]={0,0}; for (int to:v[now]) if (to!=fa) DFS(to,now),++c[ans[to]];
if ((c[a[now]]+(fa?1:0)<<1)<v[now].size()) return (void)(flag=0);
if (rst[now][0]&&rst[now][1]) return (void)(flag=0);
if (rst[now][0]) ans[now]=0; if (rst[now][1]) ans[now]=1;
if ((c[a[now]]<<1)<v[now].size()) rst[fa][a[now]]=1;
if (!~ans[now]) ans[now]=a[fa];
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) v[i].clear(),rst[i][0]=rst[i][1]=0,ans[i]=-1;
for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (scanf("%s",s+1),i=1;i<=n;++i) a[i]=s[i]=='B'?1:0;
flag=1; DFS(); if (!flag) { puts("-1"); continue; }
for (i=1;i<=n;++i) putchar(ans[i]?'B':'W'); putchar('\n');
}
return 0;
}
D - Everywhere is Sparser than Whole (Construction)
这题比较玄学啊，完全不保证个人做法的正确性，因为要特判\(D=1\)的情况才能过
先把显然无解的情况判掉，然后剩余情况我们都一定能构造
一个很感性的想法就是我们的构造方案要尽量地对称，因此可以让每个点度数都为\(2D\)
同时还要满足稠密度尽量平衡的要求，因为如果又某一部分的导出子图过于稠密或稀疏，可能就会导致出错
然后我刚开始的想法是每次选择与点\(i\)连接的点时，把剩下所有待选点按照度数从小到大排序，按顺序来选度数小的点
然后写了一发交了发现AC了33个点，WA了1个点，还T了两个点（这个因为暴力排序复杂度确实有问题），就很奇怪是不是漏了什么Corner Case
但是由于要优化掉排序的过程，后面就想了一种用循环链表来模拟上述过程的做法
大致地就是按编号从小到大枚举每个点来处理出边，然后用一个指针初始时指向\(n\)，然后每次就顺次匹配指针向前移动的元素
当一个点度数达到\(2D\)时就直接删掉这个点，手玩一下会发现它是符合上面讲的按度数选择的策略的
然后又交了一发发现这下AC了34个点，WA了两个点，更加确信肯定有什么特殊情况没判好
随即想到当\(D=1\)时要求很严苛，必须刚好形成一个\(n\)元环才能满足要求，而我们的贪心做法由于对度数相同的点的取法并没有严格的顺次要求，因此可能会挂
然后本地跑了下\(N=10,D=1\)的数据果然给我造了若干个小的环出来，后面再加一个特判\(D=1\)上去就终于过了
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=50005;
int n,d,deg[N],L[N],R[N],p;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; if (scanf("%d%d",&n,&d),1LL*n*(n-1)/2LL<n*d) return puts("No"),0;
for (puts("Yes"),i=1;i<=n;++i) L[i]=i-1,R[i]=i+1;
if (d==1)
{
for (i=1;i<n;++i) printf("%d %d\n",i,i+1);
printf("%d %d\n",1,n); return 0;
}
for (L[1]=n,R[n]=1,i=1,p=n;i<=n;++i)
{
int t=2*d-deg[i]; while (t--)
{
if (p==i) p=L[p]; ++deg[i]; ++deg[p]; printf("%d %d\n",i,p);
if (deg[p]==2*d) R[L[p]]=R[p],L[R[p]]=L[p]; p=L[p];
}
R[L[i]]=R[i]; L[R[i]]=L[i]; if (p==i) p=L[p];
}
return 0;
}
Postscript
好久没打Atcoder了又一次感受到了被Brain Fuck的感觉
总结：人菜多练
标签：AtCoder,const,int,len,RI,Regular,include,161,define From： https://www.cnblogs.com/cjjsb/p/17443619.html