本文主要是介绍Codeforces Round #228 (Div. 2) D - Fox and Minimal path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前三题 没有什么可以说的 水题， 但是 B题 大意了，最后WA了，所以 rating 大降 T_T.
何时才能进DIV1 啊。
D题， 当时 交了一发，不过被HACK了，因为考虑不全面。 当时的想法是把 K 分解为1000 内的因数相乘 而且 这些因数的和<=1000。这样显然是不正确的，因为可能根本找不到这些符合条件的因数。
之后，考虑分解为二进制，之后是相乘之积 相加。上面的错误之处也就是在于全是相乘。
用这个思路分解，比如用二进制分解 K=5, 可以这么构造k=5=2*2+1*1;
又在赛后写了一发， 在一个28个1的二进制的数上过不去， 经过计算，这样的构造方法会使节点的数目超过1000.
所以考虑其他进制的分解，可以粗略算得 十进制的构造方法最糟不会超过800多节点，故可行。 10进制的方法和二进制思路一样。
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1000000000
#define N 1005
int n,k;
bool vis[N][N];
char s[100];
int main()
{scanf("%d",&k);sprintf(s,"%d",k);int len=strlen(s);memset(vis,0,sizeof(vis));int now=2,last;for(int i=0;i<len;i++){int tmp=s[i]-'0';if(!tmp) continue;for(int j=1;j<=tmp;j++){vis[1][now+j]=vis[now+j][1]=1;}last=now;now+=tmp;int need=len-i-1;for(int j=1;j<=need;j++){last=now;if(j==1){for(int p=now-tmp+1;p<=now;p++)for(int q=now+1;q<=now+10;q++)vis[p][q]=vis[q][p]=1;}else{for(int p=now-9;p<=now;p++)for(int q=now+1;q<=now+10;q++)vis[p][q]=vis[q][p]=1;}now+=10;}if(i==0){for(int q=last+1;q<=now;q++) vis[q][2]=vis[2][q]=1;}for(int j=1;j<=i;j++){if(j==1){for(int p=last+1;p<=now;p++) vis[p][now+1]=vis[now+1][p]=1;now++;}else{vis[now][now+1]=vis[now+1][now]=1;now++;}if(j==i) vis[now][2]=vis[2][now]=1;}}printf("%d\n",now);for(int i=1;i<=now;i++){for(int j=1;j<=now;j++){if(vis[i][j]) printf("Y");else printf("N");}puts("");}return 0;
}----------------------------------------------------------------------------------------------------------------------------------
额 ， 发现 二进制分解构造 是可行的 ， 而且 结果会更优 ， 不会超过100 个点的。
比如 ， K=12； 1110（二进制）
除去 1 2 两点 分为 3层，列数决定于 二进制的位数，前2层构造完成，就构造出了最高位的方案数 样例中的8种。 再构造出 4+2 种就完成了。
就如图，连接红色的边，就完成了。 如果需要1种，就把 1 点 和左下角的点连接即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1000000000
#define N 1005
int k,n;
bool vis[N][N];
int m[N],ad,mark,now=2;
void sol()
{if(mark==0){vis[1][2]=vis[2][1]=1; return ;}vis[1][4]=vis[1][5]=vis[4][1]=vis[5][1]=1;for(int i=2;i<=mark;i++){vis[i*3+1][i*3-2]=vis[i*3-2][i*3+1]=vis[i*3+2][i*3-1]=vis[i*3-1][i*3+2]=1;vis[i*3+2][i*3-2]=vis[i*3-2][i*3+2]=vis[i*3+1][3*i-1]=vis[i*3-1][i*3+1]=1;vis[i*3][i*3-3]=vis[i*3-3][i*3]=1;}vis[mark*3][2]=vis[2][mark*3]=vis[mark*3+1][2]=vis[2][mark*3+1]=vis[mark*3+2][2]=vis[2][mark*3+2]=1;for(int i=0;i<mark;i++){if(m[i] & (!i) ){vis[1][3]=vis[3][1]=1; continue;}if(m[i]) vis[3*i+3][3*i+1]=vis[3*i+1][3*i+3]=vis[3*i+3][3*i+2]=vis[3*i+2][3*i+3]=1;}now+=mark*3;
}
int main()
{scanf("%d",&k);memset(vis,0,sizeof(vis));ad=-1;for(int i=0;i<=31;i++){int tmp=(k>>i)&1;m[++ad]=tmp;}for(int i=32;i>=0;i--){if(m[i]){mark=i; break;}}sol();printf("%d\n",now);for(int i=1;i<=now;i++){for(int j=1;j<=now;j++){printf("%c",vis[i][j]==1? 'Y':'N');}puts("");}return 0;
}
这篇关于Codeforces Round #228 (Div. 2) D - Fox and Minimal path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
