湖南大学第十六届程序设计竞赛（重现赛）_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

a.不构成三角形的情况除了水平对齐和竖直对齐之外，还需要考虑斜向对齐。处理方式：把三条边长度求出，如果两条短边相加与长边相等，那么不构成三角形。

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string>
#include<sstream>
#include<string.h>
#include<cctype>
#include<algorithm>
#include<iomanip> 
#include<vector>
using namespace std;
#define ll long long
#define INF 0x7fffffff
#define N 500010

int main()
{
	int n,x1,x2,x3,y1,y2,y3,i=1;
	string s[50000];
	cin>>n;
	while(n--){
		cin>>x1>>y1>>x2>>y2>>x3>>y3;
		ll a,b,c,x;
		a=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
		b=(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3);
		c=(x3-x1)*(x3-x1)+(y3-y1)*(y3-y1);
		if(a>b)swap(a,b);
		if(a>c)swap(a,c);
        if(b>c)swap(b,c);
        if((y1-y2)*(x3-x2)==(y3-y2)*(x1-x2))s[i]="invalid";
		else if(a+b==c)s[i]="right";
		else if(a+b>c)s[i]="acute";
		else s[i]="obtuse";
		i++;
	}
	for(int j=1;j<i;j++)cout<<s[j]<<endl;
}

b.因为不仅有两种操作方式，而且要求最少请求数量，所以需要使用bfs算法。细节注意就是求的是n的倍数，所以可以每次操作之后%n，得出一个更小的值，方便运算。

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<utility>
using namespace std; 
#define ll long long
#define INF 0x7fffffff
#define N 500010

int vis[10000000];

int main()
{
	int n,x;
	cin>>n>>x;
	if(n==1){
		cout<<0<<endl;
	}else{
		queue< pair<int,int> > q;
		q.push({1,1});
		vis[1]=1;
		while(!q.empty()){
			pair<int,int> p=q.front();
			q.pop();
			int num=p.first,step=p.second;
			int n1=num*10%n,n2=(num-1+x)%n;
			if(n1==0||n2==0){
				cout<<step<<endl;
				return 0;
			}
			if(!vis[n1]){
				q.push({n1,step+1});
				vis[n1]=1;
			}
			if(!vis[n2]){
				q.push({n2,step+1});
				vis[n2]=1;
			}
		}
		cout<<-1<<endl;
	}
}

d.期望：E(m)=(m-1)/n+1。只有一个人时，期望是1。除了这种情况之外，每增加一个人，期望值便会增加1/n。

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string>
#include<sstream>
#include<string.h>
#include<cctype>
#include<algorithm>
#include<iomanip> 
#include<vector>
using namespace std;
#define ll long long
#define INF 0x7fffffff
#define N 500010

int main()
{
	int n,m;
	cin>>n>>m;
	double x=1.0/n;
	double ans=m*x+(n-1)*x;
	printf("%.8lf\n",ans);
}

f.可以用unsigned long long加特判来处理，也可以用字符串高精度处理。这里用的是高精度。

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string>
#include<sstream>
#include<string.h>
#include<cctype>
#include<algorithm>
#include<iomanip> 
#include<vector>
using namespace std;
#define ll long long
#define INF 0x7fffffff
#define N 500010

string sum(string a,string b){
	int len_a=a.length(),len_b=b.length(),c[10000];
	memset(c,0,sizeof(c));
	string r;
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	int n=max(len_a,len_b);
	
	
	for(int i=0;i<n;i++){
		int q,p,w;
		if(i<len_a)q=a[i]-'0';else q=0;
		if(i<len_b)p=b[i]-'0';else p=0;
		w=q+p;
		c[i]+=w;
		while(c[i]>=10){
			c[i]-=10;
			c[i+1]++;
		}char h=c[i]+'0';
		string x(1,h);
		r+=x;;
	}
	if(c[n]!=0){
		char h=c[n]+'0';
		string x(1,h);
		r+=x;
	}
	//cout<<r<<endl;
	reverse(r.begin(),r.end());
	//cout<<r<<endl<<endl;
	return r;
}

int main()
{
	string a,b,c;
	cin>>a>>b>>c;
	string s=sum(a,b);
	string ans=sum(s,c);
	cout<<ans<<endl;
}

g.判断操作数量只能是0,1,2.对于这个，只用从前往后和从后往前进行判断即可，前指针大于后两个指针的值结束判断。

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string>
#include<sstream>
#include<string.h>
#include<cctype>
#include<algorithm>
#include<iomanip> 
#include<vector>
using namespace std;
#define ll long long
#define INF 0x7fffffff
#define N 500010

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string>
#include<sstream>
#include<string.h>
#include<cctype>
#include<algorithm>
#include<iomanip> 
#include<vector>
using namespace std;
#define ll long long
#define INF 0x7fffffff
#define N 500010

int main()
{
	string s,t;
	cin>>s>>t;
	int g=0;
	while(s[g]==t[g])g++;
	int r=s.size()-1,l=t.size()-1;
	while(s[r]==t[l])r--,l--;
	if(s==t)cout<<0<<endl;
	else if(g>=r||g>=l)cout<<1<<endl;
	else cout<<2<<endl;
}

i.这道题的难点是对于次数的把控，前面开始想的时候自然可以想当然用二分法模拟操作，但是题目要求的是最优解，所以这个方法不行。那么只用判断一个给定的值x（每次跳跃的楼层数），可以满足   x*(x-1)/2<=楼层数   即可，用二分查找求出x值。{操作方式就是第一次x层，第二次2x层......一直到蛋摔碎。如果在2x层摔碎的话，就返回第x+1层开始往上判断。这样求出的x值就是最优解}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; 
#define ll long long
#define INF 0x7fffffff
#define N 500010

ll sum(ll k){
	return k*(k+1)/2;
}

int main()
{
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll l=1,r=2e9;
		while(l<r){
			ll mid=(l+r)/2;
			if(sum(mid)<n)l=mid+1;
			else r=mid;
		}
		cout<<l<<endl;
	}
}

L.判断水管路径，因为求的是是否导通，所以可以把它看成图。用dfs进行模拟操作。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; 
#define ll long long
#define INF 0x7fffffff
#define N 500010

int a[N],n,m;
int dic[5][2]={{-1,0},{0,-1},{1,0},{0,1}};
int mp[10][4]={{0,0,0,0},{1,0,1,0},{0,1,0,1},{0,0,1,1},{1,1,0,0},{1,1,0,1},{0,1,1,1} };
int vis[N]={0};

int getid(int a,int b){
	return m*(a-1)+b;
}
bool check(int x,int y){
	if(x<1||x>n||y<1||y>m)return false;
	if(vis[getid(x,y)])return false;
	else return true;
}
bool dfs(int x,int y){
	vis[getid(x,y)]=1;
	if(x==n&&y==m)return true;
	for(int i=0;i<4;i++){
		int fx=x+dic[i][0],fy=y+dic[i][1];
		if(check(fx,fy)&&mp[a[getid(x,y)]][i]&&mp[a[getid(fx,fy)]][(i+2)%4])
			if(dfs(fx,fy))return true;
	}
	return false;
}
int main(){
	cin>>n>>m;
	int cnt=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[cnt++];
	if(mp[a[1]][1]==0||mp[a[getid(n,m)]][3]==0){
		cout<<"NO"<<endl;
		return 0;
	}
	if(dfs(1,1))cout<<"YES";
	else cout<<"NO";
}