本文为题解集：

P6685 可持久化动态仙人掌的直径问题
P6686 混凝土数学
P6687 论如何玩转 Excel 表格

为什么不全呢，因为 Yurchiu 太弱了，还不能解决那些题目，以后可能会补充（是不可能的）。

P6685 可持久化动态仙人掌的直径问题

~~题目名称没有任何意义。~~

题意：给定 $n$ ， $m$ ，求有多少个正整数 $x$ ，使得 $x^m\le n$ 。

题解： $x^m\le n$ 等价于 $x \le \sqrt[m]n$ 。

代码：printf("%.0lf",pow(n,1.0/m));

P6686 混凝土数学

题意：给定 $n$ 个数，问这些数可组成多少等腰三角形。

点击查看题解

题解：

我们可以枚举腰来判断。注意以下内容在正整数范围内讨论。

首先，注意到当腰为 $x$ 时，底边的取值范围是： $[1,2x-1]$ 。

所以，我们可以计算，设值为 $i$ 的数有 $a_i$ 个，则我们可以组成的等腰三角形（非等边三角形）的个数为（ $C$ 是组合数）：

C_{a_x}^2 \times [(\sum_{i=1}^{2i-1}a_i)-a_x]

然后，别忘了，相同数之间也能组成等边三角形。所以我们可以得到，可组成的等边三角形数为：

C_{a_x}^3

然后答案就很明显了。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const long long N=200000+10,Mod=998244353;
	long long n,a[N*2],p[N*2],ans=0,mx=-1;
	long long C1(long long x,long long y)
	{
		return (x-y)*y*(y-1)/2;
		//(x-y)*C_y^2  底*腰 
	}
	long long C2(long long x)
	{
		return x*(x-1)*(x-2)/6;
		//C_m^3  
	}
	void yzmain()
	{
		long long tmp;
		scanf("%lld",&n);
		for(long long i=1;i<=n;i++)
		{
			scanf("%lld",&tmp);
			mx=max(mx,tmp);
			a[tmp]++;
		}
		for(int i=1;i<=2*N-5;i++) 
			p[i]=p[i-1]+a[i];//用前缀和记录
		for(long long i=1;i<=mx;i++)
		{
			ans=(ans+C1(p[2*i-1],a[i]))%Mod;
			ans=(ans+C2(a[i]))%Mod;
		}
		printf("%lld\n",ans%Mod);
		return;
	}
}
int main()
{
	//freopen("out.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}

P6687 论如何玩转 Excel 表格

题意：

有一个 $2 \times n$ 的表格，表格内不重不漏地填有 $1 \sim 2 \times n$ 这些数字。你可以进行若干次操作，每次操作可以选择一个 $2 \times 2$ 的正方形区域，然后旋转 $180°$ 。

给出现在的状态以及目标状态。问是否可以达到目标状态。如果能，最少操作次数是多少。

点击查看题解

题解：

我们要想解决这道题，可以分两步：判断无解、得到答案。

我们注意到，旋转操作中，每列数字只可能会上下颠倒，不可能变成其他的数字；旋转一列数字，旋转奇数次会上下颠倒，旋转偶数次会恢复原来的位置。

所以，在现在的状态和目标状态间，列是一一对应的。

据此，我们得到判断无解的两个依据：

在原状态中同一列的两个数在目标状态中不处于同一列。
对于现有状态的一列，其翻转到目标状态时，上下关系不一致。比如，旋转奇数次，目标状态中的列相对原状态中的列会上下颠倒，但实际并没有颠倒。

接下来是得到答案。

既然列是一一对应的，且翻转操作不可能将一列拆散，且翻转操作会将相邻两列交换，我们可以把一列“绑在一起”：给每个对应的列设定同一个编号，再以任一状态的列的顺序作为关键字，得到另一状态的列的编号的顺序。我们就得到一个编号顺序的数列。求其逆序对个数，就是答案。

例如：

     1 6 2                                     2 4 3
     4 3 5  根据左面的状态，得到右面状态的编号顺序。 5 1 6
编号：1 2 3 ----------------------------------> 3 1 2

注意特判 $n=1$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const long long N=1000000+10;
	long long n,ans=0,Map[N],O[N];
	string Err="dldsgay!!1";
	struct Tree
	{
		long long c[N],size;
		Tree(){memset(c,0,sizeof(c));}
		long long lowbit(long long x){return x&(-x);}
		void update(long long x){while(x<=size){c[x]++;x+=lowbit(x);}}
		long long query(long long x){long long ans=0;while(x>=1){ans+=c[x];x-=lowbit(x);}return ans;}
	}tree;
	struct Pair{long long x,y;}A[N],B[N],P[N*2];
	void swap(long long &a,long long &b){long long c=a;a=b;b=c;}
	void yzmain()
	{
		scanf("%lld",&n);tree.size=n;
		for(int i=1;i<=n;i++) scanf("%lld",&A[i].x);
		for(int i=1;i<=n;i++) scanf("%lld",&A[i].y);
		for(int i=1;i<=n;i++) scanf("%lld",&B[i].x),P[B[i].x]=(Pair){i,1};
		for(int i=1;i<=n;i++) scanf("%lld",&B[i].y),P[B[i].y]=(Pair){i,2};
		if(n==1){if(A[1].x==B[1].x&&A[1].y==B[1].y)printf("0");else cout<<Err<<endl;return;}
		for(int i=1;i<=n;i++) Map[A[i].x]=A[i].y,Map[A[i].y]=A[i].x;
		for(int i=1;i<=n;i++)
		{
			if(Map[B[i].x]!=B[i].y || Map[B[i].y]!=B[i].x){cout<<Err<<endl;return;}//在原状态中同一列的两个数在目标状态中不处于同一列
			if(P[A[i].x].y==1 && abs(i-P[A[i].x].x)%2){cout<<Err<<endl;return;}//对应列数字上下关系相同，却移动了奇数次
			if(P[A[i].x].y==2 && abs(i-P[A[i].x].x)%2==0){cout<<Err<<endl;return;}//对应列数字上下关系不同，却移动了偶数次
		}
		for(int i=1;i<=n;i++) O[i]=P[A[i].x].x;//以初始状态的列的顺序作为关键字，得到另一状态的列的编号的顺序
		for(int i=n;i>=1;i--)
		{
			ans+=tree.query(O[i]-1);
			tree.update(O[i]);
		}
		printf("%lld\n",ans);
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}