---
tags: IOICamp
---

# Day3 團體賽

:::spoiler Description
:::

:::spoiler Scoreboard
:::

:::spoiler pA**
:::

:::spoiler pB**
:::

:::spoiler pC**
:::

:::spoiler pD**
:::

:::spoiler pE**
:::

:::spoiler pF**
:::

:::spoiler pG**
:::

:::spoiler pH
:::

:::spoiler pI
:::

:::spoiler pJ**
:::

:::spoiler pK**
:::

---

[TOC]

#### **pA. 小風愛翻轉字串**

#### **pB. 放石頭**

#### **pC. 最小生成樹？**

#### **pD. 天王寺璃奈與她的璃奈板**

:::spoiler Solution (loIicon)

/*
?__,.??.　　　　/　,?﹑ 〉
　　　　　＼ ', !-─?-i　/　/’
　　　 　 ／‘?'　　　 L/／‘?﹑
　　 　 /　 ／,　 /|　 ,　 ,　　　 ',
　　　? 　/ /-?/　ｉ　L_ ? ?!　 i
　　　 ? ? 7?‘?　 ?'?-?﹑!?|　 |
　　　　 !,/7 '0'　　 ’0i?| 　 |　　　
　　　　 |.?"　　_　　 ,,,, / |./ 　 |
　　　　 ?'| i＞.﹑,,__　_,.? / 　.i 　|
　　　　　 ?'| | / k_７_/?'?,　?.　|
　　　　　　 | |/i 〈|/　 i　,.? |　i　|
　　　　　　.|/ /　ｉ： 　 ?!　　＼　|
　　　 　 　 k?>﹑? 　 _,.?﹑ 　 /﹑!
　　　　　　 !'〈//‘Ｔ’', ＼ ‘'7'?r'
　　　　　　 ?'?L__|___i,___,??|?
　　　　　 　　　?-,/　|___./
　　　　　 　　　'?'　　!_,.:
?__,.??.　　　　/　,?﹑ 〉
　　　　　＼ ', !-─?-i　/　/’
　　　 　 ／‘?'　　　 L/／‘?﹑
　　 　 /　 ／,　 /|　 ,　 ,　　　 ',
　　　? 　/ /-?/　ｉ　L_ ? ?!　 i
　　　 ? ? 7?‘?　 ?'?-?﹑!?|　 |
　　　　 !,/7 '0'　　 ’0i?| 　 |　　　
　　　　 |.?"　　_　　 ,,,, / |./ 　 |
　　　　 ?'| i＞.﹑,,__　_,.? / 　.i 　|
　　　　　 ?'| | / k_７_/?'?,　?.　|
　　　　　　 | |/i 〈|/　 i　,.? |　i　|
　　　　　　.|/ /　ｉ： 　 ?!　　＼　|
　　　 　 　 k?>﹑? 　 _,.?﹑ 　 /﹑!
　　　　　　 !'〈//‘Ｔ’', ＼ ‘'7'?r'
　　　　　　 ?'?L__|___i,___,??|?
　　　　　 　　　?-,/　|___./
　　　　　 　　　'?'　　!_,.:
?__,.??.　　　　/　,?﹑ 〉
　　　　　＼ ', !-─?-i　/　/’
　　　 　 ／‘?'　　　 L/／‘?﹑
　　 　 /　 ／,　 /|　 ,　 ,　　　 ',
　　　? 　/ /-?/　ｉ　L_ ? ?!　 i
　　　 ? ? 7?‘?　 ?'?-?﹑!?|　 |
　　　　 !,/7 '0'　　 ’0i?| 　 |　　　
　　　　 |.?"　　_　　 ,,,, / |./ 　 |
　　　　 ?'| i＞.﹑,,__　_,.? / 　.i 　|
　　　　　 ?'| | / k_７_/?'?,　?.　|
　　　　　　 | |/i 〈|/　 i　,.? |　i　|
　　　　　　.|/ /　ｉ： 　 ?!　　＼　|
　　　 　 　 k?>﹑? 　 _,.?﹑ 　 /﹑!
　　　　　　 !'〈//‘Ｔ’', ＼ ‘'7'?r'
　　　　　　 ?'?L__|___i,___,??|?
　　　　　 　　　?-,/　|___./
　　　　　 　　　'?'　　!_,.:
?__,.??.　　　　/　,?﹑ 〉
　　　　　＼ ', !-─?-i　/　/’
　　　 　 ／‘?'　　　 L/／‘?﹑
　　 　 /　 ／,　 /|　 ,　 ,　　　 ',
　　　? 　/ /-?/　ｉ　L_ ? ?!　 i
　　　 ? ? 7?‘?　 ?'?-?﹑!?|　 |
　　　　 !,/7 '0'　　 ’0i?| 　 |　　　
　　　　 |.?"　　_　　 ,,,, / |./ 　 |
　　　　 ?'| i＞.﹑,,__　_,.? / 　.i 　|
　　　　　 ?'| | / k_７_/?'?,　?.　|
　　　　　　 | |/i 〈|/　 i　,.? |　i　|
　　　　　　.|/ /　ｉ： 　 ?!　　＼　|
　　　 　 　 k?>﹑? 　 _,.?﹑ 　 /﹑!
　　　　　　 !'〈//‘Ｔ’', ＼ ‘'7'?r'
　　　　　　 ?'?L__|___i,___,??|?
　　　　　 　　　?-,/　|___./
　　　　　 　　　'?'　　!_,.:
?__,.??.　　　　/　,?﹑ 〉
　　　　　＼ ', !-─?-i　/　/’
　　　 　 ／‘?'　　　 L/／‘?﹑
　　 　 /　 ／,　 /|　 ,　 ,　　　 ',
　　　? 　/ /-?/　ｉ　L_ ? ?!　 i
　　　 ? ? 7?‘?　 ?'?-?﹑!?|　 |
　　　　 !,/7 '0'　　 ’0i?| 　 |　　　
　　　　 |.?"　　_　　 ,,,, / |./ 　 |
　　　　 ?'| i＞.﹑,,__　_,.? / 　.i 　|
　　　　　 ?'| | / k_７_/?'?,　?.　|
　　　　　　 | |/i 〈|/　 i　,.? |　i　|
　　　　　　.|/ /　ｉ： 　 ?!　　＼　|
　　　 　 　 k?>﹑? 　 _,.?﹑ 　 /﹑!
　　　　　　 !'〈//‘Ｔ’', ＼ ‘'7'?r'
　　　　　　 ?'?L__|___i,___,??|?
　　　　　 　　　?-,/　|___./
　　　　　 　　　'?'　　!_,.:
*/

#include <iostream>
#define int long long
#define iris 100000007
using namespace std;

char aa[512],bb[512];
int p[512];
int dp[310][310][610];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m,w,i,j,k,ouo;
    cin>>n>>m>>w;
    for(i=1;i<=n;i++)
    {
        cin>>aa[i];
    }
    for(i=1;i<=m;i++)
    {
        cin>>bb[i];
    }
    for(i='a',ouo=999999999999999;i<='z';i++)
    {
        cin>>p[i];
        ouo=min(ouo,p[i]);
    }
    
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            for(k=0;k<=n+m;k++)
                dp[i][j][k]=999999999999999;
    dp[0][0][0]=0;
    
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            for(k=0;k<=n+m;k++)
            {
                if(i)
                {
                    dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]);
                    if(k)
                    {
                        dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-1]+p[aa[i]]);
                    }
                }
                if(j)
                {
                    dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]);
                    if(k)
                    {
                        dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-1]+p[bb[j]]);
                    }
                }
                if(i&&j&&k&&aa[i]==bb[j])
                {
                    dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-1][k-1]);
                }
            }
        }
    }
    
    int ans=0;
    for(i=0;i<=n+m;i++)
    {
        if(dp[n][m][i]<=w)
        {
            ans=max(ans,i+(w-dp[n][m][i])/ouo/2);
        }
    }
    cout<<ans<<'\n';
    
    return 0;
}

:::

#### **pE. 產品配送問題**

#### **pF. 小風愛球球**

#### **pG. 有趣**

#### **pH. 當堅果遇上莫隊**

:::spoiler Solution (SorahISA)

#pragma GCC optimize("Ofast", "unroll-loops")

#include <cstdio>
#include <random>
#include <chrono>
#include <functional>
using namespace std;

using lli = long long;

#ifdef LOCAL
    inline int nextint() {
        int n; scanf("%d", &n);
        return n;
    }
    
    inline lli nextlli() {
        lli n; scanf("%lld", &n);
        return n;
    }
#else
    inline char readchar() {
    #define B 1048576
        static char buf[B], *p, *q;
        if(p == q and (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
        return *p++;
    #undef B
    }
    
    inline int nextint() {
        int x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
    
    inline lli nextlli() {
        lli x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    
auto gen = bind(uniform_int_distribution<int>(1, 1E9), rng);
const int maxc = 5E5 + 5;
const int maxn = 5E5 + 5;

int n, q;
lli k, v[maxn], mp[maxc], cnt[maxc];

int main() {
    n = nextint();
    k = nextlli();
    q = nextint();
    
    for (int i = 0; i < n; ++i) v[i] = nextlli();
    
    /// Random weight ///
    
    for (int i = 0; i < n; ++i) {
        if (!mp[v[i]]) mp[v[i]] = gen();
        if (++cnt[v[i]] == k) {
            cnt[v[i]] = 0;
            v[i] = -1 * (k - 1) * mp[v[i]];
        }
        else v[i] = mp[v[i]];
    }
    
    /// Prefix sum ///
    
    for (int i = 1; i < n; ++i) v[i] += v[i - 1];
    
    int a, b;
    while (q--) {
        a = nextint();
        b = nextint();
        --a, --b;
        if (v[b] - (a ? v[a - 1] : 0) == 0) putchar('1');
        else putchar('0');
    }
    
    puts("");
}

:::

#### **pI. YP 的阿 XXX**

:::spoiler Solution (SorahISA)

#include <cstdio>
#include <set>
using namespace std;

using lli = long long;

#ifdef LOCAL
    inline int nextint() {
        int n; scanf("%d", &n);
        return n;
    }
    
    inline lli nextlli() {
        lli n; scanf("%lld", &n);
        return n;
    }
#else
    inline char readchar() {
    #define B 1048576
        static char buf[B], *p, *q;
        if(p == q and (q = (p = buf) + fread(buf, 1, B, stdin)) == buf) return EOF;
        return *p++;
    #undef B
    }
    
    inline int nextint() {
        int x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
    
    inline lli nextlli() {
        lli x = 0, c = readchar();
        while('0' >  c  or c >  '9') c = readchar();
        while('0' <= c and c <= '9') x = x * 10 + (c ^ '0'), c = readchar();
        return x;
    }
#endif

int main() {
    int n, q;
    n = nextint();
    q = nextint();

    int v[n];
    for (int i = 0; i < n; ++i) v[i] = nextint();

    set<int> s;
    int ans[n] = {}, lP = 0;
    for (int i = 0; i < n; ++i) {
        while (s.count(v[i])) {
            s.erase(v[lP]);
            ++lP;
        }
        ans[i] = lP;
        s.insert(v[i]);
    }

    int tmp;
    while (q--) {
        tmp = nextint();
        printf("%d\n", ans[tmp - 1] + 1);
    }
    
    return 0;
}

:::

#### **pJ. 殿壬的王國**

#### **pK. 小風愛數學**