时隔三个月的第一篇题解，集训也是正式开始了，加油呀
A. Triangles
题意：判断三角形的形状以及是否能构成三角形。
思路：题中说不能构成三角形的为点重合或点在一条直线上，所以判断一下斜率是否相等即可。 判断下三条边平方的大小关系即可判断是什么形状。
#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。
思路：由题意得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次，最多两次。分情况讨论：
思路：分析题意可得最少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;
} 
京公网安备 11010502036488号