湖南大学第十六届程序设计竞赛（重现赛）

时隔三个月的第一篇题解，集训也是正式开始了，加油呀

题意：判断三角形的形状以及是否能构成三角形。

思路：题中说不能构成三角形的为点重合或点在一条直线上，所以判断一下斜率是否相等即可。判断下三条边平方的大小关系即可判断是什么形状。

#include <bits stdc="">
using namespace std;

int main()
{
	int t; cin >> t;
	while(t--)
	{
		int x1,x2,x3,y1,y2,y3;
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
		int tmp1,tmp2,tmp3;
		tmp1=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
		tmp2=(x1-x3)*(x1-x3)+(y1-y3)*(y1-y3);
		tmp3=(x3-x2)*(x3-x2)+(y3-y2)*(y3-y2);
		if(tmp1>tmp2) swap(tmp1,tmp2);
		if(tmp1>tmp3) swap(tmp1,tmp3);
		if(tmp2>tmp3) swap(tmp2,tmp3);
		if((x1==x2&&y1==y2)||(x1==x3&&y1==y3)||(x2==x3&&y2==y3)||(x1==x2&&x1==x3)||(y1==y2&&y1==y3)||((y1-y2)*(x1-x3)==(x1-x2)*(y1-y3))) puts("invalid");
		else if(tmp1+tmp2<tmp3>tmp3) puts("acute");
		else puts("right");
	}
	
	return 0;
}</tmp3></bits>

B. Yuki with emofunc and playf

题意：开始有一个苹果，我们可以进行两种操作：1.数量*10；2.数量+x-1，问最少进行多少次操作让苹果的数量为n的倍数。

思路：根据题意转化下思路，苹果数量为k，要使得k%n==0，即两种操作可转化为：1.k=(k*10)%n；2.k=(k+x-1)%n，将问题范围缩小到n。bfs求最短路，起点为1，终点为0。

代码：

#include <bits stdc="">
using namespace std;
typedef long long ll;
int n, x;
const int N = 1e6 + 5;
bool flag = false;
queue<pair><int>> q;
int vis[N];
int cnt;
int check1(int x)
{
    x = x * 10 % n;
    return x;
}
int check2(int y)
{
    y = (y + x - 1) % n;
    return y;
}
void bfs()
{
    q.push(make_pair(1, 0));
    cnt = 0;
    while(!q.empty())
    {
        int tmp1 = q.front().first;
        int tmp2 = q.front().second;
        q.pop();
        int a = check1(tmp1), b = check2(tmp1);
        cnt=tmp2+1;
        if(a==0||b==0) {
            flag = true;
            break;
        }
        else 
        {
            if(vis[a]==0) {
                q.push(make_pair(a, cnt)), vis[a] = 1;
            }
            if(vis[b]==0) {
                q.push(make_pair(b, cnt)), vis[b] = 1;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> x;
    if(n!=1) {
        bfs();
        if (flag)
            cout << cnt << endl; else cout << -1 << endl; } else cout << 0 << endl; return 0; }</int></pair></bits>

C. Doorman：

D. Queuing：

题意：有n个窗口，现在我们前面有m-1个人，每个人去任意一个窗口的概率均是1/n，求我们在新队列中的排名期望。
思路：由题意得E(m)为第m个人的期望，假设E(m-1)已求，那E(m)=E(m-1)+1/n, m>=2.因为m有1/n的概率和前m-1个人在同一队，很明显E(1)=1，也满足于前面推出的式子，所以递推可得通式：E(m)=(m-1)/n+1。

解题&讨论那里有个大佬用数学公式推出来了，tql，看懂之后我也尝试自己推了一遍，E(m)表示 m 号人前有多少个人，然后用权值去乘以这个权值出现的概率

代码：

#includeusing namespace std;
const int eps=1e-6;

int main()
{
	double n,m; cin >> n >> m;
	double ans=(m-1)/n+1;
	if(ans>=eps) printf("%.8lf\n",ans);
	return 0;
}

E. Catching Stars：

F. Team

t题意：计算a+b+c。

思路：数据范围特别大，可以用字符串也可以用__int128。

代码：

#includeusing namespace std;
inline __int128 read()
{
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch - '0'); ch = getchar(); } return x * f; } void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
int main()
{
    __int128 a = read();
    __int128 b = read();
    __int128 c = read();
    
    print(a+b+c);
    return 0;
}

G. Binbin's string

题意：给出两个字符串s和t，我们有两个操作，1.删去字符串中某子串，2.在某个位置插入一字符串。问最少多少次将s变t
思路：分析题意可得最少0次，最多两次。分情况讨论：

1.s和t长度相等时，如果它们存在相同位置不相等的字符，我们需要先删除再插入新字符串，所以要2次。

2.s和t长度相等时，且s==t，不需要操作。

3.s和t长度不相等时，标记s和t相同字符的位置pos1，不断更新直至不相等，倒着找第一个相等字符的位置pos2，不断更新直至不相等，再分情况：a).如果s串长度len1小于t串长度len2，判断pos1+pos2+1与len1的大小关系，如果相等则操作一次，否则两次；b).如果s串长度len1大于t串长度len2，同理。

代码：

#includeusing namespace std;
const int eps=1e-6;

int main()
{
	string s,t; cin >> s >> t;
    int flag=0;
	int len1=s.length(),len2=t.length();
	if(len1==len2)
	{
		for(int i=0;i= pos1 + 1 && i <= len2; i++) { if (s[len1 - i] != t[len2 - i]) break; else pos2 = i; } if(len1<=len2) { if(pos1+1+pos2==len1) cout << 1 << endl; else cout << 2 << endl; } else { if(pos1+1+pos2==len2) cout <<1

H. Professor Yang's Homework

I. Binbin and Balls

题意：有两个球和n层楼的房子，球从第x层掉落后不会碎，但如果从x+1,x+2,...球会碎，问最坏情况下，最少多少次能找到这个最大的x。

思路：假设丢x次是最优选择，我们首先从x层丢，如果球碎了，那么我们只能从1层开始到x-1逐个增加层数去找最大的x，在最坏情况下，最少x次一定能找到；如果x没碎，我们就从x+x-1开始丢，同理碎了我们就从x到x+x-2一个个去尝试，没碎就从x+x-1+x-2层往下丢，以此类推...到这就很容易看出其实就是一个等差数列求和：(x+1)*x/2。我们只要让求和式子大于等于n，即可保证得到前n楼的答案，所以二分查找最小满足的x即可。

代码：

#include#define endl '\n'
using namespace std;
const int eps=1e-6;
typedef long long ll;
const ll maxn=5e9+5;
int check(ll x,ll n)
{
	if(x*(x+1)/2+1>n) return 1;
	else return 0;
}
int main()
{
	
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while(t--)
	{
		ll n; cin >> n;
		if(n==1) {
			cout << 1 << endl; continue; } else if(n==2) { cout << 2 << endl; continue; } else { ll l=1,r=maxn,ans,mid; while(l<=r) { mid=l+r>>1;
				if(check(mid,n)) {
					r=mid-1;
					ans=mid;
				} 
				else {
					l=mid+1;
				}
			}
			cout << ans << endl; } } return 0; }

J. Yuki with playf：

K. Yuki with emofunc：

L. Cracked Pipes：

题意：有六种水管和n*m的区域，问是否能让水管联通从(1,0)流到(n,m+1)；

思路：数据特别大，别用二维数组，我用了map标记每个位置属于哪种水管，dfs，搜上下左右四个方向并将搜过位置标记，搜的时候不能越界且该位置要能与上个位置的水管相连（我用了一个数组表示每种水管的开口，1表示开，0表示关），当搜到(n,m)退出。再判断一下（n,m)位置的水管是否与(n,m+1)相连。

代码：

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int eps=1e-6;
typedef long long ll;
const ll N=2e5+5;
int dir[4][2]={0,-1,1,0,-1,0,0,1};//上下左右
int pos[7][4]={{},{0,1,1,0},{1,0,0,1},{0,1,0,1},{1,0,1,0},{1,0,1,1},{1,1,0,1}};
int a[N],vis[N];
int flag=0;int n,m; 
map<pair<int,int>,int>mp;
map<pair<int,int>,int>mmp;
bool check1(int x,int y)
{
	return x&&y&&x<=n&&y<=m;
}
bool check2(int x,int y)
{
	return pos[x][y];
}
void dfs(int x,int y)
{
	 mmp[{x,y}]=1;
    for(int i=0;i<4;i++){
    	int dx=dir[i][0]+x;
		int dy=dir[i][1]+y;
    	if(check1(dx,dy)&&check2(mp[{x,y}],i)&&check2(mp[{dx,dy}],3-i)&&!mmp[{dx,dy}]) dfs(dx,dy);
    }
    if(x==n&&y==m) flag=1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			int x; cin >> x;
			mp[{i,j}]=x;
		}
	}
	mp[{1,0}]=2;
	dfs(1,0);
	if(flag) 
	{
		if(mp[{n,m}]==2||mp[{n,m}]==5||mp[{n,m}]==6) cout << "YES" << endl;
	}
	else cout << "NO" << endl;
	return 0;
}