gps建站教程视频,搜启网站建设,电子商务网站建设的整体规划,个人网站注册费用文章目录做题情况项目报告Uncle Bogdan and Country HappinessGraph ColoringHow Many Paths?Array Differentiation做题情况项目报告 T1,T3T1,T3T1,T3一眼题#xff0c;在实现上#xff0c;T3T3T3耗时略长#xff08;有些情况未考虑到位#xff09; T4T4T4感觉题#xf…
文章目录做题情况项目报告Uncle Bogdan and Country HappinessGraph ColoringHow Many Paths?Array Differentiation做题情况项目报告
T1,T3T1,T3T1,T3一眼题在实现上T3T3T3耗时略长有些情况未考虑到位
T4T4T4感觉题一眼隐隐约约有正解的思路
T2T2T2感觉题思考到二分图性质后并未往DPDPDP上想
Uncle Bogdan and Country Happiness
CD1388C rating:1800 简单题 给出一颗根节点为111的树对于每个节点iii有pip_ipi个人的家在节点iii上
一开始所有人都在根节点上然后每个人会往家沿着最短路走
每个人出发时有一个心情可能是好心情也可能是坏心情在经过一条边时心情可能由好变坏但是不可能由坏变好
每个点有一个幸福检测器最后的检测结果为所有经过该节点的人中好心情的人数减坏心情的人数
现在给出hih_ihi问有没有可能最后每个节点的检测结果恰好为hih_ihi solution
observation1 : 这是一棵以111为根的树经过每个点的人数是固定的即为子树内居住人数大小记为sizi\rm siz_isizi
observation2 : 由于心情变化规则可知父亲的坏心情人数一定不小于直系儿子坏心情人数和
所以直接dfs树一遍根据goodbadsizi,good−badhi\rm goodbadsiz_i,good-badh_igoodbadsizi,good−badhi可以求得经过每个点时的好坏心情人数然后根据坏心情人数是否够判断 #include cstdio
#include vector
using namespace std;
#define maxn 100005
vector int G[maxn];
int T, n, m, flag;
int p[maxn], h[maxn], bad[maxn], siz[maxn];void dfs1( int u, int fa ) {siz[u] p[u];for( auto v : G[u] )if( v fa ) continue;else dfs1( v, u ), siz[u] siz[v];bad[u] ( siz[u] - h[u] ) 1;
}void dfs2( int u, int fa ) {int cnt 0;for( auto v : G[u] ) {if( v fa ) continue;else dfs2( v, u ), cnt bad[v];}if( cnt p[u] bad[u] ) flag 1;
}int Fabs( int x ) { return x 0 ? -x : x; }int main() {scanf( %d, T );next :while( T -- ) {scanf( %d %d, n, m );flag 0;for( int i 1;i n;i )G[i].clear(), siz[i] bad[i] 0;for( int i 1;i n;i )scanf( %d, p[i] );for( int i 1;i n;i )scanf( %d, h[i] );for( int i 1, u, v;i n;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u );}dfs1( 1, 0 );for( int i 1;i n;i )if( ( ( siz[i] - h[i] ) 1 ) or ( siz[i] Fabs( h[i] ) ) ) {printf( NO\n );goto next;}dfs2( 1, 0 );if( flag ) printf( NO\n );else printf( YES\n );}return 0;
}Graph Coloring
CF1354E rating 2100: 中档题 现有一张nnn个节点mmm条边的无向图要求用{1,2,3}\{1,2,3\}{1,2,3}对每个点染色使得相邻的两个点的权值的绝对值之差刚好为111
现在需要求出一个方案使得一共染了n1n_1n1个111n2n_2n2个222和n3n_3n3个333保证n1n2n3nn_1n_2n_3nn1n2n3n
无解则输出NO\rm NONO否则输出YES\rm YESYES并输出一个字符串其中第iii位表示节点iii的颜色 solution
observation1: 各连通块之间互不影响所以可以分连通块求解
observation2: 1/3只能和2相邻所以这张图一定是个二分图并且2一定是全为一种颜色黑色/白色
dfs遍历图判断是否是二分图
至于222必须是同种颜色分连通块就可以设计dpdpdp转移了
dfs求出连通块黑白颜色的个数及分别是哪些点
dpi,j:dp_{i,j}:dpi,j: 到第iii个连通块被标记222的点数个数为jjj是否存在一种方案可行
dpi,jdpi−1,j−cnt0,i∣dpi−1,j−cnt1,idp_{i,j}dp_{i-1,j-cnt_{0,i}}|dp_{i-1,j-{cnt_{1,i}}}dpi,jdpi−1,j−cnt0,i∣dpi−1,j−cnt1,i
只要最后dpcnt,n21dp_{cnt,n2}1dpcnt,n21就一定有解
剩下就是很简单的根据dpdpdp倒着回去构造解了先把所有的222找到剩下的就是1,31,31,3无所谓了
倒回去看转移的两个dpdpdp哪个是可行的 #include cstdio
#include vector
#include cstring
#include iostream
using namespace std;
#define maxn 5005
vector int G[maxn], G0[maxn], G1[maxn];
int n, m, n1, n2, n3, cnt;
int c[maxn], ans[maxn];
bool dp[maxn][maxn];
bool vis[maxn], MS[maxn];void dfs1( int u ) {for( auto v : G[u] ) {if( ! ~ c[v] ) {c[v] c[u] ^ 1;dfs1( v );}else if( c[u] c[v] ) {printf( NO\n );exit( 0 );}}
}void dfs2( int u ) {vis[u] 1;if( c[u] ) G1[cnt].push_back( u );else G0[cnt].push_back( u );for( auto v : G[u] )if( ! vis[v] ) dfs2( v );
}int main() {scanf( %d %d %d %d %d, n, m, n1, n2, n3 );for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );G[u].push_back( v );G[v].push_back( u ); }memset( c, -1, sizeof( c ) );for( int i 1;i n;i )if( ! ~ c[i] ) c[i] 0, dfs1( i );for( int i 1;i n;i )if( ! vis[i] ) cnt , dfs2( i );dp[0][0] 1;for( int i 1;i cnt;i )for( int j 0;j n;j ) {if( G0[i].size() j )dp[i][j] | dp[i - 1][j - G0[i].size()];if( G1[i].size() j )dp[i][j] | dp[i - 1][j - G1[i].size()];}if( ! dp[cnt][n2] ) return ! printf( NO\n );else printf( YES\n );int now n2;for( int i cnt;i;i -- ) {if( now G0[i].size() and dp[i - 1][now - G0[i].size()] )MS[i] 0, now - G0[i].size();else if( dp[i - 1][now - G1[i].size()] )MS[i] 1, now - G1[i].size();}for( int i 1;i cnt;i ) if( MS[i] )for( auto j : G1[i] )ans[j] 2;else for( auto j : G0[i] )ans[j] 2;for( int i 1;i n;i )if( ! ans[i] ) {if( now n1 ) ans[i] 1, now ;else ans[i] 3;}for( int i 1;i n;i ) printf( %d, ans[i] );return 0;
}How Many Paths?
CF1547G
有一个有向图图中含有nnn个点mmm条边边中可能有自环但是没有重边
设顶点iii的答案为ansians_iansi则
如果不存在一条111到iii的路径ansians_iansi为000如果只存在一条111到iii的路径ansians_iansi为111如果至少存在两条111到iii的路径并且路径数量是有限的ansians_iansi为222如果存在无限条111到iii的路径ansians_iansi为−1-1−1
注意路径不必是简单路径
对于每一个1≤i≤n1 \leq i \leq n1≤i≤n输出ansians_iansi observation1: 不必是简单路径所以可以到处绕弯
observation2: 只要存在一条路上有环那么到iii的路径就一定是无线条
自环特殊记录一下
tarjan缩点对缩点后的状态建图同一个连通块内的边不再出现
连通块内点数111或者有自环标记说明该连通块是环连出去的边边权−1-1−1否则边权000
从111所在的连通块scc[1]开始跑堆优化dijkstra最短路
并记录经过iii的次数vis[i]
如果iii的路径长为inf证明到达不了没有路径
如果路径长为负数说明有至少一条路径上有环则是无限条路径
堆优化dijkstra最短路记录经过次数后直接判断是否111是不对的
因为写法会导致多次经过某点时若没有最短路更新是不会入队也就不会使得后面的点的经过次数增加
也就是说经过次数其实维护的是假的
在记录一个pre[i]表示最短路iii由preipre_iprei更新
最后倒着往前面找然后vis[i]取一路上的最大值
这样虽然维护的还是假的真正经过次数但是就已经可以区别出是只经过一次还是更多次我们也没有必要找到真正经过了多少次iii
#include stack
#include queue
#include cstdio
#include vector
#include iostream
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 400005
struct node {int to, w;node(){}node( int To, int W ) { to To, w W; }bool operator ( const node t ) const { return w t.w; }
};
struct edge {int u, v;edge(){}edge( int U, int V ) { u U, v V; }
}E[maxn];
priority_queue node q;
stack int sta;
vector node g[maxn];
vector int G[maxn], cnt[maxn];
int T, n, m, ip, tot;
int dfn[maxn], low[maxn], dis[maxn], vis[maxn], scc[maxn], cir[maxn], pre[maxn], gone[maxn];void tarjan( int u ) {dfn[u] low[u] ip, sta.push( u );for( auto v : G[u] ) {if( ! dfn[v] ) { tarjan( v ); low[u] min( low[u], low[v] ); }else if( ! scc[v] ) low[u] min( low[u], dfn[v] );}if( low[u] dfn[u] ) { tot; int v;do {v sta.top(), sta.pop(), scc[v] tot;cnt[tot].push_back( v );} while( v ! u );}
}void find( int i ) {if( ! i or gone[i] ) return;else gone[i] 1, find( pre[i] ), vis[i] max( vis[i], vis[pre[i]] );
}int main() {scanf( %d, T );int Case;while( T -- ) {scanf( %d %d, n, m );ip tot 0;while( ! q.empty() ) q.pop();while( ! sta.empty() ) sta.pop();for( int i 1;i n;i ) {cnt[i].clear(), G[i].clear(), g[i].clear();dfn[i] vis[i] cir[i] scc[i] gone[i] pre[i] 0, dis[i] inf;}int Edge 0;for( int i 1, u, v;i m;i ) {scanf( %d %d, u, v );if( u v ) cir[u] 1;else G[u].push_back( v ), E[ Edge] edge( u, v );}for( int i 1;i n;i )if( ! dfn[i] ) tarjan( i );for( int i 1;i Edge;i )if( scc[E[i].u] ^ scc[E[i].v] ) {if( cir[E[i].u] or cir[E[i].v] or cnt[scc[E[i].u]].size() 1 or cnt[scc[E[i].v]].size() 1 )g[scc[E[i].u]].push_back( node( scc[E[i].v], -1 ) );elseg[scc[E[i].u]].push_back( node( scc[E[i].v], 0 ) );}dis[scc[1]] cnt[scc[1]].size() 1 ? -1 : 0;q.push( node( scc[1], 0 ) );vis[scc[1]] ;while( ! q.empty() ) {int u q.top().to; q.pop();for( int i 0;i g[u].size();i ) {int v g[u][i].to, w g[u][i].w;vis[v] ;if( dis[v] 0 ) continue; if( dis[u] w dis[v] ) {dis[v] dis[u] w, pre[v] u;q.push( node( v, dis[v] ) );}}}gone[scc[1]] 1;for( int i 1;i tot;i ) find( i );for( int i 1;i n;i )if( dis[scc[i]] inf ) printf( 0 );else if( dis[scc[i]] 0 or cir[i] or cnt[scc[i]].size() 1 ) printf( -1 );else if( vis[scc[i]] 1 ) printf( 2 );else printf( 1 );printf( \n );}return 0;
}Array Differentiation
CF1552D
ttt组数据每一组给定一个数组{an}\{a_n\}{an}问是否存在这样一个数组{bn}\{ b_n \}{bn}对于所有i∈[1,n]i \in [1,n]i∈[1,n]都存在一组j、k∈[1,n]j、k\in[1,n]j、k∈[1,n]满足aibj−bka_ib_j-b_kaibj−bk
1n10 solution
如果把bib_ibi当成点权建构一棵树使得aja_jaj恰好等于树上的边权
那么最后剩下的aja_jaj就会使得树变成一张图并不是一个环因为这是有向边
但是如果这其中的某些边取反似乎就能成为一个环
看nnn的范围那么小基本锁定正解就是3n3^n3n暴搜取反某些aia_iai的值−ai-a_i−ai然后存在某些aaa的和为000 #include cstdio
#include algorithm
using namespace std;
int T, n, flag;
int a[15];void dfs( int x, int sum, int cnt ) {if( sum 0 and cnt ) {flag 0;return;}if( x n ) return;if( flag ) dfs( x 1, sum, cnt );if( flag ) dfs( x 1, sum a[x], cnt 1 );if( flag ) dfs( x 1, sum - a[x], cnt 1 );
}int main() {scanf( %d, T );next :while( T -- ) {scanf( %d, n );for( int i 1;i n;i )scanf( %d, a[i] );sort( a 1, a n 1 );for( int i 1;i n;i )if( a[i] a[i 1] ) {printf( YES\n );goto next;}n unique( a 1, a n 1 ) - a - 1;flag 1;dfs( 1, 0, 0 );if( flag ) printf( NO\n );else printf( YES\n );}return 0;
}
