---
tags: IOICamp
---

# Day5 模擬賽

:::spoiler Description
:::

:::spoiler Problems (PDF) QQ
{%pdf https://www.csie.ntu.edu.tw/~b07902024/ioicamp2020-final.pdf %}
:::

:::spoiler Scoreboard (155min)
:::

:::spoiler Scoreboard (165min, pM rejudged)
:::

:::spoiler Scoreboard (220min)
:::

:::spoiler Scoreboard (240min, Frozen)
:::

:::spoiler Scoreboard (317min, Ended, Frozen)
:::

---

[TOC]

#### **pA. 二分圖判定**

:::spoiler Solution (SorahISA)

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

#include <bits/stdc++.h>
using namespace std;

using lli = long long;

const int maxn = 1E3;

vector<int> adj[maxn];

bool side[maxn][maxn], flag = 1;
int col[maxn] = {};

void dfs(int now) {
    for (auto x : adj[now]) {
        if (col[x] == 0) {
            col[x] = col[now] ^ 1;
            dfs(x);
        }
        else if (col[x] == col[now]) {
            flag = 0;
        }
    }
}

int main() {
    lli n, m;
    scanf("%lld %lld", &n, &m);
    
    int u, v;
    
    if (n > maxn) {
        printf("No\n");
        return 0;
    }
    
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &u, &v);
        side[u][v] = 1;
        side[v][u] = 1;
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = i+1; j <= n; ++j) {
            if (!side[i][j]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!col[i]) {
            col[i] = 2;
            dfs(i);
        }
    }
    
    if (flag) printf("Yes\n");
    else printf("No\n");
    
    return 0;
}

:::

#### **pB. 當堅果遇上松果**

#### **pC. 當堅果遇上隨機**

#### **pD. 小風數堅果**

#### **pE. 最好吃的堅果**

#### **pF. 小風愛數堅果樹**

#### **pG. 當堅果遇上午餐**

:::spoiler Solution (SorahISA)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    
    int kind[n], cost[m];
    for (int i = 0; i < n; ++i) cin >> kind[i];
    for (int i = 0; i < m; ++i) cin >> cost[i];
    
    string s, t;
    cin >> s >> t;
    
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') {
            ans += cost[kind[i] - 1];
            ans -= t[i] == '1';
        }
    }
    
    cout << ans << "\n";
    return 0;
}

:::

#### **pH. 照亮堅果樹**

#### **pI. 周伯欲點兵，姬桂算剩餘**

:::spoiler Solution (loIicon)

/*
?__,.??.　　　　/　,?﹑ 〉
　　　　　＼ ', !-─?-i　/　/’
　　　 　 ／‘?'　　　 L/／‘?﹑
　　 　 /　 ／,　 /|　 ,　 ,　　　 ',
　　　? 　/ /-?/　ｉ　L_ ? ?!　 i
　　　 ? ? 7?‘?　 ?'?-?﹑!?|　 |
　　　　 !,/7 '0'　　 ’0i?| 　 |　　　
　　　　 |.?"　　_　　 ,,,, / |./ 　 |
　　　　 ?'| i＞.﹑,,__　_,.? / 　.i 　|
　　　　　 ?'| | / k_７_/?'?,　?.　|
　　　　　　 | |/i 〈|/　 i　,.? |　i　|
　　　　　　.|/ /　ｉ： 　 ?!　　＼　|
　　　 　 　 k?>﹑? 　 _,.?﹑ 　 /﹑!
　　　　　　 !'〈//‘Ｔ’', ＼ ‘'7'?r'
　　　　　　 ?'?L__|___i,___,??|?
　　　　　 　　　?-,/　|___./
　　　　　 　　　'?'　　!_,.:
ub33 love loli<3
*/
#include <iostream>
#include <algorithm>
#define loli long long
#define iris 1000000007
using namespace std;

int arr[100010],n;

struct st{
	int ouo[266666];
	bool tag[266666];
	
	void build(int l,int r,int i,int o)
	{
		int m=(l+r)>>1;
		if(l==r)
			ouo[i]=(arr[l]>>o)&1;
		else
		{
			build(l,m,i*2,o);
			build(m+1,r,i*2+1,o);
			ouo[i]=ouo[i*2]+ouo[i*2+1];
		}
	}
	
	inline void push(int l,int r,int i)
	{
		int m=(l+r)/2;
		if(!tag[i])
			return;
		tag[i]=0;
		if(l!=r)
		{
			tag[i*2]^=1;
			tag[i*2+1]^=1;
			ouo[i*2]=m-l+1-ouo[i*2];
			ouo[i*2+1]=r-m-ouo[i*2+1];
			ouo[i]=ouo[i*2]+ouo[i*2+1];
		}
	}
	
	void rev(int l,int r,int a,int b,int i)
	{
		int m=(l+r)>>1;
		push(l,r,i);
		
		if(a<=l && r<=b)
		{
			ouo[i]=r-l+1-ouo[i];
			tag[i]^=1;
			return;
		}
		else if(b<=m)
		{
			rev(l,m,a,b,i*2);
		}
		else if(a>m)
		{
			rev(m+1,r,a,b,i*2+1);
		}
		else
		{
			rev(l,m,a,b,i*2);
			rev(m+1,r,a,b,i*2+1);
		}
		ouo[i]=ouo[i*2]+ouo[i*2+1];
	}
	
	int qry(int l,int r,int a,int b,int i)
	{
		int m=(l+r)>>1;
		push(l,r,i);
		if(a<=l && r<=b)
			return ouo[i];
		else if(b<=m)
			return qry(l,m,a,b,i*2);
		else if(a>m)
			return qry(m+1,r,a,b,i*2+1);
		else
			return qry(l,m,a,b,i*2)+qry(m+1,r,a,b,i*2+1);
	}
}aoi[31];

inline loli query(int l,int r)
{
	loli i,res=0;
	for(i=0;i<31;i++)
	{
		res+=(loli)aoi[i].qry(1,n,l,r,1)<<i;
	}
	return (res)/2-(r-l+1)+(aoi[0].qry(1,n,l,r,1)+1)/2;
}

inline void change(int l,int r,int k)
{
	int i;
	for(i=0;i<31;i++)
	{
		if((k>>i)&1)
		{
			aoi[i].rev(1,n,l,r,1);
		}
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int q,i,x,a,b,c;
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	for(i=0;i<31;i++)
	{
		aoi[i].build(1,n,1,i);
	}
	
	while(q--)
	{
		cin>>x;
		if(x==1)
		{
			cin>>a>>b;
			cout<<query(a,b)<<'\n';
		}
		else
		{
			cin>>a>>b>>c;
			change(a,b,c);
		}
	}
	
	return 0;
}

:::

#### **pJ. 堅果巧克力**

:::spoiler Solution (SorahISA, Brute-Force)

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

#include <bits/stdc++.h>
using namespace std;

using lli = long long;

int n, w, h, a[20], t[20], fl = 0, tok = 0;

stack<int> ans, tmp;

void dfs(int W, int H, int Pick) {
    if (fl) return;
    
    if (Pick == 0) {
        fl = 1;
        while (!ans.empty()) {
            tmp.push(ans.top());
            ans.pop();
        }
        return;
    }
    
    for (int i = 0; i < n; ++i) {
        if (Pick & (1 << i) and a[i] % W == 0) {
            ans.push(t[i]); ans.push(W); ans.push(a[i] / W);
            dfs(W, H - a[i] / W, Pick ^ (1 << i));
            if (!ans.empty()) {ans.pop(); ans.pop(); ans.pop();}
        }
        if (Pick & (1 << i) and a[i] % H == 0) {
            ans.push(t[i]); ans.push(a[i] / H); ans.push(H);
            dfs(W - a[i] / H, H, Pick ^ (1 << i));
            if (!ans.empty()) {ans.pop(); ans.pop(); ans.pop();}
        }
    }
}

int main() {
    srand(time(NULL));
    
    scanf("%d %d %d", &n, &w, &h);
    
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) t[i] = i + 1;
    
    for (int i = 1; i < n; ++i) {
        int rnd = rand() % i;
        swap(a[i], a[rnd]);
        swap(t[i], t[rnd]);
    }
    
    dfs(w, h, (1 << n) - 1);
    
    if (fl) {
        puts("Yes");
        while (!tmp.empty()) {
            printf("%d", tmp.top()); tmp.pop();
            printf("%c", ++tok % 3 == 0 ? '\n' : ' ');
        }
    }
    else {
        puts("No");
    }
    
    return 0;
}

:::

#### **pK. 天天吃堅果**

#### **pL. 小風的堅果塔**

:::spoiler Solution (SorahISA)

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

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

using lli = long long;

#define A first
#define W second

const int maxn = 5E3 + 5;

pair<lli, lli> nut[maxn];
lli dp[maxn][maxn], ans = 0;

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; ++i) scanf("%lld %lld", &nut[i].A, &nut[i].W);
    
    sort(nut, nut + n);
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = 0;
        }
        dp[i][0] = nut[i].W;
        if (i) dp[i][0] += nut[0].W;
//        Max[i][0] = dp[i][0];
    }
    
    for (int i = 2; i < n; ++i) {
        for (int j = 1; j < i; ++j) {
            /// dp[i][j] = max_{w[k] <= w[i] - w[j]}(dp[j][k]) + w[i] ///
            int lo = 0, hi = j, mi;
            
            /// binary search lower_bound of allowed range [0, lo) ///
            while (lo < hi) {
                mi = (lo + hi) >> 1;
                if (nut[i].A - nut[j].A < nut[mi].A) hi = mi;
                else lo = mi + 1;
            }
            
            if (lo == 0) {
                dp[i][j] = nut[i].W + nut[j].W;
//                Max[i][j] = max(Max[i][j - 1], dp[i][j]);
                dp[i][j] = max(dp[i][j - 1], dp[i][j]);
                ans = max(ans, dp[i][j]);
                continue;
            }
            
            /// find max_{0 <= k < lo}(dp[j][k]) ///
//            dp[i][j] = Max[j][lo - 1] + nut[i].W;
            dp[i][j] = dp[j][lo - 1] + nut[i].W;
            
            /// update max and answer ///
//            Max[i][j] = max(Max[i][j - 1], dp[i][j]);
            dp[i][j] = max(dp[i][j - 1], dp[i][j]);
            ans = max(ans, dp[i][j]);
            
//            /// O(n^3) solution ///
//            for (int k = 0; k < j; ++k) {
//                if (nut[i].A - nut[j].A < nut[k].A) break;
//                dp2[i][j] = max(dp2[i][j], dp2[j][k]);
//            }
//            dp2[i][j] += nut[i].W;
//            ans2 = max(ans2, dp2[i][j]);
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}

:::

#### **pM. 乘法大師**

:::spoiler Solution (SorahISA)

#include <bits/stdc++.h>
using namespace std;

using lli = long long;

lli part[50];

//void dfs(int now, int left, int num) {
//    if (left == 0) {
//        ++part[num];
//    }
//    
//    for (int i = now; i <= left; ++i) {
//        if (i == left or left - i >= i) {
//            dfs(i, left - i, num);
//        }
//    }
//}

void check() {
//    part[1] = 1;
//    for (int i = 2; i <= 30; ++i) {
//        part[i] = part[i - 1];
//        dfs(2, i, i);
//        printf("part[%2d] = %lld;\n", i, part[i]);
//    }
    
    part[ 1] =    1; part[ 2] =    2; part[ 3] =    3; part[ 4] =    5; part[ 5] =    7;
    part[ 6] =   11; part[ 7] =   15; part[ 8] =   22; part[ 9] =   30; part[10] =   42;
    part[11] =   56; part[12] =   77; part[13] =  101; part[14] =  135; part[15] =  176;
    part[16] =  231; part[17] =  297; part[18] =  385; part[19] =  490; part[20] =  627;
    part[21] =  792; part[22] = 1002; part[23] = 1255; part[24] = 1575; part[25] = 1958;
    part[26] = 2436; part[27] = 3010; part[28] = 3718; part[29] = 4565; part[30] = 5604;
}

int main() {
    check();
    
    int n;
    scanf("%d", &n);
    
    if (n == 1) {
        printf("0\n");
        return 0;
    }
    
    int arr[30] = {}, tok = 0;
    
    for (int i = 2; i*i <= n; ++i) {
        if (n / i * i == n) ++tok;
        while (n / i * i == n) {
            n /= i;
            ++arr[tok];
        }
    }
    
    assert(tok <= 30);
    
//    if (n != 1) {
//        arr[++tok] = 1;
//    }
    
    lli ans = 1;
    for (int i = 1; i <= tok; ++i) {
        ans *= part[arr[i]];
    }
    
    printf("%lld\n", ans);
    
    return 0;
}

:::