比賽地址

https://codeforces.ml/contest/1461

A. String Generation

題目大意

輸出一個只能由小寫字母a、b、c組成的長度為n且最長子回文串長度不超過k的序列，

解題思路

直接按照abcabc輪流輸出即可，這時候最長子回文串長度為1，

AC代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)
        if(i%3==0)
            cout<<'a';
        else if(i%3==1)
            cout<<'b';
        else if(i%3==2)
            cout<<'c';
    cout<<endl;
}
int main()
{
   int T;cin>>T;
    while(T--)
        solve();
}

B. Find the Spruce

題目大意

給你一個n*m矩陣，由.和*組成，其中*為樹的葉子，問矩陣種能組成樹的最多數量是多少，樹如圖下所示，一個小黑塊等于一個*，

解題思路

資料范圍才500，可以用n^3的暴力解決，比賽時本人寫了個動態規劃，但是注意使用short和bool，不然會MLE，其中 dp[i][j] 代表矩陣中 (i,j) 向前有多少個連續的*，is[i][j][k] 代表 (i,j) 之前的k個元素是一棵樹的底層，然后我們只要列舉最下面一層的大小，假設為k，則狀態轉移方程為
if(dp[i][j]>=k&&is[i-1][j-1][k-2])
ans++,is[i][j][k]=1;
含義是，(i,j) 向前有至少k個連續的*，而且上一層的 (i-1,j-1) 向前的k-2個元素是一棵樹的最底層，那么第 (i,j) 向前的k個連續* 可以拼湊在上面一棵樹之下作為新的底層形成一顆新的樹，

AC代碼

#include<bits/stdc++.h>
#define MAXN 505
using namespace std;
typedef long long ll;
short dp[MAXN][MAXN];
bool is[MAXN][MAXN][MAXN];
char mmap[MAXN][MAXN];
void clr(int n,int m)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=0;
            for(int k=1;k<=m;k++)
                is[i][j][k]=0;
        }
}
void solve()
{
    int n,m;cin>>n>>m;
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>mmap[i][j];
            if(mmap[i][j]=='*')
            {
                is[i][j][1]=dp[i][j]=1;
                if(mmap[i][j-1]=='*')
                    dp[i][j]+=dp[i][j-1];
                ans++;
            }
        }
    for(int k=3;k<=m;k+=2)
        for(int i=2;i<=n;i++)
            for(int j=1;j<=m;j++)
            if(dp[i][j]>=k&&is[i-1][j-1][k-2])
                ans++,is[i][j][k]=1;
    cout<<ans<<endl;
    clr(n,m);
}
int main()
{
   int T;cin>>T;
    while(T--)
        solve();
}

C. Random Events

題目大意

給你一個1~n的隨機序列，再給你n次操作，每次操作有一定概率p觸發，操作的方式是對0 ~ r 進行排序，問你整個序列最終變成有序的概率是多少，

解題思路

比較簡單的數學題，假設從0~m是無序序列，m+1到n是有序序列，那我們需要知道至少有一次 r>=m 的操作的發生的概率就是我們要求的概率，如果序列本身就是有序的，則概率為1，

AC代碼

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
typedef long long ll;
int a[MAXN];
int dp[MAXN];
void solve()
{
    int n,m;cin>>n>>m;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        cin>>a[i];
    double np=1;
    for(int i=n;i>=1&&a[i]==i;i--)
        dp[i]=1;
    dp[n+1]=1;
    for(int i=1;i<=m;i++)
    {
        int aa;double b;
        cin>>aa>>b;
        if(dp[aa+1]) //說明這次操作的r>=m
            np*=(1-b);
    }
    np=1-np;
    if(dp[1])
        np=1;
    printf("%.8f\n",np);;
}
int main()
{
   int T;cin>>T;
    while(T--)
        solve();
}

D. Divide and Summarize

題目大意

給你一個陣列，設mid=（陣列中最大元素+最小元素）/2，你可以把小于等于mid的數放在一堆，大于mid的數放在一堆形成兩個新的陣列，同樣，新形成的兩個陣列也可以進行相同操作，給你一堆詢問，每次詢問給出一個數，問是否有通過這樣方式構造的陣列的元素和等于這個數，

解題思路

直接排序以后二分模擬他的操作，并且把所有可能的值存下來，計算陣列和的時候可以用前綴和差分陣列O(1)計算，最后對著記錄下來的答案輸出詢問，聽說unordered_map在比賽中有可能被hack，所以建議以后老老實實用logn的map，

AC代碼

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
typedef long long ll;
unordered_map<ll,bool> um;
int a[MAXN];
ll premix[MAXN];
void func(int l,int r)
{
    if(l>=r) return;
    int mid=(a[l]+a[r])/2;
    int pos=upper_bound(a+l,a+r+1,mid)-a;
    if(pos==r+1)return;
    um[premix[pos-1]-premix[l-1]]=1;
    um[premix[r]-premix[pos-1]]=1;
    func(l,pos-1);
    func(pos,r);
}
void solve()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        premix[i]=premix[i-1]+a[i];
    um[premix[n]]=1;
    func(1,n);
    for(int i=1;i<=m;i++)
    {
        int t;cin>>t;
        cout<<(um[t]?"YES":"NO")<<endl;
    }
    um.clear();
}
int main()
{
   int T;cin>>T;
    while(T--)
        solve();
}