Pinely Round 1 (Div. 1 + Div. 2) A B C

---

一、A - Two Permutations

• 思路: 只要给这个排列最少留下两个位置,就可以,也就是说n - (a + b) >= 2,同时注意 a == n并且b == n,还有n == 1的情况
• 代码:

#include 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int>
#define int long long
using namespace std;

const int N = 2e5 + 100,M = N * 2,INF = 0x3f3f3f3f,mod = 1e9 + 7;
int n,m;

void solve()
{
    int a,b;
    cin >> n >> a >> b;
    if(a + b <= n - 2 || n == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

signed main()
{
    ios; 
    int T; cin >> T; while(T -- ) solve();
    
    return 0;
}
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

二、B - Elimination of a Ring

• 思路: 只要不是一直类似abababab,的这种情况,答案就是n,但如果是这样的情况答案就是(n + 2) / 2,可以推一下
• 代码:

#include 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int>
#define int long long
using namespace std;

const int N = 2e5 + 100,M = N * 2,INF = 0x3f3f3f3f,mod = 1e9 + 7;
int n,m;
int a[N];
void solve()
{
    
    cin >> n;
    for(int i = 1;i <= n;i ++ ) cin >> a[i];
    if(n == 1) cout << "1" << endl;
    else
    {
        bool f = false;
        for(int i = 1;i <= n - 2;i ++ )
        {
            if(a[i] != a[i + 2])
            {
                f = true;
                break;
            }
        }
        
        if(f) cout << n << endl;
        else cout << (n + 2) / 2 << endl;
    }
   
}

signed main()
{
    ios; 
    int T; cin >> T; while(T -- ) solve();
    
    return 0;
}
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

三、C - Set Construction

• 思路: 看样例你会发现,这其实就是一个拓扑序列,样例就是 1 -> 4,2 -> 4,3 -> 4.2->1,跑一边拓扑序列,如果点 T 到点 U,有一条边,那 U 包含的序列就是 {U 并上 T},比如 T包含1,3此时U包含2,3,当遍历到U的时候就是U包含的点就是 {1,2,3},可以用set,也可以手动去重
• 代码:

#include 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int>
#define int long long
using namespace std;

const int N = 210,M = N * 2,INF = 0x3f3f3f3f,mod = 1e9 + 7;

int n,m;
char a[N][N];
int res[N][110];
int d[N];
int w[N];

void bfs()
{
    queue<int> q;
    int cnt = 0;
    for(int i = 1;i <= n;i ++ )
    if(d[i] == 0)
    {
        q.push(i);
        ++cnt;
        res[i][cnt] = 1;
        w[i] = 1;
    }
    
    while(q.size())
    {
        int t = q.front();q.pop();
        
        for(int j = 1;j <= n;j ++ )
        {
            if(a[t][j] == '1')
            {
                d[j]--;
                for(int k = 1;k <= n;k ++ )
                if(res[t][k] == 1 && res[j][k] != 1)
                {
                    w[j]++;
                    res[j][k] = 1;
                }
                
                if(d[j] == 0)
                {
                    ++cnt;
                    w[j]++;
                    q.push(j);
                    res[j][cnt] = 1;
                }
                
            }
        }
    }
}
void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i ++ )
        for(int j = 1;j <= n;j ++ )
        {
             cin >> a[i][j];
             if(a[i][j] == '1')
             {
                 d[j]++;
             }
             
        }
        
        bfs();
        for(int i = 1;i <= n;i ++ )
        {
            cout << w[i] << ' ';
            
            for(int j = 1;j <= n;j ++ )
            if(res[i][j] == 1)
            cout << j << ' ';
            
            cout << endl;
        }

       for(int i = 1;i <= n;i ++ )
       {
           w[i] = 0;
           for(int j = 1;j <= n;j ++ )
           res[i][j] = 0;
       }
       
   
}

signed main()
{
    ios; 
    int T; cin >> T; while(T -- ) solve();
    
    return 0;
}
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

四、D - Carry Bit

• 大佬讲解

---

总结

D不会,好像自己这种算计数的大部分都不会,得加强一下练习了