湖南大学第十六届程序设计竞赛（重现赛）
A Triangles
题目描述
在平面坐标系上给你三个点，让你判断三点构成的三角形的类型
解题思路
判断公式
钝角三角形：
直角三角形：
锐角三角形：
就根据判断条件判断就好了
代码实现
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
int main() {
int t;
cin>>t;
while(t--) {
double x1,y1,x2,y2,x3,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
double l[3];
l[0]=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
l[1]=(y3-y2)*(y3-y2)+(x3-x2)*(x3-x2);
l[2]=(y3-y1)*(y3-y1)+(x3-x1)*(x3-x1);
sort(l,l+3);
if(l[0]==0||l[1]==0||l[2]==0) {cout<<"invalid"<<endl;continue;}
else if(x1!=x2&&x2!=x3&&y1!=y2&&y2!=y3&&((y2-y1)/(x2-x1)==(y3-y2)/(x3-x2)||(y3-y1)/(x3-x1)==(y3-y2)/(x3-x2)||(y3-y1)/(x3-x1)==(y2-y1)/(x2-x1))) {cout<<"invalid"<<endl;continue;}
else if((x1==x2&&x2==x3)||(y1==y2&&y2==y3)) {cout<<"invalid"<<endl;continue;}
else {
double n=l[0]+l[1]-l[2];
if(n==0) cout<<"right";
else if(n>0) cout<<"acute";
else cout<<"obtuse";
cout<<endl;
}
}
return 0;
}B Yuki with emofunc and playf
题目描述
给出数字n和x(1<=n<=1e6,1<=x<=1e9)， 初始的数字k=1。
每次可以在两个操作中任选一个进行:
1.k=k*10
2.k= k+x-1
问最少操作多少次，使得k是n的倍数。如果永远不能，输出-1。
解题思路
k是n的倍数，满足k%n==0。 以上两种类型的操作可以转换为:
1.k=(k*10)%n
2.k=(k+x-1)%n
这样就把k（实际上是k%n）能到达的范围缩小到(0,n)了。起点从1开始，终点为0。
BFS：从队头取数，判断是否能整除N，整除则得到结果，否则将K进行两种不同的操作，即不同操作后的K%n可能与队列元素相同，记录第一次出现后如果后面重复出现可直接跳过，因为第一次出现使用的操作次数最少，当无解时，输出-1。
DFS:思路一样，不过这里我看了别人的代码，步数超过25之后，这条路就不走了，我一开始也不懂为啥，后面有人说是打表找过，奇奇怪怪，其他的步骤和BFS差不多。
代码实现
BFS解法：
#include<algorithm>
#include<iostream>
#include<string>
#include<math.h>
#include<string.h>
#include<queue>
const int N=1e6+5;
using namespace std;
int n,x,p[N],tmp[N];
queue<int> q;
int main(){
memset(p,0,sizeof(p));
cin>>n>>x;
p[1%n]=1;
tmp[1%n]=0;
q.push(1%n);
while(!q.empty()){
int t=q.front();
q.pop();
if(t%n==0){
cout<<tmp[t%n]<<endl;return 0;
}
if(!p[(t*10)%n]) {q.push((t*10)%n);tmp[(t*10)%n]=tmp[t%n]+1;p[(t*10)%n]=1;}
if(!p[(t+x-1)%n]) {q.push((t+x-1)%n);tmp[(t+x-1)%n]=tmp[t%n]+1;p[(t+x-1)%n]=1;}
}
cout<<-1<<endl;
return 0;
}dfs解法：
#include<iostream>
#include <vector>
#define int unsigned long long
using namespace std;
const int Max=1000000;
int n,m,ans=0x3f3f3f3f;
void dfs(int now,int step){
if(step==25) return;
if(now%n==0){
ans=min(ans,step);
return;
}
dfs((10*now)%n,step+1);
dfs((now+m-1)%n,step+1);
}
signed main(){
cin>>n>>m;
dfs(1,0);
if(ans!=0x3f3f3f3f)cout<<ans<<endl;
else cout<<-1<<endl;
}
D Queuing
题目描述
在上课铃响之前，食堂前已经排起了长队。
当食堂开门时，队列中的每个人都以接近光速的速度冲向食堂的n个窗口之一，形成一个新的n个队列。
这个过程遵循以下规则：
- 每个人都冲向第i 个 以 1/n 的概率独立开窗；
- 如果一开始A在B前面，A和B冲到同一个窗口，那么A还在B前面。
现在Playf在队伍里排第m，也就是说有m-1个人领先于 Playf。Playf 想知道在自助餐厅开放后他在新队列中的排名期望。
解题思路
这里不要将注意集中在窗口分布情况，换个角度：也就是每个人可能在palyf前也有可能不在palyf前面。
事件t:在playf前面,事件发生概率：p(t)=1/n,实验次数就是总人数m-1。
那么前m-1在窗口前符合二项分布X~B（m-1,1/n)
易知二项分布数学期望E(t)=np=(m-1)(1/n)
那么playf的排名就是(m-1)(1/n)+1
代码实现
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
int main() {
int n,m;
scanf("%d %d",&n,&m);
double sum=1+(m-1)/(double)n;
printf("%.8lf\n",sum);
return 0;
}F Team
题目描述
大数相加：a+b+c
解题思路
解法1：看完题目首先我想到的就是大数相加
解法2：观察数据,unsigned long long的范围：
而a+b+c的范围是超过了三个数字，用unsigned long long存储，再加个特判即可
代码实现
解法1：
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
int carry=0;
int main(){
string a,b;
int c[10000];
cin>>a>>b;
int l=a.length(),r=b.length();
int mmax=max(l,r);
int t=mmax;
while(l&&r){
l--;r--;
c[--mmax]=(a[l]+b[r]+carry-96)%10;
carry=(a[l]+b[r]+carry-96)/10;
}
while(l){
c[--mmax]=(a[--l]+carry-48)%10;
carry=(a[l]+carry-48)/10;
}
while(r){
c[--mmax]=(b[--r]+carry-48)%10;
carry=(b[r]+carry-48)/10;
}
int carry1;
cin>>carry1;
for(int i=t-1;i>=0;i--){
c[i]=c[i]+carry1;
carry1=c[i]/10;
if(c[i]>=10) c[i]=c[i]%10;
}
if(carry+carry1) cout<<carry+carry1;
for(int i=0;i<t;i++) cout<<c[i];
return 0;
}解法2：补坑
G Binbin's string
题目描述
给你两字符串a和b,对字符串a进行操作，每一次操作可在字母后面插入一段字符串或者删除长度一定的字符串，求a变b的最少操作次数，如果要插入字符串开头，只要在第0个位置之后插入即可
解题思路
这里只要最多只要2步就可以满足要求，1删除字符串，2加入字符串b
所以只要考虑操作次数为1的情况：即a字符串只要删除或者插入一段字符串就可以满足条件
a==b,答案为0
所以只要判断一下情况就可以
代码实现
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
int main() {
string a,b;
cin>>a>>b;
int k=a.length()-b.length();
if(a==b) cout<<0<<endl;
else if(a!=b&&k==0) cout<<2<<endl;
else if(k>0) {
int x=-1;
for(int i=0; i<b.length(); i++) {
if(a[i]!=b[i]) {
x=i;
break;
}
}
if(x==b.length()) cout<<1<<endl;
else {
for(int i=x; i<b.length(); i++) {
if(a[i+k]!=b[i]) {
cout<<2<<endl;
return 0;
}
}
cout<<1<<endl;
}
}
else if(k<0){
int x=-1;
for(int i=0; i<a.length(); i++) {
if(a[i]!=b[i]) {
x=i;
break;
}
}
if(x==a.length()) cout<<1<<endl;
else {
for(int i=x; i<a.length(); i++) {
if(a[i]!=b[i-k]) {
cout<<2<<endl;
return 0;
}
}
cout<<1<<endl;
}
}
return 0;
}I Binbin and Balls
题目描述
给你两个球，可任意选择楼层扔下去，球可能碎或不碎，若球碎掉不可再次使用，在最坏的情况下，求至少扔几次才能找到最大的X层，即从X层丢下去球不碎。
解题思路
这道题实际上是一个等差数列求和，可二分求满足条件的最高层数。
注意到只有两个球，那么如果第一个球碎了，第二个球只能从最低
的楼层开始往.上试。假设最少需要扔T次，那么最好的选择应该是这
样的:
第一次从T楼往下扔，如果碎了说明答案在1到T-1之间;
第二个球从1楼开始扔，总共不超过T次一定能找到答案;
如果没碎，第二次从T+T-1楼往下扔，同理，碎了说明答案在T~2T-2之间;
没碎就从T+T-1+T-2楼往下扔.....
那么，这样的策略最多能保证覆盖前T(T+1)/2楼。所以只需要保
证T(T+1)/2的值>=n，即保证这样的策略能得到前n楼的答案即可。二分
查找最小满足条件的T就是答案。也可以根据等差数列求和公式求T，非整数向上取整即可，可画图理解。
代码实现
等差数列求和公式，求根公式
#include<algorithm>
#include<iostream>
#include<string>
#include<math.h>
typedef long long ll;
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
ll n,sum;
cin>>n;
sum=ceil((sqrt(8*n+1)-1)/2);
cout<<sum<<endl;
}
return 0;
}二分查找
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll l=1,r=2e9;
while(l<r){
ll mid=l+r>>1;
if(mid*(mid+1)/2LL>=n) r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
return 0;
}
L Cracked Pipes
题目描述
给你一个n*m的水管图，水管类型一共六种，（1,0）为起点，（n,m+1)为终点，判断水是否能从该水管的起点流到终点。
解题思路
第一个想到的就是深搜，然后根据水管类型来判断这条路是否能通，比赛的时候这题都没来得及看。。。看了好几篇题解，有几个的东西：
水管向上：1 2 4 5 对3取模：1，2
水管向下：1 3 6 对3取模：1，0
水管向左：2 4 5 6（非1，3）
水管向右：2 3 5 6 对3取模：2，0
其次是存图，很多题解好像都是二维存图，但是有一个存图是用一维存图，很巧妙，具体细节看代码理解。
最后判断一下（n,m+1)处水管的方向即可。
代码实现
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
int f[1<<19],t[1<<19],n,m;
void dfs(int x){
if(f[x]) return;
f[x]=1;
int i=x/m,j=x%m;
if(i>0&&(t[x]%3==1||t[x]==5)&&(t[x-m]==1||t[x-m]%3==0))
dfs(x-m);
if(i<n-1&&(t[x]==1||t[x]%3==0)&&(t[x+m]%3==1||t[x+m]==5))
dfs(x+m);
if(j>0&&(t[x]!=1||t[x]!=3)&&(t[x-1]%3!=1))
dfs(x-1);
if(j<m-1&&t[x]%3!=1&&(t[x+1]!=1||t[x+1]!=3))
dfs(x+1);
}
int main(){
cin>>n>>m;
for(int i=0;i<n*m;i++) cin>>t[i];
if(t[0]==1||t[0]==3){
cout<<"NO";
return 0;
}
dfs(0);
if(f[n*m-1]&&t[n*m-1]%3!=1){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
return 0;
}J Yuki with playf
H Professor Yang's Homework
待补
查看1道真题和解析
