网站开发啊,汉中做网站的公司电话,网站中主色调,手机商城官网旗舰店还有些没补的题以后回来补。 索引 1001100210031005100910101012 1001
感觉是大暴力题#xff0c;数据范围给的很小所以每次可以暴力求出两人的路径。枚举路径的交集里的点然后看看两个人在这个点相遇需要的最短时间就可以了。确定了具体的点之后求 4 4 4 次exgcd即可知道答…还有些没补的题以后回来补。 索引 1001100210031005100910101012 1001
感觉是大暴力题数据范围给的很小所以每次可以暴力求出两人的路径。枚举路径的交集里的点然后看看两个人在这个点相遇需要的最短时间就可以了。确定了具体的点之后求 4 4 4 次exgcd即可知道答案分别看两个人是在 来/回 的路上相遇。
代码如下
#include bits/stdc.h
using namespace std;
#define maxn 200010
#define inf 999999999#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 T,n,m;
struct edge{int y,next;}e[maxn1];
int first[maxn],et;
void buildroad(int x,int y){e[et](edge){y,first[x]};first[x]et;
}
int fa[maxn],dep[maxn];
void dfs(int x){for(int ifirst[x];i;ie[i].next){int ye[i].y;if(yfa[x])continue;fa[y]x;dep[y]dep[x]1;dfs(y);}
}
vectorint A,B;
int sta[maxn],t0;
void get_path(int S,int T,vectorint d){int xS,yT;d.clear();while(dep[x]dep[y])d.push_back(x),xfa[x];while(dep[x]dep[y])sta[t]y,yfa[y];while(x!y){d.push_back(x);xfa[x];sta[t]y;yfa[y];}d.push_back(x);while(t)d.push_back(sta[t--]);
}
int inA[maxn],inB[maxn];
int exgcd(int a,int b,int x,int y){if(b0){x1;y0;return a;}int gexgcd(b,a%b,y,x);return y-a/b*x,g;
}
int calc(int a,int l1,int b,int l2){int x,y;a1;b1;int gexgcd(a,b,x,y);if(abs(l2-l1)%g)return inf;x*(l2-l1)/g,y*(l2-l1)/g;x-x/(b/g)*(b/g);if(x0)xb/g;return a*xl1;
}int main()
{read(T);while(T--){read(n);read(m);for(int i1;in;i)first[i]0;et0;for(int i1;in;i){int x,y;read(x);read(y);buildroad(x,y);buildroad(y,x);}dfs(1);for(int i1;im;i){int Sa,Ta,Sb,Tb;read(Sa);read(Ta);read(Sb);read(Tb);get_path(Sa,Ta,A);get_path(Sb,Tb,B);for(int j1;jn;j)inA[j]inB[j]-1;for(int j0;jA.size();j)inA[A[j]]j;for(int j0;jB.size();j)inB[B[j]]j;int lenAA.size()-1,lenBB.size()-1;int ansinf;for(int j1;jn;j)if(inA[j]!-1inB[j]!-1){ansmin(ans,calc(lenA,inA[j],lenB,inB[j]));if(inA[j]!0inA[j]!lenA)ansmin(ans,calc(lenA,2*lenA-inA[j],lenB,inB[j]));if(inB[j]!0inB[j]!lenB)ansmin(ans,calc(lenA,inA[j],lenB,2*lenB-inB[j]));if(inA[j]!0inA[j]!lenA inB[j]!0inB[j]!lenB)ansmin(ans,calc(lenA,2*lenA-inA[j],lenB,2*lenB-inB[j]));}if(ansinf)puts(-1);else{ans%lenA*2;if(anslenA)write(A[2*lenA-ans]);else write(A[ans]);puts();}}}
}1002
很裸的树形dp感觉应该有原题叭
设 f i , 0 / 1 / 2 f_{i,0/1/2} fi,0/1/2 表示 i i i 点没有被cover i i i 自己这里放了路由器 i i i 被某个儿子cover了的情况转移可以看代码
#include bits/stdc.h
using namespace std;
#define maxn 200010int n,a[maxn];
vectorint to[maxn];
long long f[maxn][3];
void dfs(int x,int fa){f[x][0]f[x][2]0;f[x][1]a[x];long long mi1e10;//注意这个inf值别给太大了之前给1e18还WA了一发因为假如有一个点下面挂了很多个叶子那他的f[x][0]就会爆炸了for(int y:to[x])if(y!fa){dfs(y,x);f[x][0]f[y][2];f[x][1]min(min(f[y][0],f[y][1]),f[y][2]);if(f[y][1]f[y][2])f[x][2]f[y][1],mi0;else f[x][2]f[y][2],mimin(mi,f[y][1]-f[y][2]);}f[x][2]mi;
}int main()
{int T;cinT;while(T--){scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]),to[i].clear();for(int i1;in;i){int x,y;scanf(%d %d,x,y);to[x].push_back(y);to[y].push_back(x);}dfs(1,0);printf(%lld\n,min(f[1][1],f[1][2]));}
}1003
这题其实不是很难但赛时看过的人少就没怎么看最后一点时间看的时候就感觉应该可以做但是dp方向想错了一点时间不够接着思考了。
实际上就是考虑dp f l , r , k , r f_{l,r,k,r} fl,r,k,r 表示 [ l , r ] [l,r] [l,r] 区间内消得只剩一张 k k k 类 r r r 级牌的最优贡献另外多一种状态是 f l , r , 0 , 0 f_{l,r,0,0} fl,r,0,0 表示 [ l , r ] [l,r] [l,r] 区间内啥也不剩的最优贡献很容易就能得到转移复杂度是 P ( n 3 m R ) P(n^3mR) P(n3mR)无压力过。
代码如下
#include bits/stdc.h
using namespace std;
#define ll long longint n,m,R,P;
int a[110],V[110];
ll f[110][110][21][8];
int pw[9];int main()
{int T;cinT;while(T--){cinnmRP;for(int i1;in;i)cina[i];for(int i1;im;i)cinV[i];Rmin(R,6);for(int i1;in;i)for(int j1;jn;j)for(int k0;km;k)//注意初始化别忘记 f[i][j][0][0] 的情况for(int r0;rR;r)f[i][j][k][r]-1e13;for(int i1;in;i)f[i][i][a[i]][1]0,f[i][i][0][0]V[a[i]];pw[0]1;for(int i1;iR;i)pw[i]pw[i-1]*P;for(int len2;lenn;len){for(int i1;ilen-1n;i){int jilen-1;for(int k1;km;k)for(int r1;rR(1r-1)len;r){for(int pi;pj;p){f[i][j][k][r]max(f[i][j][k][r],f[i][p][k][r]f[p1][j][0][0]);f[i][j][k][r]max(f[i][j][k][r],f[i][p][0][0]f[p1][j][k][r]);f[i][j][k][r]max(f[i][j][k][r],f[i][p][k][r-1]f[p1][j][k][r-1]);}if(f[i][j][k][r]0)f[i][j][0][0]max(f[i][j][0][0],f[i][j][k][r]1ll*V[k]*pw[r-1]);}}}coutf[1][n][0][0]\n;}
}1005
将每个已知串哈希一下放到map里每次O(1)查询即可。
但是似乎没有什么很好的环哈希技术只能先求个最小表示法再用串哈希了。
代码很简单就不贴了。
1009
用鸽巢原理判断一下即可
1010 x j ≥ x j 1 x_j\geq x_{j1} xj≥xj1可以得到一个很经典的性质 [ a i ≥ x j ] [a_i\geq x_j] [ai≥xj] 的值只可能形如 1 , 1 , 1 , 0 , 0 , 0 , 0 , . . . 1,1,1,0,0,0,0,... 1,1,1,0,0,0,0,...也就是至多发生一次转换。
那么也很经典的用线段树来维护就行 a i ≥ x j a_i\geq x_j ai≥xj 时每次操作相当于区间减每次看看区间内最小值是否 x j x_j xj是的话暴力进去修改成 a i x j a_ix_j aixj 类的点这一类点每次操作相当于区间取反并且 x j x_j xj。
队友写的代码有空再补。
1012
是一类很经典的博弈的几乎板子题但我居然没见过啊可恶 一棵树每次删掉一条边 以及去掉所有不和根节点相连的点不能操作者败。 考虑SG函数假如子树是一条链那么SG值显然是总边数这个相当于 Nim 游戏只有一堆石子的情况。
对于一个点如果有多个儿子先递归进去求他们的SG值假如一个儿子SG值为 p p p那么其实可以直接将子树看做一条长度为 p p p 的链那么这个点的SG值就是 S G x ⊕ y ∈ s o n ( S G y 1 ) SG_x\oplus_{y\in son} (SG_y1) SGx⊕y∈son(SGy1)因为每个儿子的链相当于多了一条边那么SG值自然就1然后根据经典的博弈结论直接将他们的新SG值异或起来就得到这个点的SG值了。 看回这个题每次删掉一棵子树不可操作者获胜其实等价于上面的每次删掉一条边以及对应的子树不可操作者失败。
所以用一个换根dp求一下每个点的SG值即可求出答案。
代码很简单就不贴了。
