HZNU 2019 Summer training 10

A - Complicated GCD

 CodeForces - 664A 

题意：a 到 b 的最大公约数是多少

题解：a == b 答案即为 a，否则为1

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 2e2 + 10;
const int MOD = 1e9 + 7;

int main()
{
    string a,b;
    cin >> a;
    cin >> b;
    if(a == b)
        cout << a << endl;
    else
        cout << 1 << endl;
}
View Code

B - Spider Man

 CodeForces - 705B 

题意：给你n个数 两人游戏 若一方不能分解任何数（也就是全部被分解为1）则输

题解：计算不为 1 的数一共可以分解几次就可以了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;


int main()
{
   int n;
   scanf("%d",&n);
   LL tmp = 0;
   LL x;
   for(int i = 0; i < n; i++)
   {
       scanf("%lld",&x);
       tmp += (x - 1);
       if(tmp == 0)
           puts("2");
       else
       {
           if(tmp % 2 == 1)
               puts("1");
           else
               puts("2");
       }
   }
}
View Code

C - Catch Overflow!

 CodeForces - 1175B 

题意：给出for循环伪代码，计算执行add的次数（加了几次）。

题解：两个栈，一个记录for的次数，一个记录add的数字即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
const LL MAXX = (1LL<<32) - 1LL;
stack<LL>sta;
stack<LL>stb;
// 4294967296
int main()
{
   int n;

   scanf("%d",&n);
   //cout<<MAXX<<endl;
   string s;
   LL total = 0;
   LL num;
   int flag = 0;
   while(n--)
   {
       cin >> s;
       if(s == "add")
       {
           if(sta.size() == 0)
               total += 1;
           else
           {
               LL tmp = stb.top();
               stb.pop();
               tmp++;
               //cout<<tmp<<endl;
               stb.push(tmp);
           }
       }
       else if(s == "for")
       {
           scanf("%lld",&num);
           if(sta.size() == 0)
               sta.push(num);
           else
           {
               //cout<<sta.top() * num<<endl;
               if(sta.top () * num > MAXX)
                sta.push(MAXX * 2);
               else
                   sta.push(sta.top() * num);
           }
           stb.push(0);
       }
       else if(s == "end" && flag == 0)
       {
           LL tmp1 = sta.top();
           sta.pop();
           LL tmp2 = stb.top();
           stb.pop();
           //printf("%lld %lld
",tmp1,tmp2);
           total += tmp1 * tmp2;
           if(total > MAXX)
               flag = 1;
       }
       //cout<<total<<endl;
   }
   if(flag == 1 || total > MAXX)
       puts("OVERFLOW!!!");
   else
       printf("%lld
",total);
}
View Code

D - Maximal Area Quadrilateral

 CodeForces - 340B 

题意：一些点中去四个点形成四边形，求四边形的最大面积

题解：枚举两个点，寻求第三个点，用向量的乘积来计算面积

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 3e2 + 10;
const int MOD = 1e9 + 7;
const LL MAXX = (1LL<<32) - 1LL;

struct node{
    double x,y;
}p[MAXN];

double multi(node p1,node p2,node p3)
{
    double a1,b1,a2,b2;
    a1 = p2.x - p1.x;
    a2 = p3.x - p2.x;
    b1 = p2.y - p1.y;
    b2 = p3.y - p2.y;
    return a1 * b2 - a2 * b1;
}

int main()
{
    int n;
    double ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
        scanf("%lf %lf",&p[i].x,&p[i].y);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            double s1 = 0,s2 = 0;
            for(int k = 0; k < n; k++)
            {
                double tmp = multi(p[i],p[j],p[k]);
                if(tmp > 0)
                    s1 = max(s1,tmp / 2.0);
                else
                    s2 = max(s2,-tmp / 2.0);
            }
            if(s1 > 0 && s2 > 0 && s1 + s2 > ans)
                ans = s1 + s2;
        }
    }
    printf("%lf
",ans);
}
View Code

E - Two Arithmetic Progressions

 CodeForces - 710D 

题意：x 满足 L <= x <= R,并且 x = a1k + b1  = a2l + b2,(k ,l >= 0)，求x的个数有几个

题解：找出最小解后，其余的解就是加上 a1 和 a2 的最小公倍数即可，最小解的寻找可以使用扩展中国剩余定理写，也可以直接循环逼近，这里使用的是循环逼近最小解，即一开始a1 和 a2 都为0，然后使得小的一个加上该式中的a1或a2的某倍数后使得值大于等于另一个，以此循环，如果等于了就停止，不停止的话最多逼近100000次我限制的

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 3e2 + 10;
const int MOD = 1e9 + 7;
const LL MAXX = (1LL<<32) - 1LL;

LL gcd(LL a,LL b)
{
    return b == 0 ? a : gcd(b,a % b);
}

int main()
{
    LL a1,b1,a2,b2,L,R;
    cin >> a1 >> b1 >> a2 >> b2 >> L >> R;

    LL lcm = a1 * a2 / gcd(a1,a2) ;
    //cout<<lcm<<endl;

    LL tmp1 = b1,tmp2 = b2;
    int pos = 1e5;
    while(tmp1 != tmp2)
    {
        if (tmp1 < tmp2)
        {
            LL tmp = tmp2 - tmp1;
            tmp1 += ceil(tmp * 1.0 / (a1 * 1.0)) * a1;
        }
        else
        {
            LL tmp = tmp1 - tmp2;
            tmp2 += ceil(tmp * 1.0 / (1.0 * a2)) * a2;
        }
        pos--;
        if(pos == 0)
            break;
      //printf("%lld %lld
", tmp1, tmp2);
    }
    if(pos == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    L = max(L,max(b1,b2));
    if(L > R)
    {
        cout<<0<<endl;
        return 0;
    }
    LL ans = 0;
    if(tmp1 <= R)
        ans += (R - tmp1) / lcm + 1;
    if(tmp1 < L)
        ans -= (L - tmp1 - 1) / lcm + 1;
    cout << ans << endl;


}
View Code

F - Lucky Permutation

 CodeForces - 286A

题意：给了一个pi数组，ppi = n - i + 1，要求求出这个数组

题解：判断-1的情况，推一推就好了，之后两两交换，再头尾交换即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
const LL MAXX = (1LL<<32) - 1LL;

int a[MAXN];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if (n == 1)
            cout << 1 << endl;
        else if ((n / 2) % 2 == 1)
            cout << -1 << endl;
        else
        {
            for (int i = 1; i <= n; i++)
                a[i] = i;
            for (int i = 1; i <= n; i += 2)
            {
                if (n % 2 == 1 && i == (n + 1) / 2)
                    i++;
                swap(a[i], a[i + 1]);
            }
            for (int i = 2; i <= n / 2; i += 2)
                swap(a[i], a[1 + n - i]);
            for (int i = 1; i <= n; i++)
                printf("%d%c", a[i], i == n ? '
' : ' ');
        }
    }
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/smallhester/p/11178212.html