前言
最不能轻易自信的算法---贪心
考场上自信满满，除了最后一道暴力，其他都是认认真真想到的贪心，预计得分300+pts
实际得分：90pts
题解
T1alignment
初看特别复杂，再看感觉很简单。
原本思路：统计每一个人到上一个同势力人的距离dis，（设当前势力人数为m）最后选m-1个dis即可
但是这样m>n/2会有问题，因为选的dis可能不连续
正解：将环序列复制成2n（常用处理），对于每个势力，选一个包含指定人数的最短序列即可
T2flower
考场想到错误的贪心，就是优先选存活时间长的，而且花不能死，可能还写错了一点爆零了
正解：状压dp，dp[s]表示s状态下种花的最小时间，同时规定从晚到早的种花顺序，即可转移求解
T3reformat
花了大概1h想了个错误的贪心
正解：delta>0在前面，按照x从小到大排序；delta<0在后面，按照y从大到小排序，也相当于用了逆时间的操作
原本思路的错误直接看代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1e6+10;
int n;
ll now,ans;
struct node
{
int x,y,del;
}a[N];
//错误原因：当del<0时会浪费空间
//bool cmp(node a,node b) //return 1----- a在前面
//{
// //差值为负数全部排在后面
// if(a.del>=0&&b.del>=0) return a.x<b.x;
// return a.del>b.del;
//}
bool cmp(node a,node b)
{
if(a.del<0&&b.del<0) return a.y>b.y;
if(a.del>=0&&b.del>=0) return a.x<b.x;
if(a.del>=0&&b.del<0) return 1;
if(a.del<=0&&b.del>0) return 0;
}
int main()
{
//freopen("reformat.in","r",stdin);
//freopen("reformat.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].del=a[i].y-a[i].x;
sort(a+1,a+n+1,cmp);
// for(int i=1;i<=n;i++)
// {
// printf("x=%d,y=%d
",a[i].x,a[i].y);
// }
for(int i=1;i<=n;i++)
{
if(now<a[i].x)
{
ans+=a[i].x-now;
now=a[i].y;
}
else
{
now+=a[i].del;
}
}
printf("%lld",ans);
return 0;
}
/*
4
6 6
1 7
3 5
3 5
----------
4
2 2
3 3
5 1
5 10
----------
3
2 1
3 1
4 7
*/
/*WA----
5
2000 1999
20 1
20 19
3500 1000
5000 4000
*/
T4inverse
考场暴力（还挂了），忽略了异或运算可以用字典树
这里可以算是一种按位贪心，因为每一位二进制数是否反转对答案的影响都是独立的，所以可以分别考虑每一位
注意一些细节实现即可（ps：！！操作把所有非0的数变成1，把0变成0）
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 4e6+10;
ll trie[N][2],ans[22][2],tot=1,siz[N];
int n;
void insert(int x)
{
int p=1;
for(int i=20;i>=0;i--)
{
int t=!!(x&(1<<i));//!!
if(t) ans[i][1]+=siz[trie[p][0]];//ans[i][0]逆序对
else ans[i][0]+=siz[trie[p][1]];//ans[i][1]正序对
if(!trie[p][t])
trie[p][t]=++tot;
p=trie[p][t];
siz[p]++;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
insert(x);
}
ll res=0,num=0;
for(int i=0;i<=20;i++)
{
if(ans[i][0]<=ans[i][1])
res+=ans[i][0];
else res+=ans[i][1],num+=(1<<i);
}
printf("%lld %lld
",res,num);
return 0;
}