问题集合Tag ArchiveSubscribe

• 有 N 个数，初始均为 0。有 Q 个操作，第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问，所有操作结束后，每个数的值

并查集维护每个点右边最近的未修改的点，把操作全部读入以后倒序处理，因为是倒着处理所以每个点只能被修改一次，直接用数组记录就可以了。初始f[i]=i;当l..r合并以后区间内每个f[i]=i+1;查询函数加上路径压缩，当遇见一个被改变过的点可以立刻跳过后面所有被改变了的点

#include<iostream>
#include<stdio.h>
using namespace std;
int f[1001]={0};
int qm[1001][3]={0};
int a[1001]={0};
int n=0,q=0;
int ff(int x)
{
	if(f[x]==x) return x;
	else return f[x]=ff(f[x]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n+2;i++) f[i]=i;
	for(int i=q;i>0;i--)
	{
		scanf("%d%d%d",&qm[i][1],&qm[i][2],&qm[i][0]);
	}
	for(int i=1;i<=q;i++)
	{
		int l=qm[i][1],r=qm[i][2],v=qm[i][0];
		while(l<=r)
		{			
			l=ff(l);
			if(l<=r)
			{
				a[l]=v;
				f[l]=l+1;
				l+=1;
			}
			else
			{
				break;
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
} 

 … Read the rest

• 蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”：因为非齐次方程组的系数行列式为0，所以方程的解不唯一，所以最后一个方程没有贡献。

末态相同的题目，可以往方程组方向去想。最后可以往坐标的距离方面去靠。

• 蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明：

设开始每个墓碑相差A，移动后每个墓碑相差M，M可以不相同，因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

[latex][/latex]A-X_1+X_2=M =X_2=X_1-(A-M)

A-X_2+X_3=M =X_3=X_1-2(A-M)

…

A-X_n+X_1=M =X_n=X_1-n(A-M)

同样可以变成X1到各个数字的距离最小的问题，即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案，因为M仅仅是假设存在一个M使其满足末态，由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest

• 中间商优化

http://codeforces.com/problemset/problem/867/E

一个长度为N的序列，代表每天股票的价格，每天只能执行 买/卖/无动作 三种操作。问如何才能赚得最多。

维护一个优先队列，队首存当前最小的价格，见到比最小的价格高的就先卖掉，并且把低价股票的价格变成当前价格，更低的就进队。如果以后遇到更高的可以和交易过的股票交易，也可以和没交易过的股票交易，它们赚的钱是一样的。。经过xyjj的指点知道了这类题的做法叫中间商优化，先找到更高的卖了提升价格，以后可以继续交易。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans=0;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		b.push(t);
		if(b.top()<t)
		{
			ans+=t-b.top();
			b.pop();
			b.push(t);
		}
	}
	printf("%lld",ans);
}

 … Read the rest