题目链接:Codeforces 388B Fox and Minimal path
题目大意:给出k,要求构建一张图,从点1到达点2的最短路径有k条。
解题思路:二进制数差分,因为没有要求说节点尽量少,所以直接构造出初始图,当k >= (1<<i)时;在对应的两点之间建立一条边,增加(1<<i)条,建图的步骤见代码。
#include <stdio.h>
#include <string.h>
const int N = 105;
int g[N][N];
inline void set (int x, int y) {
g[x][y] = g[y][x] = 1;
}
void init () {
memset(g, 0, sizeof(g));
set(1, 3); set(1, 4); set(2, 100);
for (int i = 3; i < 60; i += 2) {
set(i, i+2); set(i, i+3);
set(i+1, i+2); set(i+1, i+3);
}
for (int i = 63; i < 100; i++) set(i, i+1);
}
void solve () {
int k;
scanf("%d", &k);
for (int i = 30; i; i--) if (k >= (1<<i)) {
k -= (1<<i);
set(2*i+1, 63+i); set(2*i+2, 63+i);
}
if (k) set(1, 63);
}
void put () {
printf("100\n");
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++)
printf("%c", g[i][j] ? 'Y' : 'N');
printf("\n");
}
}
int main () {
init();
solve ();
put();
return 0;
}
分享到:
相关推荐
然后抛出Infinite Path的定义:对于某个 i ,p[ i ] , p[ p[ i ] ] , p[ p[ p[ i ] ] ] 无限嵌套下去,且每个位置的颜色相同,即 c[ i ] = c[ p[ i ] ] = c[ p[ p[ i ] ] ] = c[ p[ p[ p[ i ] ] ] ] 等等等等 ...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
使用 C# + WPF 开发 ...你只需要提前构造好某些题的叉点数据,填入它,OK!一切就是这么的方便! 注:仅适用于 Edu 以及 Div.3 轮比赛赛后 hack,不支持 Div.1/2 赛时 hack。 适用人群:想进入首页 Hack 榜的选手
Codeforces round 678 D2_Codeforces_源码
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
打codeforces的神器
codeforces-js Codeforces JS
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces Round #723 (Div. 2).md