本周专题：常见基础算法
知识点：
A-B：位运算
C-D：前缀和、差分
E-F：简单二分
G：离散化
H：ST表（倍增）
I-K：贪心
L-O：综合练习

A - Raising Modulo Numbers

INPUT

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

1
2
3
4
5
6
7
8
9
10
11
12
13
14

OUTPUT

2
13195
13
1
2
3

打个快速幂。

#include
#define llg long long
using namespace std;
int n,mod;

llg ksm(int base,int power,int m)
{
	llg ans=1;
	base%=m;
	while(power)
	{
		if(power&1)
			ans=ans*base%m;
		power>>=1;
		base=base*base%m;
	}
	return ans;
}

int main()
{
	cin>>n;
	while(n--)
	{
		int t;
		cin>>mod;
		cin>>t;
		llg ans=0;
		while(t--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			llg temp=ksm(a,b,mod);
			//printf("ksm(%d,%d,%d):%lld\n",a,b,mod,temp);
			ans+=temp;
			ans%=mod;
		}
		printf("%lld\n",ans);
	}
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

B - 起床困难综合症

链接

位运算特点：二进制下不进位
尽量让可控范围的每一位经过操作之后都是1.

#include
using namespace std;

int n,m;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
pair<string,int> a[100005];

int cal(int bit,int now)
{
	for(int i=1;i<=n;i++)
	{
		int x=a[i].second>>bit&1;//把操作数的当前位提取出来
		if(a[i].first=="AND") now&=x;
		if(a[i].first=="OR") now|=x;
		if(a[i].first=="XOR") now^=x;
	}
	return now;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		string s;
		int x;
		cin>>s>>x;
		a[i]=make_pair(s,x);
	}
	int val=0,ans=0;
	for(int bit=29;bit>=0;bit--)//枚举每个二进制位（从高位开始）
	{
		int res0=cal(bit,0);//这一位是0，经过如题操作后得到的结果
		int res1=cal(bit,1);//这一位是1，经过如题操作后得到的结果
		if(val+(1<<bit)<=m&&res0<res1)//不能超过最大值
			val+=1<<bit,ans+=res1<<bit;
		else ans+=res0<<bit;
	}
	cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---

C - 激光炸弹

链接

二维前缀和。

#include
using namespace std;
int n,m,mp[5010][5010],maxn;
const int N=5001;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x,y,v;
		cin>>x>>y>>v;
		mp[x+1][y+1]+=v;//横纵坐标都加1，防止之后越界
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			mp[i][j]=mp[i][j-1]+mp[i-1][j]-mp[i-1][j-1]+mp[i][j];//二维前缀和
	for(int i=m;i<=N;i++)
		for(int j=m;j<=N;j++)
		{
			int temp=mp[i][j]-mp[i-m][j]-mp[i][j-m]+mp[i-m][j-m];
			//算出每一个边长为m的正方形内包含的数
			maxn=max(maxn,temp);
		}
	cout<<maxn<<endl;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

D - Tallest Cow

链接

差分，让左右端点中间陷下去（高度最少-1）.注意避免关键字冲突。

#include
#include
#include
#include
#include
#include
using namespace std;

#define ll long long
pair<ll,ll> a[10100];
map<ll,ll> q;
ll n,m,i,j,k,p,h,c[10100],d[10100];

int main()
{

    cin>>n>>p>>h>>m;
    for (i=1;i<=m;i++)
    {
        ll A,B;
        cin>>A>>B;
        if(A>B) swap(A,B);
        if(q[A]!=B)//关键字不冲突
        {
            a[i]=make_pair(A,B);
            q[A]=B;
            d[A+1]--;
            d[B]++;
        }
    }
    for (i=1;i<=n;i++)
        c[i]=c[i-1]+d[i];
    for (i=1;i<=n;i++)
        cout<<c[i]+h<<endl;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

E - Best Cow Fences

链接
给定正整数数列A，求一个平均数最大的、长度不小于L的（连续的）子段。

二分答案求平均值。

#include
using namespace std;
double a[100001],b[100001],pre[100001];
int n,len;

int main()
{
	cin>>n>>len;
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i]);
	double eps=1e-5;
	double l=-1e5,r=1e5;
	while(l+eps<r)
	{
		double mid=(l+r)/2;
		for(int i=1;i<=n;i++) b[i]=a[i]-mid;
		for(int i=1;i<=n;i++)
			pre[i]=pre[i-1]+b[i];
		double minn=1e5,ans=-1e5;
		for(int i=len;i<=n;i++)
		{
			minn=min(minn,pre[i-len]);
			ans=max(ans,pre[i]-minn);
		}
		if(ans>=0) l=mid;
		else r=mid;
	}
	cout<<int(r*1000)<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

F - 借教室

链接

前缀和+差分+二分答案

#include
using namespace std;
const int N=1000010;
int a[N],dif[N],temp[N];
int d[N],s[N],t[N];
int n,m;
bool check(int x)
{
	memset(dif,0,sizeof(dif));
	for(int i=1;i<=x;i++)
	{
		dif[s[i]]-=d[i];
		dif[t[i]+1]+=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		temp[i]=temp[i-1]+dif[i];
		if(temp[i]+a[i]<0) return 0;
	}
	return 1;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=1;j<=m;j++)
		scanf("%d%d%d",&d[j],&s[j],&t[j]);
	if(check(m))
	{
		cout<<'0';
		return 0;
	}
	int l=1,r=m,mid,ans;
	while(l<r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	cout<<"-1\n"<<l;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

G - Cinema

链接

先把所有的数据读入，离散化一下，用桶装每种语言对应的教授的个数。根据题意找到最合适的电影序号。

#include
using namespace std;
const int N=200010;
int a[N],b[N],c[N],d[N*3],box1[N*3],n,m,cnt,maxn1,num;
int mem,maxn2;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
	n=read();
	for(int i=1;i<=n;i++) 
		a[i]=read(),d[++cnt]=a[i];
	m=read();
	for(int i=1;i<=m;i++)
		b[i]=read(),d[++cnt]=b[i];
	for(int i=1;i<=m;i++)
		c[i]=read(),d[++cnt]=c[i];
	sort(d+1,d+cnt+1);
	int total=unique(d+1,d+cnt+1)-d;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(d+1,d+total+1,a[i])-d;
		box1[a[i]]++;
	}
	for(int i=1;i<=m;i++)
	{
		b[i]=lower_bound(d+1,d+total+1,b[i])-d;
		c[i]=lower_bound(d+1,d+total+1,c[i])-d;
		int ansx=box1[b[i]],ansy=box1[c[i]];
		if(ansx>maxn1||(ansx==maxn1&&ansy>maxn2))
			num=i,maxn1=ansx,maxn2=ansy;
	}
	//cout<<"maxn:"<
	if(num==0) cout<<1<<endl;
	else cout<<num<<endl;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---

H - Balanced Lineup

典型RMQ。

#include
using namespace std;
int n,m,f[180010][20],g[180010][20];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int main()
{
	cin>>n>>m;
	memset(g,0x3f,sizeof(g));
	for(int i=1;i<=n;i++)
		f[i][0]=g[i][0]=read();
	int t=log(n)/log(2);
	for(int j=1;j<=t;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]),
			g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
	while(m--)
	{
		int r,l;
		l=read(),r=read();
		int k=log(r-l+1)/log(2);
		int high=max(f[l][k],f[r-(1<<k)+1][k]);
		int low=min(g[l][k],g[r-(1<<k)+1][k]);
		printf("%d\n",high-low);
	}
	return 0;		
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

---

I - Best Cow Line

链接

两端不同取小，两端相同向内比较，直到不同位置（中间的一直相同的话直接从左端点到右端点了）。

#include
using namespace std;
char a[2005];
int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=1,r=n,p=0;
	while(l<=r)
	{
		if(a[l]<a[r]) cout<<a[l++];
		else if(a[r]<a[l]) cout<<a[r--];
		else
		{
			int ll=l,rr=r;
			while(a[ll]==a[rr]&&ll<=rr)
				ll++,rr--;
			if(a[ll]<=a[rr])
				cout<<a[l++];
			else cout<<a[r--];
		}
		p++;
		if(p%80==0) cout<<endl;
	}
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

J - Fence Repair

链接

（二叉哈夫曼树？）
每次选两个最小的合并。

#include
#include
#include
using namespace std;
int main()
{
	int n,m,a,b;
	long long sum;
	while(~scanf("%d",&n))
	{
		priority_queue<int,vector<int>, greater<int> >Q;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&m);
			Q.push(m);
		}
		sum=0;
		while(Q.size()>1) 
		{
			a=Q.top();
			Q.pop();
			b=Q.top();
			Q.pop(); 
			Q.push(a+b);
			sum+=a+b;
		}
		printf("%lld\n",sum);
	}
	return 0; 
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

K - Radar Installation

链接

以每个岛为圆心画圆，求出在x轴上的左右端点。坐标在左右端点之间的雷达可以覆盖到该岛。把这些点对按照右端点大小排序。下一点对的左端点若在当前点对的右边，就需要加装一个雷达，否则当前雷达也能覆盖到下一座岛屿。（画图就好理解啦，又怪我太懒了）

#include
#include
#include
using namespace std;
struct island
{
	double l,r;
};
int n;
double d;
int cnt=0;
bool cmp(island x,island y)
{
	return x.r<y.r;
}
int main()
{
	while(cin>>n>>d)
	{
		if(n==0&&d==0) break;
		++cnt;
		island is[1010];
		int ok=1,sum=1;
		for(int i=1;i<=n;i++)
		{
			double x,y;
			cin>>x>>y;
			if(y>d) ok=0;
			double dis=sqrt(d*d-y*y);
			is[i].l=x-dis,is[i].r=x+dis;
		}
		if(!ok)
		{
			printf("Case %d: -1\n",cnt);
			continue;
		}
		sort(is+1,is+n+1,cmp);
		double now=is[1].r;
		for(int i=2;i<=n;i++)
		{
			if(is[i].l>now)
			{
				now=is[i].r;
				sum++;
			}
		}
		printf("Case %d: %d\n",cnt,sum);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

---

L - Corral the Cows

链接

坐标的范围在1 ~ 10000，如果直接开二维数组遍历显然不现实，再看N的范围最大是500，那么我们就可以将坐标离散化后存在一个数组里，用这个数组来进行前缀和运算的操作，就会大大降低时间复杂度。

#include
#include
using namespace std;
int num[1001],x[1001],y[1001];
int sum[1001][1001],c,n,cnt,total;

bool check(int len)
{
	for(int x1=1,x2=1;x2<=total;x2++)
	{ 
		while(num[x2]-num[x1]+1>len) x1++;
		//离散化前的左右边界横坐标距离已经超过len，左边界右移 
		for(int y1=1,y2=1;y2<=total;y2++)
		{
			while(num[y2]-num[y1]+1>len) y1++;
			//离散化前的上下边界纵坐标距离已经超过len，下边界上移 
			if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>=c)
			//在这个区域内的三叶草数量超过题目要求的 
			return true;
		}
	}
	return false;
}
int main()
{
	cin>>c>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		num[++cnt]=x[i],num[++cnt]=y[i];//所有可能出现的坐标 
	}
	sort(num+1,num+cnt+1);
	total=unique(num+1,num+cnt+1)-num-1;
	for(int i=1;i<=n;i++)
	{
		x[i]=lower_bound(num+1,num+total+1,x[i])-num;
		y[i]=lower_bound(num+1,num+total+1,y[i])-num;//离散化一下 
		sum[x[i]][y[i]]++;//离散化过后对应坐标处有一株三叶草 
	}
	for(int i=1;i<=total;i++)
		for(int j=1;j<=total;j++)
			sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+sum[i][j];//二维前缀和 
	int l=1,r=10000;
    while(l<r) 
	{
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

---

M - 超级钢琴

链接

我说这是本周最难的题目一点也不为过吧QAQ。

可以先做一下这一题：P1631 序列合并
看起来没关系但可以用到这种思想（实际上我想说我做了这题之后才能看懂题解，躺）

先把第一列的数都放到优先队列里，n次循环，每次弹出优先队列里最小的数，从这个最小的数所在行中取下一个。

#include
#define llg long long
using namespace std;

const int N=1e5+10;
llg a[N],b[N],c[N],point[N];
int n;
struct Node
{
	int val,pos;
	bool operator < (const Node& x) const
	{
        return val>x.val;
    }
};

priority_queue<Node>q;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&b[i]);
		point[i]=1;
		Node temp;
		temp.pos=i,temp.val=a[1]+b[i];
		q.push(temp);
	}
	for(int i=1;i<=n;i++)
	{
		int now=q.top().pos;
		int v=q.top().val;
		//cout<<"now:"<
		printf("%d ",v);
		q.pop();
		Node temp;
		temp.pos=now,++point[now],temp.val=a[point[now]]+b[now];
		q.push(temp);
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

来看这道题：

首先，题目是要求区间和，可以考虑用前缀和。
控制了区间长度在[L,R]区间内，对于每个合法的左端点i，右端点可能的位置为$min(n,i+R-1)$
我们可以对每个左端点x求一个$t(x+L-1<=t<=min(n,x+R-1))$。把$sum[x,t]$，即$pre[t]-pre[x-1]$放入优先队列，

for(int i=1;i+L-1<=n;i++)
q.push((Node){i,i+L-1,min(n,i+R-1),query(i+L-1,min(n,i+R-1))});
1
2

k次循环，每次从优先队列队首取出一个元素（优先队列内放四元组$(x,l,r,t)$,x是左端点,l和r是右端点的范围,t是当前解的右端点的位置）

struct Node
{
	int x,l,r,t;
	bool operator < (const Node& y) const
	{
		return pre[t]-pre[x-1]<pre[y.t]-pre[y.x-1];
	}
};
priority_queue<Node> q;
1
2
3
4
5
6
7
8
9

对该左端点来说，最优的右端点对应的答案已经被计入，该右端点已被弹出，但仍有若干次优右端点分布在最优右端点的左右，将它们放入优先队列（注意控制边界）。弹出k个元素即找到了k个区间，求解完成。

int x=q.top().x,l=q.top().l,r=q.top().r,t=q.top().t;
q.pop();
ans+=pre[t]-pre[x-1];
if(t!=l) q.push((Node){x,l,t-1,query(l,t-1)});
if(t!=r) q.push((Node){x,t+1,r,query(t+1,r)});
1
2
3
4
5

现在的问题在于对于每个左端点x，怎么找到t的位置。$pre[t]-pre[x-1]$，$pre[x-1]$是确定的，只需要让$pre[t]$最大即可，在$(x+L-1<=t<=min(n,x+R-1))$范围内求$pre[t]$的最大值（只不过我们用ST表记录下的是下标），RMQ问题。这就好解了。

void init()
{
    for(int i=1;i<=n;i++) st[i][0]=i;
    int t=log(n)/log(2);
    for(int j=1;j<=t;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
			st[i][j]=pre[x]>pre[y]?x:y;
		}
}

int query(int l,int r)
{
	int k=log(r-l+1)/log(2);
	int x=st[l][k],y=st[r-(1<<k)+1][k];
	return pre[x]>pre[y]?x:y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

完整代码：

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=500010;
int st[N][30];
long long pre[N],ans;
int n,k,L,R;

void init()
{
    for(int i=1;i<=n;i++) st[i][0]=i;
    int t=log(n)/log(2);
    for(int j=1;j<=t;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			int x=st[i][j-1],y=st[i+(1<<(j-1))][j-1];
			st[i][j]=pre[x]>pre[y]?x:y;
		}
}

int query(int l,int r)
{
	int k=log(r-l+1)/log(2);
	int x=st[l][k],y=st[r-(1<<k)+1][k];
	return pre[x]>pre[y]?x:y;
}
struct Node
{
	int x,l,r,t;
	bool operator < (const Node& y) const
	{
		return pre[t]-pre[x-1]<pre[y.t]-pre[y.x-1];
	}
};

priority_queue<Node> q;

int main()
{
	scanf("%d%d%d%d",&n,&k,&L,&R);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&pre[i]);
		pre[i]+=pre[i-1];
	}
	init();
	for(int i=1;i+L-1<=n;i++)
		q.push((Node){i,i+L-1,min(n,i+R-1),query(i+L-1,min(n,i+R-1))});
	while(k--)
	{
		int x=q.top().x,l=q.top().l,r=q.top().r,t=q.top().t;
		q.pop();
		ans+=pre[t]-pre[x-1];
		if(t!=l) q.push((Node){x,l,t-1,query(l,t-1)});
		if(t!=r) q.push((Node){x,t+1,r,query(t+1,r)});
	}
	cout<<ans;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

---

N - 糖果传递

链接

可以先做：
P1031 [NOIP2002 提高组] 均分纸牌
104. 货仓选址

#include
#include
#include
using namespace std;
const int N=1000010;
long long a[N],pre[N],n,ave;
long long sum,ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	ave=sum/n;//最终每个人分到的糖果
	for(int i=1;i<=n;i++)
	{
		a[i]-=ave;
		pre[i]=pre[i-1]+a[i];
		//相当于将前i个人视作一个整体，这个整体需要给后面的人（或者从后面的人处取得）一定的糖果数
	}
	//下面利用的主要是中位数的性质（到各数距离和最小）
	sort(pre+1,pre+n+1);
	int mid=pre[(n+1)/2];
	for(int i=1;i<=n;i++)
		ans+=abs(mid-pre[i]);
	cout<<ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

O - Too Rich

INPUT

3
17 8 4 2 0 0 0 0 0 0 0
100 99 0 0 0 0 0 0 0 0 0
2015 9 8 7 6 5 4 3 2 1 0
1
2
3
4

OUTPUT

9
-1
36
1
2
3

先考虑朴素的贪心：
要尽可能多拿出来钱币 <-> 把所有钱币都拿出来之后尽量少拿回去几个（当然还是得凑出来正确面额的）。想尽量少拿，就得尽量拿大面值的。于是就有了我的第一版朴素贪心：

#include
#include
using namespace std;
const int N=1000010;
long long a[N],pre[N],n,ave;
long long sum,ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	ave=sum/n;
	for(int i=1;i<=n;i++)
	{
		a[i]-=ave;
		pre[i]=pre[i-1]+a[i];
	}
	sort(pre+1,pre+n+1);
	int mid=pre[(n+1)/2];
	for(int i=1;i<=n;i++)
		ans+=abs(mid-pre[i]);
	cout<<ans;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

毫无疑问WA了。对于下面这组数据：

2
250 1 0 0 3 1 0 1 0 0 0
190 0 0 0 5 100 0 0 0 0 0
1
2
3

肉眼观察可得输出应该是 2 5 ，但上面的程序输出 -1 -1（凑不出250和190），显然是不对的。以第一组数据为例，上面的程序相当于先取了50，这导致剩下来的一个1，三个20，一个200凑不出250。主要原因就是20不是50的约数，200不是500的约数。
50可能取奇数次，这是20所凑不出的。
500可能取奇数次，这是200所凑不出的。
于是我们枚举以下四种情况

（50和500都是偶数个，不先取50和500）
（50为奇数个，500为偶数个，即我们先取一个50）
（50为偶数个，500为奇数个，即我们先取一个500）
（50为奇数个，500为奇数个，即我们先取一个50和一个500）

之后对于50和500都成对地取。
每次取50或500的时候就取偶数个。然而消除的时候也消除偶数个。
这样的枚举，就消除了这个两个特殊关系的影响啦。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
const int N=55,M=0,Z=1e9+7,maxint=2147483647,ms31=522133279,ms63=1061109567,ms127=2139062143;const double eps=1e-8,PI=acos(-1.0);//.0
int casenum,casei;
UI m;
int a[12],c[12],b[12],e[12];
int ans;
void init()
{
    c[1]=1;
    c[2]=5;
    c[3]=10;
    c[4]=20;
    c[5]=50;
    c[6]=100;
    c[7]=200;
    c[8]=500;
    c[9]=1000;
    c[10]=2000;
}
int cntmin(UI tmp,int p)
{
    int num=0;
    for(int i=p;i>=1;i--)
    {
        if(e[i]==-1)
        {
            int g=min((UI)b[i],tmp/c[i]);
            num+=g;
            tmp-=g*c[i];
        }
        else
			
        {
            int g=min((UI)b[i],tmp/c[i]);
            if(g&1)--g;
            num+=g;
            tmp-=g*c[i];
        }
    }
    if(tmp==0)return num;
    else return -1;
}
void tryit()
{
    if(e[5]>a[5]||e[8]>a[8])return;
    MS(b,0);
    int num=e[5]+e[8];
    UI tmp=e[5]*50+e[8]*500;
    for(int i=1;i<=10;i++)
    {
        if(e[i]==-1)
        {
            num+=a[i];
            b[i]=a[i];
            tmp+=a[i]*c[i];
        }
        else
        {
            b[i]=a[i]-e[i];
            if(b[i]&1)--b[i];
            num+=b[i];
            tmp+=b[i]*c[i];
        }
        if(tmp>=m)
        {
            int more=tmp-m;
            int over=cntmin(more,i);
            if(~over)
            {
                num-=over;
                gmax(ans,num);
            }
            return;
        }
    }
}
int main()
{
    init();
    scanf("%d",&casenum);
    for(casei=1;casei<=casenum;casei++)
    {
        scanf("%d",&m);
        for(int i=1;i<=10;i++)scanf("%d",&a[i]);
        MS(e,-1);ans=-1;
        e[5]=0;e[8]=0;tryit();
        e[5]=0;e[8]=1;tryit();
        e[5]=1;e[8]=0;tryit();
        e[5]=1;e[8]=1;tryit();
        printf("%d\n",ans);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

我自己写调了好久还是挂了，这是粘贴这篇博客的代码以及部分文字。特别鸣谢233

但是如果有更多(20<->50)(200<->500)这样的数对，这样整活就太麻烦了，可以考虑DFS在每个面值处递归两次（一次全部取，一次少取一个），这样写起来比打补丁的贪心简洁多了。

#include
#include
#include
#include
#include

using namespace std;
typedef long long ll;
const int v[10]= {1,5,10,20,50,100,200,500,1000,2000};
int p,c[10],totval,totcnt,ans;
 
void dfs(int left,int cur,int cnt)
{
    if(left<0) return;
    if(left==0) ans=min(ans,cnt);
    else if(cur>=0)
    {
        int num=min(left/v[cur],c[cur]);
        dfs(left-num*v[cur],cur-1,cnt+num);//全部取出
        if(num>0) dfs(left-(num-1)*v[cur],cur-1,cnt+(num-1));//少取一个
    }
}
 
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        totcnt=0,totval=0;
        scanf("%d",&p);
        for(int i=0;i<10;i++)
        {
            scanf("%d",&c[i]);
            totcnt+=c[i];
            totval+=c[i]*v[i];
        }
        ans=0x3f3f3f3f;
        dfs(totval-p,9,0);
        if(ans==0x3f3f3f3f) printf("-1\n");
        else printf("%d\n",totcnt-ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44