上海哪家公司可以做网站,整套vi设计机构,云南昆明网站建设,网站开发下人员配置这场没考什么算法#xff0c;比较水#xff0c;难度也不是很高。比赛链接
硬要说的话E有个 前缀和 加 二分#xff0c;F是数学BFS#xff0c;G是个构造 A. Turtle Puzzle: Rearrange and Negate
题意#xff1a;
给你一个由 n n n 个整数组成的数组 a a a 。您必须对…这场没考什么算法比较水难度也不是很高。比赛链接
硬要说的话E有个 前缀和 加 二分F是数学BFSG是个构造 A. Turtle Puzzle: Rearrange and Negate
题意
给你一个由 n n n 个整数组成的数组 a a a 。您必须对数组执行以下两个操作先执行第一个操作再执行第二个操作
任意重新排列数组元素或保持元素顺序不变。最多选择一个连续的元素段并将该元素段中所有元素的符号替换为相反符号。形式上可以选择一对索引 l , r l, r l,r 这样的 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n 并为所有 l ≤ i ≤ r l \le i \le r l≤i≤r 指定 a i − a i a_i -a_i ai−ai 符号取反。请注意您也可以不选择一对索引让所有元素的符号保持不变。
在进行这两次操作后数组元素的最大和是多少
思路
显然先把负的元素排到一起然后对它们符号取反得到的就全是正数了这时候加起来最大
code
#include iostream
#include cstdio
using namespace std;int T,n;
long long t;int main(){cinT;while(T--){cinn;t0;for(int i1,tmp;in;i){cintmp;tabs(tmp);}couttendl;}return 0;
}B. Turtle Math: Fast Three Task
题意
给你一个数组 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an 。
在一次移动中你可以执行以下两种操作中的任何一种。您可以执行任意次数的移动
从数组中选择一个元素并将其从数组中移除。这样数组的长度会减少 1 1 1 从数组中选择一个元素并将其数值增加 1 1 1 。
如果当前数组为空则不能再移动。
你的任务是找出使数组中的元素之和 a a a 能被 3 3 3 整除所需的最少移动次数。你可能需要走 0 0 0 步。
注意空数组(长度为 0 0 0 的数组)的元素之和等于 0 0 0 。
思路
先把元素和算出来如果元素和本身就模3同余0那就就不需要动了。如果余1那么删掉模3余1的某个元素就可以了或者给某个元素加两次。如果余2那么删掉模3余2的某个元素就可以了或者给某个元素加一次。因此统计一下有无模3余1和2的元素之后直接讨论就行了。
code
#include iostream
#include cstdio
#include set
using namespace std;int T,n;int main(){cinT;while(T--){cinn;setint S;int tot0;for(int i1,t;in;i){cint;tot(ttot)%3;S.insert(t%3);}if(tot0){cout0endl;}else if(tot1){if(S.count(1))cout1endl;else cout2endl;}else if(tot2){//直接加1就完事了还删它干嘛cout1endl;}}return 0;
}C. Turtle Fingers: Count the Values of k
题意
给你三个正整数 a a a 、 b b b 和 l l l ( a , b , l 0 a,b,l\gt 0 a,b,l0 )。
可以证明总有一种方法可以选择非负(即 ≥ 0 \ge 0 ≥0 )的整数 k k k 、 x x x 和 y y y 使得 l k ⋅ a x ⋅ b y l k \cdot a^x \cdot b^y lk⋅ax⋅by .
你的任务是找出所有这些方法中 k k k 的不同可能值的个数。
思路
发现 l ≤ 1 0 6 l\le 10^6 l≤106数据范围很小而且 x , y x,y x,y 都在指数上根本没有很多可行的取值。所以直接暴力枚举就行了。
code
#include iostream
#include cstdio
#include set
using namespace std;
typedef long long ll;int T,a,b,l;int main(){cinT;while(T--){cinabl;setint S;for(ll x1;l%x0;x*a){for(ll y1;l%y0;y*b){if(l%(x*y)0)S.insert(l/x/y);}}coutS.size()endl;}return 0;
}D. Turtle Tenacity: Continual Mods
题意
给定数组 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,…,an 判断是否有可能将其元素**重排为 b 1 , b 2 , … , b n b_1, b_2, \ldots, b_n b1,b2,…,bn 从而得到 b 1 m o d b 2 m o d … m o d b n ≠ 0 b_1 \bmod b_2 \bmod \ldots \bmod b_n \neq 0 b1modb2mod…modbn0 。
这里的 x m o d y x \bmod y xmody 表示 x x x 除以 y y y 所得的余数。另外模运算是从左向右计算的。即 x m o d y m o d z ( x m o d y ) m o d z x \bmod y \bmod z (x \bmod y) \bmod z xmodymodz(xmody)modz 。例如 2024 m o d 1000 m o d 8 ( 2024 m o d 1000 ) m o d 8 24 m o d 8 0 2024 \bmod 1000 \bmod 8 (2024 \bmod 1000) \bmod 8 24 \bmod 8 0 2024mod1000mod8(2024mod1000)mod824mod80 。
思路
不妨先给所有数排个序不难发现如果最小的数只有一个那就按顺序模就行了。
如果最小的数有多个考虑用某个大数模它得到比它更小的正数然后继续像上面一样做。
但是如果得不到比最小数更小的正数说明每个大数都是最小数 x x x 的倍数它们互相模得到的也是 x x x 的倍数这时无论怎么搞都一定会被模 x x x 给干成 0 0 0无解。
code
#include iostream
#include cstdio
#include algorithm
using namespace std;
const int maxn1e55;int T,n;
int a[maxn];int main(){cinT;while(T--){cinn;for(int i1;in;i)cina[i];sort(a1,an1);if(a[1]!a[2])puts(YES);else {bool flagfalse;for(int i3;in;i){if(a[i]%a[1]){flagtrue;break;}}puts((flag)?YES:NO);}}return 0;
}E. Turtle vs. Rabbit Race: Optimal Trainings
题意
艾萨克开始训练。有 n n n 条跑道可供使用 i i i 条跑道( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n )由 a i a_i ai 个等长的部分组成。
给定一个整数 u u u ( 1 ≤ u ≤ 1 0 9 1 \le u \le 10^9 1≤u≤109 )完成每一段都能使艾萨克的能力提高一个特定值具体描述如下
完成第 1 1 1 部分会使艾萨克的成绩提高 u u u 。完成第 2 2 2 部分会使艾萨克的能力提高 u − 1 u-1 u−1 。完成第 3 3 3 部分会使艾萨克的成绩提高 u − 2 u-2 u−2 。 … \ldots …完成第 k k k 部分( k ≥ 1 k \ge 1 k≥1 )会使艾萨克的成绩提高 u 1 − k u1-k u1−k 。 u 1 − k u1-k u1−k 的值可以是负数这意味着完成额外的部分会降低艾萨克的成绩。
您还得到了一个整数 l l l 。您必须选择一个整数 r r r 使 l ≤ r ≤ n l \le r \le n l≤r≤n 和艾萨克都能完成赛道 l , l 1 , … , r l, l 1, \dots, r l,l1,…,r 的个段(即总共完成 l ≤ r ≤ n l \le r \le n l≤r≤n 个段)。(即总共完成 ∑ i l r a i a l a l 1 … a r \sum_{il}^r a_i a_l a_{l1} \ldots a_r ∑ilraialal1…ar 节。
请回答下列问题你所能选择的最佳 r r r 是什么能最大限度地提高艾萨克的成绩
如果有多个 r r r 可以最大限度地提高艾萨克的成绩请选出小的 r r r 。
为了增加难度你需要回答 q q q 个不同值的 l l l 和 u u u 。
思路
因为如果区间和为 u u u 或者 u 1 u1 u1时进行进行第 u u u 或 u 1 u1 u1 组训练的时候收益就已经降到 1 1 1 或 0 0 0 了之后再训练就是负数了。因此贪心的思路想就是尽量使得 [ l , r ] [l,r] [l,r] 区间和尽量等于 u u u 或者 u 1 u1 u1。
因为算的是区间和所以先用前缀和处理一下用数组 s [ i ] s[i] s[i] 表示前 1 ∼ i 1\sim i 1∼i 位置上的和。左区间确定后我们想要右区间的前缀和 s [ r ] s[r] s[r] 满足 s [ r ] − s [ l − 1 ] u s[r]-s[l-1]u s[r]−s[l−1]u于是 s [ r ] s [ l − 1 ] u s[r]s[l-1]u s[r]s[l−1]u我们使用二分可以找到第一个 s [ r ] ≥ s [ l − 1 ] u s[r]\ge s[l-1]u s[r]≥s[l−1]u 的位置但是我们二分找到的无法保证它一定是最优的但是我们可以保证最优的答案一定在它左边一个位置他自己或右边一个位置再向外找就会离 u , u 1 u,u1 u,u1 越远因此答案一定不优。我们只找一下这三个位置的收益取最大值即可。
收益的计算式是个等差数列求和 u ( u − 1 ) ( u − 2 ) ⋯ ( u 1 − t ) ( u u 1 − t ) ∗ t 2 u(u-1)(u-2)\dots(u1-t)\frac{(uu1-t)*t}{2} u(u−1)(u−2)⋯(u1−t)2(uu1−t)∗t
实际上它的收益函数画出来是个二次函数形状的函数直接跑三分也是可以的。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1e55;
typedef long long ll;
const ll inf1e18;int T,n,a[maxn];
ll s[maxn];int Q,l,u;inline ll f(ll u,ll t){return (uu1-t)*t/2;}int main(){cinT;while(T--){cinn;for(int i1;in;i)cina[i],s[i]s[i-1]a[i];cinQ;while(Q--){cinlu;ll ans-inf,r;int idxlower_bound(sl-1,sn1,s[l-1]u)-s;for(int imax(l,idx-1);imin(idx1,n);i)if(ansf(u,s[i]-s[l-1])){ansf(u,s[i]-s[l-1]);ri;}coutr ;}coutendl;}return 0;
}F. Turtle Mission: Robot and the Earthquake
题意
世界是一个有 n n n 行和 m m m 列的网格。行的编号为 0 , 1 , … , n − 1 0, 1, \ldots, n-1 0,1,…,n−1 列的编号为 0 , 1 , … , m − 1 0, 1, \ldots, m-1 0,1,…,m−1 。在这个世界里列是循环的(即每列的顶部和底部单元格是相邻的)。第 i i i 行和第 j j j 列( 0 ≤ i n , 0 ≤ j m 0 \le i\lt n, 0 \le j \lt m 0≤in,0≤jm )上的单元格表示为 ( i , j ) (i,j) (i,j) 。
在 0 0 0 时间 ( i , j ) (i,j) (i,j) 单元格(其中 0 ≤ i n , 0 ≤ j m 0 \le i \lt n, 0 \le j \lt m 0≤in,0≤jm 单元格)包含 ( i , j ) (i,j) (i,j) 和 0 0 0 时间。(其中 0 ≤ i n , 0 ≤ j m 0 \le i \lt n, 0 \le j \lt m 0≤in,0≤jm 包含石或无。单元格 ( i , j ) (i,j) (i,j) 的状态可以用整数 a i , j a_{i,j} ai,j 来描述
如果是 a i , j 1 a_{i,j} 1 ai,j1则 ( i , j ) (i,j) (i,j) 处有一块石头。如果是 a i , j 0 a_{i,j} 0 ai,j0则 ( i , j ) (i,j) (i,j) 处什么都没有。
由于地震余震的影响岩柱跟随构造板块运动每个岩柱以每单位时间 1 1 1 个单元的速度循环向上移动。从形式上看对于某个 0 ≤ i n , 0 ≤ j m 0 \le i \lt n, 0 \le j \lt m 0≤in,0≤jm 如果 ( i , j ) (i,j) (i,j) 中包含一块岩石那么它将从 ( i , j ) (i, j) (i,j) 移动到 ( i − 1 , j ) (i - 1, j) (i−1,j) (如果 ( i − 1 , j ) (i - 1, j) (i−1,j) 中包含一块岩石那么它将从 ( i , j ) (i, j) (i,j) 移动到 ( n − 1 , j ) (n - 1, j) (n−1,j) )。(或移动到 ( n − 1 , j ) (n - 1, j) (n−1,j) 如果是 i 0 i0 i0 。
名为 RT 的机器人最初位于 ( 0 , 0 ) (0,0) (0,0) 。它必须移动到 ( n − 1 , m − 1 ) (n-1,m-1) (n−1,m−1) 处进行地震救援(移动到最右下方的单元格)。地震不会改变机器人的位置只会改变世界中岩石的位置。
假设 RT 的当前位置为 ( x , y ) (x,y) (x,y) ( 0 ≤ x n , 0 ≤ y m 0 \le x \lt n, 0 \le y \lt m 0≤xn,0≤ym )那么它可以在 0 ≤ x n , 0 ≤ y m 0 \le x \lt n, 0 \le y \lt m 0≤xn,0≤ym 中移动。 0 ≤ x n , 0 ≤ y m 0 \le x \lt n, 0 \le y \lt m 0≤xn,0≤ym 它可以执行以下操作
循环向上移动一格即使用 1 1 1 单位时间从 ( x , y ) (x,y) (x,y) 移动到 ( ( x n − 1 ) m o d n , y ) ((xn-1) \bmod n, y) ((xn−1)modn,y) 。向下循环移动一个单元格即以 1 1 1 为时间单位从 ( x , y ) (x,y) (x,y) 移动到 ( ( x 1 ) m o d n , y ) ((x1) \bmod n, y) ((x1)modn,y) 。向右移动一格即使用 1 1 1 个时间单位从 ( x , y ) (x,y) (x,y) 到 ( x , y 1 ) (x, y1) (x,y1) 。(只有在 y m − 1 y \lt m-1 ym−1 时RT 才能执行此操作。
注意RT 不能使用操作向左移动也不能停留在某一位置。
不幸的是RT 在与岩石碰撞后会爆炸。因此当 RT 位于 ( x , y ) (x,y) (x,y) 处而 ( ( x 1 ) m o d n , y ) ((x1) \bmod n, y) ((x1)modn,y) 或 ( ( x 2 ) m o d n , y ) ((x2) \bmod n, y) ((x2)modn,y) 处有一块岩石时RT 不能向下移动否则就会被岩石击中。 同样如果 y 1 m y1 \lt m y1m 和 ( ( x 1 ) m o d n , y 1 ) ((x1) \bmod n, y1) ((x1)modn,y1) 处有一块岩石RT 就不能向右移动否则就会被岩石击中。 然而值得注意的是如果在 ( x m o d n , y 1 ) (x \bmod n, y1) (xmodn,y1) 和 ( ( x 1 ) m o d n , y ) ((x1) \bmod n, y) ((x1)modn,y) 处有一块岩石RT 仍然可以安全地向右移动。 求 RT 到达 ( n − 1 , m − 1 ) (n-1,m-1) (n−1,m−1) 时不与任何岩石相撞所需的最短时间。如果无法做到则输出 − 1 -1 −1 。
思路
逆天长题面读着读着就读假了以为有个向左走的操作然后WA一小时的test 4恶心人。
先说好行是从 0 ∼ n − 1 0\sim n-1 0∼n−1列是从 0 ∼ m − 1 0\sim m-1 0∼m−1方便取模 模拟循环。
石头可能有很多我们不可能每次移动都算一下石头在哪里所以我们根据相对论不如把石头看成静止的把移动附加到终点和机器人的移动上。发现终点相当于每次向下移动一格机器人向下走变成了向下走两步向右走变成了向右下走一步向上走变成了静止不动。
显然我们在中间是不会静止不动的因为终点所在列没有石头所以我们不如先跑到终点列再看要不要静止等终点。现在就变成了用两种移动方式向下两格或向右下一格跑bfs。
到终点列看如何到终点最快由于我们在终点的时候不需要管石头所以现在再让石头动起来现在终点就静止了我们要么一步一步向下走到终点要么一步一步向上走到终点两者取小值。假设我们已经走过了 t m tm tm 时间到达第 m − 1 m-1 m−1 列现在在第 u x ux ux 行上。那么终点现在相当于在第 p o s ( n − 1 t m ) % n pos(n-1tm)\%n pos(n−1tm)%n 行上 t a b s ( p o s − u x ) tabs(pos-ux) tabs(pos−ux) 就是两点间距离 n − t n-t n−t 就是走另外一条路的距离取 m i n ( t , n − t ) min(t,n-t) min(t,n−t) 即可。
code
#include iostream
#include cstdio
#include queue
#include vector
using namespace std;
const int maxn1e35;
const int inf1e9;int T,n,m;struct state{int x,y;state(int x,int y):x(x),y(y){};
};int fx[]{2,1},fy[]{0,1};int main(){cinT;while(T--){cinnm;vectorvectorint mp(n1,vectorint(m1,0));for(int i0;in;i)for(int j0;jm;j)cinmp[i][j];queuestate q;vectorvectorint d(n1,vectorint(m1,inf));int ansinf;q.push(state(0,0));d[0][0]0;while(!q.empty()){int uxq.front().x,uyq.front().y;q.pop();if(d[ux][uy]ans)continue;if(uym-1){int pos(n-1d[ux][uy])%n,tabs(ux-pos);ansmin(ans,d[ux][uy]min(t,n-t));continue;}for(int i0,x,y;i2;i){x(uxfx[i])%n;yuyfy[i];if(y0)continue;if((i0 mp[(ux1)%n][uy]) || mp[x][y])continue;if(d[ux][uy]1d[x][y]){d[x][y]d[ux][uy]1;q.push(state(x,y));}}}if(ans!inf)coutansendl;else cout-1endl;}return 0;
}G. Turtle Magic: Royal Turtle Shell Pattern
思路
乌龟爱丽丝目前正在设计一个幸运饼干盒她想把洛书的理论融入其中。
这个盒子可以看作是一个 n × m n \times m n×m 网格( n , m ≥ 5 n, m \ge 5 n,m≥5 )其中行的编号为 1 , 2 , … , n 1, 2, \dots, n 1,2,…,n 列的编号为 1 , 2 , … , m 1, 2, \dots, m 1,2,…,m 。每个单元格既可以是空也可以有一个以下形状的幸运饼干圆形或正方形。位于第 a a a 行和第 b b b 列交叉处的单元格表示为 ( a , b ) (a, b) (a,b) 。
最初整个网格是空的。然后爱丽丝对幸运饼干盒进行 q q q 次操作。 i i i /th操作( 1 ≤ i ≤ q 1 \le i \le q 1≤i≤q )如下指定当前空单元格 ( r i , c i ) (r_i,c_i) (ri,ci) 和一个形状(圆形或方形)然后在单元格 ( r i , c i ) (r_i,c_i) (ri,ci) 中放入一个指定形状的幸运饼干。请注意在进行 i i i /th操作后单元格 ( r i , c i ) (r_i,c_i) (ri,ci) 不再为空。
在所有操作和之后的每一次 q q q 操作之前爱丽丝想知道在所有剩余的空单元格中放置幸运饼干的方法有多少种从而满足以下条件
没有三个连续的单元格(水平方向、垂直方向和对角线方向)包含相同形状的饼干。形式上
不存在满足 1 ≤ i ≤ n , 1 ≤ j ≤ m − 2 1 \le i \le n, 1 \le j \le m-2 1≤i≤n,1≤j≤m−2 条件的 ( i , j ) (i,j) (i,j) 即 ( i , j ) , ( i , j 1 ) , ( i , j 2 ) (i,j), (i,j1), (i,j2) (i,j),(i,j1),(i,j2) 单元格中有相同形状的饼干。不存在满足 1 ≤ i ≤ n − 2 , 1 ≤ j ≤ m 1 \le i \le n-2, 1 \le j \le m 1≤i≤n−2,1≤j≤m 条件的 ( i , j ) (i,j) (i,j) 即 ( i , j ) , ( i 1 , j ) , ( i 2 , j ) (i,j), (i1,j), (i2,j) (i,j),(i1,j),(i2,j) 单元格中存在形状相同的饼干。不存在满足 1 ≤ i ≤ n − 2 , 1 ≤ j ≤ m − 2 1 \le i \le n-2, 1 \le j \le m-2 1≤i≤n−2,1≤j≤m−2 条件的 ( i , j ) (i,j) (i,j) 即 ( i , j ) , ( i 1 , j 1 ) , ( i 2 , j 2 ) (i,j), (i1,j1), (i2,j2) (i,j),(i1,j1),(i2,j2) 单元格中有形状相同的曲奇饼干。不存在满足 1 ≤ i ≤ n − 2 , 1 ≤ j ≤ m − 2 1 \le i \le n-2, 1 \le j \le m-2 1≤i≤n−2,1≤j≤m−2 条件的 ( i , j ) (i,j) (i,j) 即 ( i , j 2 ) , ( i 1 , j 1 ) , ( i 2 , j ) (i,j2), (i1,j1), (i2,j) (i,j2),(i1,j1),(i2,j) 单元格中有形状相同的曲奇饼干。
您应该输出所有答案的模数 998244353 998244353 998244353 。另外请注意在经过一些操作后有可能已经放置的糖果已经不满足条件在这种情况下您应该输出 0 0 0 。
思路
建议看这个讲解。就是个构造发现只有八种情况能构造成功然后一个一个暴力对一下看看能不能行。放G题算是有点德不配位了。
code
#include iostream
#include cstdio
#include set
#include cstring
using namespace std;int T,n,m,q;
string str[2]{circle,square};int main(){cinT;while(T--){cinnmq;setint S;for(int i1;i8;i)S.insert(i);cout8endl;string t;for(int i1,x,y;iq;i){cinxyt;x--;y--;int ans0;if(S.count(1)){if(str[(xy%4/2)1]!t)S.erase(1);}if(S.count(2)){if(str[(x(y3)%4/2)1]!t)S.erase(2);}if(S.count(3)){if(str[(x(y2)%4/2)1]!t)S.erase(3);}if(S.count(4)){if(str[(x(y1)%4/2)1]!t)S.erase(4);}if(S.count(5)){if(str[(x%4/2y)1]!t)S.erase(5);}if(S.count(6)){if(str[((x3)%4/2y)1]!t)S.erase(6);}if(S.count(7)){if(str[((x2)%4/2y)1]!t)S.erase(7);}if(S.count(8)){if(str[((x1)%4/2y)1]!t)S.erase(8);}coutS.size()endl;}}return 0;
}
