西宁建设厅培训中心网站,网页界面设计的参考文献,网站用户建设的设计与实现,企业网站建设立项书文章目录T1题目题解codeT2题目题解codeT3题目题解codeT1
题目
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕#xff0c;于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的…
文章目录T1题目题解codeT2题目题解codeT3题目题解codeT1
题目
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕于是他们决定去TYVJ七夕祭游玩。
TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多不过cl只对其中的一部分摊点感兴趣比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq希望能够通过恰当地布置会场使得各行中cl感兴趣的摊点数一样多并且各列中cl感兴趣的摊点数也一样多。 不过zhq告诉Vani摊点已经随意布置完毕了如果想满足cl的要求唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下至少需要交换多少次摊点。
输入格式 第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。 接下来T行每行两个整数x, y表示cl对处在第x行第y列的摊点感兴趣。
输出格式 首先输出一个字符串。如果能满足Vani的全部两个要求输出both如果通过调整只能使得各行中cl感兴趣的摊点数一样多输出row如果只能使各列中cl感兴趣的摊点数一样多输出column如果均不能满足输出impossible。 如果输出的字符串不是impossible 接下来输出最小交换次数与字符串之间用一个空格隔开。
样例 样例输入1 2 3 4 1 3 2 1 2 2 2 3 样例输出1 row 1 样例输入2 3 3 3 1 3 2 2 2 3 样例输出2 both 2 数据范围与提示 对于30% 的数据N, M≤100。 对于70% 的数据N, M≤1000。 对于100% 的数据1≤N, M≤1000000≤T≤min(NM, 100000)1≤x≤N1≤y≤M
题解
这道题先初级均分纸牌后中级糖果传递然后这题就变成水题了 我们知道如果要满足每一行或者每一列的摊点数一样感兴趣的摊点数一定能整除行或列 这道题的行与列操作是彼此独立的接下来以行为例大家类比列 考虑糖果怎么写的把这nnn行每一行看成一个人那么一共就有nnn个人围成一圈每个人手上的糖果就是该行感兴趣的摊点数设平均数averT/naverT/naverT/n每一个人都会向右边的人传递糖果然后接受左边的人传来的糖果最后手上均有averaveraver个设原本手上就有pip_ipi颗糖果XiX_iXi表示第iii个人给了第i−1i-1i−1人XiX_iXi颗糖特殊的X1X_1X1表示第一个人给第nnn个人如果值为负则表示i−1i-1i−1给iii
然后就可以写出nnn个方程 {p1−X1X2aver−−X2aver−p1X1(令pre[i]∑j1iaver−Xj)p2−X2X3aver−−X3aver−p2X2−−X3aver−p2aver−p1X1X1pre[i]...pn−XnX1aver−−XnX1pre[n]\begin{cases} p_1-X_1X_2aver--X_2aver-p_1X_1(令pre[i]\sum_{j1}^{i}aver-X_j)\\ p_2-X_2X_3aver--X_3aver-p_2X_2--X_3\\ aver-p_2aver-p_1X_1X_1pre[i]\\ ...\\ p_n-X_{n}X_{1}aver--X_nX_1pre[n]\\ \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧p1−X1X2aver−−X2aver−p1X1(令pre[i]∑j1iaver−Xj)p2−X2X3aver−−X3aver−p2X2−−X3aver−p2aver−p1X1X1pre[i]...pn−XnX1aver−−XnX1pre[n] 这里我们翻转preprepre的定义pre[i]∑j1iXj−averpre[i]\sum_{j1}^iX_j-averpre[i]∑j1iXj−aver 那么最后的答案则是min(∣X1∣∣X1−pre[1]∣∣X1−pre[2]∣...∣X1−pre[n]∣)min(|X_1||X_1-pre[1]||X_1-pre[2]|...|X_1-pre[n]|)min(∣X1∣∣X1−pre[1]∣∣X1−pre[2]∣...∣X1−pre[n]∣) 注意这个绝对值可以用数轴的含义来表示∣X1−Y∣|X_1-Y|∣X1−Y∣表示在数轴上X1X_1X1与YYY之间的距离 然后我们就可以把pre[i]pre[i]pre[i]对应到数轴上面然后调用初中知识当X1X_1X1取之中位数时距离和最小
code
#include cmath
#include cstdio
#include algorithm
using namespace std;
#define MAXN 100005
#define int long long
int N, M, T, result;
int row[MAXN], col[MAXN], pre[MAXN];int cal ( int *p, int n ) {int ans 0, average T / n;for ( int i 1;i n;i )pre[i] pre[i - 1] - p[i] average;sort ( pre 1, pre n 1 );int mid pre[( n 1) 1];for ( int i 1;i n;i )ans fabs ( mid - pre[i] );return ans;
}signed main() {scanf ( %lld %lld %lld, N, M, T );for ( int i 1;i T;i ) {int x, y;scanf ( %lld %lld, x, y );row[x] ;col[y] ;}if ( T % N T % M )printf ( impossible );else if ( T % N 0 T % M 0 ) {result cal ( row, N );result cal ( col, M );printf ( both %lld, result );} else if ( T % N 0 ) {result cal ( row, N );printf ( row %lld, result );} else {result cal ( col, M );printf ( column %lld, result );}return 0;
}T2
题目
现有一个传动系统包含了NNN个组合齿轮和MMM个链条。每一个链条连接了两个组合齿轮uuu和vvv并提供了一个传动比x:yx:yx:y 。即如果只考虑这两个组合齿轮编号为uuu的齿轮转动xxx圈编号为vvv的齿轮会转动yyy圈。传动比为正表示若编号为uuu的齿轮顺时针转动则编号为vvv的齿轮也顺时针转动。传动比为负表示若编号为uuu的齿轮顺时针转动则编号为vvv的齿轮会逆时针转动。若不同链条的传动比不相容则有些齿轮无法转动。我们希望知道系统中的这NNN个组合齿轮能否同时转动。
输入格式 有多组数据第一行给定整数TTT表示总的数据组数之后依次给出TTT组数据。 每一组数据的第一行给定整数NNN和MMM表示齿轮总数和链条总数。 之后有MMM行依次描述了每一个链条其中每一行给定四个整数 uuuvvvxxx 和yyy表示只考虑这一组联动关系的情况下编号为uuu的齿轮转动xxx圈编号为vvv的齿轮会转动yyy圈。请注意 xxx为正整数而yyy为非零整数但是yyy有可能为负数。
输出格式 输出TTT行对应每一组数据。首先应该输出标识这是第几组数据参见样例输出。之后输出判定结果如果NNN个组合齿轮可以同时正常运行则输出 Yes否则输出 No。
样例 样例输入 2 3 3 1 2 3 5 2 3 5 -7 1 3 3 -7 3 3 1 2 3 5 2 3 5 -7 1 3 3 7 样例输出 Case #1: Yes Case #2: No 数据范围与提示 对于所有的数据T≤32,N≤1000,M≤10000,∣x∣,∣y∣≤100T\le 32,N\le 1000,M\le 10000,|x|,|y|\le 100T≤32,N≤1000,M≤10000,∣x∣,∣y∣≤100
题解
这里其实理解了相容是什么意思就可以了 无非就是每一个齿轮因为我们按的链条有了一定的旋转速度 然后保证这些链条所涉及的齿轮彼此间的旋转速度是永恒的
那么我们就可以用dfsdfsdfs判断即可 以单位1的旋转速度开始当uuu点以单位1旋转那么vvv点就会以yx\frac{y}{x}xy速度旋转
当这个齿轮没有被访问过就更新它的旋转速度 反之则判断此时它的旋转速度跟之前的速度是否一致 这道题比较良心不会卡精度
code
#include cmath
#include cstdio
#include vector
using namespace std;
#define MAXN 1005
#define eps 1e-5
struct node {int v;double w;node () {}node ( int V, double W ) {v V;w W;}
};
vector node G[MAXN];
int T, n, m;
bool flag;
bool vis[MAXN];
double speed[MAXN];bool check ( int u, double now ) {vis[u] 1;speed[u] now;for ( int i 0;i G[u].size();i ) {int v G[u][i].v;double w G[u][i].w;if ( ! vis[v] ) {if ( ! check ( v, now * w ) )return 0;}else {if ( fabs ( now * w - speed[v] ) eps )return 0;}}return 1;
}int main() {scanf ( %d, T );for ( int t 1;t T;t ) {scanf ( %d %d, n, m );for ( int i 1;i n;i ) {G[i].clear();vis[i] 0;}for ( int i 1;i m;i ) {int u, v, x, y;scanf ( %d %d %d %d, u, v, x, y );G[u].push_back( node ( v, y * 1.0 / x ) );G[v].push_back( node ( u, x * 1.0 / y ) );}flag 1;for ( int i 1;i n;i )if ( ! vis[i] ) {if ( ! check ( i, 1 ) ) {flag 0;break;}}if ( flag )printf ( Case #%d: Yes\n, t );elseprintf ( Case #%d: No\n, t );}return 0;
}T3
题目
SD0062 号选手小 Q 同学为了偷到 SDOI7012 的试题利用高超的黑客技术潜入了 SDOI 出题组的内联网的中央控制系统然而这个内联网除了配备有中央控制系统还为内联网中的每条单向网线设定了特殊的通信口令这里通信口令是一个字符串不同网线的口令可能不同。这让小 Q 同学感觉有些棘手 不过这根本难不倒他很快他就分析出了整个内联网的结构。
内联网中有nnn个节点从111到nnn标号和mmm条单向网线中央控制系统在第111个节点上每条网线单向连接内联网中的某两个节点从111号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序应用程序会携带一条通信口令当且仅当程序的口令与网线的口令相同时程序才能通过这条网线到达另一端的节点继续运行并且通过每条网线都需要花费一定的时间。
每个应用程序可以在任意一个节点修改通信口令修改通信口令花费的时间可以忽略不计但是为了减小修改量需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀记其长度为 lenlenlen由于获取网线的口令的某个字符会比较耗时调用一次这个子程序需要花费lenlenlen个单位时间。
除此之外小 Q 同学还在中央控制系统中发现了一个字典每条网线的口令都是字典中的某个字符串。具体来说这个字典是一棵kkk个节点从 1 到 k 标号的有根树其中根是第111个节点每条边上有一个字符字符串SSS在字典中当且仅当存在某个点 uuu使得从根节点出发往下走到vvv的这条路径上的字符顺次拼接构成SSS。
现在小 Q 同学在111号节点同时开启了n−1n-1n−1个应用程序这些应用程序同时运行且互不干扰每个程序的通信口令都为空他希望用最短的时间把这些程序分别发送到其他节点上你需要帮小 Q 同学分别计算出发送到第i(2,3,...n)i(2,3,...n)i(2,3,...n)个节点的程序完成任务的最短时间。
题解
首先我们把一条边拆成四个点这条边的发起者出点和这条边的接受者入点以及各自再建一个虚点彼此之间的权还是以前的边权 建一个源点s然后向所有入点是1的点建一条边权为0的边 然后枚举每一个点u将所有形如i,u和u,j的边彼此之间建一条边边权就是他们的lcp(最长公共前缀) 跑一次原图对于源点而言的最短路 最后对于一个点u枚举所有i,u的边取它们中出点最小的dis 但是一个点的入边和出边会有很多别人都说连出的边数大概是O(n2)O(n^2)O(n2)的GG了 所以我们考虑优化建图 一条边被拆成四个点两个入点两个出点分别用来处理前缀和后缀 对于一个点我们以前缀为例子后缀与之类似以下略过 1.按照每条边对应字符串在Trie树上的dfs序排序上面是入边下面是出边 2.上下分别按照顺序连边权为0的有向边(灰色边) 3.考虑到一个性质lcp(a1,an)mini1n−1lcp(ai,ai1)lcp(a_1,a_n)min^{n−1}_{i1}lcp(a_i,a_{i1})lcp(a1,an)mini1n−1lcp(ai,ai1) 4.考虑dfs序相邻的两点xi,xi1x_i,x_{i1}xi,xi1有可能都是入点或出点计算出lcp(xi,xi1)lcp(x_i,x_{i1})lcp(xi,xi1) 考虑它们的影响范围显然我们找到序号最大且小于等于iii的入边ckc_kck和序号大于等于i1i1i1的出边rjr_jrj连边ck,rjc_k,r_jck,rj长度为lcp(xi,xi1)lcp(x_i,x_{i1})lcp(xi,xi1)图中省略了lcplcplcp 这样就可以满足一个序号小的入边到任意一个序号比它大的出边之间的最短路就是它们的lcp值 对于步骤4其实是一种虚树的思想吧 经典的就是为什么按dfndfndfn序排序后两两之间的lcalcalca会覆盖任意两个点之间的lcalcalca 接下来给出简单证明假设a,b,ca,b,ca,b,c是排序后紧挨着的三个点且dfnadfnbdfncdfn_adfn_bdfn_cdfnadfnbdfnc 因此bbb不可能成为lca(a,b)lca(a,b)lca(a,b)ccc不可能成为lca(b,c),lca(a,c)lca(b,c),lca(a,c)lca(b,c),lca(a,c) 那么会有几种情况呢 情况1当b,cb,cb,c的lcalcalca在a,ba,ba,b的b−lca(a,b)b-lca(a,b)b−lca(a,b)路径上(ccc可以是bbb的儿子是一样的情况)显然lca(a,c)lca(a,b)lca(a,c)lca(a,b)lca(a,c)lca(a,b) 情况2lca(a,b)lca(b,c)lca(a,b)lca(b,c)lca(a,b)lca(b,c)那么也很简单lca(a,c)lca(a,b)lca(b,c)lca(a,c)lca(a,b)lca(b,c)lca(a,c)lca(a,b)lca(b,c) 情况3lca(b,c)lca(b,c)lca(b,c)在lca(a,b)lca(a,b)lca(a,b)的子树外那么lca(a,b)lca(a,b)lca(a,b)一定是lca(b,c)lca(b,c)lca(b,c)子树内的一点 因此lca(a,c)lca(b,c)lca(a,c)lca(b,c)lca(a,c)lca(b,c) 情况4lca(a,c)lca(a,c)lca(a,c)在a−lca(a,b)a-lca(a,b)a−lca(a,b)路径上这个时候好像出了问题别急往下看 根据dfndfndfn的定义我们得把lca(a,c)lca(a,c)lca(a,c)的子树遍历完了才能去bbb那一边 那么按道理dfncdfnbdfn_cdfn_bdfncdfnb与我们之前的前提矛盾因此此情况并不存在
code
#include queue
#include cstdio
#include vector
#include cstring
#include iostream
#include algorithm
using namespace std;
#define MAXN 20005
#define MAXM 200005
#define LL long long
#define inf ( 1ll 60 )
struct noded {int u;LL w;noded () {}noded ( int U, int W ) {u U;w W;}bool operator ( const noded t ) const {return w t.w;}
};
struct node {int v, next, w;node () {}node ( int V, int W, int Next ) {v V;next Next;w W;}
}edge[MAXM * 10];
priority_queue noded q;
vector int G[MAXM], Redge[MAXM], Cedge[MAXM];//R入边,C出边
int T, n, m, k, a, b, c, d, id, tot, cnt, idx;
int pos[MAXM], head[MAXM], dfn[MAXN], dep[MAXN], flag[MAXM];
int f[MAXN][20];
LL dp[MAXM];int Fabs ( int x ) {return ( x 0 ? ( - x ) : x );
}void init () {id tot cnt idx 0;memset ( head, 0, sizeof ( head ) );for ( int i 1;i k;i )G[i].clear();for ( int i 1;i n;i ) {Redge[i].clear();Cedge[i].clear();}
}void addEdge ( int u, int v, int w ) {edge[ cnt] node ( v, w, head[u] );head[u] cnt;
}void insert ( int a, int b, int c, int d ) {pos[ id] d;//1/3出 2/4入 addEdge ( tot 1, tot 2, c );addEdge ( tot 1, tot 4, c );addEdge ( tot 3, tot 2, c );addEdge ( tot 3, tot 4, c );Redge[b].push_back( id );Cedge[a].push_back( id );tot 4;
}bool cmp ( int x, int y ) {return dfn[pos[Fabs ( x )]] dfn[pos[Fabs ( y )]];
}void dfs ( int u, int fa ) {dfn[u] idx;f[u][0] fa;dep[u] dep[fa] 1;for ( int i 1;i 20;i )f[u][i] f[f[u][i - 1]][i - 1];for ( int i 0;i G[u].size();i )if ( G[u][i] ! fa )dfs ( G[u][i], u );
}int lca ( int u, int v ) {if ( dep[u] dep[v] )swap ( u, v );for ( int i 19;i 0;i -- )if ( dep[f[u][i]] dep[v] )u f[u][i];if ( u v )return u;for ( int i 19;i 0;i -- )if ( f[u][i] ! f[v][i] ) {u f[u][i];v f[v][i];}return f[u][0];
}int getlca ( int u, int v ) {//因为点1的深度是1,因此边的个数是点的深度-1 return dep[lca ( u, v )] - 1;
}void build ( int x ) {if ( Redge[x].empty() || Cedge[x].empty() )return;sort ( Redge[x].begin(), Redge[x].end(), cmp );sort ( Cedge[x].begin(), Cedge[x].end(), cmp );for ( int i 0;i Redge[x].size() - 1;i ) {addEdge ( Redge[x][i] * 4 - 2, Redge[x][i 1] * 4 - 2, 0 );addEdge ( Redge[x][i 1] * 4, Redge[x][i] * 4, 0 );}for ( int i 0;i Cedge[x].size() - 1;i ) {addEdge ( Cedge[x][i] * 4 - 3, Cedge[x][i 1] * 4 - 3, 0 );addEdge ( Cedge[x][i 1] * 4 - 1, Cedge[x][i] * 4 - 1, 0 );}int len 0;for ( int i 0;i Redge[x].size();i )flag[ len] Redge[x][i];for ( int i 0;i Cedge[x].size();i )flag[ len] - Cedge[x][i];sort ( flag 1, flag len 1, cmp );for ( int p 1, i 0, j 0;p len;p ) {if ( flag[p] 0 ) {flag[p] - flag[p];j ;}else i ;//我们只能保证当前p的flag是正数但无法保证p1int lca getlca ( pos[flag[p]], pos[Fabs ( flag[p 1] )] );if ( i j Cedge[x].size() )addEdge ( Redge[x][i - 1] * 4 - 2, Cedge[x][j] * 4 - 3, lca );if ( j i Redge[x].size() )addEdge ( Redge[x][i] * 4, Cedge[x][j - 1] * 4 - 1, lca );}
}void Dijkstra () {while ( ! q.empty() )q.pop();tot ;for ( int i Cedge[1].size() - 1;i 0;i -- ) {addEdge ( tot, Cedge[1][i] * 4 - 1, 0 );addEdge ( tot, Cedge[1][i] * 4 - 3, 0 );}memset ( dp, 0x7f, sizeof ( dp ) );dp[tot] 0;q.push( noded ( tot, 0 ) );while ( ! q.empty() ) {noded t q.top();q.pop();if ( t.w dp[t.u] )continue;for ( int i head[t.u];i;i edge[i].next ) {int v edge[i].v, w edge[i].w;if ( dp[v] dp[t.u] w ) {dp[v] dp[t.u] w;q.push( noded ( v, dp[v] ) );}}}for ( int i 2;i n;i ) {LL ans inf;for ( int j 0;j Redge[i].size();j )ans min ( ans, dp[Redge[i][j] * 4] );printf ( %lld\n, ans );}
}int main() {scanf ( %d, T );while ( T -- ) {scanf ( %d %d %d, n, m, k );init ();for ( int i 1;i m;i ) {scanf ( %d %d %d %d, a, b, c, d );insert ( a, b, c, d );}for ( int i 1;i k;i ) {scanf ( %d %d %d, a, b, c );G[a].push_back( b );G[b].push_back( a );}dfs ( 1, 0 );for ( int i 2;i n;i )build ( i );Dijkstra ();}return 0;
}终于把拖了的坑填完了 有任何问题欢迎评论我看见会回复大家的Thanks♪(ω)
