A - Distinct Strings

问题陈述

给你一个长度为 \(3\) 的字符串 \(S\) ，由小写英文字母组成。

将\(S\)中的字符排列组合可以得到多少个不同的字符串？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s[0]==s[1]&&s[1]==s[2])
    {
        cout<<1<<'\n';
    }
    else if(s[0]==s[1]||s[0]==s[2]||s[1]==s[2])
    {
        cout<<3<<'\n';
    }
    else 
    {
        cout<<6<<'\n';
    }
    return  0;
}
//很容易理解的

B - Star or Not

问题陈述

给你一棵有 \(N\) 个顶点和 \(N-1\) 条边的树。
顶点的编号为 \(1,2,\ldots,N\)。连接顶点 \(a_i\) 和顶点 \(b_i\) 的 \(i\) 条边。

请判断这棵树是否是一棵星形树。

在这里，星形树是指有一个顶点与所有其他顶点直接相连的树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int in[N];
int main()
{
    int n;
    cin >> n;
    int u, v;
    for (int i = 2; i <= n; i++)
    {
        cin >> u >> v;
        in[u]++;
        in[v]++;
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (in[i] == n - 1)
            res = 1;
    if (res)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}
//弄入度，如果有n-1就输出

C - Calendar Validator

问题陈述

有一个\(10^{100} \times 7\)矩阵\(A\)，其中每一对整数\((i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7)\)的\((i,j)\)/th项为\((i-1) \times 7 + j\)。

给定一个\(N \times M\)矩阵\(B\)，判断\(B\)是否是\(A\)的某个（未旋转的）矩形部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n;i--)
const int N=1e5;
int a[N][10];
int main()
{
    int n,m;
    cin>>n>>m;
rep(i,1,n)
rep(j,1,m)
{
    cin>>a[i][j];
}
int ok=1;
rep(i,1,n-1)
{
    rep(j,1,m)
    {
        if(j<m&&a[i][j]+1!=a[i][j+1])
            //判断左右
        {
            cout<<"No";
            return 0;
        }
        if(a[i][j]+7!=a[i+1][j])
            //判断前后加7
        {
            cout<<"No";
            return 0;
        }
    }
}
int x=a[1][1]%7;
if(x==0)
{
    x=7;
}
if(x+m-1<=7)
    //判断会不会超过7能涵盖的数字
{
    cout<<"Yes"<<'\n';
}
else
{
    cout<<"No"<<'\n';
}
return 0;


}

D - Play Train

问题陈述

高桥正在玩玩具火车，把它们连接起来又断开。
有\(N\)节玩具火车车厢，车厢编号分别是：\(1\)节，\(2\)节，\(\ldots\)节，\(N\)节：车厢\(1\)，车厢\(2\)，\(\ldots\)，车厢\(N\)。
最初，所有车厢都是分开的。

您将收到 \(Q\) 个问题。按照给出的顺序处理它们。有以下三种查询。

  • 1 x y`：将汽车 \(y\) 的前部连接到汽车 \(x\) 的后部。
    可以保证

    • \(x \neq y\)
    • 在该查询之前，没有列车连接到车厢 \(x\) 的尾部；
    • 在此查询之前，没有列车与汽车\(y\)的前部相连；
    • 在该查询之前，\(x\)号车和\(y\)号车属于不同的连接部分。

  • 2 x y：断开\(y\)号车头与\(x\)号车尾的连接。
    可以保证

    • \(x \neq y\);
    • 就在此查询之前，\(y\)号小车的车头与\(x\)号小车的车尾直接相连。

  • 3 x:打印属于包含汽车\(x\)的连接部件的汽车编号，从前到后。

记录前驱和后继即可

然后深搜

有点像双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int nxt[N];
int pre[N];
int n, q;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
vector<int>ans;
int main()
{
cin>>n>>q;
int op,x,y;
rep(i,1,q)
{
    cin>>op;
    if(op==1)
    {
        cin>>x>>y;
        nxt[x]=y;
        pre[y]=x;
    }
    //记录
    else if(op==2)
    {
        cin>>x>>y;
        nxt[x]=0;
        pre[y]=0;
    }
    //清空
    else
    {
        cin>>x;
ans.clear();
int a=x;
while(x)
{
ans.push_back(x);
x=pre[x];
}
        //放前
reverse(ans.begin(), ans.end());
        //注意翻转
int b=nxt[a];
while(b)
{
    ans.push_back(b);
    b=nxt[b];
}
        //放后
cout<<ans.size()<<' ';
for(auto  it:ans)
{
cout<<it<<' ';
}
cout<<'\n';
    }
}

}

一份其他版本代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e1[N], e2[N], ans1, ans2;
int ne[N][3];
void dfs1(int x)
{
    ans2.push_back(x);
    if (ne[x][1] != -1)
    {
        int y = ne[x][1];
        dfs1(y);
    }
}
void dfs2(int x)
{
    int y = ne[x][2];
    if (y != -1)
        ans1.push_back(y), dfs2(y);
}
int main()
{
    int n, q;
    cin >> n >> q;
    int op, x, y;
    memset(ne, -1, sizeof ne);
    while (q--)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            ne[x][1] = y;
            ne[y][2] = x;
        }
        else if (op == 2)
        {
            cin >> x >> y;
            ne[x][1] = -1;
            ne[y][2] = -1;
        }
        else
        {
            cin >> x;
            ans1.clear(), ans2.clear();
            dfs1(x);
            dfs2(x);
            cout << ans1.size() + ans2.size() << " ";
            for (int i = ans1.size() - 1; i >= 0; i--)
            {
                cout << ans1[i] << " ";
            }
            for (int i = 0; i < ans2.size(); i++)
            {C++
                cout << ans2[i] << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

E - 7

问题陈述

有 \(N\) 个7 画在平面的第一象限。

\(i\)-th 7 是由连接 \((x_i-1,y_i)\) 和 \((x_i,y_i)\) 的线段以及连接 \((x_i,y_i-1)\) 和 \((x_i,y_i)\) 的线段组成的图形。

您可以从\(N\)中选择 0 个或多个 7 并将它们删除。7's 并删除它们。

最佳删除后，从原点完全可见的 7 的最大可能个数是多少？

这里，当且仅当\(i\)个 7 从原点完全可见：

  • 以原点、\((x_i-1,y_i)\)、\((x_i,y_i)\)、\((x_i,y_i-1)\)为顶点的四边形的内部（不包括边界）不与其他 7 相交。

E题挺假的，就是有康康线段的相交情况

只需要枚举线段斜率加上贪心就解决了

注意Long double

这个和接水什么题很像，就是贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N=2e6+100;
using ll=long long;
using lb=long double ;
struct node
{
    lb l,r;
}a[N];
bool cmp(node x,node y)
{
    if(x.l==y.l)
    {
return x.r<y.r;
    }
    return x.l<y.l;
}
int main()
{
    int n;
    cin>>n;
    rep(i,1,n)
    {
ll x,y;
cin>>x>>y;
a[i].l=((lb)(y)/(lb)(x-1.0));
a[i].r=((lb)(y-1.0)/(lb)(x));
        //左斜率和右斜率控制住就行了
    }
    sort(a+1,a+1+n,cmp);
    ll ans=1;
    lb x=a[1].l;
    rep(i,2,n)
    {
        if(a[i].r>=x)
        {
            ans++;
            x=a[i].l;
        }
    }
    cout<<ans;
}

F - String Cards

问题陈述

我们有 \(N\) 张卡片。\(i\)这张卡片上写着一个字符串\(S_i\)。

从这些卡片中选择\(K\)张，按任意顺序将它们连接起来，可以得到一个词性最小的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 题目大意是给出n个字符串，求取k个字符串组成的最小字典序的字符串
//通过dp来求解，dp[k] 表示从前i个字符串里取k个的最小字符串
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
bool cmp(string a, string b)
{
    return a + b > b + a;
}
int main()
{
    int n, k;
    cin >> n >> k;
    string dp[N];
    string str[N];
    for (int i = 1; i <= n; i++)C++
    {
        cin >> str[i];
    }
    for (int j = 1; j <= k; j++)
    {
        dp[j] = '{';
    }
    sort(str + 1, str + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j >= 1; j--)
        {
            dp[j] = min(dp[j], str[i] + dp[j - 1]);
        }
    }
    cout << dp[k] << '\n';
}