湖南大学程序设计竞赛新生赛（重现赛）
题目链接—点我开启传送门哦！ A.题意：就是求任意两个斐波那契数列的最大公约数！
思路：一开始俺是照着题意来的，但是不是超时就是内存超限什么的，估计很多人也是被这样困了很久，然后你会发现一个很奈斯的条件你没有用到啊！！GCD（m,n）=< 45. 然后你列出前几项，发现先求m,n的最大公约数然后求其最大公约数的斐波那契，与分别求m,n的斐波那契然后求最大公约数答案竟然是一样的！！！（我也不知道原理呀，知道请告诉我）。 然后就easy了吧。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int t;
LL n,m,a[50];
int main()
{
a[0]=0,a[1]=1,a[2]=1;
for(int i=2;i<=45;i++)
{
a[i]=a[i-1]+a[i-2];
}
cin>>t;
while(t--)
{
cin>>m>>n;
cout<<a[__gcd(m,n)]<<endl;
}
return 0;
}B.题意：就是找到满足bb - aa = cc - bb；
思路：给了你a，那么你要找到一组满足条件的值，可以设b = xa; c = ya;(y>x)。然后带入，随后从1开始，枚举尝试，发现b = 5a，c = 7a的时候有一组解。负数只需加个负号即可，其余不满足输出“-1”，数据还是比较水的，并没有涉及不满足的情况。
# include<iostream>
using namespace std;
int main ()
{
long long A;
cin>>A;
if(A==0)cout<<"-1"<<endl;
if(A>0)
cout<<5*A<<" "<<7*A<<endl;
else
cout<<-5*A<<" "<<-7*A<<endl;
}C.题意：就是一个由三个字符组成的迷宫，可以任意降落在迷宫随机两个点。可以向上下左右四个方向行走，然后其中有一个字符代表金钱，求能得到的最大的金钱！（好让他买小裙子穿）
思路：dfs，
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define make_pair(x,y) P(x,y)
using namespace std;
typedef long long ll;
typedef pair<string,ll> P;
char res[505][505];
bool vis[505][505];
int n,m;
int dix[4]={0,-1,1,0};
int diy[4]={1,0,0,-1};
int w=0;
void dfs(int a,int b)
{
if(res[a][b]=='$')
w++;
for(int i=0;i<4;i++)
{
int dx=a+dix[i];
int dy=b+diy[i];
if(dx>=0&&dx<=n+1&&dy>=0&&dy<=m+1&&!vis[dx][dy])
{
if(res[dx][dy]!='#')
{
vis[dx][dy]=true;
dfs(dx,dy);
}
}
}
return ;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>res[i][j];
}
vector<int>ans;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!vis[i][j]&&res[i][j]!='#')
{
w=0;
vis[i][j]=true;
dfs(i,j);
ans.push_back(w);//存入每次的金钱
}
sort(ans.begin(),ans.end());//排序
int k=2;
int sum=0;
for(int i=ans.size()-1;i>=0;i--)//取前两次最大的相加
{
sum+=ans[i];
k--;
if(k==0)
break;
}
cout<<sum;输出maxmoney
}D.题意：就是四级考试小明同学去参加，问题有n个，然后第二行是每个问题他蒙上的答案，第三行是答案中 A ,B ,C ,D的个数。如果存在情况一个都没有蒙对，那么则输出orz,否则则输出最小蒙对的个数。
思路：可以试想，如果蒙的个数（比如A）加上答案中的个数（A）若大于n,那么大于的部分就是即为蒙对的A的个数。同理可以得到B,C,D分别蒙对的个数。那么加起来就是min的个数，反之，小于等于那么存在全蒙错的情况。（思维题~~）
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
string s;
int A=0,B=0,C=0,D=0;
int a,b,c,d;
cin>>n>>s>>a>>b>>c>>d;
for(int i=0;i<n;i++){
if(s[i]=='A') A++;
if(s[i]=='B') B++;
if(s[i]=='C') C++;
if(s[i]=='D') D++;
}
if (A + a <= n && B + b <= n && C + c <= n && D + d <= n)
cout << "orz" << endl;
else
{
int min = 0;
if (A + a > n)min += A + a - n;
if (B + b > n)min += B + b - n;
if (C + c > n)min += C + c - n;
if (D + d > n)min += D + d - n;
cout << min << endl;
}
return 0;
} E. 题意：就是给一个星期几，然后给俩个数N,M，求N的M次方后的那一天是星期几。
思路：乍一看题，让啊我来做的话，肯定快速幂对7取余无疑！
#include<bits/stdc++.h>
using namespace std;
int cf(string str,int mod)
{
int ans=0;
for(int i=0; i<str.size(); i++)
ans=(ans*10+str[i]-'0')%mod;
return ans;
}
int main ()
{
string s;
while (cin>>s)
{
long long n,a;
string m;
cin>>m>>n;
if (s=="Mon") a=1;
else if (s=="Tue") a=2;
else if (s=="Wed") a=3;
else if (s=="Thu") a=4;
else if (s=="Fri") a=5;
else if (s=="Sat") a=6;
else if (s=="Sun") a=7;
if (a>7) a%=7;
if (a==1) cout<<"Mon"<<endl;
else if (a==2) cout<<"Tue"<<endl;
else if (a==3) cout<<"Wed"<<endl;
else if (a==4) cout<<"Thu"<<endl;
else if (a==5) cout<<"Fri"<<endl;
else if (a==6) cout<<"Sat"<<endl;
else if (a==7) cout<<"Sun"<<endl;
}
return 0;
}F.题意：就是给n个坐标点，求这n个坐标点是否在同一条直线上，如果在那么就输出Yes，否则就输出No。即为求n个坐标的k是否相等！
思路：首先数据没范围，咱们就尽可能的开大，然后就是存点，如果只存在一组或者两组坐标点，那么肯定在一条直线上。否则先由前两组点确定一个K值，然后遍历即可！
#include<bits/stdc++.h>
#define maxn 12345678
using namespace std;
struct node{
int x;
int y;
}a[maxn];
int main(){
ios::sync_with_stdio(false);
int n;
cin>>n;
if(n==1||n==2) cout<<"Yes"<<endl;
else{
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].y;
}
int flag =1;
int dx = a[1].x-a[0].x;
int dy = a[1].y-a[0].y;
for(int i=2;i<n;i++){
int nx = a[i].x-a[0].x;
int ny = a[i].y-a[0].y;
if(dx*ny != dy*nx){
cout<<"No"<<endl;
flag = 0;
break;
}
}
if(flag)cout<<"Yes"<<endl;
}
return 0;
}G. 题意：就是小帅同学发了一笔奖学金吧，然后他脑子抽了很想买钥匙，一个钥匙三块，三个钥匙打折10块（咱也不知道，咱也不敢问）。然后他看见钱就恶心，所以想把所有的钱都买成钥匙。但是呢，钥匙又太沉，他不愿意带很多，所以在要你设计程序求把恶心的钱花干净的情况下买最少的钥匙的数量！如果剩下了钱，他会十分恶心，输出“orz”；
思路：哪较多的钱买少的钥匙自然为最好，这种情况的适用只针对n是10的倍数，此时的话钱多，钥匙少。很容易理解·~
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
while(n>=3){
if(n % 10 == 0){
sum += (n/10)*3;
n = 0;
}
else{
sum++;
n -= 3;
}
}
if(n !=0){
cout<<"orz"<<endl;
}
else{
cout<<sum<<endl;
}
return 0;
}H 题意：欢迎来到++赌场，你妻离子散，所以决定用全身家当去堵一场！老板看你身姿魁梧，所以让你签了卖身契得到了一份你jio的很满足的一笔份额不少的money.~~ 赢了你压上的钱翻倍，输的话嘿嘿嘿！！ 所以你非常想赢，你就想出了这样的方法，第一次少压点，赢得话将钱翻倍去压下一次，如果你一直赢，那么你就一直翻倍，否则的话就不玩了~（实在是怕输啊） 然后你忽然想起你原来是个程序员，你旁边有台电脑，amazing,那么你想知道你回本的可能性有多大！（注意输出格式！）
思路：很简单的概率问题
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
double sum=0.0;
double res=1.0;
for(int i=1;i<=n;i++){
res*=0.50;
sum+=res;
}
printf("%.4lf\n",sum);
}
return 0;
} I.题意：
意思就是你天天熬夜打ACM，加上各种作息不良，你终于倒在ACM的前线。可惜，在为你叫来“俺不能死”的时候，他的脑子被你这种拼搏的精神感动了，由于情绪过于激动，他烧坏了脑子。 现在车上的人很慌，要把线接通。就是A中的第i条线连接B中的第A[i]条线，好在A中的线是N的一个排列（可以认为是从1到n）。
思路：用全部的排列次数然后减去错排的次数，得到的就是能接通的次数。
#include<bits/stdc++.h>
#define maxn 100010
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll a[maxn];
ll b[maxn];
int main()
{
a[0]=1;
for(ll i=1;i<=100000;i++)//全部
a[i]=a[i-1]*i%mod;
b[1]=0;b[2]=1;
for(ll i=3;i<=100000;i++)//错排
b[i]=(i-1)*(b[i-1]+b[i-2])%mod;
int n;
cin>>n;
int x;
for(int i=0;i<n;i++)
cin>>x;
ll ans=a[n]-b[n]+mod;
ans%=mod;
cout<<ans<<endl;
}J.题意：就是好几堆糖，然后两个人想买完，但是又一下子没那么多钱，所以每天用零花钱去买，Da只能买一堆中的偶数个（因此少于两个，Da就在那天不会买了），Tu只能买一堆中的奇数个。谁买到最后一颗糖，就算谁赢。
思路：写的没过，很怀疑没看懂题。然后大佬的代码是这样的，让我不由想哭，
那么假设有这样的一组数据， 3 8 9 8 Da 第一天把第一堆都拿走，Tu第二天把第二堆都拿走，Da第三天把第三堆都拿走。那么这个代码是怎么通过的呢！！！求指导
#include <iostream>
typedef long long ll;
using namespace std;
ll a[500001];
int main()
{
int N;
cin>>N;
int n=N;
for(int i=0;i<N;i++)
cin>>a[i];
if((n==1)&&(a[0]%2==0))
cout<<"DaDa"<<endl;
else
cout<<"TuTu"<<endl;
return 0;
}K.不懂~
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
ll read(){
ll f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
struct arr{
int atk,d;
char we;
}a[maxn],b[maxn];
int n,m;
int dp[1010][1010];
bool cmp(char a,char b){
if(a=='S' && b=='B')return 1;
if(a=='D' && b=='S')return 1;
if(a=='B' && b=='D')return 1;
return 0;
}
bool check(arr a,arr b){
if(cmp(a.we,b.we))return a.atk>=b.atk*2;
if(cmp(b.we,a.we))return a.atk*2>=b.atk;
return a.atk>=b.atk;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%s",&b[i].atk,&b[i].we);
for(int i=1;i<=m;i++)scanf("%d%d%s",&a[i].atk,&a[i].d,&a[i].we);
for(int i=1;i<=m;i++)
for(int j=n;j>=1;j--)
if(check(a[i],b[j]))
dp[i][j]=min(dp[i][j+1]+1,a[i].d);
int ans=0,pos=1,flag=1;
while(pos<=n){
int tot=0;
for(int i=1;i<=m;i++)
tot=max(tot,dp[i][pos]);
if(!tot){
flag=0;
break;
}
ans++;
pos+=tot;
}
if(!flag)puts("ManShenChuangYi");
else printf("%d\n",ans);
return 0;
}L.题意：就是素数筛选，求在一个区间里面的素数个数！
思路：水题~
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e9;
int judge(int x)
{
if(x == 0) return 0;
for(int i=2;i<=sqrt(x);++i)
{
if(x%i == 0) return 0;
}
return 1;
}
int main()
{
int L,R,num = 0;
cin>>L>>R;
for(int i=L;i<=R;++i)
{
if(judge(i) == 1) num++;
}
cout<<num<<endl;
}M.题意：就是给一个区间，求之间所有数的异或，然后输出结果。
思路：直接循环异或的话肯定是很不合理的，然后我们在纸上推理得到，从0开始，每连续的四个数字的异或和为0。所以找规律就行。
#include<bits/stdc++.h>
typedef long long ll;
ll a, b;
ll f(ll x) //从0开始（包括0），每连续的4个数的 异或和 为0
{
if(x % 4 == 0) //位于4个数中的第一位
return x;
else if(x % 4 == 1) //位于4个数中的第二位
return 1;
else if(x % 4 == 2) //位于4个数中的第三位
return x + 1;
else if(x % 4 == 3) //位于4个数中的第四位
return 0;
}
int main()
{
cin>>a>>b;
cout<< f(b) ^ f(a - 1))<<endl;
return 0;
}