化简分数

#include<bits/stdc++.h>
using namespace std;
const int N=500;

int gcd(int a,int b){
    //if(a>b) swap(a,b);
    if(a%b==0) return  b;
    else return gcd(b,a%b);
}
int main(){
    int a,b,c,d,e,f;
    int t;
    cin>>t;
    while(t--){
        cin>>a>>b>>c>>d;
        e=a*d+b*c;
        f=d*b;
        int ee=e,ff=f;
        if(e>f) swap(e,f);
        ee=ee/gcd(e,f);
        ff=ff/gcd(e,f);
        printf("%d %d\n",ee,ff);
    }
    return 0;
}

codeforce round 714 A

题意：
给你一个数字n，表示数字1~n；k表示要构造的山峰的个数；山峰即表示中间那个数要大于它左边的那个数也要大于它右边的那个数，即 ,如果能够构造出数组则输出该数组，不能的话，输出“-1”。

思路：
我们可以选取前k大的数作为山峰；其他的1~n-k作为山谷，那么什么时候是不能构造的时候呢，明显可以知道，党山峰过多的时候，是构造不来这样的数组的，即： .

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
     int tests;
     cin>>tests;
     while(tests--)
     {
         int n,k;
         cin>>n>>k;
         vector<int> ans(n+1);
         int num=n;
         for(int i=2;i<n;i+=2)
         {
              if(k==0)break;
              ans[i]=num--;
              k--;
         }
         cout<<k<<endl;
         if(k)
         {
             cout<<-1<<endl;
             continue;
         }
         int cur=1;
         for(int i=1;i<=n;i++)
         {
             if(!ans[i])
             ans[i]=cur++;
         }

         for(int i=1;i<=n;i++)
         cout<<ans[i]<<" ";
         cout<<endl;
     }
}

力扣236周赛 B题

亚瑟夫成环问题

思路：比较容易想到的思路是用vector模拟整个过程
代码：

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> a(n);//这里在力扣上好像必须设置它的长度，不然就会报错。
        for(int i=0;i<n;i++){
            a[i]=i+1;
        }
        int t=0;
        while(a.size()>1){
            t=(t+k-1)%a.size();
            a.erase(a.begin()+t);
        }
        return a[0];
    }
};

另一种方法就是递推，有点不太理解；

代码：

int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}

//或者
int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}