NOIP 2015 提高组Day1 题解
|
416
|
DP,noip&&noi,图论,最小环,模拟,算法
|
Dewct

2064 字
|
9 分钟

T1 神奇的幻方

幻方是一种很神奇的 N∗NN∗N 矩阵：它由数字 1,2,3,⋯⋯,N×N1,2,3,⋯⋯,N×N 构成，且每行、每列及两条对角线上的数字之和都相同。当 NN 为奇数时，我们可以通过下方法构建一个幻方：首先将 11 写在第一行的中间。之后，按如下方式从小到大依次填写每个数 K(K=2,3,⋯,N×N)K(K=2,3,⋯,N×N) ：

  • 1.若 (K−1)(K−1) 在第一行但不在最后一列，则将 KK 填在最后一行， (K−1)(K−1) 所在列的右一列；
  • 2.若 (K−1)(K−1) 在最后一列但不在第一行，则将 KK 填在第一列， (K−1)(K−1) 所在行的上一行；
  • 3.若 (K−1)(K−1) 在第一行最后一列，则将 KK 填在 (K−1)(K−1) 的正下方；
  • 4.若 (K−1)(K−1) 既不在第一行，也最后一列，如果 (K−1)(K−1) 的右上方还未填数，则将 KK 填在 (K−1)(K−1) 的右上方，否则将 LL 填在 (K−1)(K−1) 的正下方。

现给定 NN ，请按上述方法构造 N∗NN∗N 的幻方。

输入格式

输入文件只有一行，包含一个正整数 NN ，即幻方的大小。

输出格式

输出文件包含 NN 行 ，每行 NN 个整数，即按上述方法构造出的 N∗NN∗N 的幻方，相邻两个整数之间用单空格隔开。

样例一

input

3

output

8 1 6
3 5 7
4 9 2

数据规模与约定

对于全部数据， 1≤N≤391≤N≤39 且 NN 为奇数。
时间限制：1s1s
空间限制：128MB

纯模拟，水题 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int map[50][50];
int main()
{
	int n;
	cin>>n;
	map[1][n/2+1] = 1;
	for(int i = 2;i <= n*n;i ++)
	{
		for(int j = 1;j <= n;j ++)
		{
			for(int k = 1;k <= n;k ++)
			{
				if(map[j][k] == i-1 && j == 1 && k!=n)
					map[n][k+1] = i;
				if(map[j][k] == i-1 && j != 1 && k == n)
					map[j-1][1] = i;
				if(map[j][k] == i-1 && j == 1 && k == n)
					map[j+1][k] = i;
				if(map[j][k] == i-1 && j != 1 && k != n)
				{
					if(map[j-1][k+1] == 0)
						map[j-1][k+1] = i;
					else
						map[j+1][k] = i;
				}
			}
		}
	}
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= n;j ++)
			printf("%d ", map[i][j]);
		cout<<endl;
	}
	return 0;
}

T2 信息传递

有 nn 个同学（编号为 11 到 nn ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 ii 的同学的信息传递对象是编号为 TiTi 的同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象（注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象）。当有人从别人口中得知自 己的生日时，游戏结束。请问该游戏一共可以进行几轮？

输入格式

输入共2行。 第1行包含1个正整数 nn ，表示 nn 个人。
第2行包含 nn 个用空格隔开的正整数 T1,T2,⋯⋯,TnT1,T2,⋯⋯,Tn ，其中第 ii 个整数 TiTi 表示编号为 ii 的同学的信息传递对象是编号为 TiTi 的同学， Ti≤nTi≤n 且 Ti
≠iTi≠i 。
数据保证游戏一定会结束。

输出格式

输出共1行，包含1个整数，表示游戏一共可以进行多少轮。

样例一

input

5
2 4 2 3 1

output

3

数据规模与约定

测试点编号 nn 的规模
1 n≤200n≤200
2
3
4 n≤2500n≤2500
5
6
7 n≤200000n≤200000
8
9
10

时间限制：1s1s
空间限制：128MB
求最小环

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 214748347l;
int t[233333], used[233333], in[233333];
int tot = 0;
int ask(int x)
{
	int p = x;
	while(1)
	{
		in[x] = ++tot;
		used[x] = p;
		x = t[x];
		if(used[x])
		{
			if(used[x] == p)
				return tot - in[x] + 1;
			else
				return INF;
		}
	}
}
int main()
{
	freopen("message.in", "r", stdin);
	freopen("message.out", "w", stdout);
	int n, ans = INF;
	cin>>n;
	for(int i = 1;i <= n;i ++)
		scanf("%d", &t[i]);
	for(int i = 1;i <= n;i ++)
		if(!used[i])
			ans = min(ans, ask(i));
	cout<<ans;
	return 0;
}

T3 斗地主

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关 系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由 nn 张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

牌型 牌型说明 牌型举例
火箭 即双王（双鬼牌） ♂ ♀
炸弹 四张同点牌。 ♠A ♥A ♣A ♦A
单张牌 单张牌 ♠3
对子牌 两张码数相同的牌 ♠2 ♥2
三张牌 三张码数相同的牌 ♠3 ♥3 ♣3
三带一 三张码数相同的牌 + 一张单牌 ♠3 ♥3 ♣3 ♠4
三带二 三张码数相同的牌 + 一对牌 ♠3 ♥3 ♣3 ♠4 ♥4
单顺子 五张或更多码数连续的单牌（不包括 2 点和双王） ♠7 ♣8 ♠9 ♣10 ♣J
双顺子 三对或更多码数连续的对牌（不包括 2 点和双王） ♣3 ♥3 ♠4 ♥4 ♠5 ♥5
三顺子 二个或更多码数连续的三张牌（不能包括 2 点和双王） ♠3 ♥3 ♣3 ♠4 ♥4 ♣4 ♠5 ♦5 ♥5
四带二 四张码数相同的牌+任意两张单牌（或任意两对牌） ♠5 ♥5 ♣5 ♦5 ♣3 ♣8

输入格式

第一行包含用空格隔开的2个正整数 T,nT,n ，表示手牌的组数以及每组手牌的张数。
接下来 TT 组数据，每组数据 nn 行，每行一个非负整数对 ai,biai,bi ，表示一张牌，其中 aiai 表示牌的数码， bibi 表示牌的花色，中间用空格隔开。特别的，我们用 11 来表示数码 A， 1111表示数码 J， 1212 表示数码 Q， 1313 表示数码 K；黑桃、红心
、梅花、方片分别用 1-4 来表示；小王的表示方法为 0 1 ，大王的表示方法为 0 2 。

输出格式

共 TT 行，每行一个整数，表示打光第 ii 组手牌的最少次数。

样例一

input

1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

output

3

explanation

共有 11 组手牌，包含 88 张牌：方片 7，方片 8，黑桃 9，方片 10，黑桃 J，黑桃 5，方片 A以及黑桃 A。可以通过打单顺子（方片 7，方片 8，黑桃 9，方片 10，黑桃 J），单张牌（黑桃 5）以及对子牌（黑桃 A以及方片 A）在 33 次内打光。

样例二

input

1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2

output

6

数据规模与约定

对于不同的测试点，我们约定手牌组数 TT ，与张数 nn 的规模如下:

测试点编号 T 的规模 n 的规模 测试点编号 T 的规模 n 的规模
1 100 2 11 100 14
2 100 2 12 100 15
3 100 3 13 10 16
4 100 3 14 10 17
5 100 4 15 10 18
6 100 4 16 10 19
7 100 10 17 10 20
8 100 11 18 10 21
9 100 12 19 10 22
10 100 13 20 10 23

数据保证：所有的手牌都是随机生成的。
时间限制：2s2s
空间限制：1GB

 
 
喜讯：我调到了35分（35分什么鬼！！）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int p[25];
int zhadan()
{
	int ans = 0;
	for(int i = 2;i <= 14;i ++)
		if(p[i] == 4)
			ans++, p[i] = 0;
	return ans;
}
int duipai()
{
	int ans = 0;
	for(int i = 2;i <= 14;i ++)
		if(p[i] == 2)
			ans ++, p[i] = 0;
	if(p[16] == 1 && p[15] == 1)
		ans++, p[16] = 0, p[15] = 0;
	return ans;
}
int sanzhang()
{
	int ans = 0;
	for(int i = 2;i <= 14;i ++)
		if(p[i] == 3)
			ans++, p[i] = 0;
	return ans;
}
int ds = 0;
int danshun(int pl)
{
	if(p[pl] < 1)
		return 0;
	if(p[pl] >= 1)
	{
		ds ++;
		if(pl + 1 < 15)
			danshun(pl+1);
		return ds;
	}
}
int ssans = 0;
int shuangshun(int pl)
{
	if(p[pl] < 2)
		return 0;
	if(p[pl] >= 2)
	{
		ssans ++;
		if(pl + 1 < 15)
			shuangshun(pl+1);
		return ssans;
	}
}
int san = 0;
int sanshun(int pl)
{
	if(p[pl] < 3)
		return 0;
	if(p[pl] >= 3)
	{
		san ++;
		if(pl + 1 < 15)
			sanshun(pl+1);
		return san;
	}
}
void deal(int i, int ss, int shu)
{
	for(int j = i;j <= i+ss;j ++)
	{
		p[j] -= shu;
	}
}
int main()
{
//	freopen("landlords.in", "r", stdin);
//	freopen("loifrancis.txt", "w", stdout);
	int t, n;
	cin>>t>>n;
	while(t--)
	{
		for(int i = 0;i <= 20;i ++)
			p[i] = 0;
		for(int i = 1;i <= n;i ++)
		{
			int a, b;
			scanf("%d%d", &a, &b);
			if(a == 0 && b == 1)
				a += 15;
			if(a == 0 && b == 2)
				a += 16;
			if(a == 1)
				a += 13;
			p[a] ++;
		}
//----------- n == 4 -------------------------------------------
		if(n <= 4)
		{
			if(n == 2)
			{
				int ll = duipai();
				if(ll != 0)
					cout<<1<<endl;
				else
					cout<<2<<endl;
			}
			else if(n == 3)
			{
				int ans = 0;
				int ll = sanzhang();
				if(ll != 0)
					ans = 1;
				else
				{
					ll = duipai();
					if(ll != 0)
						ans = 2;
					else
						ans = 3;
				}
				cout<<ans<<endl;
			}
			else if(n == 4)
			{
				int ll = zhadan(), ans;
				if(ll != 0)
					ans = 1;
				else
				{
					ll = sanzhang();
					if(ll != 0)
						ans = 1;
					else
					{
						ll = duipai();
						if(ll == 2)
							ans = 2;
						else if(ll == 1)
							ans = 3;
						else if(ll == 0)
							ans = 4;
					}
				}
				cout<<ans<<endl;
			}
		}
//---------------------------------------------------------------------------
		else
		{
			/*for(int i = 1;i <= 16;i ++)
			{
				cout<<p[i]<<" ";
			}*/
			int anss = 0;
			for(int i = 3;i <= 12;i ++)
			{
				ssans = 0;
				int ss = shuangshun(i);
				if(ss >= 3)
					deal(i, ss, 2), anss ++;
//				cout<<anss<<" shuangshun "<<ss<<endl;
			}
			for(int i = 3;i <= 13;i ++)
			{
				san = 0;
				int ss = sanshun(i);
				if(ss >= 2)
					deal(i, ss, 3), anss ++;
//				cout<<anss<<" sanshun "<<ss<<endl;
			}
			for(int i = 3;i <= 10;i ++)
			{
				ds = 0;
				int ss = danshun(i);
				if(ss >= 5)
					deal(i, ss, 1), anss ++;
//				cout<<anss<<" danshun "<<ss<<endl;
			}
			int duiz = duipai(), sanz = sanzhang(), siz = zhadan(), danz = 0;
			for(int i = 2;i <= 14;i ++)
			{
				if(p[i] == 1)
					danz ++, p[i] = 0;
//				cout<<danz<<" danz"<<endl;
			}
			if(p[15] == 1 && p[16] == 1)
				duiz += 1, p[15] = 0, p[16] = 0;
			else if(p[15] == 1 || p[16] == 1)
				danz ++, p[15] = 0, p[16] = 0;
//			cout<<danz<<" danz "<<duiz<<" duizi "<<sanz<<" sanz "<<siz<<" siz"<<endl;
			if(duiz > 0 && siz > 0)   //四带二（双）
			{
				if(siz * 2 > duiz)
					anss += duiz / 2, siz -= duiz / 2, duiz = 0;
				else
					anss += siz, duiz -= siz * 2, siz = 0;
//				cout<<"四带二（双） "<<anss<<" "<<siz<<" "<<duiz<<endl;
			}
			if(duiz > 0 && sanz > 0) //三带二
			{
				if(sanz > duiz)
					anss += duiz, sanz -= duiz, duiz = 0;
				else
					anss += sanz, duiz -= sanz, sanz = 0;
			}
			if(sanz > 0 && danz > 0) //三带一
			{
				if(sanz > danz)
					anss += danz, sanz -= danz, danz = 0;
				else
					anss += sanz, danz -= sanz, sanz = 0;
			}
			if(siz > 0 && danz > 0)//四带二（单）
			{
				if(danz % 2 == 0)
				{
					if(siz * 2 > danz)
						anss += danz/2, siz -= danz/2, danz = 0;
					else
						anss += siz * 2, danz -= 2*siz, siz = 0;
				}
				else
				{
					anss ++, danz --;
					if(siz * 2 > danz)
						anss += danz/2, siz -= danz/2, danz = 0;
					else
						anss += siz*2, danz -= 2*siz, siz = 0;
				}
//				cout<<" asfasf "<<siz<<" "<<anss<<" "<<danz<<endl;
			}
			if(duiz > 0)
				anss += duiz;
			if(danz > 0)
				anss += danz;
			cout<<anss<<endl;
		}
	}
	return 0;
}
/*
1 10
11 3
2 2
9 1
13 4
10 3
9 2
10 1
9 4
9 3
8 3
*/

 
 
 
 
 
 
 
 
 
 
 

上一篇
下一篇