A

看到这题名字就想吐……

滚粗的预感（逃

---

Solution

貌似这题也不难。分类讨论(防溢出)即可:

①当$n=1$时，输出$n$；
②当$n\ge 40$时，输出$1$；
③否则暴力枚举$x$的值，用快速幂优化乘方。

最差情况时间复杂度为$O(\sqrt{n})$。($m=2$)

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;int n,m;int quick_power(int a,int b)
{int res=1;for (;b;b=b>>1,a=(a*a)){if (b&1)  res=(res*a);}return res;
}signed main()
{cin>>n>>m;if (m==1)  cout<<n<<endl;else if (m>=40)  cout<<1<<endl;else{int cnt=0;for (int i=1;i<=n;i++){if (quick_power(i,m)<=n&&quick_power(i,m)!=-1)  cnt++;else break;}cout<<cnt<<endl;}return 0;
}

B

本蒟蒻的数学能力算是个蒟蒻，而别的只能算个菜鸡，所以本蒟蒻相对来说就擅长点数学啦……于是就开了B题。

看了一半题，接着又开了D题；

D题看懂后，又开了C题；

于是，把$B,C,D$全部看懂后，开始想$B$题显然的思路。

Solution

假设一个等腰三角形三条边的长度为$a,a,b$，简记$b$为底。

分别考虑每条边为底，然后累加满足要求情况即可。设这条边的长度为$x$，长度为$i$的木棍的数量为$v_i$，$maxlen=max${$a_i$}，则其满足要求的情况数为${\sum }_{j=\lfloor \frac{n}{2}\rfloor +1}^{maxlen}{C}_{v_j}^2$。

可以发现，此时每个等边三角形都被算了三次，所以答案还要减去$(3-1){\sum }_{i=1}^{maxlen}{C}_{v_i}^3$。

注意随时取模即可。由于有$n\le 2\times 10^5$的限制，并不需要逆元。

万万没想到，由于溢出与$RE$的问题，导致提交了$20$发才过…… 辛亏心态还好，否则就直接滚上床睡觉颓废了

Code

#include <bits/stdc++.h>
#define int long long
#define rg register
using namespace std;
const int mod=998244353;int n,ans=0,maxlen=200000;
int a[1000005],v[1000005],pre[1000005];inline int C(int k)
{return ((k*k-k)/2)%mod;
}inline int CC(int k)
{rg int now=(k*k-k)/2;return (((now%mod)*(k-2))/3)%mod;
}inline int read()
{int s=0,w=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}return s*w;
}signed main()
{cin>>n;for (rg int i=1;i<=n;++i)  a[i]=read(),v[a[i]]++;for (rg int i=1;i<=maxlen;++i)  pre[i]=pre[i-1]+C(v[i]);for (rg int i=1;i<=maxlen;++i){rg int p=(i/2)+1;ans=(ans+((pre[maxlen]-pre[p-1]-C(v[i]))*v[i]))%mod;}for (rg int i=1;i<=maxlen;++i){ans=(ans+CC(v[i]))%mod;}cout<<ans%mod<<endl;return 0;
}

C

果断开C题。

话不多说，顺利先骗到$11$分，然后考虑正解。令人惊讶的是，我骗完$Subtask3$，以为只暂时拿到$6$分，结果$Subtask4$跟着$Subtask3$也过了……

Solution

显然，我们可以将每列捆绑起来看。首先考虑无解的情况。定义"移动"为，一列在移到正确的位置中需要被翻转的次数。

①原来这两个数在同一列，现在不在同一列了；
②原来这两个数在同一列，经过奇数次移动，这两个数的上下顺序仍然相同；
③原来这两个数在同一列，经过偶数次移动，这两个数的上下顺序变化了。

int m[2*maxlen+5][3];
for (rg int i=1;i<=2;i++)
{for (rg int j=1;j<=n;j++)  a[i][j]=read();
}
for (rg int i=1;i<=2;i++)
{for (rg int j=1;j<=n;j++){b[i][j]=read();m[b[i][j]][1]=i,m[b[i][j]][2]=j;}
}
bool no_solution()
{for (int i=1;i<=n;i++){int x=a[1][i],y=a[2][i];int xx=m[x][1],xy=m[x][2];int yx=m[y][1],yy=m[y][2];if (xy!=yy)  return true;if (i%2==xy%2&&yx!=xx+1)  return true;else if (i%2!=xy%2&&xx!=yx+1)  return true;v[i]=xy;}return false;
}
//判断无解的方法

既然已经保证有解，考虑最少翻转的次数。

我们可以将每列捆绑起来看，设第$i$列它在$b$数组中的位置为第$v_i$列。此时，答案就是$v$的逆序对个数！即，我们每次转换都会减少有且仅有一个逆序对，最终逆序对的数量为$0$。

用树状数组可以在$O(nlo{g}_{2}n)$的时间复杂度内求逆序对数。

本题略微卡常，注意快速读入即可。总时间复杂度为$O(nlo{g}_{2}n)$。

当时比赛的时候脑子瓦特，第一次数组开小$RE$，第二次用$map$记录数字位置导致超时，第三次快读忘写导致卡常……

Code

#include <bits/stdc++.h>
#define int long long
#define rg register
using namespace std;
const int maxlen=1000000;int n,ans=0;
int a[5][maxlen+5],b[5][maxlen+5],m[2*maxlen+5][3];
int v[maxlen+5],tree[maxlen+5];inline int lowbit(int k)
{return k&(-k);
}bool no_solution()
{for (int i=1;i<=n;i++){int x=a[1][i],y=a[2][i];int xx=m[x][1],xy=m[x][2];int yx=m[y][1],yy=m[y][2];if (xy!=yy)  return true;if (i%2==xy%2&&yx!=xx+1)  return true;else if (i%2!=xy%2&&xx!=yx+1)  return true;v[i]=xy;}return false;
}inline void change(int rt)
{while (rt<=n){tree[rt]++;rt+=lowbit(rt);}
}inline int query(int rt)
{int ans=0;while (rt>=1){ans+=tree[rt];rt-=lowbit(rt);}return ans;
}inline int read()
{int s=0,w=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}return s*w;
}signed main()
{cin>>n;for (rg int i=1;i<=2;i++){for (rg int j=1;j<=n;j++)  a[i][j]=read();}for (rg int i=1;i<=2;i++){for (rg int j=1;j<=n;j++){b[i][j]=read();m[b[i][j]][1]=i,m[b[i][j]][2]=j;}}if (no_solution())  return cout<<"dldsgay!!1"<<endl,0;for (int i=n;i>=1;i--){ans+=query(v[i]-1);change(v[i]);}cout<<ans<<endl;return 0;
}