Dylan's Blog
Dylan's Blog

白衣苍狗

最短路

 发布于  收录于 OI

最短路算法

Floyd

SPFA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

const int maxn=103;
const int maxm=23;
const int maxe=maxm*maxm*2;
const int INF=2e9;

int n,m,k,e,x,y,z,d,p,a,b;
int tot,point[maxm],nxt[maxe],v[maxe],c[maxe];
int dis[maxm];
bool vis[maxm],flag[maxm];
queue <int> q;

inline void addedge(int x,int y,int z)
{
    ++tot;
    nxt[tot]=point[x];
    point[x]=tot;
    v[tot]=y;
    c[tot]=z;
    ++tot;
    nxt[tot]=point[y];
    point[y]=tot;
    v[tot]=x;
    c[tot]=z;
}
inline int spfa()
{
    memset(dis,0x7f,sizeof(dis));
    dis[1]=0;
    memset(vis,0,sizeof(vis));
    vis[1]=true;
    while (!q.empty()) q.pop();
    q.push(1);

    while (!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=false;
        for (int i=point[now]; i; i=nxt[i])
            if (dis[v[i]]>dis[now]+c[i]&&!flag[v[i]])
            {
                dis[v[i]]=dis[now]+c[i];
                if (!vis[v[i]])
                {
                    vis[v[i]]=true;
                    q.push(v[i]);
                }
            }
    }
    return dis[m];
}

Dijkstra

例题：hdu2544

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

//Dijkstra
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
int read(T& w)
{
	char r=getchar();bool f=false;
	if(r==-1)return -1;
	for(;(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=true;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	if(f)w=-w;
	return 1;
}
const int maxn=103;
const int maxm=10003;
int n,m;
struct EDGE
{
	int to,nxt,w;
	void init(int too,int nxtt,int ww)
	{
		to=too;nxt=nxtt;w=ww;
	}
}edge[maxm<<1];
int ek=0;
int node[maxn];
struct p
{
	int d,id;
	p(){d=id=0;}
	p(int idd,int dd)
	{
		d=dd,id=idd;
	}
};
void addEdge(int from,int too,int ww)
{
	edge[++ek].init(too,node[from],ww);
	node[from]=ek;
}
bool operator<(const p& a,const p& b)
{
	return a.d<b.d;
}
int to[maxn]; 
//小根堆
const int maxnode=maxn;
template<typename T>
struct HEAP
{
	T ary[maxnode];
	int f;
	HEAP(){f=0;}
	void clear(){f=0;}
	bool empty(){return f==0;}
	void push(const T& w)
	{
		ary[++f]=w;
		for(int k=f;k!=1&&ary[k]<ary[k/2];k/=2)
		{
			Swap(ary[k],ary[k/2]);
			Swap(to[ary[k].id],to[ary[k/2].id]);
		}
	}
	void adjust(int k,int dd)
	{
		if(dd<ary[k].d)ary[k].d=dd;
		for(;k!=1&&ary[k]<ary[k/2];k/=2)
		{
			Swap(ary[k],ary[k/2]);
			Swap(to[ary[k].id],to[ary[k/2].id]);
		}
	}
	T top() {return ary[1];}
	void pop()
	{
		ary[1]=ary[f--];
		for(int k=1,son=k*2;son<=f;k=son,son=k*2)
		{
			if(son+1<=f&&ary[son+1]<ary[son])
				++son;
			if(ary[son]<ary[k])
				Swap(ary[son],ary[k]),
				Swap(to[ary[son].id],to[ary[k].id]);
			else break;
		}
	}
};
HEAP<p> q;
int s,t;
typedef unsigned int uint;
const uint uinf=4294967295u;
uint d[maxn];
bool ok[maxn];

void Dijkstra()
{
	memset(d+1,255,n*sizeof(uint));
	memset(ok+1,0,n*sizeof(bool));
	memset(to+1,0,n*sizeof(int));
	q.clear();
	if(!to[s])
		to[s]=q.f+1;
	q.push(p(s,0));
	for(int i=1;i<=n&&!q.empty();++i)
	{
		p tmp;
		do
		{	tmp=q.top();
			q.pop();
			to[tmp.id]=0;
		}while(ok[tmp.id]&&!q.empty());
		ok[tmp.id]=true;
		d[tmp.id]=tmp.d;
		for(int j=node[tmp.id];j;j=edge[j].nxt)
		{
			int v=edge[j].to;
			if(d[tmp.id]!=uinf&&!ok[v])
			if(d[tmp.id]+edge[j].w<d[v])
			{
				if(!to[v])
					to[v]=q.f+1,q.push(p(v,d[tmp.id]+edge[j].w));
				else q.adjust(to[v],d[tmp.id]+edge[j].w);			
			}
		}
		if(tmp.id==t)break;
	}
}
void input()
{
	ek=0;
	memset(node+1,0,n*sizeof(int));
	int x,y,l;
	for(int i=1;i<=m;++i)
	{
		read(x),read(y),read(l);
		if(x!=y)
		{
			addEdge(x,y,l);
			addEdge(y,x,l);
		}
	}
	s=1,t=n;
}
int main()
{
	freopen("hdu2544_1.in","r",stdin);
	//freopen("hdu2544.out","w",stdout);
	while(read(n),read(m),n!=0)
	{
		input();
		Dijkstra();
		printf("%u\n",d[t]);
	}
	return 0;
}

更多题目：

阅读全文
DijkstraSPFAFloyd最短路图论OIC++

NOIP2016提高组 解题报告

 发布于  收录于 OI

NOIP2016提高组 解题报告

Day1

玩具谜题

【题目描述】略。

思路分析

​ 首先我们容易想到的是把圈拉开成链，也就是将小人按照输入的顺序存储在数组中。

为了代码书写的方便，我们为小人定义一个结构体。

1
2
3
4
5

struct MAN
{
int face;
char job[];
}

其中face是面向的方向，job[]是最后用来输出的职业。

那么我们如何实现不同方向的数呢？通过思考我们发现，面向圈内时向左和面向圈外时向右数的方向其实是一样的。我们联想到 1*1=(-1)*(-1)=1,1*(-1)=(-1)*1=-1的性质，可以设计将朝向和输入的数数的方向的取值映射为1/-1，这样就可以用step*face*direction表示偏移量了。

阅读全文
期望动态规划图论最短路组合数二维前缀和单调队列哈希LCANOIPOIC++

动态规划——悬线法

 发布于  收录于 OI

动态规划——悬线法

例题：USACO 6.1.2 rectbarn

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

/*
ID:du331691
PROG:rectbarn
LANG:C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
template<typename T>
void read(T& w)
{
	char r;
	for(r=getchar();r<48||r>57;r=getchar());
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
template<typename T>
T Min(const T& a,const T& b){return a<b?a:b;}
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
const int maxn=3003;
const int maxp=30003;
int n,m,p;
bool tree[maxn][maxn];
int height[2][maxn];
int treel[2][maxn],treer[2][maxn];
int Left[2][maxn],Right[2][maxn];
void input()
{
	read(n),read(m),read(p);
	int x,y;
	for(int i=1;i<=p;++i)
	{
		read(x),read(y);
		tree[x][y]=true;
	}

}
int ans=0;
void dp()
{
	for(int j=1;j<=m;++j)
		tree[0][j]=tree[n+1][j]=true;
	for(int i=2;i<=n-1;++i)
	{
		tree[i][0]=tree[i][m+1]=true;
	}
	
	for(int i=1;i<=n;++i)
	{
		int now=i&1,lst=i&1^1;
				
		for(int j=1,last=0;j<=m;++j)
		{
			if(tree[i][j])
				last=j;
			treel[now][j]=last;
		}
		for(int j=m,last=m+1;j>=1;--j)
		{
			if(tree[i][j])
				last=j;
			treer[now][j]=last;
		}
		for(int j=1;j<=m;++j)
		{
			if(tree[i-1][j])
			{
				height[now][j]=1;
				Left[now][j]=treel[now][j];
				Right[now][j]=treer[now][j];
			}
			else
			{
				height[now][j]=height[lst][j]+1;
				Left[now][j]=Max(treel[now][j],Left[lst][j]);
				Right[now][j]=Min(treer[now][j],Right[lst][j]);
			}
			if(!tree[i][j])
			{
				int tans=(Right[now][j]-Left[now][j]-1)*height[now][j];
				if(tans>ans)
					ans=tans;
			}
		}

	}
}
int main()
{
	freopen("rectbarn.in","r",stdin);
	freopen("rectbarn.out","w",stdout);
	input();
	dp();
	printf("%d\n",ans);
	return 0;
}

参考资料

国家集训队2003论文集-王知昆

阅读全文
动态规划悬线法C++OI

最小表示法

 发布于  收录于 OI

最小表示法

例题：luogu1709（USACO5.5.2）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/*
ID:du331691
PROG:hidden
LANG:C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cctype>
using namespace std;
const int maxn=100003*2;
int n;
char s[maxn];
void input()
{
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		char r;
		do{r=getchar();}
		while(!islower(r));
		s[i]=s[i+n]=r;
	}
}
int ans;
void solve()
{
	int i=0,j=1;
	while(j<=n)
	{
		bool ok=true;
		for(int k=0;k<=n-1&&ok;++k)
		{
			if(s[i+k]!=s[j+k])
			{
				ok=false;
				if(s[i+k]>s[j+k])
					i=i+k+1;
				else j=j+k+1;
			}
		}
		if(ok)
		{
			ans=i;
			return;
		}
		if(i==j)++j;
	}
	ans=i;
}
int main()
{
	freopen("hidden.in","r",stdin);
	freopen("hidden.out","w",stdout);
	input();
	solve();
	printf("%d\n",ans);
	return 0;
}

参考资料

阅读全文
子串字符串OIC++

扫描线

 发布于  收录于 OI

扫描线

矩形周长并

例题：USACO5.5.1picture

分两次水平和竖直的扫描，以从左往右扫为例 首先对于所有竖直边按从左到右排序， 再将所有边的上坐标，下坐标离散化(tox[],toy[])

用线段树动态维护当前的线段长度，Ans表示总答案 过程中有用到栈的思想（但并不用打出来） 也就是对于每一个有边的小区间， 每次 遇到矩形的左边如果包含它就+1， 如果+1后值为1 ， 说明是左边露出来的一个面，ans+=len 遇到矩形的右边如果包含它就-1 如果减一后值为0， 说明“栈”为空，是右边露出的面，ans+=len

阅读全文
扫描线线段树栈OIC++

网络流

 发布于  收录于 OI

网络流

最大流

这里参考了hzwer（%%%）的模板。

luogu3376

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
template<typename T>
T Min(const T& a,const T& b){return a<b?a:b;}
const int maxn=10003;
const int maxm=100003;
const int inf=2147483647;
int n,m,s,t;
struct EDGE
{
	int to,nxt,w;
}edge[maxm<<1];
int ek=0;
int node[maxn];
int cur[maxn];
inline void addEdge(int from,int too,int ww)
{
	++ek;
	edge[ek].to=too;
	edge[ek].w=ww;
	edge[ek].nxt=node[from];
	node[from]=ek;
}
const int maxnode=maxn;
template<typename T>
struct QUE
{
	T ary[maxnode];
	int ff,tt;
	QUE(){ff=tt=1;}
	void clear(){ff=tt=1;}
	bool empty(){return ff==tt;}
	void push(const T& w){ary[tt++]=w;}
	void pop(){++ff;}
	T front(){return ary[ff];}
};
QUE<int> q;
int d[maxn];
bool findPath()//bfs初始化d 
{
	memset(d+1,0,n*(sizeof(int)));
	//memset(d,0,sizeof(d));
	d[s]=1;
	q.clear();
	q.push(s);
	while(!q.empty())
	{
		int f=q.front();q.pop();
		for(int i=node[f];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(edge[i].w&&!d[v])
			{
				d[v]=d[f]+1;
				q.push(v);
			}
		}
	}
	return d[t];
}
int dfs(int k,int flow)//当前点，当前最大流量 
{
	if(k==t)
		return flow;
	int used=0;//当前已用流量 
	for(int i=cur[k];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(d[v]==d[k]+1)
		{
			int tmp=dfs(v,Min(flow-used,edge[i].w));//这条边往下最大流 
			edge[i].w-=tmp;
			edge[i+i&1?1:-1].w+=tmp;//反向边 
			used+=tmp;
			if(edge[i].w)
				cur[k]=i;//标记，这条边以前的边在这次都流满了，这条边还有可能压榨 
			if(used==flow)//已经流满 
				return flow;
		}
	}
	if(!used)//这条边流不到汇点 
		d[k]=0;
	return used;
}
long long ans=0;
void dinic() 
{
	while(findPath())
	{
		memcpy(cur+1,node+1,n*sizeof(int));
		//memcpy(cur,node,sizeof(node));
		ans+=dfs(s,inf);
	}
}
void input()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;++i)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		addEdge(x,y,w);
		addEdge(y,x,0);
	}
}
int main()
{
	input();
	dinic();
	printf("%lld\n",ans);
	return 0;
}

usaco4.2.1

阅读全文
最小割最大流网络流图论OIC++

NOIP2012提高组 解题报告

 发布于  收录于 OI

NOIP2012提高组 解题报告

这些代码是两年前冲刺NOIP时写下的，现在AFO的我已经来不及写详细的解题报告了，所以这里仅仅给出代码和简解。

PS:真的想要我写解题报告可以留言。

Day1

维热纳尔密码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/*
    vi
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cctype>
using namespace std;
const int maxkey=103;
const int maxl=2003;
char key[maxkey];int lenk;
char msg[maxl];int lenm;
char real[maxl];
void input()
{
    scanf("%s",key);
    scanf("%s",msg);
    lenk=strlen(key);
    lenm=strlen(msg);
}
char code(char c,int pos)
{
    int up,upk;
    if(isupper(c))up='A';
    else if(islower(c))up='a';
    
    if(isupper(key[pos]))upk=key[pos]-'A';
    else if(islower(key[pos]))upk=key[pos]-'a';
    
    return (c-up-upk+26)%26+up;
}
void solve()
{
    int kk=0;
    for(int i=0;i<lenm;++i)
    {
        real[i]=code(msg[i],kk);
        kk=(kk+1)%lenk;
    }
}
int main()
{
    //freopen("test3.in","r",stdin);
    input();
    solve();
    printf("%s\n",real);
    return 0;
}

开车旅行

第一步

​ 首先预处理出在每个城市A和B会去的下一个城市 ​ 也就是在数列中找出它后面距离它第一近的和第二近的 ​ 想法：先排序，然后枚举每个点，向左右找编号比它大的第一/二个数。 ​ 这样看起来就是n^2的了，因为向左右找可能会有极端情况 ​ 怎么办呢？ ​ 我们如果更改一下枚举顺序，让编号小的先处理， ​ 这样这个点在以后就没有用了，可以删掉 ​ 这样一来每次枚举的时候由于编号更小小的都被删掉了， ​ 所以周围都是编号比它大的（害怕）， ​ 只用找前后各两个这四个数判断一下即可 ​ 需求：支持动态删除的线性存储表 ​ ->双向链表 ​

阅读全文
NOIPOIC++

NOIP2014提高组 解题报告

 发布于  收录于 OI

NOIP2014 提高组 解题报告

Day1

生活大爆炸版石头剪刀布

思路分析

这是一道模拟题，可以为每一个出拳设一个编号，然后预处理一个二维数组来表示某个出拳对另一个出拳的胜负情况，也可以直接记为得分。

本来看这个题目还觉得一时想不到什么较好的方法，但是看一下数据范围，maxn=200，所以直接暴力累加每一场的胜负得分即可。

实现代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/*
    rps
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
const int maxn=203;
const int inf=2147483647;
int n,na,nb;
int ta[maxn],tb[maxn];
int win[5][5];
int scorea=0,scoreb=0;
void initwin()
{
    win[0][1]=0,win[1][0]=1;
    win[0][2]=1,win[2][0]=0;
    win[0][3]=1,win[3][0]=0;
    win[0][4]=0,win[4][0]=1;
    win[1][2]=0,win[2][1]=1;
    win[1][3]=1,win[3][1]=0;
    win[1][4]=0,win[4][1]=1;
    win[2][3]=0,win[3][2]=1;
    win[2][4]=1,win[4][2]=0;
    win[3][4]=1,win[4][3]=0;
}
void print()
{
    for(int i=0;i<=4;++i)
    {
        for(int j=0;j<=4;++j)
        {
            cout<<win[i][j]<<' ';
        }
        cout<<endl;
    }
}
void input()
{
    scanf("%d%d%d",&n,&na,&nb);
    for(int i=1;i<=na;++i)
    {
        scanf("%d",&ta[i]);
    }
    for(int i=1;i<=nb;++i)
    {
        scanf("%d",&tb[i]);
    }
}
int main()
{
    freopen("rps.in","r",stdin);
    freopen("rps.out","w",stdout);
    initwin();
    //print();
    input();
    for(int i=1;i<=n;++i)
    {
        scorea+=win[ta[(i-1)%na+1]][tb[(i-1)%nb+1]];
        scoreb+=win[tb[(i-1)%nb+1]][ta[(i-1)%na+1]];
    }
    printf("%d %d\n",scorea,scoreb);
    return 0;
}

联合权值

题意分析

给定一棵边权全为1的无根树，且每个节点具有一定权值，求所有互相距离为2的有序点对的权值乘积最大值，和所有有序点对的权值乘积的总和。

阅读全文
NOIPOIC++

NOIP2013提高组 解题报告

 发布于  收录于 OI

NOIP2013 提高组 解题报告

Day1

转圈游戏

题意分析

容易看出每次进行一轮，x=(x+m)% n（出题人很好心地让位置从0开始）。

一共进行了10k轮，则x=(x+$10^k$m)% n。

根据数据范围和上面的式子分析，这道题的关键是求$10^k$。

再进一步，求$10^k$% n。

几个有用的结论

  1. (ab)% c=[ (a % c)(b % c)] % c

    简单的证明一下：（带余除法）

    设a=xc+p,b=yc+q；

阅读全文
NOIPOIC++

NOIP2015提高组 解题报告

 发布于  收录于 OI

NOIP2015提高组 解题报告

Day1

神奇的幻方

【题目描述】略。

思路分析

​ 幻方问题是一个经典的数学问题，这道题叙述的是奇数幻方的构造方法。

题目中已经很明确地说明了构造的方法，只要一条条转换为代码即可。

具体代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

/*
Magic
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n;
int mid;
int a[50][50];
void fill()
{
  /*
  1.若(K-1)在第一行但不在最后一列，则将K填在最后一行，(K-1)所在列的右一列；
  2.若(K-1)在最后一列但不在第一行，则将K填在第一列，(K-1)所在行的上一行；
  3.若(K-1)在第一行最后一列，则将K填在(K-1)的正下方；
  4.若(K-1)既不在第一行，也不在最后一列，如果(K-1)的右上方还未填数，
  则将K填在(K-1)的右上方，否则将K填在(K?1)的正下方。
  */
  a[1][mid]=1;
  int tx=1,ty=mid;
  for(int i=2;i<=n*n;++i)
  {
      if(tx==1)
      {
          if(ty==n)
          {
              ++tx;
          }
          else
          {
              tx=n,++ty;
          }
      }
      else if(ty==n)
      {
          ty=1;
          --tx;
      }
      else
      {
          if(a[tx-1][ty+1]==0)
          {
              --tx,++ty;
          }
          else 
          {
              ++tx;
          }
      }
      a[tx][ty]=i;
  }
}
void output()
{
  for(int i=1;i<=n;++i)
  {
      for(int j=1;j<=n;++j)
      {
          printf("%d",a[i][j]);
          if(j!=n)
              printf(" ");
      }
      printf("\n");
  }
}
int main()
{
  freopen("magic.in","r",stdin);
  freopen("magic.out","w",stdout);
  scanf("%d",&n);
  mid=(n+1)>>1;
  fill();
  output();
  return 0;
}

信息传递

【题面描述】略。

阅读全文
NOIPOIC++
0%