AtCoder Beginner Contest 246
A （思维）
这个题大意是告诉你一个矩形的三个点，求第四个点，并且已知每条边都是平行于\(x\)轴或者是\(y\)轴的，那么我们可以确定，\(x\)坐标只有两种，并且每一种都有两个，\(y\)坐标也是
题目输入三个坐标，那么答案就是缺少的那个个（数量为\(1\)的那一个坐标）
所以我们可以用异或来处理
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
const int maxn=2e5+10;
const int mod=998244353;
int t;
void solve()
{
int x,y;
cin>>x>>y;
for (int i=1;i<=2;i++)
{
int tx,ty;
cin>>tx>>ty;
x^=tx;
y^=ty;
}
cout<<x<<" "<<y<<"\n";
return ;
}
signed main ()
{
// cin>>t;
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
B（向量，几何）
这道题在\(vp\)的时候死活没看懂，我也是看了其他人的解释才知道这个题的题意
大意就是给你一个点的坐标\(x\)和\(y\),我们可以把从原点到这个点的方向移动，找到到距离为\(1\)的位置并输出，同一个方向，距离为\(1\)，不就很像向量里面的方向向量
所以我们可以用求方向向量的方法来求，故直接除以模
记得数据的类型为\(double\)
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=1500+10;
#define int long long
signed main ()
{
double x,y;
cin>>x>>y;
double sx,sy;
double l=sqrt(x*x+y*y);
sx=x/l;
sy=y/l;
printf ("%.10lf %.10lf\n",sx,sy);
system ("pause");
return 0;
}
C（贪心）
这个题目大意就是有\(n\)个物品，有\(k\)张优惠券，每张优惠券最多可以省\(x\)元（当物品的价格小于\(x\)时，我们需要支付的费用为\(0\))
对于这些优惠券，我们要尽可能的让它发挥到最大效用。所以首先我们考虑每一张优惠券都帮我们省了\(x\)元，然后如果还有多余的优惠券，我们再考虑给那些价格高的使用
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int n,k,x;
signed main ()
{
cin>>n>>k>>x;
vector<int>res;
int sum=0;
for (int i=1;i<=n;i++)
{
int t;
cin>>t;
int p=t/x;
int get=0;
if(k>=p)
{
get=p*x;
k-=p;
}
else
{
get=k*x;
k=0;
}
sum+=(t-get);
res.push_back(t-get);
}
sort(res.rbegin(),res.rend());
for (auto x:res)
{
if(k)
{
sum-=x;
k--;
}
else break;
}
cout<<sum<<"\n";
system ("pause");
return 0;
}
D (二分)
这个题是给你一个\(n\)，问是否找到一对\(a\)和\(b\),满足\(x=a^3+b^3+a^2b+ab^2\),其中\(x\)是大于\(n\)的数中最小的一个
对于这一道题，\(n\)的范围是\(1e18\),故我们可以知道这个\(a\)和\(b\)的最大值是\(1e6\),所以我们不太可能一一去枚举\(a\)和\(b\)，但是我们可以先枚举\(a\)，然后对于\(b\)的选取采用二分的方式
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=1500+10;
#define int long long
int mx=1e6;
int n;
int check(int a,int b)
{
int res=a*a*a+b*b*b+a*a*b+a*b*b;
return res;
}
signed main ()
{
cin>>n;
int ans=1e18+10;
for (int a=0;a<=mx;a++)
{
int l=0,r=mx;
int t=mx;
while (l<=r)
{
int mid=(l+r)>>1;
int p=check(a,mid);
if(p>=n)
{
ans=min(ans,p);
r=mid-1;
}
else
{
l=mid+1;
}
}
}
cout<<ans<<"\n";
system ("pause");
return 0;
}
E （bfs)
题目给出一个网格，一个起点，一个终点，其中\(.\)代表空地，可以走，\(#\)代表障碍，不可以走，其中走的方式也和一般的走法不同，他是斜着走的
比如此时为\((x,y)\),它有以下四种走法
走到\((x+d,y+d)\)，但要保证\((x+1,y+1)\),\((x+2,y+2)\),\((x+3,y+3)\),直到\((x+d,y+d)\)这些点都是空地
走到\((x+d,y-d)\)，但要保证\((x+1,y-1)\),\((x+2,y-2)\),\((x+3,y-3)\),直到\((x+d,y-d)\)这些点都是空地
走到\((x-d,y+d)\)，但要保证\((x-1,y+1)\),\((x-2,y+2)\),\((x-3,y+3)\),直到\((x+d,y+d)\)这些点都是空地
走到\((x-d,y-d)\)，但要保证\((x-1,y-1)\),\((x-2,y-2)\),\((x-3,y-3)\),直到\((x-d,y-d)\)这些点都是空地
问从起点走到终点最小需要走多少次
对于可不可以到达，如果两个点的坐标的和的奇偶性不同，那么不管如何都是到达不了的（每一次横纵坐标的变化和都是偶数）
这个很像最短路，但是有一点要注意，加入队列里面的不要太多了，不然会\(re\)
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int maxn=2500+10;
#define int long long
int n;
int sx,sy,ex,ey;
string s[maxn];
bool vis[maxn][maxn];
int dx[4]={-1,-1,1,1};
int dy[4]={1,-1,1,-1};
struct node
{
int x,y,dis;
friend bool operator < (const node a,const node b)
{
return a.dis>b.dis;
}
};
bool check(int x,int y)
{
if(x>=1&&y>=1&&x<=n&&y<=n)
{
if(s[x][y]=='.')
{
return true;
}
}
return false;
}
int bfs(int sx,int sy)
{
priority_queue<node>q;
q.push({sx,sy,0});
vis[sx][sy]=true;
while (!q.empty())
{
auto [x,y,dis]=q.top();
q.pop();
// if(vis[x][y]) continue;//如果是在这儿判断，可能会有很多重复的坐标进入到队列里面，然后就会re,所以我们可以在进入队列的时候判断一下这个是否在队列里面
// vis[x][y]=true;
if(x==ex&&y==ey) return dis;
for (int d=0;d<4;d++)
{
int tx=x+dx[d];
int ty=y+dy[d];
while (check(tx,ty))
{
if(tx==ex&&ty==ey) return dis+1;
if(!vis[tx][ty]) q.push({tx,ty,dis+1});
vis[tx][ty]=true;
tx+=dx[d];
ty+=dy[d];
}
}
}
return -1;
}
signed main ()
{
cin>>n>>sx>>sy>>ex>>ey;
for (int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=" "+s[i];
}
if((sx+sy)%2==(ex+ey)%2)
{
cout<<bfs(sx,sy)<<"\n";
}
else
{
cout<<-1<<"\n";
}
system ("pause");
return 0;
}
F（容斥）
这个题大意是给你\(n\)个字符串，我们要从这\(n\)个字符串里面选择\(l\)次，每次选出一个字符串，然后从字符串里面选择出一个字符，组成一个长度为\(l\)的字符串，问最后有多少种不同的字符串
如果是只有一个字符串，那就很好办，直接计算出字母的种类\(cnt\)，然后输出\(2^cnt\)
但是这个题不仅仅只有一个，还有其他的字符串和它一起构建字符串
所以我们就可以想到容斥
对于某一种搭配有偶数个组成的，用减法
对于某一种搭配有奇数个组成的，用加法
然后我们该怎么搭配呢
我们可以看到这个\(n\)最大只有\(18\)，所以我们可以用二进制状态来表示
对于每一个搭配，都会有不同字母种类（所以在这些搭配里面的字母种类的叠加），对于重叠部分，只有是他们所有字符串都共有的
我们可以发现\(bitset\)可以很简单的实现以上效果，并快速求出所共有的字母\(cnt\),那么此时的组合方式有\(l^cnt\)个
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <bitset>
using namespace std;
const int maxn=2500+10;
#define int long long
const int mod=998244353;
int n,l;
int ksm(int x,int p)
{
int res=1;
while (p)
{
if(p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res%mod;
}
signed main ()
{
cin>>n>>l;
bitset<36>state[20];
for (int i=0;i<n;i++)
{
string s;
cin>>s;
for (int j=0;j<s.size();j++)
{
state[i][s[j]-'a']=1;
}
}
int ans=0;
bitset<36>tmp;
for (int now=1;now<(1<<n);now++)//从1开始，0会减去不该减的
{
tmp.set();
int cnt=0;
for (int j=0;j<n;j++)
{
if((now>>j)&1)
{
cnt++;
tmp&=state[j];
}
}
if(cnt&1)
{
ans=(ans+ksm(tmp.count(),l))%mod;
}
else
{
ans=(ans-ksm(tmp.count(),l)+mod)%mod;
}
}
cout<<ans<<"\n";
system ("pause");
return 0;
}
F（树形dp）
这个题大意是有一个数，小明要删除一个节点上的权值，小红从根节点出发，到它的子节点的位置，直到小红不可以走结束（叶子结点的位置），得分为小红所到达的位置的权值的最大值，小明想让小红的分数尽量低，小红想分数尽量高，小明是先手，问最后小红得到的最高分是多少
我们还是可以二分求解
我们二分小红的分数，然后我们进行一次\(dfs\),对于每一个点，只要它活着一个大于等于\(mid\)的权值，那么就可以了，那么对于小红来说，只要从根节点出发活着一个就可以成功的得到这个分数了
对于\(dfs\)里面怎么写
我们对于每一个点的子树的所有大于等于的数量都会记录，但是由于还会有小明来删除，并且小明需要先删除
所以，我们每一次这一个点的贡献都会\(res=max(res-1,0)+(w[i]>=mid)\)(小明需要删除的数量)
然后具体可以看代码
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <bitset>
using namespace std;
const int maxn=2e5+10;
#define int long long
const int mod=998244353;
int n;
int w[maxn];
vector<int>g[maxn];
int dfs(int u,int fa,int now)
{
int res=0;
for (auto v:g[u])
{
if(v==fa) continue;
res+=dfs(v,u,now);
}
res=max(res-1,0ll);
if(w[u]>=now) res++;
return res;
}
signed main ()
{
cin>>n;
int l=0,r=0;
for (int i=2;i<=n;i++)
{
cin>>w[i];
r=max(r,w[i]);
}
for (int i=2;i<=n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
int ans=0;
while (l<=r)
{
int mid=(l+r)>>1;
if(dfs(1,-1,mid))
{
ans=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
cout<<ans<<"\n";
system ("pause");
return 0;
}
Ex（矩阵转移，dp,线段树）
题目很好懂，就是给你一个字符串，有\(0\)有\(1\)还有\(?\),每一次我们都会把\(?\)变成\(0\)或者\(1\)，然后输出此时的\(01\)串的数量（其中\(?\)既可以变成\(0\),又可以变成\(1\)，在查询\(01\)的数量的时候）
其实按照一般的思路来写，我们可以看成是一个\(dp\),\(dp[i] [0]\)代表以\(i\)为结尾，最后一个是\(0\)的数量，\(1\)同上
状态转移方程如下
如果\(s[i]=='0'\)
\[dp[i][0]=dp[i-1][1]+dp[i-1][0]+1 \]\[dp[i][1]=dp[i-1][1] \]如果\(s[i]=='1'\)
\[dp[i][1]=dp[i-1][1]+dp[i-1][0]+1 \]\[dp[i][0]=dp[i-1][0] \]如果\(s[i]=='？'\)
\[dp[i][1]=dp[i-1][1]+dp[i-1][0]+1 \]\[dp[i][0]=dp[i-1][0]+dp[i-1][1]+1 \]但是每一次我们都会修改\(?\)的状态，每一次都进行一次重新计算不太现实，然后有大佬使用了线段树和矩阵变换的方式
对于上面每一种字符，都会有不同的矩阵
我们可以构造一个下面这样的矩阵(因为最多有三项)
\[\left[ \begin{matrix} dp[i][0]\\ dp[i][1] \\ 1 \end{matrix} \right] \]对于转移，我们可以构造\(A_{s_i}\)的矩阵
\[\left[ \begin{matrix} dp[i][0]\\ dp[i][1] \\ 1 \end{matrix} \right]=\left[ \begin{matrix} dp[i-1][0]\\ dp[i-1][1] \\ 1 \end{matrix} \right]\times A_{s_i} \]然后根据矩阵的特性，我们可以发现
\[\left[ \begin{matrix} dp[n][0]\\ dp[n][1] \\ 1 \end{matrix} \right]=\left[ \begin{matrix} dp[1][0]\\ dp[1][1] \\ 1 \end{matrix} \right]\times A_{s_2}\times A_{s_2}\times A_{s_3}\times ...\times A_{s_n} \]这样就很好计算了
如果\(s[i]=='0'\)
\[dp[i][0]=dp[i-1][1]+dp[i-1][0]+1 \]\[dp[i][1]=dp[i-1][1] \]可以变成这样
\[A_{s_i}=\left[\begin{matrix} 1 & 1 & 1\\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}\right] \]（如果不懂可以自己试试矩阵乘起来，感觉还蛮方便的）
如果\(s[i]=='1'\)
\[dp[i][1]=dp[i-1][1]+dp[i-1][0]+1 \]\[dp[i][0]=dp[i-1][0] \]可以变成这样
\[A_{s_i}=\left[\begin{matrix} 1&0&0\\ 1&1&1\\ 0&0&1 \end{matrix}\right] \]如果\(s[i]=='？'\)
\[dp[i][1]=dp[i-1][1]+dp[i-1][0]+1 \]\[dp[i][0]=dp[i-1][0]+dp[i-1][1]+1 \]可以变成这样
\[A_{s_i}=\left[\begin{matrix} 1&1&1\\ 1&1&1\\ 0&0&1 \end{matrix}\right] \]然后这里面\(n\)个矩阵的乘法有线段树来实现
具体的实现可以看代码
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define lson root<<1
#define rson root<<1|1
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e9+7;
const int maxn=1e6+100;
string s;
struct segtree
{
int l,r;
int a[3][3];
}tr[maxn<<2];
int n,q;
void assign(int root,char ch)
{
if(ch=='0')
{
tr[root].a[0][0] = 1;
tr[root].a[0][1] = 1;
tr[root].a[0][2] = 1;
tr[root].a[1][0] = 0;
tr[root].a[1][1] = 1;
tr[root].a[1][2] = 0;
tr[root].a[2][0] = 0;
tr[root].a[2][1] = 0;
tr[root].a[2][2] = 1;
}
else if(ch=='1')
{
tr[root].a[0][0] = 1;
tr[root].a[0][1] = 0;
tr[root].a[0][2] = 0;
tr[root].a[1][0] = 1;
tr[root].a[1][1] = 1;
tr[root].a[1][2] = 1;
tr[root].a[2][0] = 0;
tr[root].a[2][1] = 0;
tr[root].a[2][2] = 1;
}
else
{
tr[root].a[0][0] = 1;
tr[root].a[0][1] = 1;
tr[root].a[0][2] = 1;
tr[root].a[1][0] = 1;
tr[root].a[1][1] = 1;
tr[root].a[1][2] = 1;
tr[root].a[2][0] = 0;
tr[root].a[2][1] = 0;
tr[root].a[2][2] = 1;
}
return ;
}
void pushup(int root)
{
for (int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
tr[root].a[i][j]=0;
}
}
for (int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
for (int k=0;k<3;k++)
{
int x=tr[lson].a[i][k];
int y=tr[rson].a[k][j];
tr[root].a[i][j]=(x*y%mod+tr[root].a[i][j])%mod;
}
}
}
return ;
}
void build(int root,int l,int r)
{
tr[root].l=l;
tr[root].r=r;
if (l==r)
{
assign(root,s[r]);
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(root);
return ;
}
void update(int root,int l,int r,char ch)
{
if (l<=tr[root].l&&tr[root].r<=r)
{
assign(root,ch);
return ;
}
int mid=(tr[root].l+tr[root].r)>>1;
if (l<=mid)
{
update(lson,l,r,ch);
}
if (r>mid)
{
update(rson,l,r,ch);
}
pushup(root);
return ;
}
signed main ()
{
cin>>n>>q;
cin>>s;
s=" "+s;
build(1,1,n);
while (q--)
{
int x;
char ch;
cin>>x>>ch;
update(1,x,x,ch);
int ans=(tr[1].a[0][2]+tr[1].a[1][2])%mod;
cout<<ans<<"\n";
}
system ("pause");
return 0;
}