$NOIP 2015 Day1$ 模拟考试题解报告

目录

• $NOIP 2015 Day1$ 模拟考试题解报告
  • 得分情况
  • 考试过程
  • 题解
    • $T1$ 神奇的幻方
    • $T2$ 信息传递
    • $T3$ 斗地主

(NOIP 2015 Day1) 模拟考试题解报告

得分情况

(T1 100 Pts)

(T2 100 Pts)

(T3 100 Pts)

总分: (300 Pts)

考试过程

三道题都做过

十分钟过 (T1) 二十分钟过 (T2) 三十分钟过 (T3)

然后写对拍... 挨个模 (T1) 拍 (T2) ... 算 (T3) ... 等等... 到结束

---

题解

(T1) 神奇的幻方

模拟

代码

/*
  Time: 6.20
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
/*--------------------------------------头文件*/
inline void File() {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
}
/*----------------------------------------文件*/
int n, x, y, mp[50][50];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/

/*----------------------------------------函数*/
int main() {
	File();
	n = read(); y = (n >> 1) + 1; x = 1; mp[x][y] = 1;
	for(int i = 0; i <= n + 1; i++) mp[0][i] = mp[i][0] = mp[n + 1][i] = mp[i][n + 1] = 1;
	for(int i = 2; i <= n * n; i++)
	{
		if(x == 1 && y != n) x = n, y++, mp[x][y] = i;
		else if(x != 1 && y == n) y = 1, x--, mp[x][y] = i;
		else if(x == 1 && y == n) x++, mp[x][y] = i;
		else if(x != 1 && y != n)
			if(!mp[x - 1][y + 1]) x--, y++, mp[x][y] = i; else x++, mp[x][y] = i;
	}
	for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) printf("%d ", mp[i][j]); puts("");}
	return 0;
}

---

(T2) 信息传递

拓扑跑一遍 没走到过的搜一遍 统计数量即可

代码

/*
  Time: 6.20
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#include<queue>
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*--------------------------------------头文件*/
const int B = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("message.in", "r", stdin);
	freopen("message.out", "w", stdout);
}
/*----------------------------------------文件*/
int n, in[B], cnt, ans = INF;
struct edge {int v, nxt;} e[B];
int head[B], ecnt;
std::queue <int> q;
bool vis[B];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
void add_edge(int u, int v) {e[++ecnt] = (edge){v, head[u]}; head[u] = ecnt;}
void dfs(int u) {
	vis[u] = 1; cnt++;
	for(int i = head[u]; i; i = e[i].nxt) if(!vis[e[i].v]) dfs(e[i].v);
}
/*----------------------------------------函数*/
int main() {
//	File();
	n = read();
	for(int i = 1, x; i <= n; i++) x = read(), add_edge(i, x), in[x]++;
	for(int i = 1; i <= n; i++) if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int u = q.front(); q.pop(); vis[u] = 1;
		for(int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].v; in[v]--;
			if(!in[v]) q.push(v);
		}
	}
	for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i), ans = Min(ans, cnt), cnt = 0;
	printf("%d", ans);
	return 0;
}
/*
7
2 4 2 3 1 7 6

*/

---

(T3) 斗地主

搜索

代码

/*
  Time: 6.20
  Worker: Blank_space
  Source: 
*/
/*--------------------------------------------*/
#include<cstdio>
#define Min(x, y) ((x) < (y) ? (x) : (y))
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("landlords.in", "r", stdin);
	freopen("landlords.out", "w", stdout);
}
/*----------------------------------------文件*/
int T, n, s[20], ans;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
void f1(int l, int r, int k) {for(int i = l; i <= r; i++) s[i] += k;}
void dfs(int t) {
	if(t >= ans) return ;
	int z = 0;
	for(int i = 3; i <= 14; i++)
	{
		if(s[i]) z++; else z = 0;
		if(z >= 5) {f1(i - z + 1, i, -1); dfs(t + 1); f1(i - z + 1, i, 1);}
	}
	z = 0;
	for(int i = 3; i <= 14; i++)
	{
		if(s[i] > 1) z++; else z = 0;
		if(z >= 3) {f1(i - z + 1, i, -2); dfs(t + 1); f1(i - z + 1, i, 2);}
	}
	z = 0;
	for(int i = 3; i <= 14; i++)
	{
		if(s[i] > 2) z++; else z = 0;
		if(z >= 2) {f1(i - z + 1, i, -3); dfs(t + 1); f1(i - z + 1, i, 3);}
	}
	for(int i = 2; i <= 14; i++) if(s[i] >= 3)
	{
		s[i] -= 3;
		for(int j = 2; j <= 15; j++) if(s[j]) {s[j]--; dfs(t + 1); s[j]++;}
		for(int j = 2; j <= 14; j++) if(s[j] > 1) {s[j] -= 2; dfs(t + 1); s[j] += 2;}
		s[i] += 3;
	}
	for(int i = 2; i <= 14; i++) if(s[i] >= 4)
	{
		s[i] -= 4;
		for(int j = 2; j <= 15; j++) if(s[j])
		{
			s[j]--;
			for(int k = 2; k <= 15; k++) if(s[k]) {s[k]--; dfs(t + 1); s[k]++;}
			s[j]++;
		}
		for(int j = 2; j <= 14; j++) if(s[j] > 1)
		{
			s[j] -= 2;
			for(int k = 2; k <= 14; k++) if(s[k] > 1) {s[k] -= 2; dfs(t + 1); s[k] += 2;}
			s[j] += 2;
		}
		s[i] += 4;
	}
	for(int i = 2; i <= 15; i++) if(s[i]) t++;
	ans = Min(ans, t);
}
void clear() {ans = INF; for(int i = 2; i <= 15; i++) s[i] = 0;}
void work() {//A 14 王 15
	for(int i = 1; i <= n; i++)
	{
		int x = read(), y = read();
		if(x == 1) s[14]++;
		else if(!x) s[15]++;
		else s[x]++;
	}
	dfs(0);
	printf("%d
", ans);
}
/*----------------------------------------函数*/
int main() {
	File();
	T = read(); n = read(); while(T--) clear(), work();
	return 0;
}