[题目链接]("蔚来杯"2022牛客暑期多校训练营7_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com))
C Constructive Problems Never Die题目大意
有一个数组 A,构造一个长为n的排列P,使得Pi ≠ Ai。
题解
只有当A中都是同一个数时没有构造方法,其他情况下都能找出构造方法。
要构造一个排列P,只有在A中出现过的数字有放置的限制,其他的数字都可以随便放。
出现过的数字可以错位放置,即第一个出现的数字放在第二个出现的数字的第一个位置(其实任意一个位置都可以),以此类推。
代码
#includeF Candiesusing namespace std; typedef long long ll; typedef pair P; const int maxn = 1e5 + 5; int t, n, cnt, x; int loc[maxn], res[maxn]; bool vis[maxn]; vector v; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) res[i] = loc[i] = vis[i] = 0; v.clear(); cnt = 1; for (int i = 1; i <= n; i++) { cin >> x; if (!loc[x]) loc[x] = i; } for (int i = 1; i <= n; i++) if (loc[i]) v.push_back({i, loc[i]}); if (v.size() == 1) cout << "NO" << endl; else { cout << "YES" << endl; for (int i = 1; i < v.size(); i++) { res[v[i].second] = v[i - 1].first; vis[v[i - 1].first] = 1; } res[v[0].second] = v[v.size() - 1].first; vis[v[v.size() - 1].first] = 1; for (int i = 1; i <= n; i++) { if (res[i]) continue; while (vis[cnt]) cnt++; res[i] = cnt++; } for (int i = 1; i <= n; i++) cout << res[i] << " "; cout << endl; } } return 0; }
题目大意
给定一个圆环数组a,和一个特殊的数x。
可以对圆环数组上连续的两个数执行两个操作:①如果两数相等可以删除;②如果两数之和等于x可以删除。
求最多可以删除多少次。
题解
模拟,能删除就删除。
代码
#includeG Regular Expressionusing namespace std; typedef long long ll; const int maxn = 1e5 + 5; int n, res, x; int a[maxn]; deque q; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> x; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { if (q.size()) { if (a[i] == q.back() || a[i] + q.back() == x) { res++; q.pop_back(); } else q.push_back(a[i]); } else q.push_back(a[i]); } while (q.size() >= 2) { if (q.front() == q.back() || q.front() + q.back() == x) { res++; q.pop_back(); q.pop_front(); } else break; } cout << res << endl; return 0; }