PAT 520 钻石争霸赛 2021(100)

文章目录

• 总结
• • 7-5 大勾股定理
  • • 题意
    • 思路
    • 小结
    • 解法1 - 数学 - 待检验
    • 解法2 - 二分 - 待检验
    • 题目
    • 输入格式：
    • 输出格式：
    • 输入样例：
    • 输出样例：
  • 7-7 约会大作战
  • • 题意
    • 思路
    • 题解 - 待检验
  • 7-6 矩阵列平移
  • • 思路
    • 解法1 - AC
  • 7-8 浪漫侧影
  • • 思路
    • 题解
  • 7-1 自动编程
  • 7-2 加油冲鸭
  • 7-3 520的表白
  • 7-4 奇葩楼层

总结

5、7题没AC。
前4题简单，10min内搞定。第五题卡了25min没AC。6题11min较简单，不熟悉顺序表的插入删除操作。8题12min，简单板子题。7题7min到时间了，10min过的样例。5题卡了25min，差1分。
#大勾股定理

7-5 大勾股定理

25min 14/15

题意

给定数字n，总能找到一个等式形式如下： s 2 + . . . + ( s + n ) 2 = ( s + n + 1 ) 2 + . . . + ( s + 2 ∗ n ) 2 s^2 +...+ (s+n)^2 = (s+n+1)^2+...+(s+2*n)^2 s2+...+(s+n)2=(s+n+1)2+...+(s+2∗n)2
要求找到并输出。

思路

正确思路：

• 根据给定公式进行数学简化，找到s与n的关系。
• 直接输出即可。
  错误思路：
• 相当于有数列 A s = [ ( s 2 + . . . + ( s + n ) 2 ) ] − [ ( s + n + 1 ) 2 + . . . + ( s + 2 ∗ n ) 2 ] A_s = [(s^2 +...+ (s+n)^2)] - [(s+n+1)^2+...+(s+2*n)^2] As​=[(s2+...+(s+n)2)]−[(s+n+1)2+...+(s+2∗n)2]
  • 求 A s = 0 A_s = 0 As​=0
  • 而 A s + 1 = A s − s 2 + 2 ∗ ( s + n + 1 ) 2 − ( s + 2 ∗ n + 1 ) 2 A_{s+1} = A_s - s^2 + 2*(s+n+1)^2 - (s+2*n+1)^2 As+1​=As​−s2+2∗(s+n+1)2−(s+2∗n+1)2
  • A s + 1 − A s = 4 s ( n + 1 ) + 2 ( n + 1 ) 2 − 2 ( s ( 2 n + 1 ) ) − ( 2 n + 1 ) 2 A_{s+1} - A_s= 4s(n+1)+2(n+1)^2 - 2(s(2n+1))-(2n+1)^2 As+1​−As​=4s(n+1)+2(n+1)2−2(s(2n+1))−(2n+1)2
    = 4sn + 4s + 2n2 + 4n + 2 -4sn - 2s - 4n2 - 4n - 1
    = 2s + 1 - 2n^2
  • A_1 = 1+…+n^2
• 遍历找满足条件As即可.

小结

• 能用数学方法简化的一定要先考虑用数学方法简化。
• 开始被卡时间，想到滑动窗口，就每次s++时 − s 2 + 2 ∗ ( s + n + 1 ) 2 − ( s + 2 ∗ n + 1 ) 2 - s^2 + 2*(s+n+1)^2 - (s+2*n+1)^2 −s2+2∗(s+n+1)2−(s+2∗n+1)2 。但是仍然TLE。思考可能pow用多了，于是先用f数组存所有下标对应平方，但是MLE了。
• 这时候想折个中，一半f数组，一半pow函数。这种思想是不对的，只是可以骗分，也没过14分。
• 交卷后考虑到可以二分，算了一下时间应该会短些。

解法1 - 数学 - 待检验

#include
using namespace std;
#define int long long
signed main(){int n, i, j; cin>>n;for(i = n * (2 * n + 1), j = 1; j <= n + 1; i ++, j ++){printf("%lld^2", i);if(j != n + 1) printf(" + "); }printf(" =\n");for(int j = 1; j <= n; i++, j ++){printf("%lld^2", i);if(j != n) printf(" + ");}return 0;
}

解法2 - 二分 - 待检验

#include
using namespace std;
#define int long long
int n, s, f[5000000], l, r;
int cmp(int s){int l = 0, r = 0;for(int i = s; i <= s + n; i ++)l += pow(i, 2);for(int i = s + n + 1; i <= s + 2 * n; i ++)r += pow(i, 2);if(l < r) return 1;else if(l > r) return 3;else return 2;  
}
signed main(){cin>>n;int l = 1, r = 10000000000;while(l <= r){int m = l + r >> 1;int ptr = cmp(m);if(ptr == 1) l = m + 1;else if(ptr == 3) r = m - 1;else{s = m;break;}}for(int i = 0; i <= n; i ++){if(i) printf(" + ");printf("%d^2", i + s);}cout<<" =\n";for(int i = n + 1; i <= 2 * n; i ++){if(i != n + 1) printf(" + ");printf("%d^2", i + s);}return 0;
}

题目

大勾股定理是勾股定理的推广：对任何正整数 n 存在 2n+1 个连续正整数，满足前 n+1 个数的平方和等于后 n 个数的平方和。例如对于 n=1 有  3 2 + 4 2 = 5 2 3^2+4^2=5^2 32+42=52；n=2 有  1 0 2 + 1 1 2 + 1 2 2 = 1 3 2 + 1 4 2 10^2+11^2+12^2=13^2+14^2 102+112+122=132+142 等。给定 n，本题就请你找出对应的解。

输入格式：

输入在一行中给出正整数 n（≤ 1 0 4 10^4 104）。

输出格式：

分两行输出满足大勾股定理的解，格式如下：

a[0]^2 + a[1]^2 + ... + a[n]^2 =
a[n+1]^2 + ... + a[2n]^2

其中解的数列 a[0] ... a[2n] 按递增序输出。注意行首尾不得有多余空格。

输入样例：

3

输出样例：

21^2 + 22^2 + 23^2 + 24^2 =
25^2 + 26^2 + 27^2

7-7 约会大作战

7min 1/20, 10min过样例

题意

给定两组人的人员数量n、m，和询问数q。
然后给出矩阵a[n][m] 和 b[m][n]表示两组对对方好感度分别为多少。
最后给出q组询问对，问哪几对能匹配成功。

思路

• 记录n、m、q。矩阵存在a、b中。
• 然后循环q次：
  • 首先判断两个人是否有人出去了，出去则匹配失败，continue
  • 记录成员前两次约会次数在cnt1[101], cnt2[101]以及对这两次进行最大值更新mp1[101], mp2[101]
  • 匹配成功则两个人出去，out1[101], out2[101]中记录。

题解 - 待检验

#include
using namespace std;
int n, m, q,x, y, a[101][101], b[101][101], cnt1[101], cnt2[101], num, mp1[101], mp2[101], out1[101], out2[101];
int main(){cin>>n>>m>>q;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin>>a[i][j];for(int i = 1; i <= m; i ++)for(int j = 1; j <= n; j ++)cin>>b[i][j];for(int i = 0; i < q; i ++){cin>>x>>y;if(out1[x] || out2[y]) continue;bool f = true;if(cnt1[x] < 2){f = false;cnt1[x]++;mp1[x] = max(mp1[x], a[x][y]);}if(cnt2[y] < 2){f = false;cnt2[y]++;mp2[y] = max(mp2[y], b[y][x]);}if(f == true){num ++;cout<<x<<' '<<y<<endl;out1[x] = true;out2[y] = true;}}if(num == 0) puts("PTA is my only love");return 0;
}

7-6 矩阵列平移

11min

思路

• 数组存入int f[N][N]。int ptr记录偏移量。
• 将每列看做一个顺序表，遍历偶数个列，计算偏移量，向下偏移，然后对前偏移量个元素赋值为x。
  • 计算偏移量：从1-k循环。
• 然后循环每行、每列，计算每行元素和。

解法1 - AC

#include
using namespace std;
int n, k, x, f[101][101], ans[101];
int main(){cin>>n>>k>>x;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)cin>>f[i][j];int ptr = 0;for(int i = 2; i <= n; i += 2){ptr = ptr % k + 1;for(int j = n; j >= ptr; j --)f[j][i] = f[j - ptr][i];for(int j = 0; j <= ptr; j ++)f[j][i] = x;}for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){cout<<f[i][j]<<' ';ans[i] += f[i][j];}cout<<endl;}for(int i = 1; i <= n; i ++){if(i - 1)cout<<' ';cout<<ans[i];}return 0;
}

7-8 浪漫侧影

12min

思路

• 常规造树，额外记录树高。
• 层序遍历。两个指针分别记录上一个弹出元素pre，和当前队列头部元素ptr。每次访问到下一层，将pre记入ansr数组对应高度的位置，将ptr记入ansl数组对应高度的位置。
• 按序输出ansl和ansr数组即可。

题解

#include
using namespace std;
int n, in[40], post[40], mh;
int ansl[40], ansr[40];
struct node{int k, h;struct node*l, *r;
};
node* mt(int il, int ir, int pl, int pr, int h){mh = max(mh, h);if(il > ir) return NULL;node * t = (node*)malloc(sizeof(node));t->k = post[pr];t->h = h;int i = il;while(in[i] != post[pr])i++;t->l = mt(il, i - 1, pl, pl + i - 1 - il, h + 1);t->r = mt(i + 1, ir, pl + i - il, pr - 1, h + 1);return t;
} 
int main(){cin>>n;for(int i = 0; i < n; i ++) cin>>in[i];for(int i = 0; i < n; i ++) cin>>post[i];node * t = mt(0, n - 1, 0, n - 1, 0);queue<node*> que; que.push(t);ansl[0] = ansr[0] = t->k;int th = 0;node * tn = t;while(que.size()){auto tar = que.front();if(tar->h > th){ansr[th] = tn->k;th = tar->h;ansl[th] = tar->k;}tn = tar;que.pop();if(tar->l) que.push(tar->l);if(tar->r) que.push(tar->r);}ansr[th] = tn->k;cout<<"R:";for(int i = 0; i < mh; i ++)printf(" %d", ansr[i]);puts("");cout<<"L:";for(int i = 0; i < mh; i ++)printf(" %d", ansl[i]);return 0;
}

7-1 自动编程

1min

#include
using namespace std;
int n;
int main(){cin>>n;printf("print(%d)", n);return 0;
}

7-2 加油冲鸭

3min

#include
using namespace std;
int n, m, s, sum;
int main(){cin>>n>>m>>s;sum = n - m * s;if(sum <= n / 2) printf("hai sheng %d mi! chong ya!", sum);else printf("hai sheng %d mi! jia you ya!", sum);return 0;
}

7-3 520的表白

2min

#include
using namespace std;
int main(){string r; cin>>r;for(int i = 0; i < 520; i ++)puts(r.c_str());return 0;
}

7-4 奇葩楼层

2min

#include
using namespace std;
int main(){int n, d; cin>>n>>d;int cnt = n;for(int i = 1; i <= n; i ++){string s = to_string(i);if(s.find('0' + d) != -1) cnt--;}cout<<cnt;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！