AtCoder Beginner Contest 246
文章目录
A - Four Points
题意：
给出三个点，找到一个点，让这4个点组成一个矩形
思路：
分别找到横纵坐标中只有一个的值。
时间复杂度：
O ( 1 ) O(1) O(1)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =1e2+5,M =2e4+10,INF =0x3f3f3f3f,mod =1e9+7;intmain(){// std::ios::sync_with_stdio(false);// std::cin.tie(nullptr);// std::cout.tie(nullptr);int x,y,ans_x =0,ans_y =0;for(int i =1; i <=3; i++){
std::cin>>x>>y;
ans_x ^= x,ans_y ^= y;}
std::cout<<ans_x<<' '<<ans_y;return0;}
B - Get Closer
题意：
给出一个向量，将其变成单位向量。
思路：
将向量除以他的模即可。
时间复杂度：
O ( 1 ) O(1) O(1)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =1e2+5,M =2e4+10,INF =0x3f3f3f3f,mod =1e9+7;intmain(){// std::ios::sync_with_stdio(false);// std::cin.tie(nullptr);// std::cout.tie(nullptr);double x,y;scanf("%lf%lf",&x,&y);printf("%.10f %.10f",x /sqrt(x*x+y*y),y /sqrt(x*x+y*y));return0;}
C - Coupon
题意：
给定n个商品，每个商品的价格是
a i a_i ai，现在有k张优惠券，每张优惠券可以减少某个商品x元(不得低于0)，询问购买全部商品的最小花费。
思路：
先保证不浪费优惠券的情况下，把尽可能多的商品价格减免到x元以下，然后如果还有优惠券剩余，我们对剩下的商品价格从高到低使用优惠券。
时间复杂度：
O ( n l o g n ) O(nlogn) O(nlogn)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =2e5+10,M =2e4+10,INF =0x3f3f3f3f,mod =1e9+7;int a[N];intmain(){// std::ios::sync_with_stdio(false);// std::cin.tie(nullptr);// std::cout.tie(nullptr);int n,k,x;
std::cin>>n>>k>>x;for(int i =1; i <= n ; i++){
std::cin>>a[i];if(k ==0)continue;if(k >= a[i]/x){
k -= a[i]/x;
a[i]%= x;}else{
a[i]-= k * x;
k =0;}}
ll sum =0;
std::sort(a+1,a+1+n,std::greater<int>());for(int i =1+ k ; i <= n ; i++)sum += a[i];
std::cout<<sum;return0;}
D - 2-variable Function
题意：
给定一个数n，找到一个数x，满足下列两个条件：
x ≥ n x\geq n x≥n∃ a ∃ b , 使 得 x = a 3 + a 2 b + a b 2 + b 3 ( a , b ∈ N ) \exists a\exists b,使得x=a^3+a^2b+ab^2+b^3(a,b\in N) ∃a∃b,使得x=a3+a2b+ab2+b3(a,b∈N)
思路：
∵ n ≤ 1 0 18 \because n\leq 10^{18} ∵n≤1018 ∴ a , b ≤ 1 0 6 \therefore a,b\leq10^{6} ∴a,b≤106我们可以使用双指针，从小到大枚举
a a a，从大到小 b b b，从而枚举出所有的 x = a 3 + a 2 b + a b 2 + b 3 ≥ n x=a^3+a^2b+ab^2+b^3\geq n x=a3+a2b+ab2+b3≥n，并从中找到最小值。
时间复杂度：
O ( n 3 ) O(\sqrt[3]{n}) O(3n)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =1500+10,M =2e4+10,INF =0x3f3f3f3f,mod =1e9+7;intmain(){// std::ios::sync_with_stdio(false);// std::cin.tie(nullptr);// std::cout.tie(nullptr);
ll n;
std::cin>>n;
ll res =1e18;
ll j =1e6;for(ll i =0; i <=1e6; i++){
ll temp = i*i*i+i*i*j+i*j*j+j*j*j;while(temp >= n && j >=0){
res = std::min(res,temp);
j--;
temp = i*i*i+i*i*j+i*j*j+j*j*j;}}
std::cout<<res;return0;}
E - Bishop 2
题意：
给出一个
n ∗ n n*n n∗n的地图，其中 ′ . ′ '.' ′.′是平地，其中 ′ # ′ '\#' ′#′是障碍，并给出一个起点和终点，在不跨越障碍的情况下，可以往左上，右上，右下，左下四个斜角方向一次移动任意个单位，询问从起点移动到终点的最小步数，若不存在路径，则输出-1。
思路：
修改正常BFS的拓展方式即可，每次拓展的时候把四个斜角方向可以拓展的点全部拓展。
时间复杂度：
O ( n 2 ) O(n^2) O(n2)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =1500+10,M =2e4+10,INF =0x3f3f3f3f,mod =1e9+7;structNode{int x,y,step;}que[N*N];char a[N][N];bool book[N][N];int ne[4][2]={1,1,1,-1,-1,1,-1,-1};int n,start_x,start_y,end_x,end_y;boolOK(int x,int y){if(x<1||y<1||x>n||y>n||a[x][y]=='#')returnfalse;returntrue;}voidbfs(){int head =0,tail =-1;
que[++tail]={start_x,start_y,0};
book[start_x][start_y]=true;while(tail>=head){auto temp = que[head++];if(temp.x == end_x && temp.y == end_y){
std::cout<<temp.step;return;}for(int i =0; i <4; i++){int tx = temp.x + ne[i][0];int ty = temp.y + ne[i][1];while(OK(tx,ty)){if(!book[tx][ty])que[++tail]={tx,ty,temp.step+1};
book[tx][ty]=true;
tx += ne[i][0];
ty += ne[i][1];}}}
std::cout<<-1;}intmain(){// std::ios::sync_with_stdio(false);// std::cin.tie(nullptr);// std::cout.tie(nullptr);
std::cin>>n>>start_x>>start_y>>end_x>>end_y;for(int i =1; i <= n ; i++)std::cin>>(a[i]+1);bfs();return0;}
F - typewriter
题意：
给出n个键盘，每个键盘可以打印字母由一个字符串表示，现在要打印一个长度为L的字符串，每次选择一个键盘打印字符串，可以打印出多少不同的字符串。
思路：
应用容斥原理，以n=3为例：
ans =
+（只使用第一个键盘）+（只使用第二个键盘）+（只使用第二个键盘）-（只使用第一个键盘和第二个键盘共有的字母打印）-（只使用第一个键盘和第三个键盘共有的字母打印）-（只使用第二个键盘和第三个键盘共有的字母打印）+（使用所用键盘共有的字母打印）。因此我们只需要枚举上述所有情况，求出答案即可。
时间复杂度：
N个字母所能打印的长度为L的字符串的个数为
N L N^{L} NL。使用快速幂会花费
O ( l o g L ) O(logL) O(logL)的时间。此外，枚举所有的情况是
O ( 2 n ) O(2^n) O(2n)所以总时间复杂度为
O ( 2 n l o g L ) O(2^nlogL) O(2nlogL)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =30,M =2e4+10,INF =0x3f3f3f3f,mod =998244353;bool temp[N],a[N][N];
ll ans,n,len;
ll quickPow(ll x,ll k){
ll res =1;while(k){if(k&1)res =(x * res)% mod;
x = x * x % mod;
k >>=1;}return res;}voiddfs(int u,int cnt){if(u==n){if(cnt==0)return;int count =0;for(int i =0; i <26; i++)if(temp[i])count++;if(cnt&1)ans =(ans +quickPow(count,len))% mod;else ans =(ans -quickPow(count,len)+ mod)% mod;return;}dfs(u+1,cnt);bool last[N];memcpy(last,temp,sizeof temp);for(int i =0; i <26; i++)temp[i]&= a[u][i];dfs(u+1,cnt+1);memcpy(temp,last,sizeof temp);}intmain(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin>>n>>len;for(int i =0; i < n ; i++){
std::string s;
std::cin>>s;for(int j =0; j < s.size(); j++) a[i][s[j]-'a']=true;}for(int i =0; i <26; i++)temp[i]=true;dfs(0,0);
std::cout<<ans;return0;}
G - Game on Tree 3
题意：
给定一棵根为1的树，除了根，每个点都有一个权值
w i w_i wi，现在小明和小红从根节点开始按照如下规则玩一个游戏：
- 小红任意选择一个点，把这个点的权值变为0
- 小明从当前点出发，可以走到任意一个儿子节点
- 然后小明可以决定是否结束游戏(如果小明在叶子节点则必须结束游戏)
最后小明获得的分数就是小明所在点的权值，小明希望获得的分数尽可能得高，小红希望小明获得的分数尽可能的低,假设两人都足够聪明的情况下(即总是做出对当前最有利的操作)，小明可以获得的最大分数是多少。
思路：
使用动态规划(树形dp)和二分答案。
考虑对于某一个分数x x x，小明是否存在方案可以获得比 x x x大的分数：我们令
w u ≥ x w_u\geq x wu≥x的点 v u v_u vu为1， w u < x w_u< x wu<x的点 v u v_u vu为0，。如果要使小明无法获得分数
x x x，那么必须要使这些为1的点变成0，我们假设 d p [ i ] dp[i] dp[i]为小明在点 i i i开始游戏小红所需要的消除次数。那么对于某个点的
d p [ i ] dp[i] dp[i]，我们可以用如下式子求出：d p [ i ] = v i + m a x ( 0 , ∑ c d p [ c ] − 1 ) ( c ∈ c h i l d r e n i ) dp[i]=v_i+max(0,\sum_{c}dp[c]-1)(c\in children_i) dp[i]=vi+max(0,∑cdp[c]−1)(c∈childreni)如果当前点
v i = 1 v_i=1 vi=1,那么肯定是要消除的，在小明走到儿子节点之前，我们还有一次消除机会(开始游戏时小红是先手)，所以还要加上 ( m a x ( ∑ c d p [ c ] − 1 , 0 ) ) (max(\sum_{c}dp[c]-1,0)) (max(∑cdp[c]−1,0))。最后可以求得
d p [ 0 ] dp[0] dp[0]，如果 d p [ 0 ] ! = 0 dp[0]!=0 dp[0]!=0，那么小明是可以获得一个比 x x x大的分数的。最后用二分找到最大值即可。
时间复杂度：
O ( n l o g ( m a x A i ) ) O(nlog(maxA_i)) O(nlog(maxAi))
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =2e5+10,M = N *2,INF =0x3f3f3f3f,mod =998244353;int h[N],e[M],ne[M],idx;int w[N],dp[N];voidadd(int a,int b){
e[idx]= b,ne[idx]= h[a],h[a]= idx++;}voiddfs(int u,int fa,int val){
dp[u]=(w[u]>= val);int sum =0;for(int i = h[u];~i ; i = ne[i]){int v = e[i];if(v==fa)continue;dfs(v,u,val);
sum += dp[v];}
dp[u]+= std::max(0,sum-1);}boolcheck(int val){dfs(1,-1,val);return dp[1]!=0;}intmain(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);int n;
std::cin>>n;memset(h,-1,sizeof h);int max =-1;for(int i =2; i <= n ; i++)std::cin>>w[i],max = std::max(max,w[i]);for(int i =1; i < n ; i++){int a,b;
std::cin>>a>>b;add(a,b),add(b,a);}
w[0]=-1;int L =0,R = max;while(R>L){int mid = L + R +1>>1;if(check(mid))L = mid;else R = mid -1;}
std::cout<<L;return0;}
Ex - 01? Queries
题意：
给定一个由
′ 0 ′ , ′ 1 ′ 和 ′ ? ′ '0','1'和'?' ′0′,′1′和′?′组成的字符串,我们可以任意得将 ′ ? ′ '?' ′?′替换成 ′ 0 ′ '0' ′0′或 ′ 1 ′ '1' ′1′,求字符串的所有子串可以形成的不同的01串有多少种。现在存在q个操作,每次操作将第x个字符变成
′ 0 ′ , ′ 1 ′ 或 ′ ? ′ '0','1'或'?' ′0′,′1′或′?′,询问每次操作后的答案。
思路：
我们先考虑在某种情况下的01串种数。
考虑动态规划,定义d p [ i ] [ 0 ] 和 d p [ i ] [ 1 ] dp[i][0]和dp[i][1] dp[i][0]和dp[i][1]分别表示前 i i i个字母所能组成的以0结尾的和以1结尾的种数。那么应该有如下状态转移方程:
s [ i ] = 0 s[i]=0 s[i]=0 d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + d p [ i − 1 ] [ 1 ] + 1 dp[i][0]=dp[i-1][0]+dp[i-1][1]+1 dp[i][0]=dp[i−1][0]+dp[i−1][1]+1 d p [ i ] [ 1 ] = d p [ i − 1 ] [ 1 ] dp[i][1]=dp[i-1][1] dp[i][1]=dp[i−1][1]s [ i ] = 1 s[i]=1 s[i]=1 d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] dp[i][0]=dp[i-1][0] dp[i][0]=dp[i−1][0] d p [ i ] [ 1 ] = d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 0 ] + 1 dp[i][1]=dp[i-1][1]+dp[i-1][0]+1 dp[i][1]=dp[i−1][1]+dp[i−1][0]+1s [ i ] = ? s[i]= \ ? s[i]= ? d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + d p [ i − 1 ] [ 1 ] + 1 dp[i][0]=dp[i-1][0]+dp[i-1][1]+1 dp[i][0]=dp[i−1][0]+dp[i−1][1]+1 d p [ i ] [ 1 ] = d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 0 ] + 1 dp[i][1]=dp[i-1][1]+dp[i-1][0]+1 dp[i][1]=dp[i−1][1]+dp[i−1][0]+1我们将上述状态转移方程用矩阵表示:
[ d p [ i ] [ 0 ] d p [ i ] [ 1 ] 1 ] = A s i [ d p [ i − 1 ] [ 0 ] d p [ i − 1 ] [ 1 ] 1 ] \begin{bmatrix} dp[i][0] \\dp[i][1] \\1 \end{bmatrix}=A_{s_{i}}\begin{bmatrix} dp[i-1][0]\\ dp[i-1][1]\\1 \end{bmatrix} ⎣⎡dp[i][0]dp[i][1]1⎦⎤=Asi⎣⎡dp[i−1][0]dp[i−1][1]1⎦⎤分别的,对于不同的
A s i A_{s_{i}} Asi,有:s [ i ] = 0 : s[i]=0: s[i]=0: A s i = [ 1 1 1 0 1 0 0 0 1 ] A_{s_{i}}=\begin{bmatrix} 1& 1 &1 \\ 0&1 & 0\\ 0& 0 & 1 \end{bmatrix} Asi=⎣⎡100110101⎦⎤ s [ i ] = 1 : s[i]=1: s[i]=1: A s i = [ 1 0 0 1 1 1 0 0 1 ] A_{s_{i}}=\begin{bmatrix} 1& 0 &0 \\ 1&1 & 1\\ 0& 0 & 1 \end{bmatrix} Asi=⎣⎡110010011⎦⎤ s [ i ] = ? : s[i]=\ ?: s[i]= ?: A s i = [ 1 1 1 1 1 1 0 0 1 ] A_{s_{i}}=\begin{bmatrix} 1& 1 &1 \\ 1&1 & 1\\ 0& 0 & 1 \end{bmatrix} Asi=⎣⎡110110111⎦⎤此外有
[ d p [ i ] [ 0 ] d p [ i ] [ 1 ] 1 ] = A s i A s i − 1 … A s 1 [ d p [ 0 ] [ 0 ] d p [ 0 ] [ 1 ] 1 ] = A s i A s i − 1 … A s 1 [ 0 0 1 ] \begin{bmatrix} dp[i][0] \\dp[i][1] \\1 \end{bmatrix}=A_{s_{i}}A_{s_{i-1}}\dots A_{s_{1}}\begin{bmatrix} dp[0][0]\\ dp[0][1]\\1 \end{bmatrix}=A_{s_{i}}A_{s_{i-1}}\dots A_{s_{1}}\begin{bmatrix} 0\\ 0\\1 \end{bmatrix} ⎣⎡dp[i][0]dp[i][1]1⎦⎤=AsiAsi−1…As1⎣⎡dp[0][0]dp[0][1]1⎦⎤=AsiAsi−1…As1⎣⎡001⎦⎤我们可以用线段树维护每一个矩阵,这样修改操作可以在
l o g n logn logn时间内完成。
时间复杂度：
O ( q l o g n ) O(qlogn) O(qlogn)
AC代码：
#include<bits/stdc++.h>typedeflonglong ll;constint N =1e5+10,M = N *2,INF =0x3f3f3f3f,mod =998244353;structNode{int l,r;
ll a[3][3];}tr[N*4];char s[N];int n,q;voidpushup(int u){memset(tr[u].a,0,sizeof tr[u].a);for(int i =0; i <3; i++)for(int j =0; j <3; j++){for(int k =0; k <3; k++)
tr[u].a[i][j]=(tr[u].a[i][j]+ tr[u<<1].a[i][k]*tr[u<<1|1].a[k][j])%mod;}}voidassign(Node &root,char ch){if(ch=='0'){
root.a[0][0]=1;
root.a[0][1]=1;
root.a[0][2]=1;
root.a[1][0]=0;
root.a[1][1]=1;
root.a[1][2]=0;
root.a[2][0]=0;
root.a[2][1]=0;
root.a[2][2]=1;}elseif(ch=='1'){
root.a[0][0]=1;
root.a[0][1]=0;
root.a[0][2]=0;
root.a[1][0]=1;
root.a[1][1]=1;
root.a[1][2]=1;
root.a[2][0]=0;
root.a[2][1]=0;
root.a[2][2]=1;}else{
root.a[0][0]=1;
root.a[0][1]=1;
root.a[0][2]=1;
root.a[1][0]=1;
root.a[1][1]=1;
root.a[1][2]=1;
root.a[2][0]=0;
root.a[2][1]=0;
root.a[2][2]=1;}}voidbuild(int u,int l,int r){if(l==r){
tr[u]={l,r};assign(tr[u],s[r]);}else{int mid = l + r >>1;
tr[u]={l,r};build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}}voidmodify(int u,int x,char ch){if(tr[u].l==x&&tr[u].r==x){assign(tr[u],ch);}else{int mid = tr[u].l + tr[u].r >>1;if(x <= mid)modify(u<<1,x,ch);elsemodify(u<<1|1,x,ch);pushup(u);}}intmain(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin>>n>>q;
std::cin>>(s+1);build(1,1,n);while(q--){int x;char ch;
std::cin>>x>>ch;modify(1,x,ch);
std::cout<<(tr[1].a[0][2]+tr[1].a[1][2])%mod<<'\n';}return0;}
标签：
算法
本文转载自: https://blog.csdn.net/qq_62213124/article/details/123933753
版权归原作者 skynesser 所有， 如有侵权，请联系我们删除。
版权归原作者 skynesser 所有， 如有侵权，请联系我们删除。