当前位置：首页 > news >正文

2019 ICPC Asia Taipei - Hsinchu Regional

news 来源：原创 2024/5/19 17:30:03

C. Are They All Integers?（暴力/思维）

题目链接

题目大意

给出一个序列判断序列中任意一个三元组是否满足 $a_i-a_j)/a_k$ 均为整数

解题思路

首先数据范围很小，可以直接暴力，时间复杂度 $O(n^3)$

但是如果数据更大了无法暴力，那么我们对此类问题必须研究一下以防不测。若任取三个数 $a \leq b \leq c$ ，如果 $a! = b$ ，则 $(b - a) / c$ 一定不为整数。若任取三个数 $a \leq b \leq c$ ，如果 $a = b$ ，则 $(c - b) / a$ 为整数当且仅当 $c$ 为 $a$ 的倍数。又因为数组 $a$ 是不递减的，因此前 $n - 1$ 个数必须相同，否则就会出现第一种情况。时间复杂度 $O (n)$

#include <iostream>

using namespace std;
int a[105];

bool solve(int n){  //暴力
    for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++){
        for(int k=0;k<n;k++){
            if(k==i || k==j) continue;
            if((a[i]-a[j])%a[k]) return false;
        }
    }
    return true;
}

bool fastsolve(int n){  //思维
    int cur=a[0];
    for(int i=1;i<n-1;i++) if(a[i]!=cur) return false;
    if(a[n-1]%cur) return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    if(fastsolve(n)) cout<<"yes\n";
    else cout<<"no\n";
    return 0;
}

D. Tapioka（签到）

题目链接

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    int flag=1;
    while(cin>>s){
        if(s!="bubble" && s!="tapioka"){
            cout<<s<<" ";
            flag=0;
        }
    }
    if(flag) cout<<"nothing\n";
    return 0;
}

H. Mining a（打表找规律）

题目链接

题目大意

求满足上述式子中最大的a

解题思路

对式子化简我们可以得到 $a^b=n*b/(b-n)$ ，因为 $a, b$ 都是正整数，那么 $a^b$ 一定是整数，因此有 $n * b / (b - n)$ 一定是整数。然后根据异或的性质，得到 $a=[n*b/(b-n)]^b$ ，首先对几个小样例在 $1000$ 枚举 $b$ ，会发现 $a$ 最大时一定是当 $b = n - 1$ 时，那么就找到规律了

#include <iostream>

using namespace std;
typedef long long ll;
int main()
{
    ll n,t;
    /*for(int i=n+1;i<=1000;i++){
        if(n*i%(i-n)==0)
        cout<<((n*i/(i-n))^i)<<endl;
    }*/
    cin>>t;
    while(t--){
        cin>>n;
        ll b=n+1;
        ll ans=(n*b/(b-n))^b;
        cout<<ans<<endl;
    }

    return 0;
}

K. Length of Bundle Rope（小根堆）

题目链接

简单的哈夫曼问题，直接使用优先队列即可

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,x;
    cin>>t;
    while(t--){
        cin>>n;
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++){
            cin>>x;
            q.push(x);
        }
        int ans=0;
        while(q.size()>1){
            int a=q.top(); q.pop();
            int b=q.top(); q.pop();
            ans+=a+b;
            q.push(a+b);
        }
        cout<<ans<<endl;
    }
    return 0;
}