时隔三个月的第一篇题解,集训也是正式开始了,加油呀
题意:判断三角形的形状以及是否能构成三角形。
思路:题中说不能构成三角形的为点重合或点在一条直线上,所以判断一下斜率是否相等即可。 判断下三条边平方的大小关系即可判断是什么形状。
#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;
}