文章目录

• 一、A - Two Permutations
• 二、B - Elimination of a Ring
• 三、C - Set Construction
• 四、D - Carry Bit
• 总结

一、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
#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;
}

二、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
#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;
}

三、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
#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 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;
}

四、D - Carry Bit

• 大佬讲解

总结

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