网站移动端优化工具,wap网站分享代码,小网站搜什么关键词,网站创建的基本流程索引 ABDEGHIJ A
直接输出两个数的差即可。再判一下无解的情况。
B
其实思路还挺顺的#xff0c;首先拿的牌肯定是一段增一段减一段增一段减……的序列#xff0c;并且 n n n 的开头和 ≤ n \leq n ≤n 的开头两种序列是对称的#xff0c;我们随便考虑一种… 索引 ABDEGHIJ A
直接输出两个数的差即可。再判一下无解的情况。
B
其实思路还挺顺的首先拿的牌肯定是一段增一段减一段增一段减……的序列并且 n n n 的开头和 ≤ n \leq n ≤n 的开头两种序列是对称的我们随便考虑一种最后答案乘以二即可。
下面称 1 1 1 ~ n n n 的数为一堆 n 1 n1 n1 ~ 2 n 2n 2n 为一堆。
为了避免计重考虑在每个序列最后一张被取走的牌的那个位置统计答案设 f i , j f_{i,j} fi,j 表示前 i i i 位合法的放置方案数并且 i i i 不在的那一堆里还有 j j j 个没用过的数。 j j j 这一维存在的意义很明确就是要用来转移的先考虑对答案的贡献分为两种 j j j 个全部按顺序用完并且剩下没有数了即 i j 2 n ij2n ij2n则对答案产生贡献 2 n × f i , j 2n\times f_{i,j} 2n×fi,j如果不是所有数都放完了而且还要取走了最后一张牌即后面不能取了那么一定是出现了不合法的取法即同一堆数不是按递减或递增顺序取的。假设最后这堆取了 k k k 张牌那么一定是 k − 1 k-1 k−1 张按顺序的以及 最后一张不按顺序的贡献为 ( i k ) × f i , j × C j k × ( k − 1 ) (ik)\times f_{i,j}\times C_j^k\times (k-1) (ik)×fi,j×Cjk×(k−1)其中 k − 1 k-1 k−1 表示选出来的 k k k 张牌中还要选一个放在最后且不能是最小/最大的那张。 f f f 的转移类似具体可以看代码。
说起来多其实写起来很短而且还没啥细节
#include bits/stdc.h
using namespace std;
#define maxn 610int n,mod,C[maxn][maxn],fac[maxn];
void add(int x,int y){x(xymod?xy-mod:xy);}
int add(int x){return xmod?x-mod:x;}
int f[maxn][maxn];int main()
{int Te;cinTe;while(Te--){cinnmod;for(int i0;i2*n;i){C[i][0]1;for(int j1;ji;j)C[i][j]add(C[i-1][j]C[i-1][j-1]);}fac[0]1;for(int i1;i2*n;i)fac[i]1ll*fac[i-1]*i%mod;for(int i0;i2*n;i)for(int j0;jn;j)f[i][j]0;f[0][n]1;int ans0;for(int i0;i2*n;i){for(int j1;ij2*njn;j){if(ij2*n)add(ans,1ll*f[i][j]*2*n%mod);for(int k2;kj;k)add(ans,1ll*(ik)*f[i][j]%mod*C[j][k]%mod*(k-1)%mod*fac[2*n-i-k]%mod);}for(int j1;ij2*njn;j)for(int k1;kj;k)if(2*n-i-jn)add(f[ik][2*n-i-j],1ll*f[i][j]*C[j][k]%mod);}ans2ll*ans%mod;coutans\n;}
}D
手玩一下发现其实只有全 0 0 0 或全 1 1 1 的矩阵才是满足要求的。 考虑一个比较粗略的证明
首先 0 ≤ r i , c j ≤ 2 n − 1 0\leq r_i,c_j\leq 2^n-1 0≤ri,cj≤2n−1
假如第一列全是 1 1 1那么 max ( c j ) 2 n − 1 \max(c_j) 2^n-1 max(cj)2n−1则 min ( r i ) 2 n − 1 \min(r_i)2^n-1 min(ri)2n−1即所有行都是全 1 1 1。
假如第一列存在一个 0 0 0 且不在第一行那么 max ( c j ) ≥ 2 n − 1 , min ( r i ) 2 n − 1 \max(c_j)\geq 2^{n-1},\min(r_i)2^{n-1} max(cj)≥2n−1,min(ri)2n−1与条件不符所以不可能出现。
所以第一列要是有 0 0 0第一行必然有一个此时 min ( r i ) 2 n − 1 \min(r_i)2^{n-1} min(ri)2n−1要使 max ( c j ) 2 n − 1 \max(c_j)2^{n-1} max(cj)2n−1则第一行不能有 1 1 1。
由此可知第一行全是 0 0 0所以 min ( r i ) 0 \min(r_i)0 min(ri)0故 max ( c j ) 0 \max(c_j)0 max(cj)0即每一列都全是 0 0 0。
证毕。
说着有点儿绕总结起来就是
第一列全是 1 → 1\red\to 1→ 所有行全是 1 1 1第一列有 0 → 0\red\to 0→ 第一行肯定有 0 → 0\red\to 0→第一行全是 0 → 0\red\to 0→ 所有列全是 0 0 0 所以考虑能不能将整个矩阵变成全 0 / 1 0/1 0/1 的矩阵。两种思路是一样的就将变全 0 0 0 的吧。
首先每一行每一列至多翻转一次重复翻转没意义。于是可以枚举第一行是否翻转操作后假如第一行还有 1 1 1那么只能翻转他所在的这一列来消除掉这个 1 1 1。接下来为了不改变第一行已经合法的状态所以不能再翻转列了看下面每一行需不需要翻转即可假如有一行既有 1 1 1 也有 1 1 1 则无解。
其实是个很贪心很暴力的简单思路代码如下
#include bits/stdc.h
using namespace std;
#define maxn 2010
#define inf 999999999int n;
char s[maxn][maxn];
bool line[maxn],col[maxn];
int get(int x,int y){int res[x][y]-0;return (re^line[x]^col[y]);
}
int solve(){int reinf;for(int line10;line11;line1){memset(line,false,sizeof(line));memset(col,false,sizeof(col));line[1]line1;int totline1;for(int i1;in;i)if(get(1,i))col[i]true,tot;for(int i2;in;i)if(get(i,1))line[i]true,tot;for(int i1;in;i)for(int j1;jn;j)if(get(i,j))totinf;remin(re,tot);}return re;
}int main()
{scanf(%d,n);for(int i1;in;i)scanf(%s,s[i]1);int ansinf;ansmin(ans,solve());for(int i1;in;i)for(int j1;jn;j)if(s[i][j]1)s[i][j]0;else s[i][j]1;ansmin(ans,solve());if(ans2*n)puts(-1);else printf(%d,ans);
}E
其实就是问 是否 dfs顺序如何变化整张图每个点的深度都不变。
先跑一次bfs跑出每个点的深度将图分层考虑不在bfs树上的几种边 ( u , v ) (u,v) (u,v)
假如 d e p u 1 d e p v dep_u1dep_v depu1depv那么这种边不影响答案假如 d e p u 1 ≠ d e p v dep_u1\neq dep_v depu1depv首先基于分层图的性质不可能是 d e p u 1 d e p v dep_u1dep_v depu1depv那么只可能是 d e p u 1 d e p v dep_u1dep_v depu1depv假如 v v v 不支配 u u u那么一定存在一条路径会使得 v v v 能得到更大的深度。此时答案为 No。否则这条边一定没用因为遍历到 u u u 时一定已经遍历过 v v v 了 u u u 无法再更新 v v v。
所以其实这题难点是会不会支配树……然而我还不会但是上网膜了个板子魔改一下之后居然过了。
代码参考性也许不是很大
#includebits/stdc.h
using namespace std;
#define maxn 500010#define cn getchar
templateclass TYvoid read(TY x){x0;int f11;char chcn();while(ch0||ch9){if(ch-)f1-1;chcn();}while(ch0ch9)xx*10(ch-0),chcn(); x*f1;
}
templateclass TYvoid write2(TY x){if(x9)write2(x/10);putchar(x%100);
}
templateclass TYvoid write(TY x){if(x0)putchar(-),x-x;write2(x);
}
int n,m,dfn[maxn],id[maxn],tot,dep[maxn];
int ffa[maxn],fa[maxn],semi[maxn],val[maxn],du[maxn],ff[25][maxn];
queueintq,q1;
vectorintcg[maxn];
struct node{vectorintedge[maxn];void add(int u,int v){edge[u].push_back(v);}void clear(int n){for(int i1;in;i)edge[i].clear();}
}a,b,c,d;
void dfs(int x,int f){dfn[x]tot,id[tot]x,ffa[x]f,c.add(f,x);for(int i0;ia.edge[x].size();i)if(!dfn[a.edge[x][i]])dfs(a.edge[x][i],x);
}
int find(int x){if(xfa[x]) return x;int tmpfa[x];fa[x]find(fa[x]);if(dfn[semi[val[tmp]]]dfn[semi[val[x]]]) val[x]val[tmp];return fa[x];
}
int LCA(int x,int y){if(dep[x]dep[y]) swap(x,y);int ddep[x]-dep[y];for(int i20;i0;i--)if(d(1i)) xff[i][x];for(int i20;i0;i--)if(ff[i][x]^ff[i][y])xff[i][x],yff[i][y];return xy?x:ff[0][x];
}
inline void tarjan(){for(int in;i2;--i){if(!id[i]) continue;int xid[i],resn;for(int j0;jb.edge[x].size();j){int vb.edge[x][j];if(!dfn[v]) continue;if(dfn[v]dfn[x]) resmin(res,dfn[v]);else find(v),resmin(res,dfn[semi[val[v]]]);}semi[x]id[res],fa[x]ffa[x],c.add(semi[x],x);}for(int x1;xn;x)for(int i0;ic.edge[x].size();i)du[c.edge[x][i]],cg[c.edge[x][i]].push_back(x);for(int x1;xn;x)if(!du[x]) q.push(x);while(!q.empty()){int xq.front();q.pop();q1.push(x);for(int i0;ic.edge[x].size();i)if(!--du[c.edge[x][i]]) q.push(c.edge[x][i]);}while(!q1.empty()){int xq1.front(),f0,lencg[x].size();q1.pop();if(len) fcg[x][0];for(int j1;jlen;j)fLCA(f,cg[x][j]);ff[0][x]f,dep[x]dep[f]1,d.add(f,x);for(int p1;p20;p)ff[p][x]ff[p-1][ff[p-1][x]];}
}
int u[maxn],v[maxn];
int fid[maxn],ID,con[maxn];
void dfs2(int x){fid[x]ID;for(int y:d.edge[x])dfs2(y);con[x]ID;
}
int mydep[maxn],myq[maxn],st,ed;
void mybfs(){myq[sted1]n;mydep[n]1;while(sted){int xmyq[st];for(int y:a.edge[x])if(!mydep[y]){mydep[y]mydep[x]1;myq[ed]y;}}
}int main()
{int T;read(T);while(T--){read(n);read(m);for(int i1;in;i){fa[i]val[i]semi[i]i;dfn[i]id[i]dep[i]ffa[i]du[i]mydep[i]0;cg[i].clear();}tot0;for(int i1;im;i){read(u[i]);read(v[i]);u[i]n-u[i]1;v[i]n-v[i]1;a.add(u[i],v[i]),b.add(v[i],u[i]);}// root: ndfs(n,0);tarjan();ID0;dfs2(n);mybfs();bool anstrue;for(int i1;im;i)if(mydep[u[i]]1!mydep[v[i]]){if(fid[u[i]]fid[v[i]]fid[u[i]]con[v[i]]);else {ansfalse;break;}}puts(ans?Yes:No);a.clear(n);b.clear(n);c.clear(n);d.clear(n);}
}G
当时一眼就想到了马拉车但是没细想开玩笑说了个是不是什么二维马拉车的神奇科技……
其实仔细考虑马拉车的话思路是很简单的考虑每一行枚举上下匹配对少列然后直接跑马拉车每次比较就是比较两段列这个用哈希整一下就行。
代码晚点儿补……
H n 1 n1 n1 的时候特判一下 n 2 n2 n2 的时候根据哥德巴赫猜想来整就行 n 3 n3 n3 其实一样先判断总和是否大于等于 2 n 2n 2n是的话就一定可以假设除了 1 , 2 1,2 1,2 位置全放 2 2 2剩下的总和是偶数那么就成功了如果不是偶数那么就把三号位变成 3 3 3总和就变成偶数了。
代码如下
#include bits/stdc.h
using namespace std;bool prime(long long x){for(long long i2;i*ix;i)if(x%i0)return false;return true;
}int main()
{int n;long long sum0;cinn;for(int i1;in;i){int x;cinx;sumx;}if(sum2*n)puts(No);else if(n1){if(prime(sum))puts(Yes);else puts(No);}else if(n2){if(sum1){if(prime(sum-2))puts(Yes);else puts(No);}else puts(Yes);}else{puts(Yes);}
}I
沿着路径走的过程肯定是贪心的能不换颜色就不换颜色但是每次要换什么颜色呢只需要将这个点的颜色和后面的点取交集尽可能往后走直到交集为空。
于是问题变成了如何快速进行一条路径的贪心其实这个贪心并不好拆成两段贪并且合并所以考虑在lca处枚举一个颜色然后看看这个颜色最多能往 x , y x,y x,y 处延伸到哪儿比如 x x , y y xx,yy xx,yy那么现在就拆成了 x → x x x \to xx x→xx 和 y → y y y\to yy y→yy 的两段贪心。
一段子孙到祖先的贪心时很好求的每个点向上二分一下找到最远能延伸到的点然后倍增跳一下就求出步数了。
另外有个小优化就是不用每次枚举之后都重新倍增跳只需要一开始跳一次跳到再跳一次就会跨过lca的位置就可以了利用这个位置的深度和枚举即可求解。
时间复杂度 O ( 60 n log n ) O(60n \log n) O(60nlogn)加上上面的优化时间复杂度其实也不变但是由于常数可能有点儿大实在是过不去……
代码如下
#include bits/stdc.h
using namespace std;
#define maxn 500010
#define inf 1000000
#define ll long long#define cn getchar
templateclass TYvoid read(TY x){x0;int f11;char chcn();while(ch0||ch9){if(ch-)f1-1;chcn();}while(ch0ch9)xx*10(ch-0),chcn(); x*f1;
}
templateclass TYvoid write2(TY x){if(x9)write2(x/10);putchar(x%100);
}
templateclass TYvoid write(TY x){if(x0)putchar(-),x-x;write2(x);
}
int n,m;
ll c[maxn];
vectorint to[maxn];
int sum[maxn][60];
int f[maxn][19],dep[maxn];
void dfs(int x){for(int i0;i60;i)if(c[x]i1)sum[x][i];for(int y:to[x]){if(yf[x][0])continue;f[y][0]x;for(int i0;i60;i)sum[y][i]sum[x][i];dep[y]dep[x]1;dfs(y);}
}
int fa[maxn][19];
void getfa(){for(int i1;in;i){int xi;for(int j18;j0;j--){bool tffalse;for(int k0;k60;k)if((c[f[x][j]]k1) sum[i][k]-sum[f[x][j]][k]dep[i]-dep[f[x][j]])tftrue;if(tf)xf[x][j];}fa[i][0]x;}for(int j1;j19;j)for(int i1;in;i)fa[i][j]fa[fa[i][j-1]][j-1];
}
int getlca(int x,int y){if(dep[x]dep[y])swap(x,y);for(int i18;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i];if(xy)return x;for(int i18;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i];return f[x][0];
}
int dis(int x,int y){if(dep[x]dep[y])swap(x,y);int re0;for(int i18;i0;i--)if(dep[f[y][i]]dep[x])yf[y][i],re(1i);if(xy)return re;for(int i18;i0;i--)if(f[x][i]!f[y][i])xf[x][i],yf[y][i],re(1i1);return re2;
}
struct par{int x,step;
};
par calc(int x,int y){if(xy)return (par){y,0};int re0;for(int i18;i0;i--)if(dep[fa[y][i]]dep[x])yfa[y][i],re(1i);if(dep[fa[y][0]]dep[x])return (par){y,re1};else return (par){y,inf};
}
int calc_ans(int x,int y){int lcagetlca(x,y);if(lcax)return calc(x,y).step-1;if(lcay)return calc(y,x).step-1;int reinf;par xxcalc(lca,x),yycalc(lca,y);if(xx.stepinf||yy.stepinf)return inf;for(int i0;i60;i)if(c[lca]i1){int totxx.stepyy.step;if(sum[xx.x][i]-sum[lca][i]dep[xx.x]-dep[lca])tot--;if(sum[yy.x][i]-sum[lca][i]dep[yy.x]-dep[lca])tot--;remin(re,tot);}//优化前写法/*for(int i0;i60;i)if(c[lca]i1){int xxx,yyy;for(int j18;j0;j--){if(dep[f[xx][j]]dep[lca] sum[f[xx][j]][i]-sum[lca][i]dep[f[xx][j]]-dep[lca])xxf[xx][j];if(dep[f[yy][j]]dep[lca] sum[f[yy][j]][i]-sum[lca][i]dep[f[yy][j]]-dep[lca])yyf[yy][j];}if(sum[xx][i]-sum[lca][i]dep[xx]-dep[lca])xxf[xx][0];if(sum[yy][i]-sum[lca][i]dep[yy]-dep[lca])yyf[yy][0];remin(re,calc(xx,x)calc(yy,y));}*/return re;
}int main()
{read(n);read(m);for(int i1;in;i)read(c[i]);for(int i1,x,y;in;i){read(x);read(y);to[x].push_back(y);to[y].push_back(x);}dep[1]1;dfs(1);for(int j1;j19;j)for(int i1;in;i)f[i][j]f[f[i][j-1]][j-1];getfa();for(int i1;im;i){int x,y;read(x);read(y);int anscalc_ans(x,y)dis(x,y);if(ansinf)puts(-1);else write(ans),puts();}
}J
题意一开始还没看懂……就是要找几个 1 1 1 ~ n n n 的排列使得给出的每个偏序关系都在某个排列中存在。
其实最多只需要两个如果整一个 1 1 1 ~ n n n 再整个 n n n ~ 1 1 1 那么所有偏序关系都有了。
那么就是要判断一下能不能一个排列整完将偏序关系连边跑一个拓扑就行有环就是需要两个排列否则拓扑序就是答案。
代码如下
#include bits/stdc.h
using namespace std;
#define maxn 1000010struct edge{int y,next;}e[maxn];
int first[maxn],et0;
void buildroad(int x,int y){e[et](edge){y,first[x]};first[x]et;
}int main()
{int n,m;cinnm;vectorint du(n1);for(int i1;im;i){int x,y;cinxy;buildroad(x,y);du[y];}vectorint sta,ans;for(int i1;in;i)if(!du[i])sta.push_back(i);while(sta.size()){int xsta.back();sta.pop_back();ans.push_back(x);for(int ifirst[x];i;ie[i].next){int ye[i].y;du[y]--;if(!du[y])sta.push_back(y);}}if(ans.size()n){cout1\n;for(auto i:ans)couti ;}else{cout2\n;for(int i1;in;i)couti ;cout\n;for(int in;i1;i--)couti ;}
}
