本溪做网站公司,东营的网站建设公司,视频拍摄案例,平邑哪里有做网站的文章目录数列solutioncode秘密通道solutioncode小X游世界树solutioncode划分solutioncode数列
a[1]a[2]a[3]1 a[x]a[x-3]a[x-1] (x3) 求 a 数列的第 n 项对 1000000007#xff08;10^97#xff09;取余的值。
输入格式 第一行一个整数 T#xff0c;表示询问个数。 以下…
文章目录数列solutioncode秘密通道solutioncode小X游世界树solutioncode划分solutioncode数列
a[1]a[2]a[3]1 a[x]a[x-3]a[x-1] (x3) 求 a 数列的第 n 项对 100000000710^97取余的值。
输入格式 第一行一个整数 T表示询问个数。 以下 T 行每行一个正整数 n。
输出格式 每行输出一个非负整数表示答案。
样例 输入样例 3 6 8 10 输出样例 4 9 19 数据范围与提示 对于 30%的数据 n100 对于 60%的数据 n2x107 对于 100%的数据 T100n2x109
solution
一眼题没得说
[a1,a2,a3]×[001100011][a2,a3,a4]\begin{bmatrix} a_1,a_2,a_3 \end{bmatrix}\times\begin{bmatrix} 001\\ 100\\ 011 \end{bmatrix}\begin{bmatrix} a_2,a_3,a_4 \end{bmatrix}[a1,a2,a3]×⎣⎡010001101⎦⎤[a2,a3,a4]
code
#include cstdio
#include cstring
#define mod 1000000007
#define ll long long
struct Matrix {ll c[4][4];Matrix() {memset( c, 0, sizeof( c ) );}Matrix operator * ( const Matrix p ) {Matrix ans;for( int i 1;i 3;i )for( int j 1;j 3;j )for( int k 1;k 3;k )ans.c[i][k] ( ans.c[i][k] c[i][j] * p.c[j][k] % mod ) % mod;return ans;}}base, v, result;
int T, n;Matrix qkpow( Matrix x, int y ) {Matrix res;res.c[1][1] res.c[2][2] res.c[3][3] 1;while( y ) {if( y 1 ) res res * x;x x * x;y 1;}return res;
}int main() {freopen( seq.in, r, stdin );freopen( seq.out, w, stdout );base.c[1][1] base.c[1][2] base.c[1][3] 1;v.c[1][3] v.c[2][1] v.c[3][2] v.c[3][3] 1;scanf( %d, T );while( T -- ) {scanf( %d, n );if( n 3 ) {printf( 1\n );continue;}result base * qkpow( v, n - 3 );printf( %lld\n, result.c[1][3] );}return 0;
}秘密通道
有一副n×mn\times mn×m的地图有n×mn\times mn×m块地每块是下列四种中的一种 墙用#表示墙有 4 个面分别是前面后面左面右面。 起点用 C 表示为主角的起点是一片空地。 终点用 F 表示为主角的目的地是一片空地。 空地用 . 表示。 其中除了墙不能穿过其他地方都能走。 主角有以下 3 种操作
移动到相邻的前后左右的地方花费一个单位时间。 向前后左右其中一个方向发射子弹子弹沿直线穿过打在最近的一堵墙的一面然 后墙的这面就会形成一个开口通往秘密通道。同一时间最多只能有两个开口若出现有 3 个 开口出现时间最早的开口会立即消失。该操作不用时间。 可以从一个与开口相邻的空地跳进去进入秘密通道从另外一个开口正对的空地跳 出来。这个过程花费一个单位时间。 地图四周都是墙问主角最少用多少时间从 C 走到 F。C 和 F 只会出现一次。 输入格式 第一行输入两个正整数 nm。 接下来 n 行每行 m 个字符描述地图。
输出格式 输出 1 个整数表示最短时间完成路途。如果无解输出 nemoguce
样例 输入样例1 4 4 #.F# #C.# 输出样例1 2 输入样例2 6 8 ######## #.##…F# #C.##…# #…#…# #…## ######## 输出样例2 4 数据范围与提示 对于 50%的数据4 ≤ , ≤ 15。 对于 100%的数据4 ≤ , ≤ 500。
solution
两眼题 这种走迷宫条件反射就想上bfs不过很明显⛏最短路 这道题还是很善良的打枪是没有时间的当然就算有也一样简单 但是考场上我想错了以为走到墙旁边的格子再打枪一定是最优的 然并卵 很明显我首先就得往下打一枪再往右走打枪穿墙瞬移 于是我被卡了30′ 所以对于地图上的每一个点都有八条建边可能 四个方向相邻格子建边边权111 四个墙相邻格子建边均为四个方向上最近的墙的距离 n×mn\times mn×m个点普通O(n2)dijkstraO(n^2)dijkstraO(n2)dijkstra整不动就上堆优化
code
#include queue
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 505
struct node {int i, j, w;node(){}node( int I, int J, int W ) {i I, j J, w W;}bool operator ( const node u ) const {return w u.w;}
};
priority_queue node q;
int n, m;
char s[maxn][maxn];
bool vis[maxn][maxn];
int Up[maxn][maxn], Down[maxn][maxn], Left[maxn][maxn], Right[maxn][maxn];bool inside( int x, int y ) {if( x 1 || x n || y 1 || y m ) return 0;else return 1;
}void Push( int x, int y, int w ) {if( ! inside( x, y ) ) return;if( s[x][y] # ) return;if( vis[x][y] ) return;q.push( node( x, y, w ) );
}void Dijkstra() {while( ! q.empty() ) {node u q.top(); q.pop();int i u.i, j u.j, w u.w;if( vis[i][j] ) continue;if( s[i][j] F ) {printf( %d\n, w );return;}vis[i][j] 1;Push( i - 1, j, w 1 );Push( i 1, j, w 1 );Push( i, j - 1, w 1 );Push( i, j 1, w 1 );int minn min( min( i - Up[i][j], Down[i][j] - i ), min( j - Left[i][j], Right[i][j] - j ) );Push( Up[i][j] 1, j, w minn );Push( Down[i][j] - 1, j, w minn );Push( i, Left[i][j] 1, w minn );Push( i, Right[i][j] - 1, w minn );}printf( nemoguce\n );
}int main() {scanf( %d %d, n, m );for( int i 1;i n;i ) {scanf( %s, s[i] 1 );for( int j 1;j m;j )if( s[i][j] C ) q.push( node( i, j, 0 ) );}for( int i 1;i n;i )for( int j 1;j m;j ) {if( s[i - 1][j] # ) Up[i][j] i - 1;else Up[i][j] Up[i - 1][j];if( s[i][j - 1] # ) Left[i][j] j - 1;else Left[i][j] Left[i][j - 1];}for( int i n;i;i -- )for( int j m;j;j -- ) {if( s[i 1][j] # ) Down[i][j] i 1;else Down[i][j] Down[i 1][j];if( s[i][j 1] # ) Right[i][j] j 1;else Right[i][j] Right[i][j 1];}Dijkstra();return 0;
}小X游世界树
小 x 得到了一个(不可靠的)小道消息传说中的神岛阿瓦隆在格陵兰海的某处,据说那 里埋藏着亚瑟王的宝藏这引起了小 x 的好奇但当他想前往阿瓦隆时发现那里只有圣诞节 时才能到达然而现在已经春天了不甘心的他将自己的目的地改成了世界树他耗费了大 量的时间终于将自己传送到了世界树下。世界树是一棵非常巨大的树它有着许许多多的 枝条以及节点每个节点上都有一个平台。好不容易来到传说中的世界树下小 x 当然要爬 上去看看风景。小 x 每经过一条边都会耗费体力值。然而世界树之主想给他弄gáo些 d ǐan麻shì烦qíng于是他在每条边上都设了一个魔法阵当小 x 踏上那条边时会 被传送回根节点魔法阵只生效一次。这岂不是要累死小 x幸运的是每个平台上都有无 数个加速器这些加速器可以让小 x 在当前节点所连的边上耗费的体力值减少不同平台的 加速器性能不一定相同但同一个平台的加速器性能绝对相同。世界树之主给了小 x 一次 “换根”的机会他可以将世界树的任何一个节点变为根但所有的边都不能改变。小 x 想 问你将根换为哪个节点能使小 x 爬到世界树上的每个节点耗费的体力值和最少。默认编号 为 1 的点为初始根
输入格式 第一行一个数 n表示有 n 个节点。 第二行 n 个数 ai表示每个平台上的加速器的性能。 第三至 n1 行每行三个数 bi,ci,di 分别表示这条无向边的起点终点与耗费的能量值。
输出格式 第一行一个数表示要换成的节点如果有多个点为根时耗费的体力值都最小则输出 编号最小的那个。如果保持为 1 是最优的就输出 1。 第二行一个数表示最小耗费的体力值。
样例 输入样例 4 2 1 3 3 1 2 3 1 3 4 2 4 6 输出样例 1 9 数据范围与提示 如果以第一个点为根则需要耗费 0(到 1)1(到 2)2(到 3)6(到 4)9 的能量值。 如果以第二个点为根则需要耗费 2(到 1)0(到 2)4(到 3)5(到 4)11 的能量值。 如果以第三个点为根则需要耗费 1(到 1)2(到 2)0(到 3)7(到 4)10 的能量值。 如果以第四个点为根则需要耗费 5(到 1)3(到 2)7(到 3)0(到 4)15 的能量值。 很明显以第一个点为根是最优的。
对于 20%的数据:n100 对于 40%的数据:n1000 对于 60%的数据:n8000 对于 80%的数据:n100000 对于 100%的数据:0n700000;ai1000;1bi,cin;di1000。
solution
一眼题没得跑换根dp还是很裸的了 g[u]g[u]g[u]uuu子树内每个点到uuu所耗费的体力值之和 f[u]f[u]f[u]除uuu子树外所有点到uuu所耗费的体力值之和 很明显 g[u]g[u]g[u]与uuu儿子挂钩需要从下往上更新 f[u]f[u]f[u]与uuu祖先挂钩需要从上往下更新 所以两个分开用dfsdfsdfs⛏
然而我因为最后的极大值附小了于是愉快地又爆掉了30′
code
#include cstdio
#include vector
using namespace std;
#define maxn 700005
#define ll long long
vector pair int, int G[maxn];
int n;
int a[maxn], siz[maxn];
ll f[maxn], g[maxn], ans[maxn];void dfs1( int u, int fa ) {siz[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i].first, w G[u][i].second;if( v fa ) continue;dfs1( v, u );siz[u] siz[v];g[u] g[v] 1ll * siz[v] * ( w - a[u] );}
}void dfs2( int u, int fa ) {for( int i 0;i G[u].size();i ) {int v G[u][i].first, w G[u][i].second;if( v fa ) continue;f[v] f[u] g[u] - g[v] - 1ll * siz[v] * ( w - a[u] ) 1ll * ( n - siz[v] ) * ( w - a[v] );ans[v] g[v] f[v];dfs2( v, u );}
}int main() {scanf( %d, n );for( int i 1;i n;i )scanf( %d, a[i] );for( int i 1, u, v, w;i n;i ) {scanf( %d %d %d, u, v, w );G[u].push_back( make_pair( v, w ) );G[v].push_back( make_pair( u, w ) );}dfs1( 1, 0 );dfs2( 1, 0 );ll result 1ll 60; int pos;ans[1] g[1];for( int i 1;i n;i )if( ans[i] result ) result ans[i], pos i;printf( %d\n%lld, pos, result );return 0;
}划分
有一个未知的序列 x长度为 n。它的 K-划分序列 y 指的是每连续 K 个数的和得到划 分序列y[1]x[1]x[2]…x[K]y[2]x[K1]x[K2]…x[KK]…。 若 n 不被 K 整除则 y[n/K1]可以由少于 K 个数加起来。 比如 n13K5则 y[1]x[1]…x[5]y[2]x[6]…x[10]y[3]x[11]x[12] x[13]。若小 A 只确定 x 的 K[1]划分序列以及 K[2]划分序列…K[M]划分序列的值情况下 问她可以确定 x 多少个元素的值。
输入格式 第一行输入两个正整数 nM。 第二行输入 M 个正整数表示 K[1],K[2]…K[M]。
输出格式 输出 1 个整数表示能确定的元素
样例 输入样例1 3 1 2 输出样例1 1 输入样例2 6 2 2 3 输出样例2 2 数据范围与提示 【样例解释】 【样例 1 解释】 小 A 知道 x 的 2-划分序列即分别知道 x[1]x[2]x[3]的值。 小 A 可以知道 x[3]的值。 【样例 2 解释】 小 A 知道 x 的 2-划分序列即分别知道 x[1]x[2]x[3]x[4]x[5]x[6] 的值。 小 A 知道 x 的 3-划分序列即分别知道 x[1]x[2]x[3] x[4]x[5]x[6] 的值。 小 A 可以知道 x[3],x[4]的值个数为 2. 【数据范围】 对于 20%的数据3 ≤ ≤ 2000, ≤ 3。 对于 40%的数据3 ≤ ≤ 5 ∗ 10^6。 对于 100%的数据3 ≤ ≤ 10^9, 1 ≤ ≤ 102 ≤ [] 。
solution
一眼题 一眼做不出来的题 首先很明显可以发现若要确定xxx当且仅当我们知道Sx,Sx−1S_x,S_{x-1}Sx,Sx−1 即xk1×ak2×b1k1×a−k2×b1xk_1\times ak_2\times b1\ \ k_1\times a-k_2\times b1xk1×ak2×b1 k1×a−k2×b1
发现这个式子长得很像扩展欧几里得axby1axby1axby1当且仅当gcd(a,b)1gcd(a,b)1gcd(a,b)1有解
求出最小正整数解a1,b1a_1,b_1a1,b1 则通解aaa为a1p×b1,p∈Za_1 p\times b_1,p∈Za1p×b1,p∈Z 去解一个不等式p×b1×kia1∗b1≤np\times b_1\times k_ia_1*b_1\le np×b1×kia1∗b1≤n
要是真这么简单就欧儿啦 我们不仅可以很明显的发现有解的条件是相差为111也能很明显地发现我们会算重 就算发现不了样例也会告诉你血的教训 容斥就好了可我容斥不行啊
我们设s1s_1s1表示所有aaa集合s2s_2s2表示所有bbb的方程。 这样每一个kik_iki只会存在于s1,s2s_1,s_2s1,s2或者都不存在。 这样枚举的复杂度是O(3m)O(3^m)O(3m)的 容斥系数就是(−1)∣A∣∣B∣(−1)^{|A||B|}(−1)∣A∣∣B∣ 推一推找找规律就知道了
这里涉及了同余方程的合并就是他们的lcmlcmlcm code
#include cmath
#include cstdio
#define int long long
#define maxm 15
#define maxn 60000
int n, m, ans;
int k[maxm], f[maxn];int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y );
}int lcm( int x, int y ) {int d gcd( x, y );return x / d * y;
}int exgcd( int a, int b, int x, int y ) {if( ! b ) {x 1, y 0;return a;}else {int d exgcd( b, a % b, y, x );y - x * ( a / b );return d;}
}int calc( int a, int b ) {int x, y;if( exgcd( a, b, x, y ) ! 1 ) return 0;x ( x % b b ) % b;if( x * a n ) return 0;else return ( n - x * a ) / ( a * b ) 1;
}void dfs( int s1, int s2, int x, int t1, int t2 ) {if( s1 n || s2 n ) return;if( x m ) {if( ! t1 || ! t2 ) return;ans ( ( t1 t2 ) 1 ? -1 : 1 ) * calc( s1, s2 );return;}dfs( lcm( s1, k[x] ), s2, x 1, t1 1, t2 );dfs( s1, lcm( s2, k[x] ), x 1, t1, t2 1 );dfs( s1, s2, x 1, t1, t2 );
}signed main() {scanf( %lld %lld, n, m );for( int i 1;i m;i )scanf( %lld, k[i] );k[ m] n;dfs( 1, 1, 1, 0, 0 );printf( %lld, ans );return 0;
}
