赛后反思
只开出来两题，好像水平就这样了TAT
I 题
给定一个排列，对于每项可以选择+1或者不加，求逆序对对数最小
我们可以思考一下什么情况下可以减少最后答案的逆序对，对于 \([4,3]\) 或者 \([2,1]\) 这种情况，将第二个元素+1才能对答案的减少做出贡献，所以只要判断某一位的后面是否有那一位 -1 的数即可，将其 +1 就行
对于求逆序对当然使用归并排序 \(O(nlogn)\)
#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 2e5 + 3;int a[N],c[N];
bool vis[N];
int ans = 0;void msort(int l,int r){if(l == r) return;int m = l + r >> 1,i = l,j = m + 1,k = l;msort(l,m); msort(m + 1,r);while(i <= m && j <= r){if(a[i] <= a[j]) c[k++] = a[i++];else c[k++] = a[j++],ans+=m-i+1;}while(i<=m) c[k++] = a[i++];while(j<=r) c[k++] = a[j++];for(int i = l;i<=r;i++) a[i] = c[i];
}void solve(){int n; cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];if(vis[a[i] + 1]) a[i]++;vis[a[i]] = 1;}msort(1,n);cout<<ans<<endl;
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}
F 题
正如题目所述，这真tm是诈骗题，每次我们都可以选择删一条边，或者删一个联通块，我们可以发现（很难发现）一个有趣的点就是，每次删除操作，两种操作均会使 \(n+m\) 的奇偶性发生改变，删一条边，边数 \(-1\)，删一个大小为 \(i\) 的联通块，点数减 \(i\)，边数减 \(i-1\)，所以我们直接对 \(n+m\) 的奇偶性进行判断即可
#include <bits/stdc++.h>
#define int long longusing namespace std;void solve(){int n,m; cin>>n>>m;if((n+m)&1) cout<<"Alice"<<endl;else cout<<"Bob"<<endl;
}signed main(){// int T; cin>>T; while(T--)solve();return 0;
}
