SMU Autumn 2024 Team Round 3（The 2024 ICPC Latin America Championship）
SMU Autumn 2024 Team Round 3（The 2024 ICPC Latin America Championship）
D. DiviDuelo
思路
代码
E. Expanding STACKS!
题意
给你两个栈，然后给出 \(n\) 个数字的入栈出栈记录，问你能否判断每个数字进入的是哪个栈，如果不能则输出 *。
思路
由题意可知，题目不要求我们输出每个数字进栈的先后顺序，只要我们输出哪些数字在哪个栈内即可。
把 \(n\) 个数字分成两个集合，其就是两个栈里的数字集合，那么我们要根据什么将这些数字分成两个集合呢？观察数字的入栈出栈记录，对于+1,+2,-1,-2这种情况，我们可以手动模拟一下，\(2\) 是比 \(1\) 后入栈的，但是 \(1\) 却比 \(2\) 先出栈，这说明什么？说明 \(1\) 和 \(2\) 不是进的同一个栈！假设 \(1\) 和 \(2\) 进入的是同一个栈，那么根据栈的性质，\(2\) 一定比 \(1\) 先出栈，否则就是不合法情况。
由此，我们可以得出一条关系，那就是+a,+b,+c,+d,-a...这样的记录中，在 \([l_{+a},r_{-a}]\) 的这个区间里，一旦有新的数进来但是却没有再出去过，那么就可以确定，这些数和 \(a\) 是不在同一个集合内的。
由以上结论我们可以处理出所有的数字间的一个排斥关系，那就是谁和谁肯定不在同一个集合里，根据这个关系然后将所有点分成两个部分，就是很典型的二分图染色，此外种类并查集也可以处理这种题型，不过种类并查集最后需要将合并得到的多个联通块再次合并成两个集合（产生多个联通块的原因就是有的数字进栈后马上就出栈了，这个数字就是属于‘中立’的那种，不与任何数字排斥，放在哪个集合都可以），我的做法是维护其中一个集合，如果当前点所排斥的点在我维护的集合中，那就说明它要放在另一个集合。
（种类并查集）代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct UFS {
int sz;
vector<int> rank, p;
UFS(int n) {
init(n);
}
void link(int x, int y) {
if (x == y)
return;
if (rank[x] > rank[y])
p[y] = x;
else
p[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
void init(int n) {
sz = n;
rank.resize(n + 1);
p.resize(n + 1);
for (int i = 0; i <= sz; i++) {
p[i] = i;
rank[i] = 0;
}
}
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
void unin(int x, int y) {
link(find(x), find(y));
}
void compress() {
for (int i = 0; i < sz; i++)
find(i);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(2 * n + 1), l(n + 1, 2 * n), r(n + 1);
for (int i = 1; i <= 2 * n; i ++) {
cin >> a[i];
l[abs(a[i])] = min(l[abs(a[i])], i);
r[abs(a[i])] = max(r[abs(a[i])], i);
}
vector<pair<int, int>> e;
for (int i = 1; i <= 2 * n; i ++) {
if (a[i] < 0) continue;
vector<int> cnt(n + 1);
for (int j = l[a[i]] + 1; j < r[a[i]]; j ++) {
if (a[j] > 0) cnt[a[j]] = 1;
if (a[j] < 0 && cnt[-a[j]]) cnt[-a[j]] = 0;
}
for (int j = 1; j <= n; j ++) {
if (cnt[j]) {
e.emplace_back(a[i], j);
}
}
}
UFS d(2 * n);
for (auto [u, v] : e) {
if (d.find(u) == d.find(v) || d.find(u + n) == d.find(v + n)) {
cout << "*\n";
return 0;
}
d.unin(u + n, v);
d.unin(u, v + n);
}
vector<vector<int>> w(2 * n + 1);
set<int> x;
for (auto [u, v] : e) {
u = d.find(u), v = d.find(v);
w[u].emplace_back(v);
w[v].emplace_back(u);
}
string ans = "", p = "SG";
for (int i = 1; i <= n; i ++) {
int t = d.find(i), f = 1;
for (auto v : w[t]) {
if (x.count(v)) f = 0;
}
ans += p[f];
if (f) {
x.insert(t);
}
}
cout << ans << '\n';
return 0;
}
队友写得，可以做个参考。
（二分图染色）代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N=1e3+3;
#define PII pair<ll,ll>
#define endl '\n'
#define mem(a, b) memset(a, b, sizeof(a))
int tt[N], g[N][N], n;
bool used[N];
bool flag=1;
void dfs(int u,int t)
{
used[u] = true;
if(!tt[u]){
tt[u]=t;
}else{
if(tt[u]!=t){
flag=0;
return;
}
}
for (int v = 1; v <= n; v++)
{
if (g[u][v])
{
if(tt[v]&&tt[v]==tt[u]){
flag=0;
break;
}
if(!used[v]){
dfs(v,t^3);
}
}
}
}
int a[N*2],b[N],c[N];
int d[N];
void solve()
{
int ans = 0;
cin>>n;
for(int i=1;i<=2*n;i++){
cin>>a[i];
if(a[i]>0)b[a[i]]=i;
else c[-a[i]]=i;
}
for(int i=1;i<=n;i++){
for(int j=b[i]+1;j<=c[i]-1;j++){
if(a[j]>0){
d[a[j]]++;
}else{
d[-a[j]]--;
}
}
for(int j=1;j<=n;j++){
if(d[j]>0){
g[j][i]=1;
g[i][j]=1;
}
d[j]=0;
}
}
for(int i=1;i<=n;i++){
if(!used[i]){
dfs(i,1);
}
}
if(flag){
for(int i=1;i<=n;i++){
if(tt[i]==1){
cout<<'G';
}else{
cout<<'S';
}
}cout<<endl;
}else{
cout<<'*';
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
}
F. Fair Distribution
题意
给你 \(n\) 对二元组 \((G,R)\)，由二元组可以得到一个值 \(x=G+k\times R(k>0)\) 你需要将这 \(n\) 对二元组分成两组，然后给每组中的二元组都确定一个值 \(x\) ，使得两组的所有 \(x\) 之和相等，更具体地，将 \(n\) 组二元组分成两个集合 \(S_1,S_2\)，问 \(\sum\limits_{i=1}^{|S_1|}G_i+k_i\times R_i=\sum\limits_{j=1}^{|S_2|}G_j+k_j\times R_j\) 是否存在。
思路
前置知识：
裴蜀定理
设 a,b 是不全为零的整数，对任意整数 x,y，满足 gcd(a,b)|ax+by，且存在整数 x,y，使得 ax+by=gcd(a,b).
先只看单独一个集合 \(S_1\)，因为 \(G\) 是一个定值，所以可以写成 \((\sum\limits_{i=1}^{|S_1|} G_i) +k_1\times R_1+k_2\times R_2+\dots\)，由裴蜀定理可得， 即存在 \(k_1,k_2,\dots\)，使得 \(k_1\times R_1+k_2\times R_2+\dots =\gcd(R_1,R_2,\dots)|X\)，设 \(\gcd(R_1,R_2,\dots)=g_{|S_1|}\)，所以集合 \(S_1\) 的总和等于 \(G_{|S_1|}+X=G_{|S_1|}+g_{|S_1|}\times k_{|S_1|}\)，同理，集合 \(S_2\) 的总和等于 \(G_{|S_2|}+X=G_{|S_2|}+g_{|S_2|}\times k_{|S_2|}\)，即有：
又由裴蜀定理可知，满足 \(\gcd(g_{|S_1|},g_{|S_2|})|(|G_{|S_1|}-G_{|S_2|}|)\)，而 \(\gcd(g_{|S_1|},g_{|S_2|})\) 其实就是 \(\gcd(R_1,R_2,\dots,R_n)=g\)，所以 \(|G_{|S_1|}-G_{|S_2|}|\) 一定能被 \(g\) 整除，即，只要我们找到一种分配方式，使得两个集合中的 \(G\) 总和相减的绝对值是 \(g\) 的倍数即可。
而对于 \(G_i\) 能凑成哪些数，直接枚举子集显然是不可取的做法，诶，取出一些数判断其能凑成的数，那不就是01背包吗！但是，这里的 \(1\le n\le 2\times 10^5\)，直接做背包是 \(O(n\times W)\)，也是难以接受的。
不过，观察到 \(0\le \sum\limits_{i=1}^nG_i\le 2\times 10^5\)，那么说明，不同种类的数最多只有 \(\sqrt{2\times 10^5}\) 个，那么我们可以用多重背包的做法去枚举 \(G_i\) 能凑成的数即可，这样复杂度就是 \(O(\sqrt W \times W\times log(\sqrt W))\) 相比朴素01背包可以接受 。
最后就是枚举 \(i\) ，判断两个集合的差值是否是 \(g\) 的整数倍即可，但是有个注意的点，如果存在 \(G_i=0\)，那么可以从 \(0\) 枚举到 $ G$，否则是 \(1\sim G -1\ (G=\sum\limits_{i=1}^nG_i)\)。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int g = 0, s = 0;
const int N = 2e5 + 10;
set<int> object;
vector<int> num(N);
for (int i = 1; i <= n; i ++) {
int G, R;
cin >> G >> R;
s += G;
g = gcd(R, g);
object.insert(G);
num[G] ++;
}
if (n == 1) {
cout << "N\n";
return 0;
}
vector<int> dp(s + 1);
dp[0] = 1;
for (auto &i : object) {
int has = num[i];
for (int k = 1; k <= has; k <<= 1) {
has -= k;
i64 w = k * i;
for (int j = s; j >= w; j --)
dp[j] |= dp[j - w];
}
if (has) {
i64 w = has * i;
for (int j = s; j >= w; j --)
dp[j] |= dp[j - w];
}
}
i64 ans = 0, f = object.count(0);
f ^= 1;
for (int i = f; i <= s - f; i ++) {
if (dp[i]) {
if (abs(s - 2 * i) % g == 0) {
cout << "Y\n";
return 0;
}
}
}
cout << "N\n";
return 0;
}
G. Greek Casino
思路
代码
K. KMOP
思路
代码
L. LED Matrix
思路
代码