2019年湘潭大学新生趣味程序设计竞赛

整场比赛都是一些数学题和构造思维题。比较适合锻炼自己逻辑思维能力

G：

一个边长n和m的矩形光滑平面，其边分别平行于坐标走轴，一个小球（视为一个质点），从左上角沿45度方向弹出，小球遇到平面的边时会发生完全弹性碰撞（入射角等于出射角）。

请问小球在碰撞多少次边以后能到达右下角？

这个结论如果有会证明的请在这个博客下留言～感激！！！

结论： 

首先对 m 和 n 进行化简（利用gcd） ，当 m 和 n 都是奇数的时候可以弹到右下角，需要 m + n - 2 次

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

const int maxn = 5e5 + 10;
const LL MOD = 998244353;

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}


int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        int x=std::__gcd(n,m);
        n/=x,m/=x;
        if(n%2==1 && m%2==1)printf("%d
",(n + m - 2));
        else puts("-1");
    }
    return 0;
}

H：

因为 n 的范围的限制所以我们可以全部都使用没有次数限制的字符进行构造。

首先就都用单独的一个字符去构造回文串，然后其余的就让其他字符随机出现就好了

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

const int maxn = 5e5 + 10;
const LL MOD = 998244353;

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

int vis[30];
std::vector<char> vec;
char ch[2];


int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        memset(vis,0, sizeof(vis));
        vec.clear();
        int n,x,y,len;
        scanf("%d%d%d%d",&n,&len,&x,&y);
        for (int i = 1;i <= n;i++) {
            scanf("%s %d",ch,&y);
            vis[ch[0]-'a'] = 1;
        }
        for (int i = 0;i < 26;i++)
            if (!vis[i])
                vec.push_back(i+'a');
        for (int i = 1;i < x;i++)
            printf("%c",vec[0]);
        int pos = 0;
        len -= x-1;
        while (len--) {
            printf("%c",vec[pos]);
            pos++;
            if (pos == vec.size())
                pos = 0;
        }
        printf("
");
    }
}

J:

给定一个整数A。
求是否存在两个整数B,C使得长度为A,B,C的三条边可以组成一个直角三角形。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

const int maxn = 5e5 + 10;
const LL MOD = 998244353;

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}


int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        LL a;
        scanf("%lld",&a);
        if ((a * a + 1) % 2 == 0 && (a * a - 1) % 2 == 0) {
            printf("%lld %lld
",(a * a + 1) / 2,(a * a - 1) / 2);
        }
        else
            printf("%lld %lld
",(a * a / 4) + 1,(a * a / 4) - 1);
    }
    return 0;
}