The 2021 ICPC Asia Taipei Regional Programming Contest

A.Ice Cream

题意：

买x个可以送y个，每个的价格是3元，问需要买n个的最小花费

标签：

模拟签到题

题解：

全买打折和买打折剩下的原价取个最小值就行了

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e6+10;
 
void solve(){
    int x,y,z;
    cin>>x>>y>>z;
    ll res=3*((z)/(x+y))*x+z%(x+y)*3,ans=3*((z+x+y-1)/(x+y))*x;
    cout<<min(ans,res)<<endl;
}   
 
signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B.Maximum Sub-Reverse Matching

题意：

  1. 给定两个长度相等的字符串，两个字符串之间的相似度是两个字符串相同下标下，两个字符串对应位置字符的数量。
  2. 我们可以进行操作，每次操作可以把某个区间的字符串进行翻转。
  3. 问我们初始状态的相似度，和操作后的最大次数。
  4. 如果有多个答案，取操作次数最少的，如果有多个相同次数的，选左边最小的。

标签：

dp，前后缀信息预处理

题解：

  1. 对于字符串的相似度，可以先处理出前缀相似度和后缀相似度，对于翻转区间以外的相似度可以直接进行查询。
  2. 处理出翻转区间后能得到的价值，dp[i][j]表示起点为i，长度为j的区间翻转能够取得的相似度，可以发现dp[i][j]=dp[i+1][i+j-1-1]+(s1[i]==s2[i+j-1])+(s2[i]==s1[i+j-1]);
  3. 遍历查询翻转某个区间，根据前后缀和dp值更新最大相似度和答案。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e3+5;
void solve(){
    int n;
    string s1,s2;
    cin>>n>>s1>>s2;
    s1='1'+s1+'1',s2='1'+s2+'1';
    vector<int>sum(n+5,0),rep(n+5,0);vector<vector<int>>dp(n+5,vector<int>(n+5,0));

    int ans=0,l=1,r=1;
    for(int i=1;i<=n;i++){
        ans+=(s1[i]==s2[i]);
        sum[i]=sum[i-1]+(s1[i]==s2[i]);
        dp[i][1]=(s1[i]==s2[i]);
    }
    for(int i=n;i>=1;i--){
        rep[i]=rep[i+1]+(s1[i]==s2[i]);
    }
    int res=ans;
    for(int j=2;j<=n;j++)
        for(int i=1;i+j-1<=n;i++){{
            int x=i+1,y=i+j-1-1;
            int tmp=0;
            if(x<=y)tmp=dp[x][j-2];
            dp[i][j]=tmp+(s1[i]==s2[y+1])+(s2[i]==s1[y+1]);
            if(res<dp[i][j]+sum[i-1]+rep[y+2]){
                l=i,r=y+1;
                res=dp[i][j]+sum[i-1]+rep[y+2];
            }
        }
    }
    cout<<ans<<' '<<res<<' '<<l<<' '<<r<<endl;
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D.Largest Remainder

题意：

给定n个1到9的数字，问我们这n个数字的排列取余于p，得到的模数最大的排列是什么。

标签：

状压dp

题解：

状压DP，dp[st][p]dp[st][p] 表示选取集合 stst 且模数为 pp 时的最大数值。那么DP转移式为dp[st∣(1<<i)][j]=max(dp[st∣(1<<i)][j],dp[st][k]∗10+a[i])dp[st|(1 << i)][j] = max(dp[st∣(1 << i)][j],dp[st][k] ∗ 10 + a[i]) ，其中 jj 是 (k+a[i])(k+a[i]), jj 是 (k+a[i])(k+a[i])%10 的余数。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N = 1e6 + 10;

int dp[1 << 16][201];
int n, p, a[20];

void solve()
{
    cin >> n >> p;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int s = 0; s < (1 << n); ++s)
    { //枚举状态
        for (int i = 0; i < n; ++i)
        { //在未选集合中选一个数
            if ((s >> i) & 1)
                continue;
            for (int j = 0; j < p; ++j)
            { //枚举模数
                if (dp[s][j] == -1)
                    continue;
                ll nxt = (j * 10ll + a[i]) % p; //下一个模数
                dp[s | (1ll << i)][nxt] = max(dp[s | (1ll << i)][nxt], dp[s][j] * 10ll + a[i]);
            }
        }
    }
    for (int i = p - 1; i >= 0; --i)
    {
        if (dp[(1ll << n) - 1][i] != -1)
        {
            printf("%lld\n", dp[(1ll << n) - 1][i]);
            return;
        }
    }
}

signed main()
{
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

I.Seesaw

题意：

给定一个天平两边的物品重量，左边为奇数，右边为偶数，只有1和2可以进行交换，问我们最少能操作多少次让天平平衡，不存在答案的话输出-1

标签：

背包模型状态dp

题解：

当我们交换 aiai 和 bjbj 时(题目要求 ai==1ai==1 且 bj==2bj==2 )，左右的重量差值会减少 i+ji + j ，题意转化为从左右分别选取 kk 个物品使得左右选取的质量之和为重量差值 sumsum。那么我们用 dp[i][j]dp[i][j] 表示前 ii 个物品达到重量 jj 的方案是否可行，就可以用 bitset 优化。转移方程为 dp[j]∣=dp[j−a[i]]<<1dp[j]∣= dp[j−a[i]] << 1 ,注意边界条件，sum<0和sum太大都要直接判结果.

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll

void solve(){
    int n,m;
	cin>>n;
	vector<int>a,b;
	a.push_back(0),b.push_back(0);
	int l=0,r=0,x;
	int res1=0,res2=0;

	for(int i=1;i<=n;i++){
		cin>>x;
		if(x==1)a.push_back(i),res1+=i;
		l+=x*i;
	}
	for(int i=1;i<=n;i++){
		cin>>x;
		if(x==2)b.push_back(i);res2+=i;
		r+=x*i;
	}
	if(l==r){
		cout<<0<<endl;
		return;
	}
	if(l>r||r-l>50001){
		cout<< -1<<endl;
		return;
	}
	n=a.size(),m=b.size();
	int sum=r-l;

/*
	vector<bitset<205>>dp1(sum+2),dp2(sum+2);

	dp1[0]=1;
	for(int i=1;i<n;i++){
		for(int j=sum;j>=a[i];j--){
			dp1[j]|=(dp1[j-a[i]]<<1);
		}
	}
	dp2[0]=1;
	for(int i=1;i<m;i++){
		for(int j=sum;j>=b[i];j--){
			dp2[j]|=(dp2[j-b[i]]<<1);
		}
	}

	for(int i=0;i<min(n,m);i++){
		for(int j=0;j<=sum;j++){
			int k=sum-j;
			if(dp1[j][i]&&dp2[k][i]){
				cout<<i<<endl;
				return;
			}
		}
	}
	cout<< -1<<endl;
*/

	vector<vector<int>>dp1(n+2,vector<int>(sum,0)),dp2(m+2,vector<int>(sum,0));
	dp1[0][0]=1;
	for(int i=1;i<n;i++){
		for(int k=i;k>=1;k--){
			for(int j=sum;j>=a[i];j--){
				dp1[k][j]|=(dp1[k-1][j-a[i]]);
			}
		}
	}
 
	dp2[0][0]=1;
	for(int i=1;i<m;i++){
		for(int k=i;k>=1;k--){
			for(int j=sum;j>=b[i];j--){
				dp2[k][j]|=(dp2[k-1][j-b[i]]);
			}
		}
	}
	for(int i=1;i<min(n,m);i++){
		for(int j=1;j<=sum;j++){
			int k=sum-j;
			if(dp1[i][j]&&dp2[i][k]){
				cout<<i<<endl;
				return;
			}
		}
	}
	cout<< -1<<endl;
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

J.Transportation Network

题意：

阅读理解，给我们一个图的建边方式权值，要我们构造一颗以0为根，根节点有p个儿子，不超过|S|，最高为三层的树，全任意两点间的距离和

标签：

模拟，建图，dfs

题解：

我们可以尽量构造权值为1的边，也就是让|S|的结点尽量接到根节点下，然后再剩下的结点接在根节点下或者第一个|S|里面的结点下面，这样可以贪心地构造出权值和最小的树，建完树后再进行dfs找到每条边两边的结点个数，相乘就是这个边被经过的次数，所以边的和的两倍加起来就是答案。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e6+10;

void solve(){
    int n,b,p;
    cin>>n>>b>>p;
    for(int i=0;i<b;i++){
        int x;
        cin>>x;
    }
    vector<pair<int,int>>e[n+1];
    vector<int>num(n+1,0);
    for(int i=1;i<=p;i++){
        if(b){
            e[0].push_back({i,1});
            e[i].push_back({0,1});   
            b--;
        }
        else{
            e[0].push_back({i,2});
            e[i].push_back({0,2});
        }

    }
    for(int i=p+1;i<n;i++){
        e[1].push_back({i,1});
        e[i].push_back({1,1});
    }
    int ans=0;
    function<void(int,int)> dfs=[&](int u,int fa){
        num[u]=1;
        for(auto [v,w]:e[u]){
            if(v==fa)continue;
            dfs(v,u);
            ans+=num[v]*(n-num[v])*w;
            num[u]+=num[v];
        }
    };
    dfs(0,-1);
    cout<<ans*2<<endl;
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

M.Escaping the Foggy Forest

题意：

给定一个n*m的矩阵，问那些点满足前面和后面和题意给定的要求一样

标签

模拟签到题

题解：

枚举每一个点，判断四个方向是否存在一个合法就可以了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N=1e6+10;
int c[110][110];
int x,y,z;

bool check(int i,int j){
    int f=0;
    if(c[i-1][j]==y&&c[i][j+1]==z)f=1;
    if(c[i][j-1]==y&&c[i-1][j]==z)f=1;
    if(c[i+1][j]==y&&c[i][j-1]==z)f=1;
    if(c[i][j+1]==y&&c[i+1][j]==z)f=1;
    return f;
}


void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
        }
    }
    cin>>x>>y>>z;
    vector<pair<int,int>>ans;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(check(i,j)&&c[i][j]==x)ans.push_back({i-1,j-1});
        }
    }
    sort(ans.begin(),ans.end());
    for(auto [u,v]:ans){
        cout<<u<<' '<<v<<'\n';
    }
}   

signed main(){
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}