AtCoder Beginner Contest 359

A - Count Takahashi

有\(n\)个字符串，每个串要么是Takahashi要么是Aoki，问有多少个字符串是Takahashi

额....这还要有题解吗(?)

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string a;
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a;
        if(a=="Takahashi")++ans;
    }
    cout<<ans<<endl;
}

B - Couples

有\(2N\)个数，第\(i\)个数是\(A_i\)，其中\(1-N\)的每个数恰好会出现两次。问有多少个\(i\)满足\(A_{i-1}=A_{i+1}\)。

翻译把题目唯一要转弯的地方直接翻译过来了，不过好像也没得差。

#include<iostream>
using namespace std;
int n,a[205],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n+n;++i)
        cin>>a[i];
    for(int i=2;i<n+n;++i)
        if(a[i-1]==a[i+1])
            ++ans;
    cout<<ans<<endl;
    return 0;
}   

C - Tile Distance 2

坐标轴被\(2\times 1\)的方块铺满。给出如下两个定义：

• 假设坐标对\((i,j)\)，那么\(A_{ij}=\{(x,y)|i\le x\le i+1 \& j\le y\le j+1\}\)
• 如果\(i+j\)是偶数，那么\(A_{i,j}\)和\(A_{i+1,j}\)被同一块方块铺满。
  现在从\((S_x+0.5,S_y+0.5)\)位置开始，希望走到\((T_x+0.5,T_y+0.5)\)，问最少要穿过几个方块。

首先沿着\(y\)轴走，每一步必定要穿过一个方块。
而沿着\(x\)轴方向走，每两步必定穿过一个方块。但是可以通过朝着\(y\)方向走，可以让自己一直不跨过方块。

因此，若沿着\(y\)方向次数多于\(x\)的次数，则可以通过朝\(y\)轴移动来避免在\(x\)轴跨方块；否则有几次\(y\)轴移动就可以使得同等次数的\(x\)轴移动不需要跨方块。

这样计算一下还有几次多出来的\(x\)轴移动，然后计算一下要跨过几个方块即可。

#include<iostream>
#include<cstdio>
using namespace std;
long long sx,sy,tx,ty,ans;
int main()
{
    cin>>sx>>sy>>tx>>ty;
    if(sx>tx)swap(sx,tx),swap(sy,ty);
    long long dx=abs(sx-tx),dy=abs(sy-ty);
    long long bx=((((sx+sy)&1)?1:0)+(((tx+ty)&1)?-1:0)+dx);
    ans=max(0ll,(bx-dy)>>1)+dy;
    cout<<ans<<endl;
    return 0;
}   

D - Avoid K Palindrome

给定一个长度为\(N\)的字符串\(S\)，包含A、B和?。同时还给出了一个数字\(K\)。
?可以随意填入A或B，问有多少个可能的串\(S\)，使得\(S\)的任意一个长度为\(K\)的子串都不是回文串。

发现\(K\)很小，所以直接状压前\(K\)位的状态即可。设\(f[i][S]\)表示当前考虑到了第\(i\)位，前\(K\)位的状态是\(S\)的方案数。转移应该很简单，枚举当前位填什么就好了，然后判断\(S\)是否回文即可。

时间复杂度\(O(n2^k)\)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MOD=998244353;
int n,k;
string S;
bool pre[1<<10];
int f[1005][1<<10];
void add(int &x,int y){x=(x+y)%MOD;}
int main()
{
    cin>>n>>k;
    cin>>S;
    for(int i=0;i<(1<<k);++i)
    {
        bool flag=true;
        for(int j=0;j<(k>>1);++j)
            if(((i>>j)&1)^((i>>(k-j-1))&1))
                flag=false;
        pre[i]=flag;
    }
    int full=(1<<k)-1;
    f[0][0]=1;
    for(int i=1;i<=n;++i)
    {
        char c=S[i-1];
        for(int j=0;j<(1<<k);++j)
        {
            if(!f[i-1][j])continue;
            if(i>k&&pre[j])continue;
            if(c=='A'||c=='?')
                add(f[i][(j<<1)&full],f[i-1][j]);
            if(c=='B'||c=='?')
                add(f[i][(j<<1|1)&full],f[i-1][j]);
        }
    }
    int ans=0;
    for(int i=0;i<(1<<k);++i)
        if(!pre[i])add(ans,f[n][i]);
    cout<<ans<<endl;
    return 0;
}

E - Water Tank

有一排水槽，编号\(0-n\)。\(1-n\)每个水槽左侧有一个隔板，给出隔板高度，0号水槽左侧可以认为有一个无限高的隔板。
现在不断地向第\(0\)个水槽注水，回答\(1-n\)每个水槽中第一次有水的时间。

考虑水槽\(i\)，显然只需要水的高度能够跨过其左侧的隔板那么就能流进来，而想要跨过左侧隔板的高度，显然只需要考虑更小编号的水槽左侧的隔板中，最靠近的、且高度大于当前隔板的隔板，然后两个隔板之间需要注满水。接下来向前重复这个过程即可。

于是用一个单调队列就可以解决问题了。

#include<iostream>
#include<cstdio>
using namespace std;
const int MAX=200200;
int n,h[MAX],a[MAX],t;
long long sum=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&h[i]);
    h[0]=1000000001;
    a[t=1]=0;
    for(int i=1;i<=n;++i)
    {
        while(h[a[t]]<=h[i])sum-=1ll*h[a[t]]*(a[t]-a[t-1]),--t;
        sum+=1ll*(i-a[t])*h[i];
        a[++t]=i;
        printf("%lld ",sum+1);
    }
    puts("");
    return 0;
}

F - Tree Degree Optimization

有\(n\)个点，每个点有一个权值\(a[i]\)。现在需要把他们连成一棵树。
一个树的代价是\(\sum_{i=1}^n a[i]*d_i^2\)，其中\(d_i\)表示节点\(i\)在树上的度数。
求最小代价。

先把权值排序，然后依次加入，每次找一个父亲节点插入到树中。
显然只会插入到插入后权值增量最小的父亲节点。用一个优先队列即可解决。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX=200200;
int n;
int a[MAX];
long long ans;
struct Node{int a,d;long long del;};
bool operator<(Node a,Node b)
{
    if(a.del!=b.del)return a.del>b.del;
    else return a.a>b.a;
}
priority_queue<Node> Q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(&a[1],&a[n+1]);
    Q.push((Node){a[1],0,a[1]});
    for(int i=2;i<=n;++i)
    {
        Node x=Q.top();Q.pop();
        ans+=x.del+a[i];
        x.d+=1;
        x.del=(1ll*(x.d+1)*(x.d+1)-1ll*x.d*x.d)*x.a;
        Q.push(x);
        Q.push((Node){a[i],1,3ll*a[i]});
    }
    printf("%lld\n",ans);
    return 0;
}

G - Sum of Tree Distance

给一个\(n\)个节点的树，每个节点有一个权值\(a[i]\)。定义\(f(i,j)\)：如果\(a[i]\neq a[j]\)则\(f(i,j)=0\)；否则\(f(i,j)\)为\(i,j\)在树上的距离。
求\(\sum_{i=1}^n\sum_{j=i+1}^n f(i,j)\)。

这个数据范围非常能分块。
对于数量大于\(\sqrt n\)的权值，可以做一遍\(O(n)\)的\(dp\)。总复杂度为\(O(n\sqrt n)\)。
对于数量小于\(\sqrt n\)的权值，可以暴力两两之间计算。具体的说，考虑\(\sum_{i=1}^k s_i\le n\)，且\(s_i\le \sqrt n\)。于是\(\sum_{i=1}^k s_i^2\le \sum_{i=1}^k s_i\sqrt n\le \sqrt n\sum_{i=1}^k s_i\le n\sqrt n\)。
所以这部分暴力求距离的次数也不会超过\(O(n\sqrt n)\)。

如果采用\(O(n\log n)\)的在线LCA求法的话，可以做到\(O(n\sqrt n\log n)\)，实际上远远不满。或者采用\(O(1)\)求LCA的方法，欧拉序+ST表，最终复杂度能做到\(O(n\sqrt n)\)。

如果不分块的就可以点分治随便弄弄，好像不是很难。