noip2011 day1[通俗易懂]

简单模拟，蜜汁WA。

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

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

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

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;

}

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

这是最暴力的：

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

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

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;

}

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

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

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

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

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

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

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;

}

noip2011 day1[通俗易懂]

相关推荐