qq音乐如何做mp3下载网站,做视频找素材的网站,打开一张图片后点击跳转到网站怎么做的,室内设计好学吗Adore 1.1 问题描述 小 w 偶然间遇到了一个 DAG。 这个 DAG 有 m 层#xff0c;第一层只有1个源点#xff0c;最后一层只有1个汇点#xff0c;剩下的每一层都有 k 个 节点。 现在小 w 每次可以取反第 i(1 i n − 1) 层和第 i 1 层之间的连边。也就是把原本从 (i,… Adore 1.1 问题描述 小 w 偶然间遇到了一个 DAG。 这个 DAG 有 m 层第一层只有1个源点最后一层只有1个汇点剩下的每一层都有 k 个 节点。 现在小 w 每次可以取反第 i(1 i n − 1) 层和第 i 1 层之间的连边。也就是把原本从 (i, k1) 连到 (i 1, k2) 的边变成从 (i, k2) 连到 (i 1, k1)。 请问他有多少种取反的方案把从源点到汇点的路径数变成偶数条 答案对 998244353 取模。 1.2 输入格式 第一行两个整数 m, k。 接下来 m − 1 行, 第一行和最后一行有 k 个整数 0 或 1剩下每行有 k 2 个整数 0 或 1 第 (j − 1) × k t 个整数表示 (i, j) 到 (i 1, t) 有没有边。 1.3 输出格式 一行一个整数表示答案。 1.4 样例输入 5 3 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1.5样例输出 4 1.6数据规模与约定 20% 的数据满足 n ≤ 10, k ≤ 2 40% 的数据满足 n ≤ 10^3 , k ≤ 2。 60% 的数据满足 m ≤ 10^3 , k ≤ 5。 100% 的数据满足 4 ≤ m ≤ 10^4 , k ≤ 10。 1. 这要是Noip d1t1我也不用学oi了。。。 每一层只有10个点我们只关心每个点的奇偶情况于是可以考虑状压dp。dp[i][j]表示第i层奇偶情况为j的答案。 暴力的写法枚举每一层每种情况枚举每条边暴力地更新奇偶算转移到的状态。60分。场上zz不知道哪个地方莫名多了一个忘删掉的for循环炸了两个点。。 优化一下预处理出连向每个点的边的集合用一个二进制串表示然后每次和转移来的状态取交判断这个数的1的个数的奇偶这一步同样是预处理。 然后又是垃圾卡常可能我真的是传说中的 真·大常数选手吧。。好不容易卡进去。。 //Twenty
#includealgorithm
#includeiostream
#includecstring
#includecstdlib
#includevector
#includecstdio
#includecmath
#includectime
#includequeue
#includestack
typedef long long LL;
const LL mod998244353;
const int maxn1e4299;
const int maxm1e6299;
int m,k,x,s,t;
using namespace std;
int a[maxn][11],b[maxn][11],ok[maxn];
int f[10005][1030];inline int get(int x) {int ret0; char chgetchar();while(ch0||ch9) chgetchar();for(;ch0ch9;chgetchar()) retret*10ch-0;xret;
}void work() {int nn(1k)-1;for(register int i0;inn;i) ok[i]ok[i1]^(i1);for(register int i3;im;i) {for(register int j0;jnn;j) if(f[i-1][j]){int now0,s10,s20;for(register int l1;lk;l) {s1|ok[a[i][l]j]l-1;s2|ok[b[i][l]j]l-1;}f[i][s1]f[i-1][j];if(f[i][s1]mod) f[i][s1]-mod;if(i!m) {f[i][s2]f[i-1][j];if(f[i][s2]mod) f[i][s2]-mod;}}}
}int main()
{freopen(adore.in,r,stdin);freopen(adore.out,w,stdout);get(m); get(k);int now0;for(register int i1;ik;i) {get(x);if(!x) continue;now|(1i-1);}f[2][now]1;for(register int i2;im-1;i) {for(register int j1;jk;j)for(register int l1;lk;l) {get(x);if(!x) continue;a[i1][l]|(1j-1);b[i1][j]|(1l-1);}}for(register int i1;ik;i) {get(x);if(!x) continue;a[m][1]|(1i-1);}work();printf(%d\n,f[m][0]);fclose(stdin);fclose(stdout);return 0;
} View Code Confess 2.1 问题描述 小w 隐藏的心绪已经难以再隐藏下去了。 小w 有 n 1(保证 n 为偶数) 个心绪每个都包含了 [1, 2n] 的一个子集。 现在他要找到隐藏的任意两个心绪使得他们的交大于等于 n/ 2。 2.2 输入格式 一行一个整数 n。 接下来每行一个长度为 k 的字符串该字符串是一个 64 进制表示 ASCII 码为 x 的字符代 表着 x − 33所有字符在 33 到 33 63 之间。 转为二进制表示有 6k 位它的前 2n 个字符就是读入的集合 第 i 位为 1 表示这个集合包 含 i为 0 表示不包含。 2.3 输出格式 一行两个不同的整数表示两个集合的编号。 如果无解输出”NO Solution”。 2.4 样例输入 10 EVK# IH# 676 R7,# 74S 6V2# O3J# S-7$ NU5 C[$$ 3N.# 2.5 样例输出 1 2 2.6 数据规模与约定 对于 20% 的数据满足 n ≤ 100。 对于 50% 的数据满足 n ≤ 1 × 10^3。 对于 100% 的数据满足 n ≤ 6 × 10^3。 2. t1写得太难受语文太烂没读懂题暴力都没打直接输出no solution。 然而没有No solution的情况正解就是暴力。 首先”NO Solution” 两个单词大小写不一致所以肯定是乱 打的不会有无解。 证明我们不妨算一算如果随机选两个集合他们交的期望 min( ∑2n i1 C(ci ,2) C(n1,2) | ∑2n i1 ci n(n 1)) n−1/2 注意 n 是偶数所以大于 n−2/2 即可说明会有交为 n 的 由于大了一个常数所以至少有 n 对 随机 O(n) 对即可 标解用了bitset开O2跑得贼快不用bitset就又是垃圾卡常怎么卡都卡不进只能一边输一遍做找到答案就输都不输了才ok。。。 //Twenty
#includealgorithm
#includeiostream
#includecstring
#includecstdlib
#includevector
#includecstdio
#includecmath
#includectime
#includequeue
using namespace std;
const int maxn6e35;
int n,sz,b[maxn];
char ch[60005];
bool a[maxn][2*maxn],tp[10];
int ok(int x,int y) {int ret0;for(int i1;i2*n;i) {if(a[x][i]1a[y][i]1) ret;if(retn/2) return 1;}return retn/2;
}
int main()
{freopen(confess.in,r,stdin);freopen(confess.out,w,stdout);scanf(%d,n);for(register int i1;in1;i) {cinch;int p0,q0;while(q2*n){int midch[p]-33;for(int j0;j6;j)a[i][q]mid(1j);} for(register int ji-1;j1;j--) if(ok(i,j)) {printf(%d %d\n,i,j);return 0;}}fclose(stdin);fclose(stdout);return 0;
} View Code -------------------------------------------------------------------------------------------- 事实证明被卡常是某个叫random_shuffle()的函数的锅。换成sort就过了。 还有getchar会比cin快很多。常数这种东西太可怕了。 //Twenty
#includealgorithm
#includeiostream
#includecstring
#includecstdlib
#includevector
#includecstdio
#includecmath
#includectime
#includequeue
using namespace std;
const int maxn6e35;
int n,sz,b[maxn],c[maxn];
char s[105];
bool a[maxn][2*maxn],tp[10];
int ok(int x,int y) {int ret0;for(int i1;i2*n;i) {if(a[x][i]1a[y][i]1) ret;if(retn/2) return 1;}return retn/2;
}bool cmp(const int x,const int y) {return b[x]b[y];
}int main()
{freopen(confess.in,r,stdin);freopen(confess.out,w,stdout);srand(time(0));cinn;for(int i1;in1;i) {int tot0; char cgetchar();while(c33||c96)cgetchar();while(c33c96) {for(int j0;j5tot2*n;j)a[i][tot](((c-33)j)1);cgetchar();}}for(int i1;in1;i) c[i]i,b[i]rand();sort(c1,cn2,cmp);for(int i1;in1;i) {for(int ji1;jn1;j)if(ok(c[i],c[i1])) {printf(%d %d\n,c[i],c[i1]);return 0;}}fclose(stdin);fclose(stdout);return 0;
} View Code Repulsed 3.1 问题描述 小 w 心理的火焰就要被熄灭了。 简便起见假设小w 的内心是一棵 n − 1 条边n 个节点的树。 现在你要在每个节点里放一些灭火器每个节点可以放任意多个。 接下来每个节点都要被分配给一个最多 k 条边远的灭火器每个灭火器最多能分配给 s 个节 点。 最少要多少个灭火器才能让小 w 彻底死心呢 3.2 输入格式 第一行三个整数 n, s, k。 接下来 n − 1 行每行两个整数表示一条边。 3.3 输出格式 一行一个整数表示答案 3.4 样例输入 10 10 3 1 8 2 3 1 5 2 4 1 2 8 9 8 10 5 6 5 7 3.5 样例输出 1 3.6 数据规模与约定 对于 20% 的数据满足 n ≤ 100, k ≤ 2。 对于另外 20% 的数据满足 k 1。 对于另外 20% 的数据满足 s 1。 对于 100% 的数据满足 n ≤ 10^5 , k ≤ 20, s ≤ 10 至底往上贪心。 考虑一条链上去只要能管得到肯定往上放比较优每次从下到上再在上面考虑下面的情况。 g[x][i]表示x点往下i的距离的位置还需要多少灭火器f[x][i]表示x点往下i的距离的位置有多少没用的灭火器。 若g[x][k]还不为0则在该点放灭火器。 考虑子树中长度为k的距离的位置和k-1距离的位置的互相配放。 到根节点后再把没用的全用了还差的一起补上。 //Twenty
#includealgorithm
#includeiostream
#includecstring
#includecstdlib
#includevector
#includecstdio
#includecmath
#includectime
#includequeue
const int maxn1e5299;
int n,s,k;
using namespace std;int ans,ecnt,fir[maxn],nxt[maxn*2],to[maxn*2];
void add(int u,int v) {nxt[ecnt]fir[u]; fir[u]ecnt; to[ecnt]v;nxt[ecnt]fir[v]; fir[v]ecnt; to[ecnt]u;
}int f[maxn][22],g[maxn][22];
void dfs(int x,int fa) {for(int ifir[x];i;inxt[i]) if(to[i]!fa){int vto[i]; dfs(v,x);for(int j1;jk;j) {f[x][j]min(n,f[x][j]f[v][j-1]);g[x][j]g[v][j-1];} }g[x][0];if(g[x][k]) {int tp(g[x][k]-1)/s1;f[x][0]tp*s,anstp;}for(int i0;ik;i) {int jk-i;int dmin(f[x][i],g[x][j]);f[x][i]-d; g[x][j]-d;}for(int i0;ik;i) {int jk-i-1;int dmin(f[x][i],g[x][j]);f[x][i]-d; g[x][j]-d;}
}int main()
{freopen(repulsed.in,r,stdin);freopen(repulsed.out,w,stdout);scanf(%d%d%d,n,s,k);for(int i1;in;i) {int x,y;scanf(%d%d,x,y);add(x,y);}dfs(1,0);for(int i0;ik;i)for(int j0;jk;j) {if(ijk) {int dmin(f[1][i],g[1][j]);f[1][i]-d; g[1][j]-d;}}int tot0;for(int i0;ik;i) {if(g[1][i]) totg[1][i];}ans(tot?(tot-1)/s1:0);printf(%d\n,ans);fclose(stdin);fclose(stdout);return 0;
} View Code 转载于:https://www.cnblogs.com/Achenchen/p/7647431.html
