ABC225

A

题意：给你一个长度为3的只包含小写字母的串，问有多少种不同的排列

方法：根据相同字符的个数，输出答案

#include
#include
#include

using namespace std;
int main(){
    string s;
    cin >> s;
    
    sort(s.begin(), s.end());
    
    int cnt = 1;
    if(s[0] == s[1]) cnt ++;
    if(s[1] == s[2]) cnt ++;
    
    if(cnt == 3) cout << 1;
    if(cnt == 2) cout << 3;
    if(cnt == 1) cout << 6;
}

B

题意：给你一个n个顶点的树，判断他是不是星形图

方法：维护每个顶点的度数，判断存不存在某一个顶点的度为n - 1

#include
#include
#include

using namespace std;

const int N = 1e5 + 10;

int d[N];
int n;

int main(){
    cin >> n;
    
    for(int i = 0; i < n - 1; i ++){
        int a, b;
        cin >> a >> b;
        d[a] ++, d[b] ++;
    }
    
    for(int i = 1; i <= n; i ++){
        if(d[i] == n - 1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    
    cout << "No" << endl;
}

C

题意：现在有一个矩阵A，大小为\(10^{100}*7\) ，A的(i, j)位置的值为$ (i-1) \times 7 + j$，A是这个样子的

\[\left[ \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 8 & 9 & 10 & 11 & 12 & 13 & 14\\ .\\ .\\ . \end{matrix} \right] \]

在给你一个NxM（M <= 7）的矩阵B(\(B_{i, j} \le 10^9\), 不会超int)，问B是不是A的子矩阵

方法：根据B数字最大为1e9, 位于A中的1428572行，就是说在A中的行下标最多到1438572行，所以下标不会超int，所以直接在A中先找到B[1][1]的位置，然后按顺序对比就行，官方题解上面是根据B中每个元素的值算出他们分别在A中的位置，然后判断这些位置是否形成一个矩形

#include
#include
#include

using namespace std;

#define int long long

int n, m;
int b[10010][10];

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> b[i][j];
            
    int t = b[1][1];
    for(int i = 1; ; i ++){
        for(int j = 1; j <= 7; j ++){
            if((i - 1) * 7 + j == t){
                for(int u = 0; u < n; u ++)
                    for(int v = 0; v < m; v ++){
                        int ax = i + u, ay = j + v;
                        int bx = u + 1, by = v + 1;
                        if(ay > 7){
                            cout << "No";
                            return 0;
                        }
                        int av = (ax - 1) * 7 + ay;
                        int bv = b[bx][by];
                        if(av != bv){
                            cout << "No";
                            return 0;
                        }
                    }
                    
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
}

D

题意：有N个火车头，给你Q个询问，三种操作

1. 1 x y，把y接到x后面
2. 2 x y, 把y从x后面断开
3. 3 x，从前到后输出包含x的火车

方法：指针连来连去

#include
#include
#include
#include

using namespace std;

struct node{
    int up, down;
}a[100010];

int n, q;

signed main(){
    cin >> n >> q;
    
    for(int i = 1; i <= n; i ++) a[i] = {i, i};
    
    while(q --){
        int id, x, y;
        cin >> id;
        if(id == 1){
            cin >> x >> y;
            a[y].up = x;
            a[x].down = y;
        }else if(id == 2){
            cin >> x >> y;
            a[y].up = y;
            a[x].down = x;
        }else{
           cin >> x;
           int pp = x;
           while(a[pp].up != pp) pp = a[pp].up;
           vector res{pp};
           while(a[pp].down != pp){
               pp = a[pp].down;
               res.push_back(pp);
           }
           cout << res.size() << ' ';
           for(auto t : res) cout << t << ' ';
           cout << endl;
        }
    }
}