1. 全栈程序员必看首页

noip2011 day1[通俗易懂]

全栈程序员-站长 • • 未分类 • 阅读 2

noip2011 day1[通俗易懂]简单模拟，蜜汁WA。因为错了还是写一下思路：   先保存，然后倒着(n到1)枚举覆盖目标点的毯子，找到即是答案。#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#include<cctype>…

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

noip2011 day1[通俗易懂]noip2011 day1[通俗易懂]

简单模拟，蜜汁WA。

因为错了还是写一下思路： 

    先保存，然后倒着(n到1)枚举覆盖目标点的毯子，找到即是答案。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define RG register
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define llin(x) x = lread
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x)
#define out(x) print(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n') 
#define ko putchar(' ')
const ll p = 1e10 + 7;
const int MAXN = 1e5+5;
int n;
int gx,gy;
int ans = -1;

struct tan
{
	int x,y;
	int lx,ly;
}cpt[MAXN];

inline int read() 
{
    int X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}

inline ll lread()  
{
    ll X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=((X<<3)+(X<<1)+ch-'0')%p,ch=getchar();
    return X*w;
}

void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}

void init()
{
	in(n);
	for(int i = 1;i <= n;i++)
	{
		in(cpt[i].x);in(cpt[i].y);
		in(cpt[i].lx);in(cpt[i].ly);
		cpt[i].lx = cpt[i].lx+cpt[i].x;
		cpt[i].ly = cpt[i].ly+cpt[i].y;
	}
	in(gx);in(gy);
}

void work()
{
	for(int i = n;i >= 1;i--)
	{
		if(cpt[i].ly >= gy && cpt[i].lx >= gx && cpt[i].x <= gx && cpt[i].y <= gy)
		{
			ans = i;
			break;
		} 
	}
	out(ans);
}

int main()
{
//	freopen("carpet.in","r",stdin);
//	freopen("carpet.out","w",stdout);
	init();
	work();
	return 0;
}

noip2011 day1[通俗易懂]noip2011 day1[通俗易懂]

显而易见的四重循环暴力，第一层枚举颜色，第二层枚举枚举第一个客栈，第三层枚举另一个同色客栈，第四层枚举两客栈中间的客栈（包括两同色客栈），找到就+1。

这是最暴力的：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define RG register
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define llin(x) x = lread
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x)
#define out(x) print(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n') 
#define ko putchar(' ')
const int MAXN = 2e5 + 5;
int n,k,p;
int cost[MAXN]; 
bool flag = 0;
vector<int> color[55];
ll ans = 0;

inline int read() 
{
    int X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}

inline ll lread()  
{
    ll X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}

void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}

void init()
{
	in(n); in(k); in(p);
	for(int i = 1;i <= n;i++)
	{
		int t;
		in(t);
		color[t].push_back(i);
		in(cost[i]);
	}
}

void work()
{
	int h,t;
	for(int i = 0;i < k;i++)
	{
		for(int j = 0;j < color[i].size();j++)
		{
			h = color[i][j];
			flag = 0;
			for(int l = j+1;l < color[i].size();l++)
			{
				t = color[i][l];
				for(int o = h;o <= t;o++)
				{
					if(cost[o] <= p)
					{
//						int len = color[i].size();
						ans++;
						break;
//						flag = 1;
//						break;
					}
				}
//				if(flag == 1) break;
			}
		}
	}
	lout(ans);
}

int main()
{
//	freopen("hotel.in","r",stdin);
//	freopen("hotel.out","w",stdout);
	init();
	work();
	return 0;
}

然后其实上面那个O（不知多少）的算法可以优化为O（n）的做法。

思路就是，从1到n枚举，输入color和price的值，我们需要记录一个距离第二个客栈最近的咖啡厅价钱合理的客栈位置，用一个now变量记录。

开三个辅助数组，last[i]表示最后一个以i为颜色的客栈的位置，cnt[i]表示以i为颜色的客栈总数，sum[i]可以看作是一个临时数组，用来存储当前的方案数。

可以这么想，当前枚举到一个客栈i，这个i是第二个客栈，那么显然第一个客栈一定在第二个客栈之前，编号必定是0~i-1之间的一个数。如果我发现枚举的时候在某一个客栈前面有一个价钱合理的咖啡厅，那么在这之前的任何一个同色客栈都是第一个客栈可以选的，那么统计一下数量，这就是当前的方案数。

然后更新last数组，更新ans，让cnt[color]++，这样从左到右地推过来就好了。

#include<bits/stdc++.h>
using namespace std;
#define RG register
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define llin(x) x = lread
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x)
#define out(x) print(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n')
#define ko putchar(' ')
const int MAXN = 55;
int n,k,p;
int color,price;
int last[MAXN],sum[MAXN],cnt[MAXN];
int ans = 0;
int now;

inline int read()
{
	int X=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
	return X*w;
}

inline ll lread()
{
	ll X=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
	return X*w;
}

void print(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		print(x/10);
	}
	putchar(x%10+'0');
}

int main()
{
	in(n);in(k);in(p);
	for(int i = 1;i <= n;i++)
	{
		in(color);in(price);
		if(price <= p)
			now = i;
		if(now >= last[color])
			sum[color] = cnt[color];
		ans += sum[color];
		last[color] = i;
		cnt[color]++;
	}
	out(ans);
	return 0;
}

noip2011 day1[通俗易懂]noip2011 day1[通俗易懂]noip2011 day1[通俗易懂]

总而言之，四条剪枝原则：

（1）交换两个颜色相同的块没有意义

（2）一个块的左边是非空块时不需要考虑左移,因为会和之前的块右移重复，即只有当左块为空时才左移

（3）根据题目优先度的排序，可以知道，右移优先于左移，所以在dfs时先考虑右移

（4）如果有一种颜色当前的块数目x满足1<=x<=2，则此情况不合法

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define RG register
#define ll long long
#define in(x) x = read()
#define lin(x) scanf("%lld",&x)
#define llin(x) x = lread
#define din(x) scanf("%lf",&x)
#define dout(x) printf("%lf",x)
#define out(x) print(x)
#define lout(x) printf("%lld",x)
#define ex putchar('\n') 
#define ko putchar(' ')
#define loop(i,a,b) for(int i = a;i <= b;i++)
#define pool(i,a,b) for(int i = a;i >= b;i--)
const ll p = 1e10 + 7;
const int MAXN = 11;
int n;
int high;
int b[10][MAXN][MAXN];
int a[MAXN][MAXN];
bool usd[MAXN][MAXN];
struct p
{
	int x,y,mv;
}ans[10];

inline int read() 
{
    int X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}

inline ll lread()  
{
    ll X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=((X<<3)+(X<<1)+ch-'0')%p,ch=getchar();
    return X*w;
}

void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}

bool check()
{
	loop(i,0,4)
		if(a[i][0]) return 0;
	return 1;
}

void find()
{
	loop(i,0,4)
	{
		int num = 0;
		for(int j = 0;a[i][j];j++)
		num++;
		if(num > high) high = num;
	}
	high--;
}

void down()
{
	loop(i,0,4)
		loop(j,0,high)
		{
			int h = i,k = j;
			while(a[h][k] && !a[h][k-1] && k > 0)
				swap(a[h][k],a[h][k-1]),k--;
		}
}

void change()
{
	down();
	bool f1 = 0;
	pool(i,high,0)
		loop(j,0,4)
		{
			if(a[j][i])
			{
				int h = j,num = 0;
				while(a[j][i] == a[h][i] && h < 7) h++,num++;
				h--;
				if(num >= 3)
				{
					f1 = 1;
					loop(k,j,h)
						usd[k][i] = 1;
				}
				h = i,num = 0;
				while(a[j][i] == a[j][h] && h >= 0) h--,num++;
				h++;
				if(num >= 3)
				{
					f1 = 1;
					loop(k,h,i)
						usd[j][k] = 1;
				}
			}
		}
	if(f1)
	{
		pool(i,high,0)
			loop(j,0,4)
			 if(usd[j][i])
			 {
			 	usd[j][i] = 0;
			 	a[j][i] = 0;
			 }
		change();
	}
	return;
}

void dfs(int x)
{
	if(x > n)
	{
		if(check())
		{
			loop(i,1,n)
			{
				out(ans[i].x);
				ko;
				out(ans[i].y);
				ko;
				out(ans[i].mv);
				ex;
			}
			exit(0);
		}
		return;
	}
	
	loop(k,0,4)
		loop(l,0,high)
			b[x][k][l] = a[k][l];

	loop(i,0,4)
		loop(j,0,high)
		if(a[i][j])
		{
			if(i != 4 && a[i][j] != a[i+1][j])
			{
				ans[x].x = i;
				ans[x].y = j;
				ans[x].mv = 1;
				swap(a[i][j],a[i+1][j]);
				change();
				dfs(x+1);
				loop(k,0,4)
					loop(l,0,high)
						a[k][l] = b[x][k][l];
			}
			if(!a[i-1][j] && i > 0)
			{
				ans[x].x = i;
				ans[x].y = j;
				ans[x].mv = -1;
				swap(a[i][j],a[i-1][j]);
				change();
				dfs(x+1);
				loop(k,0,4)
					loop(l,0,high)
						a[k][l] = b[x][k][l];
			}
		}		
}

void init()
{
	in(n);
	for(int i = 0;i < 5;i++)
	{
		int h = 0;
		int t;
		in(t);
		while(t != 0) 
		{
			a[i][h++] = t;
			in(t);
		}			
	}
}

void work()
{
	find();
	dfs(1);
	cout << -1;
}

int main()
{
	init();
	work();
	return 0;
}


版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/189713.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • 动态规划之背包问题及输出背包具体方案[通俗易懂]

    动态规划之背包问题及输出背包具体方案[通俗易懂]

    动态规划之背包问题及输出背包具体方案[通俗易懂]题型1：LintCode92.背包问题题目：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]。分析：dp[i][j]：当背包总重量为j且目前有i个物品时，背包最多装满dp[i][j]的空间。      状态转移方程为：dp[i][j]=max{dp[i-1][j-A[i-1]]+A[i-1],dp[i-1][j]}，其中dp[i-1][j-A[…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月26日
    12
  • java基础菜鸟教程_java基础菜鸟教程大全，java入门「建议收藏」

    java基础菜鸟教程_java基础菜鸟教程大全，java入门「建议收藏」

    java基础菜鸟教程_java基础菜鸟教程大全，java入门「建议收藏」java这个词语相信大家都听的耳朵快要起茧了吧，就算是没学过编程的小伙伴也一定听说过java，谁让它如今几乎火遍大江南北呢。这次我们就来讲解一些常见的java基础，希望能够让你们更加了解java。java基本概念一、什么是程序?为了完成任务，执行一系列有序的指令的集合。指令:命令。二、Java程序设计2.1什么是Java?是撰写跨平台，面向对象的计算机语言。2.2Java能做什么?开发桌面应用…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月1日
    77
  • datagrip 2021.11.4 激活码(JetBrains全家桶) idea

    datagrip 2021.11.4 激活码(JetBrains全家桶)

    (datagrip 2021.11.4 激活码)这是一篇idea技术相关文章，由全栈君为大家提供，主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，下面是详细链接哦~https://javaforall.net/100143.html0E14HXZ4QL-eyJsaWN…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年3月29日
    55
  • flex vue 垂直居中居上_推荐几种在移动端实现垂直居中的方法[通俗易懂]

    flex vue 垂直居中居上_推荐几种在移动端实现垂直居中的方法[通俗易懂]

    flex vue 垂直居中居上_推荐几种在移动端实现垂直居中的方法[通俗易懂]推荐几种在移动端实现垂直居中的方法。方法1:table-cellhtml结构垂直居中CSS.box1{display:table-cell;vertical-align:middle;text-align:center;}方法2：display:flex.box2{display:flex;justify-content:center;align-items:Center;}123…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月13日
    36
  • 栈和队列讲解_栈和队列的优缺点

    栈和队列讲解_栈和队列的优缺点

    栈和队列讲解_栈和队列的优缺点目录1、栈（1）栈的概念及结构（2）栈的实现2、队列（1）队列的概念及结构（2）队列的实现前言：栈和队列是在顺序表和链表的延伸，如果前面的顺序表和链表你已经掌握了的话，栈和队列对你来说应该就是小菜一碟了。1、栈（1）栈的概念及结构栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（LastInFirstOut）的原则。压栈：栈的插入操作叫做进栈/压栈..

    全栈程序员-站长的头像 全栈程序员-站长
    2025年6月22日
    4
  • webstorm2021永久激活【2021.10最新】 idea

    webstorm2021永久激活【2021.10最新】

    (webstorm2021永久激活)这是一篇idea技术相关文章，由全栈君为大家提供，主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，下面是详细链接哦~https://javaforall.net/100143.html1435QFILVV-eyJsaWN…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年3月30日
    775

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号