目录

题目连接:

A 跳台阶

• 题意：有一个n级台阶的楼梯，小明一次可以向上跳1步，两步，甚至是n步，请问小明跳到n级台阶有多少种跳法？

• 思路：类比于每次只能跳一个台阶或两个台阶，可以很容易的看出\(ans[i] = \sum_{j = 1}^{i}ans[j]\)

#include
    
     using namespace std;const int maxn = 1e5 + 10;typedef long long ll; char s[maxn]; ll ans[50]; int main() {    int n, T;    scanf("%d", &T);    while(T--) {        memset(ans, 0, sizeof ans);        scanf("%d", &n);        for(int i = 0; i <= n; i++) ans[i] = 1;        for(int i = 1; i <= n; i++) {            for(int j = 1; j < i; j++) { ans[i] += ans[j];  }        }        printf("%d\n", ans[n]);    }    return 0;}
    

B 跳一跳，很简单的

C 平分游戏

• 题目：：共有n位同学，他们都按照编号顺序坐在一个圆桌旁。第i位同学一开始有a[i]个硬币，他们希望使得每位同学手上的硬币变成相同的数目。每一秒钟，有且仅有一位同学可以把自己手上的一枚硬币交给另一位同学，其中这两位同学中间必须间隔k位同学。问最少几秒后所有同学手上的有相同数量的硬币

• 思路：首先分析座位是相邻的情况：
  • 假设最后每个人有M个硬币，所有人按顺序编号为1，2，3，...，n；
  • 对于第i(i<n)个人，他可以给第(i-1)个人\(x_{i+1}\)枚硬币，这里如果是第(i+1)个人给他，则\(x_{i+1}\)记为负数；同时，第(i+1)个人也可以给他\(x_{i}\)枚硬币，那么对于这个人，我们可以得到一个方程\(A_i - x_i + x_{i+1} = M\)，同样，对于其他人我们也可以得到这样的方程；最后我们可以得到n个方程，但是很遗憾，对于第n个人，\(A_n-x_n+x_1=M\)是个多余的方程， 我们可以通过前n-1个方程把它推出来；
  • 分析前n-1个方程， 对于第一个\(A_1 -x_1+x_2=M => x_2 = M - A_1+x_1 = x_1-C_1\)；对于剩下的n-2个方程，我们也可以得出类似的式子，那么题目要求的最小值就变成了求\(|x_1| + |x_1-C_1|+...+|x_1-C_{n-1}|\)的最小值，这里\(|x_1-C_i|\)即为数轴上点\(x_1\)到其他点的距离，直接取中位数就可以了。

然后是不相邻的情况：我们只需对每个人，找出它后面的人的硬币数，然后重新将他们放在一个数组里即可

#include
    
     using namespace std;typedef long long ll;const int maxn = 1e6 + 10;int a[maxn], vis[maxn];ll C[maxn];vector
     
       v;int main() {    int k, n;    while(~scanf("%d %d", &n, &k)) {        ll sum = 0;        for(int i = 0; i < n; i++) { scanf("%d", &a[i]); sum += a[i]; }        if(sum % n) { printf("gg\n"); continue; }        if(!sum) { printf("0\n"); continue; }        if(k >= n - 1) {            int fl = 0;            for(int i = 1; i < n; i++) if(a[i] != a[0]) fl = 1;            if(fl) printf("gg\n");            else printf("0\n");            continue;        }        ll M = sum / n, ans = 0;        int fl = 1;        memset(vis, 0, sizeof vis);        for(int i = 0; i < n; i++) {            int ind = i, cnt = 0;            ll tmp = 0;            if(vis[ind]) continue;            while(!vis[ind]) {                v.push_back(a[ind]);                cnt++;                vis[ind] = 1;                tmp += a[ind];                ind = (ind + k + 1) % n;            }            if(cnt * M != tmp) { fl = 0; break; }            C[0] = 0;            for(int j = 1; j < v.size(); j++) C[j] = C[j - 1] + v[j] - M;            sort(C, C + v.size());            ll x1 = C[v.size() / 2];            for(int j = 0; j < v.size(); j++) ans += abs(x1 - C[j]);            v.clear();        }        if(!fl) printf("gg\n");        else printf("%lld\n", ans);    }    return 0;}
     
    

D psd面试

• 题目：
• 思路：
  • 这题可以直接用动态规划写
  • 对于区间(i, j)，如果\(s[i] == s[j]\),那么有\(dp[i][j] = dp[i+1][j-1]+2\)， 如果\(s[i] != s[j]\)， 那么有\(dp[i][j] = max(dp[i+1][j], dp[i][j-1])\)；然后直接记忆化搜索一下就好，复杂度\(O(n^2)\)

#include
    
     using namespace std;const int maxn = 1300;typedef long long ll;int n;char s[maxn];int dp[maxn][maxn]; int lsp(int i, int j) {    if(i == j) return 1;    if(i > j) return 0;    if(dp[i][j]) return dp[i][j];    if(s[i] == s[j]) return dp[i][j] = lsp(i + 1, j - 1) + 2;    return dp[i][j] = max(lsp(i, j - 1), lsp(i + 1, j));} int main() {    while(~scanf("%s", s)) {        n = strlen(s);        for(int i = 0; i < n; i++) {            if(s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';        }        memset(dp, 0, sizeof dp);        printf("%d\n", n - lsp(0, n - 1));    }    return 0;}
    

E 回旋星空

• 题目：计算回旋图标的个数,即选中三颗星星,分别作为回旋图标的起点,拐点和终点,假设现在有三个星星分别为i,j,k,如果d(a[i],a[j]) == d(a[j],a[k])则表示找到了一个回旋图标,其中d(x,y)表示这两个点的欧氏距离为了给它很大的希望(i,j,k)和(k,j,i)被认为是两个不同的回旋图标.

• 思路：对于每个点，暴力它到其他点的距离，如果有n(n>=2)个相同距离的点， 那个ans+=n*(n-1)/2即可

#include
    
     using namespace std;const int maxn = 1e5 + 10;typedef long long ll;double EPS = 1e-10;struct P{    int x, y;    P() {}    P(int x, int y): x(x), y(y) {}} p[1005];map
     
       mp;int main() {    int T;    int n, m;    scanf("%d", &T);    while(T--) {        scanf("%d", &n);        for(int i = 0; i < n; i++) {            scanf("%d %d", &p[i].x, &p[i].y);        }        ll ans = 0;        for(int i = 0; i < n; i++) {            mp.clear();            for(int j = 0; j < n; j++) {                ll len = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);                mp[len]++;            }            map
      
       ::iterator it;            for(it = mp.begin(); it != mp.end(); it++) {                if(it -> second < 2) continue;                ans += 1LL * (it -> second - 1) * it -> second;            }        }        if(!ans) printf("WA\n");        else printf("%lld\n", ans);    }    return 0;}
      
     
    

F 等式

• 题意：

• 思路：

#include
    
     using namespace std;char s[1500];int main() {    int T, n;    scanf("%d", &T);    while(T--) {        scanf("%d", &n);        int ans = 1;        for(int i = 2; i * i <= n; i++) {            int num = 0;            while(n % i == 0) { n /= i; num++; }            ans = ans * (num << 1 | 1);            if(n == 1) break;        }        if(n > 1) ans *= 3;        printf("%d\n", (ans >> 1) + 1);    }    return 0;}
    

G 旋转矩阵

• 题意：

• 思路：

#include
    
     using namespace std;const int maxn = 1e5 + 10;typedef long long ll;double EPS = 1e-10; char s[50][50];char op[maxn]; int main() {    int T;    int n, m;    scanf("%d", &T);    while(T--) {        scanf("%d %d", &n, &m);        for(int i = 0; i < n; i++) scanf("%s", s[i]);        scanf("%s", op);        int len = strlen(op), cnl = 0, cnr = 0;        for(int i = 0; i < len; i++) {            if(op[i] == 'L') cnl++;            if(op[i] == 'R') cnr++;        }        cnl %= 4;        cnr %= 4;//        printf("cnl = %d cnr = %d\n", cnl, cnr);        if(cnl == cnr) {            printf("%d %d\n", n, m);            for(int i = 0; i < n; i++) printf("%s\n", s[i]);        } else if(cnl - cnr == 2 || cnr - cnl == 2) {            printf("%d %d\n", n, m);            for(int i = n - 1; i >= 0; i--) {                for(int j = m -1; j >= 0; j--) printf("%c", s[i][j]);                printf("\n");            }          } else if(cnl - cnr == 1 || cnr - cnl == 3) {            printf("%d %d\n", m, n);            int cnt = 0;            for(int j = m- 1; j >= 0; j--) {                for(int i = 0; i < n; i++) {                    if(s[i][j] == '-') printf("|");                    else if(s[i][j] == '|') printf("-");                    else printf("%c", s[i][j]);                }                printf("\n");            }        } else if(cnl - cnr == 3 || cnr - cnl == 1) {            printf("%d %d\n", m, n);            for(int j = 0; j < m; j++) {                for(int i = n - 1; i >= 0; i--) {                    if(s[i][j] == '-') printf("|");                    else if(s[i][j] == '|') printf("-");                    else printf("%c", s[i][j]);                }                printf("\n");            }        }        printf("\n");    }    return 0;}
    

H 哲哲的疑惑

I 填空题

• 题意：略

• 思路：输出"ac"即可

#include
    
     using namespace std; int main() {    int n, T;    printf("ac\n");    return 0;}
    

J 强迫症的序列

• 题意：

• 思路：

#include
    
     using namespace std;const int maxn = 1e5 + 10;typedef long long ll; char s[maxn]; ll ans[50];int a[maxn]; int main() {    int n, T;    scanf("%d", &T);    while(T--) {        scanf("%d", &n);        int mx = 1000000;        ll ans = 0, sum = 0;        for(int i = 0; i < n; i++) { scanf("%d", &a[i]);  mx = min(mx, a[i]); sum += a[i]; }        for(int i = 0; i < n; i++) ans += a[i] - mx;        printf("%lld %lld\n", ans, (sum + ans * (n - 1)) / n);    }    return 0;}
    

K 密码

• 题意：

• 思路：

#include
    
     using namespace std;const int maxn = 1e5 + 10;typedef long long ll;double EPS = 1e-10; char s[50][50];char op[maxn];vector
     
       v; int main() {    int T;    int n, m;    scanf("%d", &T);    while(T--) {        scanf("%d", &n);        scanf("%s", op);        v.clear();        if(n == 1) {            printf("%s\n", op);            continue;        }        int d = 2*(n-1), len = strlen(op);        for(int i = 0; ; i++) {            v.push_back(d * i);            if(d * i > len) break;        }//        printf("d = %d\n", d);        for(int i = 0; i < v.size(); i++) if(v[i] < len) printf("%c", op[v[i]]);        for(int i = 0; i < n - 2; i++) {            for(int j = 0; j < v.size(); j++) {                int ind = v[j] + (i + 1), inds = v[j] - (i + 1);                 if(inds < len && inds >= 0) printf("%c", op[inds]);                if(ind < len && ind >= 0) printf("%c", op[ind]);            }        }        for(int i = 0; i < v.size(); i++) if(v[i] + n - 1 < len) printf("%c", op[v[i] + n- 1]);        printf("\n");    }    return 0;}
     
    

L 用来作弊的药水

• 题意：

• 思路：

#include
    
     using namespace std;const int maxn = 1e5 + 10;typedef long long ll;  char s[maxn];  ll ans[50];int p[maxn], vis[maxn];ll x, a, y, b;int cnt = 0;  void init() {    int m = sqrt(maxn + 0.5);    for(int i = 2; i <= m; i++) {        if(!vis[i]) {            for(int j = i * i; j < maxn; j += i)                vis[j] = 1;        }    }    for(int i = 2; i < maxn; i++) {        if(!vis[i]) p[cnt++] = i;    }}  int p1[maxn/10], p2[maxn/10];  int main() {    int n, T;    init();//    for(int i = 0; i < 10; i++) printf("%d ", p[i]);//    printf("%d\n", cnt);    scanf("%d", &T);    while(T--) {        scanf("%lld %lld %lld %lld", &x, &a, &y, &b);        memset(p1, 0, sizeof p1);        memset(p2, 0, sizeof p2);        for(int i = 0; i < cnt; i++) {            while(x % p[i] == 0) { p1[i]++; x /= p[i]; }        }        for(int i = 0; i < cnt; i++) {            while(y % p[i] == 0) { p2[i]++; y /= p[i]; }        }        int fl = 1;        if(x != y) fl = 0;        if(x == y && x != 1 && a != b) fl = 0;//        printf("x = %lld y = %lld\n", x, y);        for(int i = 0; i < cnt; i++) {            if(a * p1[i] != b * p2[i]) { fl = 0; break; }        }        if(fl) printf("Yes\n");        else printf("No\n");    }    return 0;}