2019.8.16

YJJ's Salesman

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

#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

构造勾股数，本质上是因数分解+配凑
#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

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





80 Days

也可以用单调队列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;
}



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;
}



K-Dimensional Foil II

坐标变换变回去的时候不是很懂，但自己写的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;
}





Neko's loop

关键点在于，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
*/


全部评论

相关推荐

11-30 00:10
湖南大学 嵌入式软件开发
嵌软秋招两万字八股文汇总（六）
面试问题：Cvte面试：1、&nbsp;介绍一下Linux内核的链表。采用侵入式设计，list_head结构体，不包含数据，只包含指向前一个结构体的指针prev和后一个的next；用的时候首先用LIST_HEAD创建一个空的链表头，是由linux内核提供通用的链表操作宏和函数进行链表操作，避免了操作函数的代码重复，实现通用性，提高了效率。海康面试：2、&nbsp;linux驱动开发里中断嵌套可能会发生什么问题？上半部/下半部冲突：如果中断嵌套发生在相同设备的中断线上，并且新的中断触发了与当前正在执行的上半部或下半部相同的处理逻辑，可能会导致数据竞争、状态不一致或其他未定义的行为。&nbsp;例如，两个中断可能会同时尝试修改...
面试问题记录
点赞 评论 收藏
分享
12-04 17:17
已编辑
门头沟学院 Java
普通大学生的秋招（互联网/私企类 - 进行中）
26Java后端&nbsp;双9&nbsp;非cs硕&nbsp;timeline：&nbsp;✅拼多多（实习转正）：9月29日&nbsp;意向&nbsp;✅荣耀（ssp）：11月10日&nbsp;oc、10月21日&nbsp;线下二面、10月14日&nbsp;测评、10月14日&nbsp;一面、9月25日&nbsp;笔试&nbsp;✅顺丰科技：11月12日&nbsp;oc、10月22日&nbsp;三面、10月17日&nbsp;二面、10月13日&nbsp;一面、9月28日&nbsp;笔试&nbsp;✅中兴（池）：10月16日&nbsp;二面、10月11日&nbsp;线下一面、9月29日&nbsp;笔试&nbsp;▶️虾皮（补录）：12月4日&nbsp;HR面、11月27日&nbsp;二面、11月22日&nbsp;一面&nbsp;❌得物（第一次投递）：9月1日&nbsp;AI面、8月31日&nbsp;笔试&nbsp;❌快手：9月2日&nbsp;一面挂&nbsp;❌腾讯：9月4日&nbsp;一面挂&nbsp;❌携程：9月...
投递快手等公司10个岗位
点赞 评论 收藏
分享
10-12 00:07
哈尔滨理工大学 自动化
秋招好难啊
这简历还有必要投了吗
LXXXXd：有点杂，想搞自动化的话没必要把法律的经历写上去
点赞 评论 收藏
分享
10-24 18:54
南京大学 后端工程师
腾讯这招太狠了
QQ邮箱把字节意向归类到了广告邮件😂
看起来名字可以很长：笑死 我暑期实习阿里云的意向也被 qq 邮箱放在垃圾箱了
点赞 评论 收藏
分享
昨天 11:41
基恩士_销售工程师(准入职员工)
基恩士内推，基恩士内推码
问题（面试刚开始会让做一个自我介绍，可以提前准备一下）&nbsp;1.我是如何实现一周涨粉5000+的？&nbsp;这个问题是根据经历上面的经验提问的&nbsp;我简单回答了一下&nbsp;选题策划-AB测试-评论转换-账号定位一些内容&nbsp;2.为什么开始这个小红书运营项目？&nbsp;其实这是老师布置的小组作业&nbsp;我回答：有项目想法-调研后熟悉小红书规则等等&nbsp;3.在运营账号过程中有没有低谷期或者困难你是怎么解决的？&nbsp;这个问题的核心：就是问你遇到困难是如何解决的？&nbsp;4.你有没有向他人推销产品的经历？如果有你是如何推销的？&nbsp;这个我刷到收到面试的同学好像都问了&nbsp;这个问题必须准备，好好回答是一个必答题&nbsp;5.你推销产品时其他人是什么反应？&nbsp;我当时的回答是“...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 为了去实习，我赌上了___ #
19060次浏览 197人参与
# 摸鱼被leader发现了怎么办 #
70648次浏览 407人参与
# 百融云创求职进展汇总 #
163次浏览 0人参与
# uu们，春招你还来吗？ #
11216次浏览 79人参与
# 2025年终总结 #
11796次浏览 211人参与
# 哪一瞬间让你觉得“这班不如不上” #
10536次浏览 147人参与
# 父母对你找工作是助力还是阻力？ #
12812次浏览 192人参与
# 如果可以，你希望哪个公司来捞你 #
154739次浏览 650人参与
# 降低公积金和取消房补怎么选 #
23341次浏览 79人参与
# 工作中哪个瞬间让你想离职 #
109351次浏览 771人参与
# 十二月请对我好一点 #
23975次浏览 326人参与
# 高薪高压 vs 低薪wlb，你怎么选？ #
10194次浏览 110人参与
# 一人推荐一个值得做的项目 #
8581次浏览 115人参与
# 运营每日一题 #
112626次浏览 885人参与
# 第一份工作能做外包吗？ #
85820次浏览 574人参与
# 这些公司卡简历很严格 #
80210次浏览 367人参与
# 硬件人的简历怎么写 #
317088次浏览 3063人参与
# 工作前VS工作后，你的心态变化 #
12616次浏览 152人参与
# 学历or实习经历，哪个更重要 #
201914次浏览 1069人参与
# 秋招提前批启动你开冲了吗 #
160700次浏览 2244人参与
# 工作中出现了XX情况正常吗 #
30829次浏览 209人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务