还是开始写的很晚……因为调题速度比较慢……
赛时
约20分钟看全四道题目。
其实都没有太好的思路，
T4
认为(T4)的暴力(50pts)很好拿，先用了约(0.5h)写了(T4)的(50pts).另50分没有太想好
（赛后：写的暴力数据范围小了导致(50 o20)……
现在+机房大佬的(T4)，有如下：
把所有数字按01串存放到01trie中。
考虑如何产生逆序对：
后加的数如果比trie里已有的数大的话，必定产生逆序对。
且：当且仅当某两个数字，他们的前缀完全相同，在第i位处01串不同，且后入的数是1，前入的数是0.可以发现对于每一位的操作是独立的.
因为题里要求异或结果，若某一位的数字因异或而发生改变，则原本的逆序对变成现在的正序对，同理原本的正序对变成现在的逆序对（指每个节点下存储的正逆序对个数）.
于是问题转化为维护其正序对和逆序对，选取答案最小即可。
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 4e6+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret = 0 ; char ch = ' ' , c = getchar();
while(!(c >= '0' && c <= '9'))ch = c , c = getchar();
while(c >= '0' && c <= '9')ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
return ch == '-' ? -ret : ret;
}
int n;
int trie[N][2],tot = 1;
ll ans[35][2],siz[N];
int a[35];
void insert(int x){
for(int i = 30 ; i >= 0 ; i --)
a[i] = !!(x & (1<<i));
// for(int i = 17 ; i >= 0 ; i --)printf("%d",a[i]);puts("");
int p = 1;
for(int i = 30 ; i >= 0 ; i --){
if(a[i]) ans[i][1] += siz[trie[p][0]];
else ans[i][0] += siz[trie[p][1]];
if(!trie[p][a[i]]) trie[p][a[i]] = ++tot;
p = trie[p][a[i]];
siz[p] ++;
}
}
signed main(){
fo("inverse");
n = read();
while(n --){
int x = read();
insert(x);
}
ll Ans = 0 ;int pos = 0;
for(int i = 0 ; i <= 30 ; i ++)
if(ans[i][0] <= ans[i][1])
Ans += ans[i][0];
else Ans += ans[i][1],
pos += (1<<i);
printf("%lld %d
",Ans,pos);
}
T3
然后想了(T3)，想到了类似于正解的做法，但是还是缺少细节……
按照“格式化后增大的升序，格式化后减小的降序”排序处理即可。
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e6+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret = 0 ; char ch = ' ' , c = getchar();
while(!(c >= '0' && c <= '9'))ch = c , c = getchar();
while(c >= '0' && c <= '9')ret = (ret << 1) + (ret << 3) + c - '0' , c = getchar();
return ch == '-' ? -ret : ret;
}
int n;
struct node{int a,b;}a1[N],a2[N];
inline bool cmp1 (const node& a,const node& b){
return a.a < b.a;
}
inline bool cmp2 (const node& a,const node& b){
return a.b > b.b;
}
int cnt1,cnt2;
ll ans,emp;
signed main(){
n = read();
for(int i = 1 ; i <= n ; i ++){
int a = read() , b = read();
if(a <= b)
a1[++cnt1] = (node){a,b};
else a2[++cnt2] = (node){a,b};
}
sort(a1+1,a1+cnt1+1,cmp1);
sort(a2+1,a2+cnt2+1,cmp2);
for(int i = 1 ; i <= cnt1 ; i ++){
if(a1[i].a > emp)
ans += a1[i].a - emp , emp = a1[i].b;
else emp += a1[i].b - a1[i].a;
// printf(" (%d,%d) , %lld %lld
",a1[i].a,a1[i].b,ans,emp);
}
for(int i = 1 ; i <= cnt2 ; i ++){
if(a2[i].a > emp)
ans += a2[i].a - emp , emp = a2[i].b;
else emp += a2[i].b - a2[i].a;
}
printf("%lld",ans);
}
T2、T1
上面两道题比较有把握，但是都没有拿到如愿的分数……
(T2、T1)两道题的贪心策略就基本没有找好……导致几乎爆零……
现在看看，两道题其实都是水题……
(T2)正解：状压DP.
(T1)正解：纯贪心+暴力.
赛后
名为贪心模拟赛，问题在于没有想到很好的贪心策略。这与平时做题数量和质量是有关的。下一步要着重加强这一部分。