1. 全栈程序员必看首页

noip2011 day1[通俗易懂]

全栈程序员-用户IM • • 未分类

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


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

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

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

发表回复

您的电子邮箱地址不会被公开。

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