Preface
B题粗糙了改了好几个版本，最后索性从头理了一遍思路才过
然后剩下40min想C又歪了（构造题精通的被动消失了），还剩25min的时候忍不住了看LPL去了
话说现在的ARC感觉和以前的AGC难度相当啊，不过也许是没有陈指导教我我什么都做不来
A - AABCDDEFE
就是用类似康托展开的思路来算每一部分的值，直接看代码吧
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; scanf("%d",&n); --n;
int p=n/100000,q=n%100000; for (i=1;i<=2;++i) putchar(p+'1');
int pp=q/1000,qq=q%1000; putchar(pp/10+'0'); putchar(pp%10+'0');
int ppp=qq/100,qqq=qq%100; for (i=1;i<=2;++i) putchar(ppp+'0');
int pppp=qqq/10,qqqq=qqq%10;
putchar(pppp+'0'); putchar(qqqq+'0'); putchar(pppp+'0');
return 0;
}
B - Grid Rotations
话说我比赛时的做法怪的很，还找不到方法解释，结果现在写Editorial的时候就想到个很好的解释法
先讲比赛时想的，首先容易发现行和列的情况可以分别独立考虑，我们只要求出每一行在操作后变成哪一行即可，记为\(r_i\)
考虑对行的某次旋转操作\(a_i\)，观察到前半部分每次对换的位置的下标之和为\(a_i+1\)，后半部分每次对换的下标之和为\(a_i+1+H\)，这两个在模\(H\)意义下时一样的
因此对于某个行\(r_i\)转变后的值就是\(a_i+1-r_i\)在模\(H\)意义下的值，因此我们根据环的性质可以发现最后\(r_i\)一定可以形成一个环的形态
当然上面的说法不是很明显，我们考虑换一种方法理解
我们考虑让第\(1\)行和第\(n\)行相连，在行之间形成一个环，同时考虑一次旋转操作不会影响每一行相邻的行是什么
举个例子，比如\(H=4\)时，原来初始时环的形态是\([1,2,3,4]\)，在进行操作\(a_i=3\)后变成\([3,2,1,4]\)
不难发现每个数相邻的两个数都没有变，变化的只是\(1\)所在的位置和与其相邻的\(2\)的方向而已
因此我们只要维护每次旋转后\(1\)的位置即可，列的情况完全相同
#include<cstdio>
#include<iostream>
#include<vector>
#include<cctype>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int n,m,q,a[N],b[N],h[N],w[N],d; vector <char> A[N];
inline char getch(void)
{
char ch; while (ch=getchar(),isspace(ch)); return ch;
}
inline int Nxt(int x,CI T)
{
x+=d; if (x<=0) x+=T; if (x>T) x-=T; return x;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
for (A[i].resize(m+1),j=1;j<=m;++j) A[i][j]=getch();
int sf_h=1,sf_w=1; for (scanf("%d",&q),i=1;i<=q;++i)
{
scanf("%d%d",&a[i],&b[i]); ++a[i]; ++b[i];
if ((sf_h=a[i]-sf_h)<=0) sf_h+=n;
if ((sf_w=b[i]-sf_w)<=0) sf_w+=m;
}
d=q&1?-1:1; int ct; h[sf_h]=1; w[sf_w]=1;
for (ct=1,i=Nxt(sf_h,n);i!=sf_h;i=Nxt(i,n)) h[i]=++ct;
for (ct=1,i=Nxt(sf_w,m);i!=sf_w;i=Nxt(i,m)) w[i]=++ct;
for (i=1;i<=n;++i,putchar('\n')) for (j=1;j<=m;++j) putchar(A[h[i]][w[j]]);
return 0;
}
C - ± Increasing Sequence
原来是个如此simple的构造题，给我CPU干过载了
我们不妨先进行一次很naive的尝试，令\(x_i=i\)，并统计出此时\(\sum_{i=1}^N A_ix_i\)的值\(sum\)
若\(sum=0\)则显然直接输出即可，否则我们求出\(A_i\)的前缀和数组\(pfx_i\)，并分类讨论：
- 若\(sum>0\)，我们考虑找到第一个\(pfx_i=1\)的位置\(pos\)，然后我们发现每当我们将\(x_j,j\in[1,pos]\)减\(1\)时，最后的\(\sum_{i=1}^N A_ix_i\)就会恰好减\(1\)，因此我们直接让\(x_j,j\in[1,pos]\)减去\(sum\)即可
- 若\(sum<0\)，类似上面的思路，我们设第一个\(pfx=-1\)的位置为\(pos\)，直接让\(x_j,j\in[1,pos]\)加上\(sum\)即可
考虑到\(sum\)的范围是\(n^2\)级别的，因此可以满足\(|x_i|\le 10^{12}\)的限制
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a[N],pfx[N]; long long ans[N],sum;
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]),pfx[i]=pfx[i-1]+a[i],ans[i]=i,sum+=1LL*ans[i]*a[i];
bool flag=0; if (sum==0) flag=1;
else if (sum>0)
{
for (i=1;i<=n;++i) if (pfx[i]==1)
{
for (j=1;j<=i;++j) ans[j]-=sum; flag=1; break;
}
} else
{
for (i=1;i<=n;++i) if (pfx[i]==-1)
{
for (j=1;j<=i;++j) ans[j]+=sum; flag=1; break;
}
}
if (flag) for (puts("Yes"),i=1;i<=n;++i) printf("%lld ",ans[i]);
else puts("No"); return 0;
}