2019.8.16_牛客博客

YJJ's Salesman

https://cn.vjudge.net/problem/HDU-6447

坑：更新的顺序，x相同的时候用队列缓存

详解:https://blog.csdn.net/xianpingping/article/details/82055830

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
	int x,y,v;
}a[maxn];
int n;
int h[maxn];
ll val[maxn<<3];
ll dp[maxn];
void init()
{
	CLR(val);CLR(dp);
}
bool cmp(node a,node b)
{
	if(a.x!=b.x)return a.x<b.x;
	else return a.y<b.y;
}
void pushup(int rt)
{
	val[rt]=max(val[lson],val[rson]);
}
void upd(int pos,ll v,int rt,int l,int r)
{
	if(l==r)
	{
		val[rt]=max(val[rt],v);
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)upd(pos,v,lson,l,mid);
	else upd(pos,v,rson,mid+1,r);
	pushup(rt);
}
ll qry(int L,int R,int rt,int l,int r)
{
	if(L<=l&&r<=R)return val[rt];
	int mid=l+r>>1;
	ll res=0;
	if(L<=mid)res=qry(L,R,lson,l,mid);
	if(R>mid)res=max(res,qry(L,R,rson,mid+1,r));
	return res;
}
void show(node a)
{
	see(a.x),see(a.y),see(a.v),NL;
}
queue<int>Q;
int main()
{
	acc;int ttt;cin>>ttt;while(ttt--)
	{init();
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y>>a[i].v;
		sort(a+1,a+1+n,cmp);
		for(int i=1;i<=n;i++)h[i]=a[i].y;
		sort(h+1,h+n+1);
		int sz=unique(h+1,h+1+n)-h;
		//for(int i=1;i<sz;i++)see(i),see(h[i]),NL;
		for(int i=1;i<=n;i++)a[i].y=lower_bound(h+1,h+sz,a[i].y)-h;
		ll ans=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i].x!=a[i-1].x)
			{
				while(!Q.empty())
				{
					int idx=Q.front();Q.pop();
					upd(a[idx].y,dp[idx],1,1,n);
				}
			}
			if(a[i].y-1<1)
				dp[i]=a[i].v;
			else
				dp[i]=qry(1,a[i].y-1,1,1,n)+a[i].v;
			Q.push(i);
			ans=max(dp[i],ans);
		}
		cout<<ans<<endl;
	}
	return 0;
}
/*

1
3
3 1 1
1 2 2
3 1 3

2
3
1 1 1
1 2 2
3 3 1
3
1 1 1
2 2 2
3 3 3


1
3
1 1 1
1 1 2
3 1 3
*/

https://cn.vjudge.net/problem/HDU-6441

Find Integer

构造勾股数，本质上是因数分解+配凑

详解：https://www.cnblogs.com/AlphaWA/p/10652537.html

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (100000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main()
{acc;
	int ttt;cin>>ttt;while(ttt--)
	{
		int n,a;cin>>n>>a; 
		if(n==0)
		cout<<1<<' '<<2<<endl;
		else if(n==1)
		cout<<1<<' '<<a+1<<endl;
		else if(n==2)
		{
			if(a%2)
			{
				ll y,z,k;
				k=a>>1;
				y=2*k*k+2*k;
				z=y+1;
				cout<<y<<' '<<z<<endl;
			}
			else
			{
				ll y,z,k;
				k=a>>1;
				y=k*k-1;
				z=k*k+1;
				cout<<y<<' '<<z<<endl; 
			}
		} 
		else cout<<-1<<' '<<-1<<endl;
	}
	return 0;
}

https://cn.vjudge.net/problem/HDU-6444

Neko's loop

详解：https://www.cnblogs.com/chenquanwei/p/9537892.html

环上最大子段何+分类讨论，细节多

https://cn.vjudge.net/problem/HihoCoder-1831

80 Days

用双指针较为简单https://blog.csdn.net/Destinymiao/article/details/82817951

也可以用单调队列https://www.cnblogs.com/wangyiming/p/9740435.html用单调区间求每个点为右端点，长度为n的区间的最小值

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
ll c;
ll a[maxn<<1];
deque<ll>Q;
int main(){
	acc;int ttt;cin>>ttt;while(ttt--)
	{
		cin>>n>>c;while(!Q.empty())Q.pop_front();
		for(int i=1;i<=n;i++)cin>>a[i];
		ll ans=-1LL;
		for(int i=1;i<=n;i++)
		{
			ll t;cin>>t;a[i]-=t;a[i+n]=a[i];
		}
		for(int i=1;i<=n*2;i++)
		{
			while(!Q.empty()&&a[i]+c<0)
			{
				c-=a[Q.front()];
				Q.pop_front();
			}
			if(c+a[i]<0)continue;//如果这个点是起点但不合法就跳过
			c+=a[i];
			Q.push_back(i);
			if((int)Q.size()==n)
			{
				ans=Q.front();break;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

https://cn.vjudge.net/problem/HDU-6446

Tree and Permutation

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (1000000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
int head[maxn],tot,to[maxn<<1],pre[maxn<<1],len[maxn<<1],sz[maxn];
ll fac[maxn];
ll ans;
void adde(int u,int v,int l)
{
	to[++tot]=v,pre[tot]=head[u],head[u]=tot,len[tot]=l;
}
void dfs(int u,int fa)
{
	sz[u]=1;
	for(int i=head[u];i;i=pre[i])
	{
		int v=to[i],l=len[i];if(v==fa)continue;
		dfs(v,u);sz[u]+=sz[v];
		ans=(ans+2LL*l*sz[v]*(n-sz[v]))%mod;
	}
}
void init()
{
	fac[0]=1;
	for(int i=1;i<=100000;i++)
	{fac[i]=fac[i-1]*1LL*i%mod;}
}
int main()
{
	acc;init();
	while(cin>>n)
	{CLR(head);tot=0;
		for(int i=1;i<n;i++)
		{int u,v,l;
			cin>>u>>v>>l;
			adde(u,v,l),
			adde(v,u,l);
		}
		ans=0;
		dfs(1,0);
		cout<<ans*fac[n-1]%mod<<endl;
	}
	return 0;
}

https://cn.vjudge.net/problem/HihoCoder-1835

K-Dimensional Foil II

思路参照https://blog.csdn.net/Murphyc/article/details/82817989

坐标变换变回去的时候不是很懂，但自己写的WA了

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (500+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,k,R,c[maxn],x[maxn],d[maxn];
double chk(double v)
{
	double sum=0;
	for(int i=1;i<=k;i++)
	{
		double X=(double)d[i];
		if(X>v)sum+=X-v;
	}return sum;
}
int main()
{//acc;
	int ttt;RD1(ttt);while(ttt--)
	{
		RD3(n,k,R);for(int i=1;i<=k;i++)RD1(c[i]);
		for(int i=1;i<=n;i++)
		{
			int Sum=0;
			for(int j=1;j<=k;j++)
			{
				RD1(x[j]);d[j]=abs(x[j]-c[j]);
				Sum+=d[j];
			}
			double Ra=(double)R;
			double l=0,r=(double)Sum;
			while(r-l>1e-9)
			{
				double mid=(l+r)/2.0;
				if(chk(mid)>Ra)l=mid;
				else r=mid;
				//see(l),see(r),see(Ra),NL;
			}
			for(int j=1;j<=k;j++)
			{
				double X=(double)d[j];
				double Y;
				/*if(X>l)Y=(X-l)*(x[j]<0?-1.0:1.0);
				else Y=0;
				Y+=(double)c[j];*/
				if(X>l)X=l;
				if(x[j]>c[j])Y=-X+(double)x[j];
				else Y=X+(double)x[j];
				printf("%.8f ",Y);
			}
			printf("\n");
		}
	}
	return 0;
}

https://cn.vjudge.net/problem/HDU-6444

Neko's loop

大致思路见https://blog.csdn.net/a1214034447/article/details/82055455

关键点在于，m次的（起点或）终点必定包含最大子段，相当于通过最大子段确定了（起点或）终点，大部分代码里按终点算的

环上子段长度不超过len的最大和可以用单调队列，也可以线段树

m比循环节小，或是一圈的收益<0,吗，这两种单独讨论

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%lld",&x)
#define RDL2(x,y) scanf("%lld %lld",&x,&y)
#define RDL3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (10000+10)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int a[maxn];
bool vis[maxn];
ll sum[maxn<<1];
int n,m,k;
ll s;
deque<ll>Q;
ll cal(int len,int tot)
{
	while(!Q.empty())Q.pop_back();
	//see(len),NL;
	ll ans=0;
	for(int i=1;i<=tot;i++)
	{
		while(!Q.empty()&&i-Q.front()>len)Q.pop_front();
		if(Q.empty())ans=max(ans,sum[i]);
		else ans=max(ans,sum[i]-sum[Q.front()]);
		while(!Q.empty()&&sum[i]<=sum[Q.back()])Q.pop_back();
		Q.push_back(i);
	}
	return ans;
}
int main()
{
	int ks=1;
	acc;int ttt;cin>>ttt;while(ttt--)
	{
		CLR(vis);
		cin>>n>>s>>m>>k;for(int i=1;i<=n;i++)cin>>a[i];
		ll ans=0;
		for(int ii=1;ii<=n;ii++)
		{
					if(vis[ii])continue;
					int cnt=0;
					ll val=0;
					for(int j=ii;!vis[j];j=(j+k-1)%n+1)
					{
						vis[j]=1,sum[++cnt]=a[j],val+=1LL*a[j];		
						//see(j),NL;
					}
					
					for(int i=1;i<=cnt;i++)
						sum[i+cnt]=sum[i];
					for(int i=1;i<=2*cnt;i++)
						sum[i]+=sum[i-1];
					if(m<=cnt)
					{
						ans=max(ans,cal(m,cnt*2));
					}
					else if(val<=0)
					{
						ans=max(ans,cal(cnt,cnt*2));
					}
					else
					{
						//see(ans),see(cal(m%cnt,cnt*2)),see((m/cnt)*val),NL;
						if(m%cnt)
							ans=max(ans,cal(m%cnt,cnt*2)+(m/cnt)*val);
						ans=max(ans,cal(cnt,cnt*2)+(m/cnt-1)*val);
						//see(ans),NL;
					}
					//see(val),see(m),see(cnt),see(k),see(ans),NL;
		}
		cout<<"Case #"<<ks++<<": "<<max(s-ans,0LL)<<endl;
	}
	return 0;
}
/*
4
3 10 5 2
3 2 1
5 20 6 3
2 3 2 1 5
3 10 5 2
3 2 1
5 20 6 3
2 3 2 1 5
*/