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


相关推荐

  • Jenkins安装_jenkins安装与配置

    Jenkins安装_jenkins安装与配置

    Jenkins安装_jenkins安装与配置前言jenkins的环境搭建方法有很多，本篇使用docker快速搭建一个jenkins环境。环境准备：mac/Linuxdockerdocker拉去jenkins镜像先下载jenkins镜

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月30日
    6
  • 光场相机可以计算光线的方向,也可以计算目标的深度_相机感光器在哪里

    光场相机可以计算光线的方向,也可以计算目标的深度_相机感光器在哪里

    光场相机可以计算光线的方向,也可以计算目标的深度_相机感光器在哪里博主最近在搞光场相机方面的研究啦，好了废话不多说，开始！1.一些前言废话首先，来一下光场的基本概念，来自百度百科。光场（lightfield）：就是指光在每一个方向通过每一个点的光量。从概念里

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月3日
    6
  • html5 a标签去下划线,css中如何去掉a标签的下划线？[通俗易懂]

    html5 a标签去下划线,css中如何去掉a标签的下划线？[通俗易懂]

    html5 a标签去下划线,css中如何去掉a标签的下划线？[通俗易懂]我们在HTML网页制作过程中，相信大家对css文本超链接这个概念并不陌生。我们都知道想要给某段文本或者指定元素添加一个锚点也就是超链接需要用到HTML中的a标签。那么有的新手可能就会发现，在使用a标签时文本超链接会自动出现下划线！从视觉美观上来说枯燥单调的文本超链接显示显然并不好看。那么该如何去掉a标签的下划线呢？下面我们来看一下css去掉a标签下划线的方法。本篇文章就给大家详细讲讲怎么去掉css…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月2日
    61
  • 2021软件测试面试题及答案_2021年软件测试面试题大全

    2021软件测试面试题及答案_2021年软件测试面试题大全

    2021软件测试面试题及答案_2021年软件测试面试题大全1.数据库增删改查基本上查询考的比较多，也有考察新增，修改，删除的，极个别的会给出表结构，字段要求，让你据此建表以及临时表查询语句主要考察子查询，聚合函数，多表查询，分组，可参考下面链接（sql50题）sql50题插入语句insertinto[table]([column],[column])values(?,?)删除语句deletefrom[table]wherecolumn=?修改语句update[table]setcolumn=?wherec

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月26日
    6
  • SOAP协议规范

    SOAP协议规范

    SOAP协议规范SOAP协议规范SOAP协议规范1.简介SOAP以XML形式提供了一个简单、轻量的用于在分散或分布环境中交换结构化和类型信息的机制。SOAP本身并没有定义任何应用程序语义，如编程模型或特定语义的实现；实际上它通过提供一个有标准组件的包模型和在模块中编码数据的机制，定义了一个简单的表示应用程序语义的机制。这使SOAP能够被用于从消息传递到RPC的各种系统。SOAP包括三个部

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月27日
    4
  • 通过数据泵expdp、impdp方式备份与还原（导出与导入）Oracle数据库

    通过数据泵expdp、impdp方式备份与还原（导出与导入）Oracle数据库

    通过数据泵expdp、impdp方式备份与还原（导出与导入）Oracle数据库前言备份还原oracle数据库的方式有很多种，本文只讲解使用expdp、impdp数据泵方式备份与还原（恢复）数据库，此种方式可以导出/导入数据库表以及表中的数据。请自行修改目录路径，否则出现错误别怪我哦~一、备份step1：使用system登录oracle打开DOS命令行界面，使用system用户登录oracle，格式：sqlplus用户名/密码@实例名（或者使用plsql……

    全栈程序员-站长的头像 全栈程序员-站长
    2022年10月20日
    2

发表回复

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

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