2021年“图森未来杯”全国程序设计邀请赛 部分题目总结

其中B、F、H、J四题现在看都不太容易，以后有机会再拿出来看看

题目链接
网站链接

A. Abstract Algebra

题目大意：给定两个矩阵A和B，其中
$$A=\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right],B=\left[\begin{array}{cc}0& 1\\ ?1& 0\end{array}\right]$$
现在说有一个矩阵
$$X=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$$
其中，$$ad?bc=1,abcd=0$$现在给定整数$a、b、c、d$，保证$X$能够由若干个$A$和$B$进行矩阵乘积得到，问如何组合，保证有解，输出一组即可，转化成数学语言是$$?10^5\le a_i\le 10^5$$ c i ∈ { A , B } c_i\in \{A,B\} ci?∈{ A,B}$$X=\prod _i{c}_i^{a_i}$$

• 这道题是线性代数矩阵运算的问题，关键在于如何构造，先观察，发现因为$abcd=0,ad?bc=0$，假设$b=0$，那么有$ad=1$，因为它们都是整数，所以只能都是1或者都是-1，其他三个也可以类似的考虑，问题一下就变得简单了，这样一个显然的思路是分别讨论为0的时候，但是还有一个关键点，当$c=0$的时候（其他也可以类似考虑），
  $$X=\left[\begin{array}{cc}1& b\\ 0& 1\end{array}\right]$$
  或者
  $$X=\left[\begin{array}{cc}?1& b\\ 0& ?1\end{array}\right]$$
  前者显然有$$X=\left[\begin{array}{cc}1& b\\ 0& 1\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]}^b=A^b$$而后者显然是一个负单位矩阵$\times A^{?b}$，也就是$$X=\left[\begin{array}{cc}?1& b\\ 0& ?1\end{array}\right]=\left[\begin{array}{cc}?1& 0\\ 0& ?1\end{array}\right]\times A^{?b}$$而$$\left[\begin{array}{cc}?1& 0\\ 0& ?1\end{array}\right]={\left[\begin{array}{cc}0& 1\\ ?1& 0\end{array}\right]}^2=B^2$$所以$$X=B^2\times A^{?b}$$这样我们就讨论过了$c$的情况，综上所述$c=0$时，$$X=\{\begin{array}{llc}{A}^b& & a=d=1\\ B^2\times A^{?b}& & a=d=?1\end{array}$$其他$abd$分别为0时，都可以转化为$c=0$的情况
• 例如$a=0$时，可配凑出$$X=B\times \left[\begin{array}{cc}?c& ?d\\ 0& b\end{array}\right]$$
  也可以凑出$$X=B^{?1}\times \left[\begin{array}{cc}c& d\\ 0& ?b\end{array}\right]$$
  都可以，后面的矩阵就是刚才讨论过的$c=0$的情况，代入上面已经得到的结论可以得到答案，$bd$同理，全部求出，写成程序如下

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
int main(){
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int T;int a, b, c, d;cin >> T;while(T--){
    cin >> a >> b >> c >> d;if(c == 0){
    if(a == 1){
    cout << 1 << "\n" << "A" << " " << b << "\n";}else{
    cout << 2 << "\n" << "B " << 2 << "\n";cout << 'A' << " " << -b << "\n";}}else if(b == 0){
    if(d > 0){
    cout << 3 << "\n";cout << "B 1\n";cout << "A " << -c << "\n";cout << "B -1\n";}else{
    cout << 3 << "\n";cout << "B -1\n";cout << "A " << c << "\n";cout << "B -1\n";}}else if(a == 0){
    if(c > 0){
    cout << 2 << "\n";cout << "B -1\n";cout << "A " << d << "\n";}else {
    cout << 3 << "\n";cout << "B -1\n";cout << "B 2\n";cout << "A " << -d << "\n";}}else if(d == 0){
    if(c > 0){
    cout << 2 << "\n";cout << "A " << a << "\n";cout << "B -1\n";}else{
    cout << 3 << "\n";cout << "B 2\n";cout << "A " << -a << "\n";cout << "B -1\n";}}}return 0;
}

• 细节需要注意

C. Countdown

• 计算从4月10日到10月18日有多少天，可以手算出是189天，注意别算错了

cout << 189;

D. Divide

给出四个数$l_1,r_1,l_2,r_2$问${\prod }_{i=l_1}^{r1}i$是不是${\prod }_{i=l_2}^{r2}i$的约数

• 根据唯一分解定理，很容易想到的思路是这两个数一定能写成若干质数相乘的形式，如果前面的所有因子集合是后面的子集，那么就是，否则就不是。根据这个思路，枚举每个可能是因子的质数逐一对照，找到一个不合法就说明不是约数
• 问题等价于$(l_2?1)!\times r_1!|(l_1?1)!\times r_2!$，找这四个阶乘的所有因子数对比即可
• 这道题知识点有两个，素数筛法和求取$n!$的因子$p$的个数的方法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e7 + 100;
const double eps = 1e-6;
int Data[MAXN];
int vis[MAXN];
int p[MAXN];
int Prime(){
    int tot = 0;for(int i=2;i<=10000000;i++){
    if(!vis[i]) p[tot++] = i;for(int j=0;j<tot&&p[j]*i<=10000000;j++){
    vis[i*p[j]] = 1;if(i % p[j] == 0) break;}}return tot;
}
int divide(int n, int p){
    int ans = 0;while(n){
    ans += n / p;n /= p;}return ans;
}
int main(){
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int T;int a, b, c, d;cin >> T;int tot = Prime();while(T--){
    cin >> a >> b >> c >> d;bool flag = true;for(int i=0;i<tot;i++){
    int num1 = divide(a - 1, p[i]);int num2 = divide(b, p[i]);int num3 = divide(c - 1, p[i]);int num4 = divide(d, p[i]);if(num1-num2+num4-num3 < 0){
    flag = false;break;} }if(flag) cout << "Yes\n";else cout << "No\n";}return 0;
}

E. Edge Game

两人博弈，给出两人起点，图上路径，1号玩家先走，谁先碰到对方谁就赢了，问1号玩家是否能赢

• 显然是最段路，找两个玩家的最短距离如果是奇数就能赢，否则输，或者用$dfs$和$LCA$都一样

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const ll INF = 2147483647;
const int MAXN = 2e6+100;
int head[MAXN];
int vis[MAXN];
int cnt;
ll dis[MAXN];
struct T{
    int id;int dis;bool operator < (const T &a) const{
    return a.dis < dis;}
};
struct Edge{
    int next;int to;ll value;
}edge[MAXN];
void init(int n){
    memset(head,-1,sizeof head);for(int i=0;i<=n;i++) dis[i] = INF;cnt = 0;
}
void Add_Edge(int u, int v, ll value){
    edge[cnt].to = v;edge[cnt].value = value;edge[cnt].next = head[u];head[u] = cnt++;
}
void dijstra(int s){
    priority_queue<T> q;dis[s] = 0;T now;now.dis = dis[s];now.id = s;q.push(now);while(!q.empty()){
    T u = q.top();q.pop();if(vis[u.id]) continue;vis[u.id] = 1;for(int i=head[u.id];i!=-1;i=edge[i].next){
    if(!vis[edge[i].to] && dis[edge[i].to] > edge[i].value + dis[u.id]){
    dis[edge[i].to] = edge[i].value + dis[u.id];now.id = edge[i].to;now.dis = dis[edge[i].to];q.push(now);}}}
}
int main(){
    int T, u, v;scanf("%d", &T);init(T);for(int i=1;i<T;i++){
    scanf("%d%d", &u, &v);Add_Edge(u, v, 1);Add_Edge(v, u, 1);}scanf("%d%d", &u, &v);dijstra(u);if(dis[v] & 1){
    printf("Yes");}else printf("No");return 0;
}

G. Group QQ Speed

题意需要仔细理解，$n$个人玩$QQ$飞车，有$x$张地图，首先这$n$个人先$ban$地图，每人只能$ban$一个，之后分成$m$组，平均分组，分到同一组的人必须玩一个地图，但是不能玩同一组的人已经$ban$了的地图，问最少需要提供多少地图才能保证游戏正常进行

• 仔细分析一下题意，要注意$ban$操作是在分组之前进行的，也就是如果分组之后某一组所有地图都已经被$ban$，这一组本身就不可能被分到一起，如果不得不分，那就说明地图给少了，所以问题问的是最少需要多少地图
• 很容易想到的是如果$n$个人分成$n$组，那么显然最少需要两个地图，如果n个人分成一组，那么至少需要$n+1$张地图
• 关键在于如果不是这两种情况怎么办，考虑样例2，如果两张地图，假如四个玩家分别$ban$了1，1，1，2，那么就无法分组了，需要留一张地图以备不时之需，所以提供三张地图即可，$ban$同一张地图的人把他们分到同一组，总能分成指定的组数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
int main(){
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int t, n, m;cin >> t;while(t--){
    cin >> n >> m;if(n == m) cout << 2;else if(m == 1) cout << n + 1;else cout << 3;cout << "\n";}return 0;
}

I. I Love You

给出两个字符串，问第二个字符串是否是第一个字符串的子序列

• 用一个$for$循环找一圈即可

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
bool check(string s, string t){
    int a = s.length();int b = t.length();int num = 0;for(int i=0;i<a;i++){
    if(s[i] == t[num]) num++;if(num == b) break;}if(num == b) return true;return false;
}
int main(){
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);string s, t;cin >> s >> t;int a = s.length();int b = t.length();if(check(s, t)) cout << "Yes";else cout << "No";return 0;
}

K. K-Primes

给出$l$和$k$，问$[l,l+2k)$区间内是不是$>k$个质数

• 可以发现这个区间段内有$2k$个数，连续的$2k$个正整数里面有多于$k$个质数，这几乎是不可能的事情，因为连续的$2k$个正整数里面必然有$k$个偶数，除了$2$之外其他偶数都是合数，所以在$2$这里进行分析特判即可
• 因为质数越往后约稀疏，可以写几个数发现$l=2$时候，$k=1,2,3$都合法，其他都不行

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main(){
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);ll l, k;cin >> l >> k;if(l != 2) cout << "No";else{
    if(k < 4) cout << "Yes";else cout << "No";}return 0;
}