B.灯

#include<iostream>
#include<cstring>
using namespace std;
string z;
long long l,r=1e11;
int a[30],c[30],n[30];
bool check(long long x){
	memset(a,0,sizeof(a));
	memset(c,0,sizeof(c));
	int cnt=0;
	while(x!=0){
		a[++cnt]=x%10;
		x/=10;
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=cnt;j++){
			c[i+j-1]+=a[j]*a[i];
			c[i+j]+=c[i+j-1]/10;
			c[i+j-1]%=10;
		}
	}
	for(int i=30;i>=1;i--){
		if(n[i]>c[i]) return true;
		if(n[i]<c[i]) return false;
	}
	return true;
}
signed main(){
	cin>>z;
	for(int i=0;i<z.size();i++)n[z.size()-i]=z[i]-'0';
	while(r-l>1){
		long long mid=(r+l)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<l;
}
/*
#include<iostream>
#include<cmath>
using namespace std;
unsigned long long n,sum;
int main(){
	cin>>n;
	cout<<(unsigned long long)sqrt(n);
}
*/

C.排序plus

思路：

从前往后检查一遍，如果当前的数小于过去最大的数，那么就是一个需要更改的地方，否则最大的数就更新一遍。最后再从后往前检查一遍（跟前面一样），防止出现这种情况：

5
2 1 1 2 3

本来调整一个2的位置就可以了，但程序会认为需要调整两个一。

代码：

#include<iostream>
using namespace std;
int n,a[1000001]={-1},sum1,sum2,minn=0xfffffff,maxn;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(maxn<=a[i])maxn=a[i];
		else sum1++;
	}
	for(int i=n;i>=1;i--){
		if(minn>=a[i])minn=a[i];
		else sum2++;
	}
	if(min(sum1,sum2)<=1)cout<<"YES";
	else cout<<"NO";
}

D.同色三角形

思路：

逆向思维，求出不是红色的三角形的个数，再用总的三角形的个数-不是红色的三角形的个数就行了，不过要用到组合的公式，这里就不多多赘述了。

代码：

#include<iostream>
#define int long long
using namespace std;
int n,m,u,v,red[5001],sum;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		red[u]++,red[v]++;
	}
	for(int i=1;i<=n;i++)sum+=(red[i]*(n-1-red[i]));
	cout<<(n-2)*(n-1)*n/6-sum/2;
}