【无标题】

United We Stand(Problem - A - Codeforces)

题目大意：现有一个长为n的数组a,要拆成两个数组b,c,要求b中的任何一个元素不能整除c中的任何一个元素。

思路：我们只要将a中所有最小的挑出来，放入b，然后剩下的放入a就可以实现。

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int mi=0x3f3f3f3f;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),mi=min(mi,a[i]);
		int c=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==mi) c++;
		}
		if(c==n) printf("-1\n");
		else
		{
			printf("%d %d\n",c,n-c);
			for(int i=1;i<=c;i++) printf("%d ",mi);
			printf("\n");
			for(int i=1;i<=n;i++)
			{
				if(a[i]!=mi) printf("%d ",a[i]);
			}
			printf("\n");
		}
	}
}

Olya and Game with Arrays（Problem - B - Codeforces）?

题目大意：现在有若干个数组，我们只能从每个数组中移走一个数，但被移走的这些数可以放进任意一个数组。操作完成之后，我们求出每个数组的最小值，然后求和。

思路：显然，如果一个数组能够输出第二小的数，那么肯定比输出第一小的数要好，然后我们移走一个数组中最小的数后就可以实现输出第二小的数，但是这些被移走的数肯定得有一个地方放，而且最小的数无论被移到哪里都是会被输出的。所以一定有一个数组第二小的数没办法被输出，那么我们就找出所有第二小的数，然后从大到小排序，然后从前往后加，加到第n-1个，然后再加上所有数中最小的数即可。

#include<bits/stdc++.h>
using namespace std;
int a[200010];
bool cmp2(pair<int,int>a,pair<int,int>b)
{
	return a.second>b.second;
}
signed main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d",&n);
		vector<pair<int,int>>p;
		int mi=0x3f3f3f3f;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&m);
			for(int j=1;j<=m;j++) 
			{
				scanf("%d",&a[j]);
				//printf("%d\n",a[j]);
				mi=min(mi,a[j]);
			}
			sort(a+1,a+1+m);
			p.push_back({a[1],a[2]});
		}
		if(n==1) printf("%d\n",mi);
		else
		{
			long long sum=0;
			sort(p.begin(),p.end(),cmp2);//按第二维从大到小排
			for(int i=0;i<p.size()-1;i++) sum += (long long)p[i].second;
			sum += (long long)mi;
			printf("%lld\n",sum);
		}
	}
}

Another Permutation Problem（Problem - C - Codeforces）

题目大意：现在限制排列的长度，要求自定义排列顺序，使得sum(a[i]*i)-max(a[i]*i)的结果最大，输出最大结果。

思路：我们首先看一下能找出哪些性质：
假设原来的数和序号一一对应，那么交换后，和会变小

在末尾进行交换操作，可以使被减掉的数变小。

所以第一个思路就是前面尽量不换，后面交换。具体执行是选一段区间逆转它，其实有猜的成分在里面，但是确实对于样例可以通过，对于题目也可以通过。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int mx=0;
		for(int i=0;i<=n;i++)//选定保留长度
		{
			int sum=0,to=0;
			for(int j=1;j<=i;j++) sum += j*j,to=max(to,j*j);
			for(int j=i+1,z=n;j<=n;j++,z--)
			{
				sum += j*z;
				to=max(j*z,to);
			}
			mx=max(mx,sum-to);
		}
		printf("%d\n",mx);
	}
}

ps:这里有一点要注意，就是自己在推样例猜的时候一定要把变化算清楚，不然推出正确结果也会被判成否定的。

思路2：因为我们要减去最大值，所以我们就可以枚举规定最大值，然后找合法的排序，进而找出结果。我们可以将1-n的数记录在set中，每次从大到小，在集合中找大于i/j的第一位（i是我们枚举的最大值，j是我们当前找的位置），如果找到开头，就说明这个数不存在于集合当中 ，因为我们是向后找一位得到的。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		int mx=0;
		for(int i=1;i<=n*n;i++)
		{
			set<int>s;
			for(int j=1;j<=n;j++) s.insert(j);
			int sum=0;
			for(int j=n;j>=1;j--)
			{
				auto it=s.upper_bound(i/j);
				if(it==s.begin())//因为我们往后找一位，往后找一位找到开头，就说明使它成立的值不在集合当中，那么肯定判否
				{
					sum=0;
					break;
				}
				it--;
				sum += (*it)*j;
				s.erase(it);
			}
			mx=max(mx,sum-i);
		}
		cout<<mx<<endl;
	}
}

ps:这个思路的暗示就在于n<500，所以差不多是n^3的时间复杂度，然后枚举最大值的循环复杂度是n*n,给每个点找匹配logn,总共n个点，刚好是n*n*n*logn

Andrey and Escape from Capygrad(Problem - D - Codeforces)

题目大意：现在有若干个区间[l,r],每段区间上有一段核心区域[a,b]，我们只要处在[l,r]上就可以跳到[a,b]上任意一点，现给出若干个查询，问在每个查询位置时，最远能到哪里。

思路：

这个题属于扫描线类型的题目，之前其实遇到过类似的，但是当时不知道那个思路的名字，只是觉得思路很妙。这个思路主要用来做多组区间多组单点查询的题目，点的结果与区间位置有关系，那么就可以看一看能不能将区间端点和待访问的点记录在一块儿，通过遍历，来动态找出答案

#include<bits/stdc++.h>
using namespace std;
int s[200010],ans[200010];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		vector<pair<int,pair<int,int>>>q;
		for(int i=1;i<=n;i++)
		{
			int l,r,a,b;
			scanf("%d%d%d%d",&l,&r,&a,&b);
			q.push_back({l,{-1,i}});
			q.push_back({b,{1,i}});
		}
		int qt;
		scanf("%d",&qt);
		for(int i=1;i<=qt;i++)
		{
			int x;
			scanf("%d",&x);
			q.push_back({x,{0,i}});
		}
		sort(q.begin(),q.end());
		reverse(q.begin(),q.end());
		int hh=0,tt=0;
		for(int i=0;i<q.size();i++)
		{
			int v=q[i].first,type=q[i].second.first,idx=q[i].second.second;
			if(type==1) s[tt++]=v;
			else if(type==-1) tt--;
			else 
			{
				if(hh==tt) ans[idx]=v;
				else ans[idx]=s[hh];
			}
		}
		for(int i=1;i<=qt;i++) printf("%d ",ans[i]);
		printf("\n");
	}
}

?Maximum Monogonosity（Problem - E - Codeforces）?

题目大意：有两条线，线上各有n个节点，我们我们可以选定一段区间[l,r]，然后这一段的价值就是abs(a[l]-b[r])+abs(a[r]-b[l]),这一段的长度定义为r-l+1。我们现在需要选出总长度不超过k的若干段区间，使得这些区间的价值最大。（这题用到斜率优化dp，等我学完来贴个博客链接）

思路：虽然这里要选的不是单个的物品，但实际上我们也可以用动态规划来做。

状态表示:dp[i][j]表示从前i个中选，长度恰好是j的价值，它的值表示最大价值。

状态计算:

不选第i个点：dp[i][j]=dp[i-1][j];

选第i个点：dp[i][j]=max(dp[i-x][j-x]+w[i-x+1,i])

w[i-x+1,i]表示从从i往前延伸长度为x的区间得到的价值，dp[i-x][j-x]表示从前i-x中选，消耗j-x个长度得到的最大值，至于x的长度，我们可以暴力枚举来做。

理论上是可以的，但是，这样时间复杂度太高了，而且这道题的数据范围又很大，那么我们就要进行优化。

我们先把选i点的情况展开：

dp[i][j]=max(

dp[i-x][j-x]+a[i]-b[i-x+1]+b[i]-a[i-x+1]

dp[i-x][j-x]-a[i]+b[i-x+1]+b[i]-a[i-x+1]

dp[i-x][j-x]+a[i]-b[i-x+1]-b[i]+a[i-x+1]

dp[i-x][j-x]-a[i]+b[i-x+1]-b[i]+a[i-x+1]

)

所以现在只需要把正负号的对应关系讨论清楚即可。

dp[i-x][j-x]-b[i-x+1]-a[i-x+1]+a[i]+b[i]

dp[i-x][j-x]+b[i-x+1]-a[i-x+1]-a[i]+b[i]

dp[i-x][j-x]-b[i-x+1]+a[i-x+1]+a[i]-b[i]

dp[i-x][j-x]+b[i-x+1]+a[i-x+1]-a[i]-b[i]

mx1[i-j]=dp[i-x][j-x]-b[i-x+1]-a[i-x+1]

mx2[i-j]=dp[i-x][j-x]+b[i-x+1]-a[i-x+1]

mx3[i-j]=dp[i-x][j-x]-b[i-x+1]+a[i-x+1]

mx4[i-j]=dp[][]+b[i-x+1]+a[i-x+1]

#include<bits/stdc++.h>
using namespace std;
int dp[3010][3010],mx1[3010],mx2[3010],mx3[3010],mx4[3010];
int a[3010],b[3010];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		memset(mx1,-0x3f,sizeof mx1);
		memset(mx2,-0x3f,sizeof mx2);
		memset(mx3,-0x3f,sizeof mx3);
		memset(mx4,-0x3f,sizeof mx4);
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j) dp[i][j]=-0x3f3f3f3f;
		dp[0][0]=0;
		mx1[0]=-a[1]-b[1]; mx2[0]=-a[1]+b[1]; mx3[0]=a[1]-b[1]; mx4[0]=a[1]+b[1];
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=k;j++)
			{
				if(j>i) break;
				dp[i][j]=dp[i-1][j];
				dp[i][j]=max(dp[i][j],mx1[i-j]+a[i]+b[i]);
				dp[i][j]=max(dp[i][j],mx2[i-j]-a[i]+b[i]);
				dp[i][j]=max(dp[i][j],mx3[i-j]+a[i]-b[i]);
				dp[i][j]=max(dp[i][j],mx4[i-j]-a[i]-b[i]);
				if(i!=n)
				{
					mx1[i-j]=max(mx1[i-j],dp[i][j]-b[i+1]-a[i+1]);
					mx2[i-j]=max(mx2[i-j],dp[i][j]+b[i+1]-a[i+1]);
					mx3[i-j]=max(mx3[i-j],dp[i][j]-b[i+1]+a[i+1]);
					mx4[i-j]=max(mx4[i-j],dp[i][j]+b[i+1]+a[i+1]);
				}
				ans = max(ans,dp[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}